Discover Top Posts Tagged with #flow feild

Flow Field Pathfinding

Introduction

Flow field pathfinding is a grid-based pathfinding method, where hundreds or even thousands of agents can steer towards a single location, and that destination can dynamically change without a huge performance loss. Two fields are required to help generate a flow field: A cost field and an integration field.

Cost Field

The cost field stores information regarding the terrain type and associates a cost value for that particular terrain. As the developer, you can set any value for how the terrain cost will affect gameplay; The lower the terrain cost, the more desirable that type of terrain is to agents. The only rule is the terrain cost can not be greater than 255 or less than or equal to 0. Any impassible terrain cost value will be 255, the max value of a byte data type. A terrain cost of 0 is the destination node, which is calculated in the integration field.

My grass terrain has a cost of 1. My dirt terrain has a cost of 4. Lastly, my stone terrain has a cost of 255. My agents will prefer to path find on the grass terrain and will attempt to path find around stone and dirt terrains. They will never path find through stone terrain as it has the impassible terrain value of 255 (only on special cases, as you will see in the video demonstration).

Integration Field

The integration field calculates the cost for each cell towards the destination cell, whose cell cost value is set to 0. Cells closer to the destination cell are smaller compared to those further away. The idea is that agents will want to path find on the shortest cost path so each cell will carry a directional vector to the best cost path (the lowest cost path) when flow fields are utilizing the integration field. Each cell on the grid (besides cells with a cost value of 255) will check its neighbor cells and add its cost terrain cost value to its own to help achieve low costing pathways on the grid.

Since the grass has a terrain value of 1, every grass terrain cell on the vertical and horizontal will cumulatively increment with a value of one away from the destination cell. The diagonals will increment with a value of 2 away from the destination.

Flow Field

Finally, utilizing the integration field's newly set cost for each cell away from the destination cell, 8 directional vectors (the 4 cardinal directions and the 4 bi-cardinal directions) are created on the grid that all point to that destination cell. Numerous shortest pathways are created, which allow agents to path find on low costing pathways (shortest paths). In the agent controller class, modify the agent’s velocity by taking the directional vector (created by the flow field) that the unit is currently on and multiplying that vector by the unit’s speed, and setting the result as the agent’s velocity. As the agent moves to another cell, that directional vector will replace the previous cell's direction vector in the velocity calculation to ensure the agent steers towards the destination cell, whose direction vector has a magnitude of 0.