Run time pathfinder graph creation
In The Traveler, I have faced a problem when trying to find a way of having the AI spaceships navigating through asteroids field and other obstacles, I didn’t want to use the unity nav mesh, because there was really no need to create a giant nav mesh each time an asteroid moves, and I didn’t want to use the classic method of a grid, I think that in this situation using a grid creates a very large frontier in the A star pathfinder algorithm, and if I want to have many AIs wondering about the solar system that’s gonna be a problem for performance.
Eventually I came to the conclusion that I need to create some way of generating a graph for the PF to work with, the specification for this graph would be as follows:
- Generate the graph in real time with a frame rate of above 150 fps for a single AI
- Generate the graph only in the needed area, ie a circle in front of the AI ship
- Create the minimum amount of point needed to find a decent path
- Have a nice visual representation of nodes, edges, obstacle distances etc
- A tester class with exposed parameters so I can optimize the graph and save the parameters to a scriptable objects
General overview of the algorithm:
A CreateGraph method will return a “Graph” struct have 3 parts to it
- Graph setup, clear old data, get the needed data from external sources and organize it.
- Create graph nodes
- Create graph edges
For each obstacle that is in the search radius we will create a set of positions on circles around the obstacle, each circle has a different radius so there is some diversity to the positions of the circles, and each circle will start at a different angle. It looks like this:
Now for each point we generated we will do 2 checks
1. The first check is a Physics.CheckSphere(), to make sure that there is no obstacle in the vicinity of the point will do this check with the radius of the agent(Ai ship).
2. The second check will be to check if there is a close by node that was already generated.
In order to do the second check more efficiently I use a quadrant system, each node that is created is added to a dictionary of quadrants that contains a list of nodes, this is done using math to determine at which quadrant the node is at.
If we find that the new node is too close to another previously created node, we are merging them by averaging their positions.
When I first created this graph generator I stopped at this point, but later on when it was in use in the game, I noticed that the AI ships tends to go close to obstacles even if there was a large open area on the way to the target, the reason for that was that in this way of creating circles around obstacle I didn’t take into account large open areas, and the PF algorithm didn’t have any nodes to choose from in large open areas.
In order to fix that I added another set of nodes arranged in a circular grid, when each node is 75% the distance of the maximum edge length.
Now the nodes looks like this:
Creating the edges is pretty straight forward, the only thing that requires some attention is the finding of neighbor nodes.
Here I do another use of the quadrant system to get the nearby nodes, after getting the nearby nodes I check them for these requirements:
- Check if there is a direct line of sight from the current node to its neighbor
- Check the neighbor popularity, ie: check if he has been connected to the maximum amount of connections allowed
- Calculate the distance between the current node and the neighbor, and check if the distance is with in the threshold
If any of these checks doesn’t pass I skip that neighbor and don’t add it to the current node neighbors list.
If a node does pass these checks the neighbor is added to the neighbors list and the data (especially the distance) is saved to be used later by the PF algorithm so it doesn’t need to recalculate it again, this saves the PF a lot of time.
And that’s it, now we have a nice working graph to pass to the pathfinder.
I’m not gonna go into A star algorithm because it is widely covered all over the web.
In the attached unity project you will find the graph class together with the PF class and an example scene where you can adjust the settings and save them to a scriptable object.
Hope you find this helpful, let me know what you think in the comments below, and if you would like to have some section better explain please let me know and i’ll make another post about it.