Using the built-in functions of the NavMesh package might be enough for some, but in many cases we need customized pathfinding for our projects. Knowing how to implement, or even better, understanding A* (a-star) pathfinding, can take us a long way in our AI endeavors. It's easy to implement and very versatile. Correctly set up, it will always find the shortest path (and pretty fast too!). One of the drawbacks is that it can be memory-intensive in large areas if not kept in check.

A* is an algorithm that finds the shortest path in a graph. It's good at finding this quickly using heuristics, or an estimation of the cost to get from a position in the graph to the goal position.

Finding a good value for the heuristic (H) is very important in order to make it effective. In technical terms, H needs to be admissible. This means that the estimated cost should never exceed the actual cost.

Each position, called a node, will keep track of how the cost from the starting...