Having created a maze, I knew at some point I would need a way to navigate around it. This might be as an aid to player movement, or part of the AI system. In any case it’s a nice self-contained problem to solve as the next step in development.

The star of all search algorithms in game programming is A*. It finds the shortest path through a network of nodes, and does so in a quite efficient manner (especially if the path is very simple). So this looks like the place to start. There is one issue to resolve first though.

Essentially, the map is not really a network of nodes. It’s actually made up of connected rectangular areas forming corridors and rooms. I could put a node on every grid square, but that seems like a lot of nodes and the path would end up with a lot of stepping.

How about a node at the centre of each rectangle? The final path would need to be constructed through the connected edges, but it could be done. However, the distance between the nodes would not be accurate due to all the possible paths through the rectangles.

Back to the grid squares then, but this time only on the connected edges of the rectangles. This is enough to find an accurate shortest path, and there’s no need to pathfinding inside the rectangles.

Here’s a good description of the algorithm:

http://www.policyalmanac.org/games/aStarTutorial.htm

The only problem I had with this page is that the operations on the open set (insert/delete nodes yet sort by node distance) are not covered by any single STL data structure (assuming you don’t want to do a linear search every time). If you didn’t think about this you might end up using doubled-up maps or (god forbid) something from Boost, but actually it’s possible to defer the tricky deletions and use a simple sorted list.

It all works fine, except that the paths are still a bit steppy when passing between zones. I’ll wait until I see them in use before trying to fix what seems a minor cosmetic issue.

Is A* the end of the story? I doubt I’ll have any performance issues, but I will also need avoidance of dynamic obstacles, and it’s not clear how that will fit in. I’ll see how it goes.

 

Advertisements