Dev Diary - Shards of Magic Pathfinding

Posted by : at

Category : Shards   Dev-Diary

For this week I wanted to review and update my AI, I ended up spending the entire week on pathfinding. Back in the 2D version I had pathfinding nodes at specific intersections so that no matter where an NPC was, it would be able to see and move towards a node. I was attempting to skirt around some of the calculations of A* pathfinding by placing nodes in a way that an NPC would always have a line-of-sight to the grid. This meant manually adding nodes, and really didn't save me much in processing.

In the revamp I programatically place nodes at every whole coordinate (so every 1 unit of distance), align that node's y coordinate to the terrain, skip any placement where the terrain is too step (the normal is greater than 30 degrees off the y axis), and used terrain texture to set how much effort a unit would need to exert to walk on that ground. This is the standard normal A* pathfinding.

For example, roads are easier than grass, which is easier than walking in deep mud. When given a choice to walk a straight line through deep mud or go around the mud walking on a road the NPC should choose the road. I can do this more efficiently now because with each node being a single unit apart (instead of nodes being a variety of distances) I can review the terrain under each point and set the nodes weight at start up. An example would be a choice between going the route with node weights of 1, 5, 5, 5, 2 or 1, 1, 1, 1, 1, 1, 1, 1, 1? While it is longer, the latter path is faster because it doesn't slow the NPC down. Through Unity magic I am able to review what texture is applied to the terrain at that location as I create each node.

In the title image the NPC has several paths to his destination. The red are paths he didn't take, yellow is the path he chose, and the magenta squares are node points (made into a pretty box) showing where the road terrain was found.

There are still some kinks and side effects to work out, but overall I'm satisfied with the redesign

Useful Links