2
\$\begingroup\$

I recently started learning python and I'm working on a dungeon generator, using images for the rooms, hallways and junctions. Example of desired result.

So far I managed to generate a X * Y map and avoid the rooms from escaping the background image or colliding with each other (collision test); I was going to work on pathfinding to generate the corridors but ran into a problem. As you can see in the first image, some corridors and junctions are 1-tile wide while others are 2, and potentially wider.

Ideally I would use the generated grid to see where the corridors would go and "paste" whichever corridor or junction image would fit in that space.

Any tips on how to incorporate that into the pathfinding algorithm?, or if you have a better idea to generate the corridors, I'm all ears. Perhaps generating a single room, growing a corridor from there and adding a room at the end of that corridor, rinse and repeat?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Usually we use the term "pathfinding" to mean a unit planning a route over an existing map. Here it looks like what you're looking for is logic to generate that map by placing corridors and selecting appropriate tiles for each part. Is that accurate? It's still possible to use pathfinding algorithms as a tool to accomplish this, but we have more degrees of freedom than a typical pathfinding problem and will need some guidance about how you want the paths generated. eg. When should the algorithm choose to carve a 2-tile-wide corridor rather than a 2-tile wide? Which rooms should it connect? \$\endgroup\$
    – DMGregory
    Jul 24 '18 at 10:09
  • \$\begingroup\$ @DMGregory It's accurate. Seems my first reply was too long, I'll try to summarize a possible behavior: Generate rooms with info on the 'doors', find path to another room with an unoccupied same-sized door, if it can't find any or they are too far away, find path to a close corridor, make sure all rooms are reachable and connect corridors to other corridors if they aren't, use this info to rotate and paste the corridor or junction images on the main map. If there's a better or easier way of doing it I'd love to hear it, this is just what my inexperienced mind could think of. Thanks again! \$\endgroup\$
    – Nick S
    Jul 26 '18 at 10:08
2
\$\begingroup\$

During pathfinding for a 2x2 unit, when checking a node's neighbors, only consider it a valid node if it's open and that node's right/down/right+down neighbors are also open. If they're not, treat it the same as a wall.

Rather than writing your own pathfinder just for this, you can use this trick to transform an NxN grid into a new (N-1)x(N-1) grid, and then feed that through any off-the-shelf pathfinder.

\$\endgroup\$
1
  • \$\begingroup\$ I think OP is asking about how to generate their corridors in the first place, not about how to route 2x2 units through an existing corridor map. \$\endgroup\$
    – DMGregory
    Jul 24 '18 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.