We have come a long way since the beginning of video games and we have seen some major technological, as well as logical, advancements in the gaming industry.
Game developers have been trying different techniques to achieve the desired outcome in video games and these experiments have resulted in some outstanding achievements as well, be it in terms of graphical advancement, physical abilities, and so much more.
But one thing that is hidden to many of the gamers, that essentially builds the base of many games, are the pathfinding algorithms. I mean there’s not a single game with walking NPCs that can exist without these algorithms. In this article, I’ll give you a quick overview about what a pathfinding algorithm is, and how exactly one of them works in video games!
So without any further ado, let’s get started.
What is a Pathfinding Algorithm?
We have all played a ton of games since our childhood with enemies following us, be it a game as simple looking as PacMan or a game as complex as GTA 5. You must have noticed how these enemies always find the best possible way to reach us while maneuvering around all the blockages in their path.
That’s exactly where pathfinding algorithms come into play. A pathfinding algorithm is a way for a game to calculate the shortest possible path to reach a particular point on the map. It basically explores multiple waypoints to reach from starting point A to the finishing point B.
There are lots of pathfinding algorithms that perform the same action of finding the shortest possible path from point A to Point B on the map, but they all do so in different ways. And with time, some of these pathfinding algorithms have become more efficient than the others.
Sometimes it’s not all about being the most efficient. Some developers don’t necessarily want the NPCs to take the shortest possible path to their destination, but want their NPCs to behave more naturally, rather than like a programmed robot. For that to happen, game developers can opt to go with algorithms that are not the most efficient, but ones that follow more natural human-like pathfinding behavior.
So we are going to list some of the most commonly used pathfinding algorithms, and explore one that is often used in many video games!
Some of the Most Commonly Used Pathfinding Algorithms
There are many pathfinding algorithms out in the market. Pretty much every popular game comes up with their own version, by tweaking and playing around with the already created algorithms. Here are some of the most commonly used pathfinding algorithms.
- DFS
- BFS
- Dijkstra
- A*
All of these algorithms have one common goal and that is to find the shortest possible path between two points on the map. But each one goes about doing that in their own different way.
A* is probably the most efficient pathfinding algorithm to date, and is quite commonly used by a lot of game developers, including myself. I have been making games for quite a while now and I have used the A* pathfinding algorithm for a lot of my game projects. It gets the job done as well as you can expect, without causing your game to lag (which is pretty common for a lot of algorithms). So let’s talk about how A* works.
How A* Pathfinding Algorithm Works
A* (pronounced A-star) uses heuristics to guarantee the shortest path, and is considered to be much faster than Dijkstra’s Algorithm, which it is somewhat based on.
A* Pathfinding algorithms divide the whole map into smaller blocks (you can adjust them, depending on the size of your map). Each of these blocks represent a potential step that the player or the NPC can take to reach its target. But taking the next step isn’t completely random, there are a bunch of values that the algorithm takes into account.
Each of the blocks has “G” cost value, which is the distance from the block you are on, to the next neighboring block (in 8 directions). Then it also has an “H” cost value, which is the distance from this point to the end point. And lastly, it takes into account the sum of all these values, which is the F value.
The way it works is the algorithm takes the next step in the direction which has the lowest F value compared to other blocks or potential steps. It continuously loops through all of its potential steps to calculate which path has the lowest sum, thereby figuring out the shortest possible path to reach the target.
Pretty impressive, right?
Here is how the algorithm looks when calculating the shortest path to reach from Point A to Point B on the map.
Although it looks fairly simple, there is a lot going on behind the scene, especially when there are lots of enemies chasing after you from many different starting points, and with many different obstacles to maneuver around.
This is my favorite of the pathfinding algorithms, but maybe you have one that you like better? Tell us about it!
