Understanding Goal-Based Vector Field Pathfinding

I remember, many, many months ago we've had a webcast showing how pathfinding was implemented.
To be honest i had not caught everything. So for anyone interested in very simple/clear explanation & demo, here's a very good source (I'm not a specialist at all, but i got it all within a few minutes). And hopefully i'm not mistaking by assuming that "goal-based vector field pathfinding" is the same as "flow field pathfinding"
Read/watch it many times, think about it, match it with what you see in PA, and you will understand how it can be difficult to implement

http://gamedevelopment.tutsplus.com...-based-vector-field-pathfinding--gamedev-9007

It's not the same, not even remotely. But Uber devs are using the wrong term too, so what you dug up actually explains the right stuff.

The article explains it rather well, but Ubers current implementation takes it actually even one step further, since they extended the concept to a sparse octtree structure. Original approach with cube mapping caused nasty ... artifacts.

Flow fields differ fundamentally from that vector field path finding. A flow field expresses magnitude and direction of flow. It's not a map where to go, but a representation of the current state. Think of it more as a heat map of how much traffic there currently is in a specific region. Flow fields can be used to improve the vector fields for path finding by penalizing paths where the flow capacity has been exceeded, thereby increasing total flow by using additional pathways. That's also what the original research on flow fields in path finding was all about, but neither is Uber using any flow fields nor are they the same as what Uber refers to as "flow field".

Thanks a lot for this clarification abd additional information !

I dunno how much Elijah has changed with the pathfinding but If you want to have some sort of understanding of how the pathfinding works in Pa click the YouTube video below.



Pretty cool stuff!

Ah ok, having checked the link in my OP and then watching again Elijah explanation I understand better how it works. Now, there's something which is not clear to me : sparse octtree structure is supposed to solve artifacts involved by cube mapping. But i was thinking about this : Is the Vector field still using 2 dimentions for vectors ?
Or can it use 3 dimentions vectors so that in case sloaps are integrated in biomes, then units could path using the sloap ? In any case i daren't imagine the complexity of all this stuff. Very impressed. Making a such a game seems to be full time applied research job So considering all the inovations implemented in this game, i see Uber dev team much more as a true R&D team

thanks for re-posting the video

Ironically, this is the definition of vector. Though I understand that names don't necessarily relate to such things.

And @doud @Alpha2546 Cool stuff to keep at least somewhere in the forums!

Thought I'd poke my head out of the bat cave to say... lots of stuff has happened since that video posted.

In short, what you saw in the video above are 2d direction fields wrapped onto 3d geometry. Since then I've had to scrap that and go with integration across 3d voxels. Our flow / directional information now exists volumetrically across 3d space (when occupied by geometry).

I'll have to put together a more detailed post after the dust settles around here.

Hope this helps
Elijah

Would this mean units can path over CSG bridges or arches if we ever modded them in?

In craters as well I believe. That however requires terrain pathing to update on big events to terrain.

Craters are different because that is just going to change the shape of the surface. Arches and bridges add an additional path because you can still go under.

I know, but the vector field used for the path finding only consists of uniform vectors, so I thought that some clarification would be adequate for those not experienced with linear algebra.

Doesn't differ that much. In both cases, the path is 3D anyway. It actually is even if there are no craters or bridges at all. The actual traversable terrain consists of a lot of tiny, attached cubes with an edge length of 4 meters. Well, actually these cubes float in the air directly above(!) the pathable terrain and the unit is then pinned down onto the nearest bit of level geometry when following the found path.

So bridges and arches are already possible, even though with some limitations. It's e.g. not possible to express a height limit for a passage, so every passage must be huge enough for even the largest units to pass through.

Geometry updates when creating craters are a different thing though. It's a bit nasty to change geometry because there might still be data floating around which refers to the old state of the map and all of that has to be cleaned up, too.

Metal planets worked, if you remember. Of course, they also frequently glitched out. "I can go up but I can't go down! I can go down but I can't go up!" Probably an issue with sewing the fields together.

A more interesting application would be baising the pathfinding solution whenever an enemy unit wanders in, making units avoid its field of fire if they are not set to aggresive. Or the opposite if they are. Indeed, by having several vector fields that are added together, you could get apparently useful/intelligent behavior from the units quite cheaply computationally. This tech has a lot of possibility space to explore.