Create Hallways with least amount of bends along path?

I am in the midst of creating a 2D Dungeon Crawler styled game, very similar to the likes of Enter The Gungeon. I have a Dungeon Generation algorithm that creates rooms in a loop and connects them with hallways. However, I need to connect the final room (last loop element) to the start of the entire loop (first loop element). To do this, I use A* Pathfinding to find me the closest route from Room A, to a ‘Hallway Attachment Point’ (Points where hallway can start/end) in Room B.

This portion works fine, however, to create the hallways I need to walk along the path and instantiate GameObjects. Some of these can be corner, or horizontal/vertical objects. The hallways are 2 Tiles wide, meaning that I cannot do Zig-Zag Maneuvers as efficiently.

I am trying to achieve a path that bends the least amount of times, and if it does, has enough space to bend from a 2-wide path into another 2-wide path (4x4 Tiles).

The issue is: I have no clue where to start. I have tried messing a lot with the Grid Component’s values, such as Collision Size, Grid Size etc., but I feel like I am very close to achieving this goal.

I am not trying to change the pathfinding algorithm all too much, maybe there is a way to calculate long sides of an already existing path, and only bending it down in the middle. I have attached images of both the Dungeon Generation and the desired route.

Does anyone have an idea?

Yannick

Calculate the long sides of an existing path. If your path is represented as a grid or grid of tiles, you can determine the long sides by counting the number of cells in each direction (up, down, left, right) from the current position to the target point.
Determine the direction in which you have the least number of cells (long side). For example, if you have a 4x4 path, and you have 2 cells down and 4 cells to the right, you can choose the direction down.
Create a new point that connects to the current path. The new point must be on the long side of the path, but it must also be close enough to the current path to avoid too long corridors. For example, you can create a new point in the middle of the long side.
Use A* Pathfinding to find the path from the new point to the target point (the corridor connection point in the next room). Make sure that you take the width of the corridor into account when finding the path.
Add a new path to the existing path by joining them together.
Repeat steps 2-5 until you connect the last room to the beginning of the entire path.

2 Likes

This approach seems very well thought out and logical, so I want to thank you for taking your time to come up with this system.

Just to recap:
1.) Find length of axis on entire path (X and Y)
2.) Get the shorter axis (X or Y), and create a hallway.
3.) Move this hallway to fit correctly (possibly move on X and Y to not overlap any rooms etc.)
4.) From this newly created hallway, pathfind again to then link up the hallways.

Did I understand it correctly?
Or what else is meant with long side; the entire X and Y long sides of the path, or a current possible long side (before a bend happens)?

Once again, I want to thank you for reaching out!

i think you maybe can try to use `Wave Function Collapse - WFC ` to get a reasonable path.

but that function for your situation may not get a result . so you best have some fall back strategy.

Cheer.

1 Like