Introduction
In this project, I created a simple wave based shooter that uses a flow field as a pathfinding algorithm for the AI. In addition to the game itself, the demo shows the general flow of the flow field and also the cost for each of the grid nodes, which can be turned on and off. The player can also place a wall down onto the grid using right click and the flow field will adjust accordingly.
Path-Finding
Cost Field
For the first step of the algorithm, I needed to generate the cost field. The cost field essentially is all of the obstacles on the grid that the agent needs to know about, such as walls and difficult terrain to cross. In my implementation, I made sure that walls were their own type of object so that the cost field could automatically figure out where each wall is. When placing all of the walls into the cost field, the game gets all of the wall objects and gets their position relative to the grid. From here, it then sets the cost at the positions of the wall to 255.
Integration Field
For the second step of the algorithm, I needed to then generate the integration field. The integration field is essentially a grid where each position has its own number, which corresponds to the distance between it and the goal location. To generate this grid, I essentially had to go from the goal location and spread out from its neighbors, and then its neighbors' neighbors until all nodes had been analyzed for its location relative to the goal. In the actual implementation of the integration grid, I initialized all costs in the field to an insanely high number and then added the goal position to an open list. I then took the first element of that list and found all of its neighbors and then added those neighbors to the list, making sure their current cost is greater than the current node's cost and that it isn't a wall. I continue to do this iteration until there are no more positions inside of the open list
Flow Field
For the final step in the algorithm, I finally just needed to generate the actual flow field. To do this, I just needed to iterate through the entirety of the integration field, take the lowest cost neighbor of the current node, and then make a directional vector toward that neighbor.
Agent Path-Finding
To get the agent to actually move relative to the flow field, I found that I could just get the directional vector based on the position the agent is on relative to the grid. So essentially I took the flocking behavior that I used in advanced flocking and just made seek be instead the function that returns the directional vector based on the grid.
Conclusion
During this project, I found that I could not make the grid any larger than 10 by 10 without the engine chugging to generate it so in the future, I think I wanted to try and multithread the grid generation of the fields so that I can have much larger fields to work with. I would also like to add the ability for the developer to designate areas as tricky terrain so that it can then be included in the field generation. It would also be interesting to explore having dynamic grids to cover a level that my not be rectangular, which I would probably generate by getting the bounds of level and first generating smaller fields and then eventually combining them into one large grid.