Game AI - Flow Fields and how to implement them? (Path Finding method for game AI)

Flow Fields!

    Flow fields are a method/data structure for pathfinding with AI that takes what would usually be the job of many independent actors and turns it into a one-time gig that everyone can take advantage of (depending on how you implement it). I am going to talk about this subject under the assumption that you have a basic understanding of pathfinding (so if you have no clue then I suggest you google things like Dijkstra's algorithm and A* to get an idea of the methods/terms used).

    I want to start off by talking about what a flow field is, its advantages and its shortcomings. This won't be an in-depth dive into flow fields, just a surface-level analysis based on what I can see/understand. I do want to mention though that all of this can change based on how you implement your flow field.

This is the flow field example that I made for this blog post. It shows the "units" pathing to a target in a basic 2D environment that I generated using Unity's built-in Perlin noise generator(you can learn more about procedural generation in my previous blog post on procedural generation) after a certain amount of units reach the target, the team with the most players on the target win.

Blue squares = water

Gray squares = stone

White squares = Snow

Black squares = an Obstacle

Part 1 - What is it?

    As I mentioned before a flow field is a method of pathfinding, they allow an NPC (non-player character) to navigate around a scene without 

(A) Direct input from a player

(B) Running into obstacles (not always perfectly)

    This is usually true for a lot of pathfinding algorithms, flow fields deviate from the path however when it comes to how they deal/work with multiple NPC's. "traditional" pathfinding algorithms are usually used to give a single NPC an ideal path to a specific point, and in a lot of cases this is exactly what you want (a single NPC going to a single point). However, a "problem" arises when you need either a bunch of NPC's going to a single point, or you don't know where the NPC is going to start pathfinding from (there are many more applications for flow fields but these are two examples). While there are some pretty efficient pathfinding algorithms out there, even the best of them will start to bog down your system when you have hundreds of NPCs looking for the best path (or even just a few NPC's on a complex/large map). The goal of a flow field is to find the best path from every point on a map/grid to a single point/area once, then allow the NPCs to use this information without needing to calculate it on an individual basis.

Can you see why they call it a flow field?

    All of the arrows point towards an arrow that eventually leads to the target point. The reason why the arrows don't point straight towards the target is because they try and follow the path with the lowest cost. I made it so snow, stone, and water have a much higher cost than the grass. Even on the grass, the lighter grass represents a higher level/cost so they end up running downhill to reduce costs (could be seen as an undesired side effect but I sort of like it).

Part 2 - Why use it(or not)?

    There are countless applications for flow fields in games. From things like zombie survival (where you want a hoard to chase a player) to dynamic tower defense(where map changes need to be reflected in the NPCs actions), it really depends on the game. I would say that it works best when you only have one (or two) targets that you want many NPCs need to go after (or run away from). You can hide the creation of the flowfield behind small actions or loading times while having the NPCs use it for minimal to no cost. You can even bake flowfields into a map so you don't even need to calculate the field just use it on demand. There is a lot of room for creativity and optimization that could make your game the perfect use case for flow fields. However, they aren't the end all be all of pathfinding.

    For example, I wouldn't want to use flowfields if I was making a game where there are either too few NPCs to rationalize using flow fields or each NPC needs to find its own distinct path. I say this because a flow field is far less efficient than using a single optimized pathfinding algorithm. This is because a default flow field needs to explore every single possible point to find the best path from each one. If you were to do this for multiple points then you could end up exploring many times more points than you needed to. This problem scales exponentially with the size of the grid/map you are using.

10x10 map = 100 points to process (easy)

100x100 = 10,000 points (not bad, still doable)

500x500 = 250,000 points (you need to start thinking about optimizations)

1000x1000 = 1,000,000 points (I think the player will start to notice the pauses)

    I hope you get the point, eventually running a couple dozen optimized (maybe even interruptable) pathfinding algorithms in real-time can become far more efficient than running a dynamic flow field in real-time. This isn't set in stone obviously but it's a good rule of thumb (or thought experiment if you like thinking about those sorts of puzzles).

Part 3 - How to do it?

In order to implement a flow field, you need to first implement 3 different "fields" (I'm going to call them fields for now). You can make and store these maps/fields however you want (you can even combine them into one convenient structure that holds all 3 in the same place) but these 3 fields make the bare bones of a flow field.

Field 1: Cost Field

    This field holds the cost values for traversing the terrain. This field is usually where you will store the locations/values of obstacles and can be as simple as storing 0 for no obstacle and 1 for obstacle, or as complex as a range of numbers that depict different terrain costs with the highest being impassable obstacles.

   

    The images above show the map normally (top image) along with a depiction of the cost field (the red one obviously) the lighter the red color the cheaper the cost of traversing the terrain. Notice how the obstacle is still black since the cost is maxed out.

Field 2: Integration Field

    I don't know why it's called an integration field but I am pretty sure it's called that because it's the step between the cost field and the flow field (spoilers for the last field). This field stores a combination of the cost field and some other weighted value (usually it's a point's distance from the target). This field's primary purpose is to designate the order in which the points will be processed (I will explain this in more detail in the next field).

    This is a visual representation of the integration field. The whiter the tiles are the cheaper/closer they are to the target. Notice how the water areas are even darker than some of the grass tiles halfway across the map. This means that by the time the algorithm gets to around mid-map it will finally start exploring the closer water squares (this is simple Dijkstra's algorithm here)

Field 3: Flow Field

    This is the final field/step in implementing a flow field (besides using it to control your NPC's). It basically stores a direction that leads to a point that will store a direction that after a few points will eventually lead to the target. This is the field that your NPCs will access to get directions. You can create this field by starting from the target and using normal pathfinding methods to explore the points. Find the cheapest point in a list of points grabbed from the integration field, add its neighbors, and set their directions towards the point they came from. In the end, you have a field of directions that lead to the target.

Final flow field in all of its glory

Part 4 - What do I do with it?

    Now that you have a flow field you can use it however you like. I used it to directly control my NPCs but you don't have to do it that way. Since there is no longer any time spent finding a path for each NPC, you can spend the free time processing more complex behaviors for each unit or even spend it somewhere else (maybe you want to have a really nice particle system that previous pathfinding methods prevented you from implementing?) the world is really in your hands. A flow field is really just a tool in a bag of tools that you can use as a developer, so use it when it's needed and enjoy reaping the benefits of having the right tool when you needed it.

The End

    I once again hope that this was helpful to anyone that needed it. Let me know in the comments below if you have any questions/comments and ill try to answer them or update the post if anything new comes along. Thanks for reading!

Until next time,

Written by Adam Currier

3/11/21