Flow Fields for Pathfinding

[Bitiquinho]

From the last development blog post of Planetary Annihilation, a Kickstarter RTS game I helped to fund.

Starting at 24:25, they begin talking about how navigation is done in the game, and explain something about Flow Fields as a solution for pathfinding of great number of units and formations. As it looks like a new concept, I thought it could be a good idea to show it here. Is there some 0ad developer who is already aware of this technique ? Could it help 0ad pathfinder implementation somehow ?

English is not my native language, so sorry, I couldn't understand all of the video talking, and maybe couldn't explain my intentions really well too. However, the guys in the video seemed open to answer more tech questions from interested people, so maybe they could provide you some info. There's a forum thread for discussion here:

http://forums.uberent.com/forums/viewtopic.php?f=61&t=44788&start=30

[idanwin]

Wow, that game looks amazingly fun!!! I wanna play it!!!

[sanderd17]

Flowfields are just a stored routing tree. And you can store it because you have the same destination point for a bunch of units. So it will bring a higher performance to the game, but I do see some problems.

Since the flowfield is used by multiple units, the performance gain is because it doesn't have to be recalculated. So when you work with big units (think ships), if you want them to not go through each other, you need to edit (or re-calculate) the flow field. It looks like in that game, they allow units to squeeze together, which makes perfect sense for small units, but not for big ones.

Also, I don't immediately see this working with formations. It looks like that game mentioned will not have formations, so units more freely to the same point. While in 0AD, units will need to stick to a certain grid, but also break apart on the right times.

It would be great if there could be better cost fields already. A cost field where a forest is a really high cost for a siege, and a moderate cost for infantry. And a flat surface has no cost for any unit. With a good cost field, recalculations of the route should be fewer (as you don't have a lot of chance to bump into something), and the paths would look more logical.

[Shield Bearer]

I watched the video and it seems they are planning formations...

[Zeta1127]

If I had a better computer, I would have already got involved with funding PA by now.

[Mythos_Ruler]

@12:15 I see myconid's lighting stuff.

BTW -- WFG should be doing videos like this. Maybe something I will remedy in the nearish future (say, this Summer, if "things" the team are currently discussing goes well).

[scroogie]

Flowfields are just a stored routing tree. And you can store it because you have the same destination point for a bunch of units. So it will bring a higher performance to the game, but I do see some problems.

Since the flowfield is used by multiple units, the performance gain is because it doesn't have to be recalculated. So when you work with big units (think ships), if you want them to not go through each other, you need to edit (or re-calculate) the flow field. It looks like in that game, they allow units to squeeze together, which makes perfect sense for small units, but not for big ones.

Also, I don't immediately see this working with formations. It looks like that game mentioned will not have formations, so units more freely to the same point. While in 0AD, units will need to stick to a certain grid, but also break apart on the right times.

As far as I understand, a flow field is rather a vector field pointing to the cheapest local steering direction relative to the goal (or is that what you meant with routing tree?). So units are still free to choose the direction in which they steer, but diverting from the vector field direction will raise the movement cost. I would think you combine it with a dynamic cost map and coarse planning/replanning, so that units choose a different coarse path if the prior one is blocked. The fine movement will then be directed by the flow field. I guess you will get problems with oscillating paths, but it should work with formations etc.

Edited March 27, 2013 by scroogie

[sanderd17]

As far as I understand, a flow field is rather a vector field pointing to the cheapest local steering direction relative to the goal (or is that what you meant with routing tree?). So units are still free to choose the direction in which they steer, but diverting from the vector field direction will raise the movement cost. I would think you combine it with a dynamic cost map and coarse planning/replanning, so that units choose a different coarse path if the prior one is blocked. The fine movement will then be directed by the flow field. I guess you will get problems with oscillating paths, but it should work with formations etc.

What do you mean with oscilating paths? Units moving left-right-left-right ... ? I think that can be solved by smoothing it out. Don't go to the exact pixel with the least cost, but look 3-4 pixels ahead. That's only a very small calculation, and if the resolution of the flow field is big enough (so that every obstacle is bigger than 4 pixels) it should not cause routing problems.

For the formations, you're right. You take one unit to follow the flow field, and the others will try to stay in a grid relative to that each other. Unless there's an impassable obstacle, in which case you have to break up the formation, and use regular pathfinding to get back in formation after the obstacle.

The units going through each other could also be solved with dynamic flowfields.

So, what's needed to implement this?

1. a static cost field per movement type (which only includes terrain and relief)

2. a dynamic cost field (only depending on non-movable entities)

The dynamic cost field is updated every time a tree is cut, or a house is build. When you combine the two, you have the total cost field. The cost field should directly influence the moving speed. Btw, it would be nice if you could draw that static cost field in Atlas, so you can make a swap that's slow to cross etc. Now they just walk through a swamp as it's solid ground.

After that, per command given to a unit, you need

1. Static flow field, this depends on the destination and the total cost field for that unit

2. dynamic additions to that flow field: for every movable unit, the ground under it becomes impassable until he leaves. As this can while travelling, this can't be included in the general flow field. Note that big units can have a "keep away" aura. If you have a "keep away" aura around a unit, other units moving won't go very near to them. This is good for sieges, so they can always follow their optimal path, and other units will go around them.

After sleeping a night on it, I like it more. I think it should work with one big calculation per movement, and only local updates to avoid other moving units.

[scroogie]

Note that I never implemented flow fields. These are just my thoughts about the algorithm.

> What do you mean with oscilating paths? Units moving left-right-left-right ... ?

Yes. I would expect that relative to the original goal, units will periodically divert into orthogonal directions, as they toggle between taking an alternative route and completely following "the flow". This is basically the cost of approximating a global problem with local solutions.

> I think that can be solved by smoothing it out. Don't go to the exact pixel with the least cost, but look 3-4 pixels ahead. That's only a very small calculation,

> and if the resolution of the flow field is big enough (so that every obstacle is bigger than 4 pixels) it should not cause routing problems.

Principally, yes, but I would expect it to be a bit tricky in detail. What you describe works great with typical paths (bread-crumbs), but in this case your cells are much smaller (its your local direction after all).

[gab]

a short article showing one of flow fields short coming(at least in the supcom2 version) : http://www.rageeffect.com/post/982193331/supcom-2-flowfield-pathfinding

a video on crowd flow(not exactly flow field but also a "field" class pathfinding) :

and the associated paper : http://grail.cs.washington.edu/projects/crowd-flows/

i doubt it could be used with formations(well, with a little tweaking everythings possible...)but it is at least quitte new and efficient(5 fps for 10000 units without rendering) : would be great for isolated unit like peasants...

[madmax]

Well it seems units run away from the projected discomfort region in the video. Maybe surround the formation with a ring of discomfort ? And move this ring forward along the main path.

Lol !

So is this algorithm or an implementation publicly available ?

Edited April 7, 2013 by madmax

[gab]

just an algorithm(i may have missed the implementation but...)

(a unit could be heading not to it's final goal but to it's position in the moving formation...)