Explaining Flow Fields

In the latest stream, it was clear many people misunderstood what the flowfields actually were, and a comment by Jon stating he may no longer show off technical stuff scared me somewhat, so I'm just writing this to give what I think is the simplest way of describing it in hope of showing that more than 5 people understood it.

From what I understand, the flowfield is compromised of 2 underlying separate fields - a "cost" field (showing undesirable land), and a "distance" field (which makes units try and take the shortest route through a sector, and head towards the target). The game then takes both these fields and adds them together to get an intelligent decision on the best route.

An easier way to explain it may be to think about how you would cross a muddy field to get to a certain point. The "cost" would be each puddle - the deeper the puddle, the higher the cost, and the less likely you'd want to walk through it. The distance would radiate outwards from the target point.

For example, let's say you wanted to reach the middle. Instinctively you'd want to avoid walking by the edges as it is far from the target you'd want to reach, meaning you'd preferably try and take a direct route. So you look ahead, and see some puddles. If you had a shallow puddle, you wouldn't mind walking through it so much, as you wouldn't get your socks too wet, but you would try and avoid a deep one as much as possible.

The end result means you intelligently look at the field, and think to yourself "What is the preferable route?" If you had shallow puddles, you might just mostly ignore them and walk straight through to get to your target as quickly as possible. If you had deep puddles, you might decide to take the long walk around the edges, at the expense of it taking more time and effort.

The pathfinding AI will look at the field, and make decisions on what is the favorable route in the same way. It'll avoid high-cost areas, like a mountain, but still try and take the route which keeps it close to the target. Depending on the height of the mountain, and the distance around it, it might decide to climb over the mountain (taking a high cost but low distance route), go around (taking a low cost but high distance route), or climb the outskirts (medium distance and cost).

Both the cost and distance together adds together into what is essentially a field of arrows, showing each unit the way to go, around high-cost areas but still trying to stay close and point a quick route to the target.

It's important to understand this field is generated completely automatically, and the user never directly writes to it.

This is, however, a non-programmer's understanding of the system, so I may be wrong, in which case Jon may be correct about not showing the technical stuff.

This is how I understood it as well...

Also, I think what people were raging about, is how the units never went OVER the green "cost" areas. I think the part they didn't talk about in the livestream is how they were adding high cost areas. Not just little hills. The units (yay box army) obviously thought it was worth their time to go 3 times as far to get around it, so it wasn't just a little hill. That cost represented something much much more difficult to traverse.

If they had surrounded the boxes with the green cost, they would have gone over it. I think that would have helped assuage some of the fears/misunderstandings going on in the livestream.

A good article that explains how this function: http://aigamedev.com/open/tutorials/potential-fields/

Thanks for the explanation, it did clear up some confusion I had.

I enjoyed the demo of the flow fields very much. I think what it lacked was a control group. For example we did not see how much time would be lost traveling through the green areas so the longer routes seemed excessive.

Perhaps if the blue boxes ignored any cost area less than red and traveled through it we would have been able to see the effect of the cost more clearly and would have seen justification for the longer routes to avoid them.

Nullimus- while in an actual game the cost will presumably have a cause, they were actually painting cost, not reduced movement speed. It would actually be faster for the squares to travel in a straight line over the painted green. However the purpose of the demonstration is to show that the squares can navigate an arbitrary field of costs- and that the agents don't actually care why the cost is there.

Most of what you said is close enough to how flow fields work but this section isn't quite right.

The point behind flow fields is that they remove the need for pathfinding AI as you describe, I think part of the problem is that what was being displayed in the stream is the just the cost data that goes into creating the flow field rather than the actual flow field it's self. The actual flow field is basically a texture but where each "pixel" is a direction rather than a color, the direction of each "pixel" is determined by the cost of the surrounding pixels from the cost data, if the pixel to the left of it has the lowest cost of all the pixels around it then the direction of that "pixel" in the flow field will be left. And because the distance to the final destination affects the final costs used to create the flow field (higher costs further from the destination), the lowest cost will tend to be in the direction of the final destination unless a high cost area (obstacle) is in the way, in which case the lowest costs will tend to be around that side of that high cost area.

This means that all each unit needs to do is look at the direction of the "pixel" in the flow field that the unit is currently on and move in that direction. It can ignore everything else about the terrain, it doesn't care if there's a mountain ahead or a cliff or any other obstacle, it can just blindly follow the direction from the flow field because the direction that it gets from the flow field has already taken that into account. This makes it extremely efficient for large numbers of units because instead of each unit needing to figure out what is ahead, whether or not they can go that way, whether it's quicker to go left or right around an obstacle, and many other variables that go into traditional path finding most of which is pretty time consuming to calculate, and with many units can really slow down a game, all the units will need to do in PA is get the direction from the flow field and move in that direction, very simple, very fast and will give much better performance on several orders of magnitude more units than traditional path finding.

From what I mainly understood is that Flowfield removes the units constantly bumping in to each other and them constantly renewing their path to their goal.
Supcom 2 had this as well: http://www.youtube.com/watch?v=jA2epda-RkM

That is probably more to do with the steering behaviors that run on top of the flow fields rather than the flow fields themselves, but the flow field do allow the steering behavior to smoothly move units out of position to avoid obstacles (like other units) without needing to recalculate the pathing, the old A* type methods often aren't as flexible with units going off the calculated path so they tend to bump into each other and wait till a new path is calculated for them. If done properly though you can achieve similar looking results to flow fields with A* and good steering behavior, but it's without the significant improvement in performance that flow fields have with large unit numbers and there are a few extra issues to deal with.

There are some flow field implementations that do factor in other units, SupCom2 might be using that, but I doubt it would scale well enough to be used in PA because the creation of such flow fields can get much more computationally expensive if you do that, and with decent steering behavior you'd barely notice the difference anyway.

It is my understanding that the advantage of the flowfield system is that it is very computationally cheap to compute a path for a unit. However, instead it is computationally expensive to compute the field. However it doesn't get much more expensive no matter how many agents are trying to traverse the field.

However the number of factors that feed into the field is significant, so if every unit has to update the field you have just wiped out your gains from switching to a flowfield system. Having every unit modify the field would require constantly updating the entire flowfield in real time. Whereas if only relatively static features like terrain and structures modify the field, you might only recalculate the field when one of those changes, rather than every time a unit moves; or in other words every frame.

I think I was one of the 5 who understood everything . Okay okay, I created some games, but still the easiest example is to compare flow-fields with water. It flows around obstacles and its searching for the path with the least resistant.

So, I have a question about flowfields. Can we add one for aircraft that causes them to avoid enemy AA after a bombing run? So, you know, Strat Bombers don't fly overtop of flak, taking 10 seconds to turn around and die before they can make a second run because they are flown by lemmings?

SAMs generally represent 'High Cost' areas to me.

Can I ask?

How would gradients be represented in the 'costs'?

Will units prefer to go down hill?

That can be done with a cost-vector (a N/S cost and a E/W cost). That doubles memory usage though.

Not necessarily, as it can be taken into a account while calculating the flow field. The difference would be that instead of just using the cost field to calculate the flow field, you factor in the heightfield. For example, when integrating the cost, you additionally look into the heightmap, get the gradient and add/subtract cost. After that you still get a flow field, so instead of adding memory requirements you add computational cost. Remember that flow fields are calculated on the fly, they are not static and represent the best path of a (group of) unit(s) to one (and only one!) specific goal. If you really wanted to tax your computer, you would take 100 units and let each of them walk to the other side of the planet individually. Now your computer has to create 100 flow fields.

You can actually fairly easily modify flow fields to have any number of goals, the one I wrote for the TD game I'm working on actually generates a flow field for an arbitrary number of goals (if I want I can make half the map goals and units will always go to the nearest no matter where I spawn them), it's one of the big reasons I used flow fields for pathing as pretty much every other precise pathing solution is ridiculously slow at finding a path to the nearest of a large number of goals. But it's probably not worth the increased flow field generation time to do that for PA, though it would be kind of cool to use it to split large formations to flank enemy armies .

i think what made it hard for some people to understand is how I and probably everyone else assumed that the cost was represented on a fake color scale from green to red, where gray is no cost green is little yellow is high and red is impassable. When in fact green must have already been a really significant cost for units to choose a path that is 3 times longer on grey terrain. What also didn't help is that while green obviously represents high cost, units that passed over greenish outskirts didn't get visibly slowed down, which is what you would expect as the flow field should show the most desirable e.g. fastest path.

Overall i'm really looking forward to the final implementation, while the dots did take seemingly unnecessary detours at times I had the impression that "pathfinding" was already working better than in the releaseversion of SupCom:FA...

Yeah, though I think he did say that values 0-254 were represented by a green gradient, and that 255 was red for impassable, but I guess if you aren't used to looking at colors representing data it might still not have been clear.

Yeah agreed, though TBH I am a little curious as to if Elijah has handled the concave obstacle issue yet, where units can get stuck in the middle of a U shaped impassable obstacle, I remember thinking while watching that he seemed pretty careful not to create a concave shape for them to avoid . Though he clearly knows what he's doing so even if it's not done at the moment I'm sure it'll be done shortly .

Just some real world examples of cost which are not directly caused by terrain:
- If you have a bridge or a tunnel on your route, these will probably cut the length of your route enormously, but they may add a cost (monetary) to traverse. So the shortest route may not be the one with the least cost, and for the cheapest cost you may avoid it and take a longer route around it.
- If you want to get from northern China to South Korea, you would theoretically have to travel throw North Korea. Legally this will be very difficult to do and you would probably have to bribe your way through and conceal yourself. Anyway, because of the danger, the path is, for you, very costly, so you really want to avoid it. This is despite no obvious challenges in the terrain.

Good explaination. I have high expectations of this Flowfield algorithm. I can't say enough, this game is worth every penny .