I’ve implemented A* before for pathfinding in a simple cops-and-robbers arcade game back in college, but I assumed I’d just use a library this time around.

I did not.

The hardest part of A* isn’t the algorithm, it is determining what nodes and paths are for the game. If I had a navmesh, then I could simply treat each edge of the mesh as a valid path and use the string-pull algorithm to simplify between all of the hops.

Unfortunately, a navmesh is fairly far off right now. I want to get something simple and quick working for prototyping gameplay, and a navmesh will not be simple or quick.

So I chose to use my area system and make each grid tile center have a node and built a graph of all the tiles. When it built this graph, if it had an adjacent neighbor that wasn’t walkable, it wouldn’t create a node/edge to it.

So when the user clicks, I find the nearest tile and try to path from the unit’s current tile to it:

However, there are a few problems with this approach:

• No diagonals
• If the path is interrupted, will back-track to ensure all nodes are reached
• Won’t skip any nodes even if it is a straight line.

You can see the wonky behavior a bit better with movement:

So I added pathskipping. I raycasted to each node along the path and determined if it was necessary, which solved both the diagonal and node skipping problem. The red line shows the current path, the blue are planned nodes:

And now mages can finally move freely about their castles!

Vendor Concept Art

Check out this beautiful vendor! We’ve been discussing shops and how mages might want to buy supplies, items, or hire additional mages.