Implementing A* in a custom C++ engine was honestly a really fun challenge. It's a well-documented method for implementing game AI, so I didn't blaze any new trails during my implementation, but to work well for our engine I built it right off our Tiled parser, so the search space could be automatically generated.

Since our levels are grid-based, I used octile distance instead of Euclidian or other options, since it provides accurate guesses with little computation effort, especially compared to Euclidian distance, which uses a square root for every distance check.

Additionally, I implemented a system of adding a set cost to a tile, so the monster could break through walls when more efficient. We ended up not using it for this purpose, since the game was more approachable when the monster was predictable, and there were more important features to implement. I did use this code, however, for the terrain analysis below.

For the final path, I did a few things to improve the look of it and make the underlying grid-based map less obvious.

First, I rubber banded the final path, which involved identifying unnecessary nodes by seeing if they actually moved around walls and removing them. I did this by simply drawing a bounding box around the nodes before and after the one I was checking and only keeping the node if there were walls in the box.

Second, I took the start and end nodes off the path and replaced them with the world positions of the pathfinding agent and its goal, which made the monster look like it was actually moving towards its target rather than moving to a path and following it.

Finally, I took the result path and smoothed it using a Catmull-Rom spline. I went with this method because the Catmull-Rom spline, unlike cubic or Bezier curves, goes through all of its control points, which better guarantees that it actually follows the path that the A* algorithm found.

Before the splining, I also re-added nodes into the path if they were greater than two nodes apart from each other, which made the cornering very consistent.

A* is fantastic for quickly finding the optimal path, but we wanted the monster in DREAD IT to have a little more personality. One thing I did for this was some automatic terrain analysis to have it avoid walking next to walls with possible by just giving an added cost to tiled adjacent to walls. This made it so that it tended towards the middle of hallways, which suited its large stature and feral behavior.

Another thing I did was have each node along the path track how close it was to a corner, so when the monster was pathfinding, it could move slowly along corners. Looking back, I could have just tracked when the monster was turning and had it slow down based off of that instead of storing it in the map, but this solution worked just fine for what we needed.

Since our maps were small scale and we only had one agent pathfinding, the algorithm didn't need to be terribly fast, though if I were to implement A* again in a different context, there are some things I could do to improve performance, such as:

• Overestimating Heuristic Costs (~x1.01)

• Precomputing valid neighbors on map load

• Changing open list representation to a binary search tree or hash table representation

• Making smaller nodes and reducing use of pointers to improve cache coherency