Pathfinding is an essential component of most game AI agents, and incorrect or strange-looking AI pathfinding can really ruin the player's suspension of disbelief and could easily ruin their gameplay experience. Pathfinding however can be a very costly calculation, especially when dealing with large maps or a large number of units performing the operation. There are, of course, many techniques we can employ to improve efficiency and keep the game running smoothly, such as Spatial Partitioning, Multithreading, Interruptible Pathfinding... and Flow Fields.
When a Flow Field is implemented, instead of having each unit calculate the best path towards the target location, only one calculation occurs, and each cell in the pathfinding Grid stores information telling units which direction to proceed in. As you can imagine, this is used for calculating the best path from each cell in the grid to a single destination cell, and performing this calculation just once, as opposed calculating the best path for each unit form its location to the same target location, brings immense performance gains for high numbers of units.
In the demonstration, you see I have a grid comprised of cells, and a very basic environment with Mountains (the brown objects), Gravel (the gray objects), and Impassable Walls (the hot-pink objects). The Flow Field is calculated in three stages: the Cost field, the Integration Field, and finally the actual Flow Field. Each cell has a cost associated with traversing it, and the unit must find the cheapest path from the cell they are on and the destination cell.
The Cost Field shows the cost of traversing each cell: the Gravel has a cost of 4, the Mountains 9, the walls 255 (max value, we are using Bytes to store the costs, as the bounds are simple), and the grass (green) 1. This Cost Field is used in the calculation of the Integration Field, which is the next step.
The Integration Field calculates the accumulated cost of the Path from each cell to the Destination cell (with a total cost of 0, highlighted on the image). In short, set the best cost for each cell to the maximum value (65535), except for the destination cell, whose best cost is set to 0. We then add the destination cell to a "frontier", or an Open List of cells, and run the following algorithm (pseudo-code):
While the list is not empty:
1) Get the currentCell at the top of the Frontier (Open List)
2) Iterate through the currentCell's neighbours
2.1) Skip over any impassable cells
2.2) Check if we found a new bestCost for the neighbour
--> if the currentCell's bestCost + the currentNeighbour's cost is less than the
--> currentNeighbour's bestCost
2.3) If we found a new best cost
2.3.1) Set the currentNeighbour's new bestCost
2.3.2) Add the currentNeighbour to the Frontier
Finally, to get the Flow Field, we iterate through all the cells in the grid, and then for each cell, we iterate through its neighbours. In doing so, we check which neighbour has the lowest cost, and set the currentCell to "point" towards that cheapest neighbour to "flow" to. When the algorithm is complete, each cell will point to its neighbour with the lowest cost to get to.
Finally, after spawning units, they each get the direction to follow from the cell they are currently above. Since the calculations were already done for them and the direction is stored in each cell, they do not need to calculate any paths.
In the future, I would definitely like to revisit this project and rewrite most, if not all, of the code. Currently this code is heavily inspired by Turbo Makes Games' tutorial on YouTube, linked below in the references, but does include different approaches I decided to take. When revisiting Flow Fields, I would like the vast majority of the code, at the very least, to be my original work.
One of the changes I made is that only the cost, integration, and flow fields get recalculated when the user clicks on a new cell, saving the grid creation. I though this would increase efficiency, even though it may not be by a lot. I also added a "food" object where the mouse is clicked, similar to the one I did for the Smart Flocking V.2, where units will "consume" it, and it will eventually get destroyed. Again, there can only be one at a time, and in the gif above I kept it off-screen (remember, the units' priority is not to consume the food, but instead to get to the destination cell). Additionally, I made it so the costs of each obstacle terrain type can be modified in the Unity inspector, and the changes reflected upon the calculation of the next Flow Field (Cost, Integration, and Flow).
When I revisit this project and update all the logic, I will have a new Blog Post explaining what I did, just like I did for the Smart Flocking Project. All the projects I created posts on are available in the repositories linked in each post, so be sure to check them out. In this project, the instructions are in the Debugging Console Window, just press Play on the project and read the short prompts.
Demo Repository: https://github.com/adel-talhouk/gpr-440-01_advanced_ai
References: