Something that i'm very interested in is pathfinding. More specifically grid pathfinding. So I decided to go and learn what it is, how it's done and how I can implement it into a project.
There are 2 main different types of pathfinding. A* and Dijkstra. A* checks all the surrounding tiles of a starting point and sees which one is generally the closest to the end tile. Then that tile is checked and so on. With Dijkstra, each tile around the start point is checked to see if that tile is the end tile. If not, those surrounding tiles of that tile are checked. Below, A* can be obviously be seen to be the better of the 2. It's more efficient, and that's what i'm going to be going into with this research report.
We start with our start tile and end tile. What we want is the shortest path between the 2 tiles.
Then we check each of the start tile's surrounding tiles.
The top-left number is the G cost. This is the distance from the starting tile.
The top-right number is the H cost. This is the distance to the end tile.
Added together, these numbers form the F cost of that that tile. The F cost will be used to determine which tile's should be included, and which ones shouldn't.
By looking at the F cost of each of the surrounding tiles, we can see that the top-left tile has the lowest cost. So then that tile gets selected and the surrounding tile's values are calculated.
In this case where multiple surrounding tiles have the same F cost, we can just go with the tile that has the lowest H cost.
Here, the new tile we selected has surrounding tiles that are not the lowest on the board. From the original starting tile, we can see that the top and left tiles have the lowest F cost. They also have the same H cost too, so we can just select both of them.
In doing this, we are creating an array of tiles which could hold the possible shortest path. We just need to keep on going with these calculations, until we reach the end tile.
After some time we finally reach the end tile and out of all the red tiles, the shortest path can be found.
So how can this be used in the future?
This grid pathfinding is very useful. In the future there are games that I will probably make, which will require a system like this. Strategy games, puzzle games and even other types of games that don't use grids, which this system can be translated to. Unity already has many assets and scripts online for grid pathfinding, yet knowing how to do it yourself is always good.
Games like Civ 5 and other 4x games use grid based pathfinding to move units. These sort of games are very complex, yet at their roots use this sort of pathfinding system.
Games in the future that i'll want to hopefully make are 2D strategy games. Things similar to Civ (yet less complex) and realtime war games which use individual units. These sort of games can be as complex as you want them to be, still with a level of strategy required.