Flow Fields in Unity Engine

Uncategorized

Flow Fields are a version of pathfinding that don’t construct a single path from the agent’s current location to a target location, but instead creates a path across an entire grid. Flow Fields are broken down into three parts. The first part is is the cost field. The second part is the integrations field and the third part is the titular flow field.

The Cost Field holds the values of all the tiles in the grid. Typical these are held in some sort of 2D array, map or other data structure that have a key and a value. Having a key value pair allows for easy access of values based on a tile ID or some other kind identifying value. These values will be used in the calculations in the Integration step.

The integration field is where the most pathfinding happens. Here the algorithm becomes very similar to searching algorithms like Dijkstra’s and A*. We have an open list and a closed list which are used to keep track of the grid tiles. The open list is used to keep track of which tiles we have to visit and the closed list is kept to tell which tiles we’ve already visited.

Before the Integration process starts all tile’s cost is set to a large number. My examples uses 100, but as long the number is big enough that the costs will not add up to it you should be fine. Then the endpoint tile’s cost is set to zero so that it will always be the center. Once the Integration process starts the endpoint tile is is added to the open list. The algorithm then grabs the top of the open list (the endpoint tile) and looks at its neighbors while also removing it from the list. Each neighbor tile then has the original tile’s cost and its Cost Field Cost added together to create a new cost. This can be done using the tile’s cardinal (with diagonals) neighbors or using the tile’s orthogonal(no diagonals) neighbors. If the new cost is less than the neighbor’s current cost (the large number we set it to at the beginning) then it is added to the open list if it is not on the closed list. After all the neighbors have been looked at then the original tile is added to the closed list so that we don’t look at it again. This process continues until the open list is empty signifying that there are no more tiles left.

Once the Integration is done we then go to the Flow Field process. The Flow Field then iterates through all tiles and looks at all their neighbors to find the one with the lowest cost. Once it has found the lowest cost neighbor it computes a directional vector that points from the origin of that to its lowest cost neighbor. My example stores this directional vector in the tile itself, but you could also store it in another grid of vector values so long at it is the same size as the original grid. Once the this part is done the Flow Field is complete and units can read directional vectors in order to path find to the target location.

Leave a Reply

Your email address will not be published. Required fields are marked *