Explaining Flow Fields

Came here to say the same thing. The demo made it look like cost was binary. If there was any cost at all, it was completely avoided. Jon touched on a point at the end that I was wondering about the entire time and I hope gets implemented, which was dynamically factoring in the time it takes to get from point A to B into the cost table.

I was also really surprised to hear Jon claiming that nobody on the stream "got" it. Of course people are going to ask how they plan to use the tech. To me, that says the people understand what it can do and now want to know how it will be used.

The problem was that many of the questions were about things that were only to demonstrate how the flow fields work rather than actual features for the game (like painting cost) and many others were based on incorrect assumptions about what flow fields actually do. I can understand Jon's frustration, I noticed one or two questions that were basically the equivalent of on a stream about rubber chickens asking why a rubber chicken plays StarCraft more than TA, when clearly a rubber chicken could not actually play any game let alone have any motivations for playing one more than another.

Yeah, I already understand that - I was explaining the process of how the flowfield is generated and specifically the end result more than how particular units follow them. Near the bottom of my original post I mention how each unit just follows the stream of virtual arrows. Whether or not each pixel actually holds a value to point in a direction, or if each unit independently looks at the surrounding pixels to find the highest value, I'm not sure.

I live watching the stream i had to watch it on YouTube archive I only play games and don't work with computers for a living and i think i understand it well enough.
I am actually very interested in what else they got planned for it that was hinted (i could of read to much between the lines in to it )

I thing you are mixing up the absolute cost map (for traversing a given point).
And the integerated or as i call it cummulative cost map.

i can't see your point, what we saw was the absolute cost map but the units of course choose their way based on cumulative cost. e.g. the cheapest way.

I know that he was drawing abstract cost on the map not 'difficult terrain' (which adds cost because it undesirably slows down units). I'm just saying that i get how it could be hard to understand as most people would assume that the fastest way is also the cheapest. (which it mostly is, or should be)

While this could be regarded as intuitively true, I think the whole point is exactly decoupling the two to extend the power of the flow fields to other possible gameplay mechanics.

Path finding is actually something that I do for work (not in the games industry) and I too am curious about the concave issue. It's essentially what he ran into when that unit got stuck actually, can be seen at http://youtu.be/5Qyl7h7D1Q8?t=31m42s , so it's obviously something they haven't gotten to dealing with yet. This is the downside you can encounter when you don't produce a global answer to the path finding problem and hope that local information will get you there. The cost field is the input to the algorithm, but as far as I can tell the algorithm itself is just a gradient solver. Essentially this approach can be really powerful, but it is exceptionally greedy. This sort of stuff can be dealt with to some degree with local heuristics (detect a U shape and fill it in for example), but as far as I know none of these approaches are perfect.

As another related question, I wonder if this technology would support the adding of value as well. I don't see why not, but I wonder if it's something they've thought of. I could see a force diverting slightly to take out a mining well for example (assuming they've been set to attack move and attack anything they get within weapons range of). This would increase the corner cases where the local information doesn't get you to a "good" global solution, but would add more depth and power to the path finding engine.

The A* provides a global solution so no issue there. The stuck issue wasn't that it's caused be something else.

Thank you for the response! You had mentioned the A*, but didn't explain too much what it was used for. From the way you mentioned it, it sounded like it was only used for inter-region pathing, are you also using it for intra-region pathing? If so, is there a gradient algorithm happening as well? Perhaps you are using some sort of gradient which saves more than one solution in places to produce possible paths to goal than using A* to pick among them? Also, let me take this opportunity to say that I think it is REALLY awesome that we can actually chat about this sort of stuff while it is being made. This is the side of video game engines that is really interesting to me, but normally isn't publicly talked about.

I can only agree. It would be really sad to see the technical bits disappear to be honest. Even if we don't get half of what is actually going on, we still get a lot of insight.

I wouldn't even be reading this forum if it wasn't for the technical bits we get to see every now and then.

Also I'm thrilled to see the interaction of units with different size and speed and turnrate in formations. I imagine after knowing the tech behind it I can probably spend a few hours just happily watching units execute my movecommands.

I think I know why the video caused issue.
Impassible terrain was red, and grey terrain had null cost. People may have been confused by the fact that green had more cost than the grey when they expected it to be low cost.
The alternate view where the cost increase was shown as different colours might have been a better choice as primary view.

The use of flow fields as opposed to traditional pathfinding opens interesting possibilities in strategy. Primarily that choke points could eventually end up ignored due to wreckage.

The confusion was probably more to do with how far out of the way the units went to avoid the added cost. This is simply a matter of tweaking though, and depends on what this "cost" actually represents in game (in the demo, it was arbitrary).

Also, flowfields only factor into wreckage fields if they don't completely block movement. If they do, it's no different to other pathfinding techniques in that regard.

i have one question regarding flow fields , how well does it work with unpathable locations, would the units path to the nearest point and then give up, or would it attempt to repath at that point? i only ask because using the field approach it never appears to solve the is there a path problem.

Hi miliascolds. I'm not an expert in flow fields, but I can help you with this.

You have to imagine the flow field as a sort of sea with somewhat unnatural flows of water in it. When a unit is in the middle of a plain with no obstacles, it is free to move wherever it want, for example going straight towards its target. When a unit approach an unpathable location, for example a building or another obstacle, than the flow gets stronger and stronger as the unit comes near to it, until the flow gets so strong (infinite force) that the unit has no choice but to circle around the obstacle.
For very large obstacles, like mountaing ranges or seas, they exert their strenght on a very large area of the field, so you units will start to deviate from a straight path from far away. There is even the possibility that the planet-level A* algorithm kicks in even before the flow fields are computed, and tells your units to go through a different region of the planet where there are no large obstacles.

Actually, what you see in the video is quite similar to the case of unpathable locations. The green cost areas painted on the world map are so intense that the units decide to take very long detours even when their target is quite near. A canyon in the middle of a plain will cause exactly the same behavior. For example in the video at 31m 40s you see land units moving around mountains that for them are unpassable.
The only case in wich the flow field will probably not solve the "is there a path" problem is if you use a debug mode, like the one Elijah is using, to spawn a unit in an unpathable position. In all the other cases the construction of the flow field will prevent units to reach unpathable positions starting from valid ones.

Unfortunately that is not true, especially for RTS games, because a user can trap a unit by building all around it, I also suspect that with transports you could transport a unit to an area that is cut off from another area, so the "is there a path" problem is quite a legitimate concern for the path finding, but I'm sure Uber will be able to handle it .

One way to solve the "is there a path?" problem is to send a sort of invisible dummy ahead of the unit, that will follow the flow field until it hits the end point. If the dummy fails to hit the target end point, then there is no path, and the unit doesn't move, instead of the likely alternative where it would attemp to patch and move, despite never reaching the target.

You wouldn't need to send a new dummy until the unit tries to path to a new location, or until a significant change adding new impassible areas (new buildings, etc) is added to the cost field. It's not so important if units get in the way, as they'll probably never make completely impassible areas, and even if new cost in a form of units or the such is added, it's not important for the unit to perfectly follow the dummy as it only exists to make sure the flowfield can lead to the end point.

more likely when the game builds the flow field for that area the unit would be left sitting on 'unpassable terrain' or some equivalent and pass that instead of moving off.