How do vector field Pathfinding algorithm work ?

In today's video, we will see how to create from scratch a vector field pathfinding algorithm.

Excuse all the english mistakes.

All the animations were made on after effect and premiere pro.

Pas De Nom 2020

[JohnnySix]

This is really cool, and presumably very efficient for having multiple enemies, as they can all reference the same navigation field, rather than having to calculate their own individual path using A* on a ode graph.

[tamago]

I made a crowd simulator during a 3 day coding project recently and also had the idea of generating a vector field 'map' by doing all the calculations at once in the beginning, so this was a very interesting watch. Comparing this video to my thought process (I knew and did no real research into this topic for the project), it's interesting that there are already established distance types for these sort of vector fields, I just used euclidian distance as it seemed most natural. I also didn't even think of doing a heat map and implementing vector kernel convolution, which restricted the final movement of each individual in the crowd to 8 directions. This is a much more flexible and generally smarter approach, and I'm kind of tempted to take another look at that project now after seeing this.

[uvata]

I advised my friend to use this with an added "compression" for a labyrinth-like game he is making. The compression is that I have algorithm that basically finds "portal" tiles that connect "hallway-only" tiles and he can pre-calculate this vector field for each map in that "how to get to each of the portals". That is we have portal count * n memory use need and portals are not many. Then non-portal tiles know a list of portal tiles and when pathfinding to the target we check this list and choose a random portal (also can be preprocessed to be the "closest" for this room btw, but game looks more fun if this is randomly chosen) and enemies start to follow the path towards the portal tile. After the portal tile is found, regular small A* or something else is done for the last few steps (but its not A* for my friend as previous steps make this step linear search and very fast in his own specific case). Basically in his case this means that O(n*P) time preprocessing is needed for all portals all arrows and O(1) for every enemy is the decision about where to go ALWAYS.

But in its raw form regular A* can be faster / it depends on how many units are pathfinding to the same target... so maybe in your cases also further optimizations are needed too.

[jbtjish]

100% gold mine, I've watched this video a lot of times, always give me something new. Maybe I'm a slow learner but it's so clear and precise that I can reference this anytime

[GlobusTheGreat]

Great production value on this video. Impressive!

[Oscar-vsyw]

very interesting! A precomputed path finding algorithm, I guess you can also use a 4d array to store all possible positions of goals too. Very interesting indeed

[gumbo]

This actually taught me a lot about pathfinding

[gutzimmumdo]

3:11 what do you mean by this "dist_n" and "dist_c" im talking about what do those things stand for exactly? the formula to get the distance?
like the tchevichev formula you plug the x, y coordinates and compare or what? how do you get those two things is what im asking.

[michaelchen]

There’s another distance where the ones in the cardinal directions are 10 and in the corners are 12. It more closely resembles the sqrt of 2 while still being whole numbers.

[SarovokTheFallen]

Thanks for the clear explanation, it was very good. Some questions I'm stuck with are: Goal Based Vector field looks just like Dijkstra for all points on the map, at 3:52 we talk about Already visited, if we already visited, isn't previous the distance inherently equal or shorter in all three variations (Manhattan, tchebychev, euclidian)? I don't think we need to validate more if the node has already been found?
When Calculating each point, if you store the point it came from you also already calculated the walking vector, so I don't see the need for Kernel Convolution, considering we had the green arrow already?

[ReubenAStern]

Very useful for figuring out my own path finding logic. I think some of the nodes in Unreal Engine blueprints could be used to make a more simple algorithm... in 3d space too.

[realdragon]

But isn't generating heatmap like a star pathfinding?

[RS-ekdr]

Wow, you saved me man. I am trying to make a game where group of enemies with colliders pathfind their way to the player, but there werent any good solutions for it. This algorithm seems perfect. Also if your agents have simulated friction, setting the friction of the agents zero kinda solves the getting stuck to a wall problem and getting stuck to each other problem. I will implement this so that every agent is effected by the force that corresponds to their position on the vectorfield grid. I hope it works. My only concern is map bottlenecks like bridges and doors.

[Waffle]

"Reduce our processing time overall"
Yeah hold on a second, very misleading statement. It can be faster in certain situations, there's a lot of situations where the calculation of the vectorfield is significantly slower than A*. Its a specialized tool not a one size fits all solution. You're running non trivial calculations on n^2 cells, that will get very expensive for large areas. However, where this technique really shines is when you need to pathfind for more than one AI "agent". Calculating the vectorfield may be expensive, but its cheaper than having 100s of AI agents calculating their own A* paths on the fly.

[oniontherock]

great video, but i cant seem to get the walls of a version im working on to work well, when a cell is close to a wall, it just gets completely repulsed by it, so even if the top row of a cells neighbors are all one's, just having one wall on it's left, will make it go right, which can lead to some really bad behavior (I.E, agents not being able to go through tight corridors)

[jamesbeilby]

Thanks for the video! Curious how did you come up with f(x) = 1/x for the kernel filter? Would Prewitt operator work here or it has some disadvantage?

[eugenekuzmenko]

Wouldn't breath first search produce the same results? Why do we need calculate vectors and distances?

[Sam_Control]

Which software did you use to create this presentation? It is truly fantastic. Thanks for this great video.

[ragnarodin]

what if i don't konw anything about the goal and the maze and i want to search the maze in real time ( only one path to search per search )

[zemanntill]

Hi, i think there might be a bug in your code, at 4:11 the nodes up and down from the target (middle) node have a distance of 2.
Anyways, this tutorial really helped for a project. Thank you! <:)