Help using A* for procedural generation algorithm

Update –
Setting up polygon colliders on each “place” and then deactivating the appropriate ones prior to finding a path for a transition between places seems to be working well. So I think I’m probably good now.

Hi Everyone!

I just started with A* recently, and I have a kind of unique use case for it. I was hoping that some of the helpful folks here could just point me in the right direction.

So basically, I’m working on a procedural “place” generation algorithm that will work in a 2D, sidescroller world represented by integer cartesian coordinates (so a 2D array). The use case for A* is, I want to create “places,” which could be rooms, dungeons, etc. in the world, and then ensure that these places have “transitions” between each other that are traverseable by the player. To see why this is necessary, picture a dungeon full of rooms with no hallways connecting them.

Anyway, my thought was that I could leverage a pathfinding algorithm for this. Essentially, I could pre-determine the start point and endpoint for a transition (ie hallway, bridge, whatever) and then create with code a grid that maps to the coordinate system representing the world, and indicates whether each coordinate is valid or invalid for the pathing. If I wanted to make the transition less of a straight line, and more organic, I could insert invalid “squares” into the middle of the shortest path to ensure the pathfinding algorithm has to wind a bit.

So to accomplish this, I think I need to do the following:

  1. Generate a pathfinding grid with code that represents valid and invalid squares for the given transition.

  2. Use A* to find the path from the start point to the endpoint using said grid.

  3. Use my terrain generation functions to carve out the transition from the world.

It seems like A* could be adapted to do 1 and 2 fairly easily, I just don’t know where to start.

I thought about this some more, and I think a good idea may be to make a special Unity Layer for all of my “places” in the terrain generator, and put a polygon collider on each one. Then maybe I could have A* automatically generate the grid via its scan functionality?
The idea would be that I could just deactivate the colliders on places that transitions are allowed to path through for each transition.)

Any advice is welcome, thanks so much!

1 Like