One of the common problems in Computer Science is that of finding the shortest path from one location to another. There are a number of algorithms that do this, the most popular is known as A*.

A* works essentially by a connected network. Each node in that network knows its neighbors, and the distance to those neighbors. There is no requirement that the path be symmetric, so if a path involves, say, falling off a cliff, the algorithm will model the node one way, but not include the reverse path.

The key to A* is called the Heuristic. The heuristic is an estimate of the minimum distance between two points. If the heuristic is larger than the minimum, then a slower path could be found, but if the heuristic is too low, the algorithm will take longer to run. A common method would be to include the physical distance between two points. If your node is a tile based system, and you are going from point (2,0) to (5,0), your heuristic might be 3, for instance.

The algorithm works by starting at the start node, identifying its neighbors, and the distance to each neighbor. Each node then estimates the distance to the destination tile, using the heuristic. These tile are placed in a sorting buffer, sorted on distance. The next node tested is the node that is the closest to the end tile. The start tile is added to a list of already tested tiles, and will no longer be updated. This process continues, each tile incrementally finding the shortest distance to the start node, and working its way to the end node. Eventually, when the end node is selected, the shortest path has been identified. Each node should know the node which the path came from, and the back can be worked out backwards, Wikipedia has a nice graph that illustrates this:

A* works essentially by a connected network. Each node in that network knows its neighbors, and the distance to those neighbors. There is no requirement that the path be symmetric, so if a path involves, say, falling off a cliff, the algorithm will model the node one way, but not include the reverse path.

The key to A* is called the Heuristic. The heuristic is an estimate of the minimum distance between two points. If the heuristic is larger than the minimum, then a slower path could be found, but if the heuristic is too low, the algorithm will take longer to run. A common method would be to include the physical distance between two points. If your node is a tile based system, and you are going from point (2,0) to (5,0), your heuristic might be 3, for instance.

The algorithm works by starting at the start node, identifying its neighbors, and the distance to each neighbor. Each node then estimates the distance to the destination tile, using the heuristic. These tile are placed in a sorting buffer, sorted on distance. The next node tested is the node that is the closest to the end tile. The start tile is added to a list of already tested tiles, and will no longer be updated. This process continues, each tile incrementally finding the shortest distance to the start node, and working its way to the end node. Eventually, when the end node is selected, the shortest path has been identified. Each node should know the node which the path came from, and the back can be worked out backwards, Wikipedia has a nice graph that illustrates this:

I have implemented this algorithm in C#, and released it to GitHub. Feel free to download it, use it in your project, and even improve my implementation if you so feel like. The key to implementing it is to implement the TilePathfinder interface. Each node, or in my case, tile, is required to provide a list of neighbors, along with the heuristic function.

The exact same implementation I provided to GitHub is used to power my way through this maze, finding the shortest path. It works quite well. Note that the brown squares are land, and I can't travel to land (After all, the game is about a ship, represented by the rectangular box in the lower center of the image).

**About the Author:**

Ben Pearson is the author of the Amateur Radio and other technology blog KD7UIY and developer of Games and Apps at Google Play pearsonartphoto, where he plans to publish some of the games created by inspiration of gamedev.tv. He is currently working on a Sea Trading game, which you can subscribe to updates at his Google Group. He has been a programmer since a young age, although only recently is learning programming with game engines. He has completed the the Complete Unity Developer Course and the Procedural Generation courses, and is working through the Complete Blender Developer Course and Unity Game Physics courses. He is hoping to soon start Unreal Courses soon. Follow him on Twitter @KD7UIY.