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
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.
Not only that, but the AI can use flow graphs to avoid sending troops into areas where many have died previously and keep trying alternate routes into the player's bases etc. :)
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.
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.
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
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.
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.
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
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?
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.
Hi! Thank you for your comment, it really encourages to make more videos like that! As for your question, i did some experiment with the sobel operator in order to evaluate the local orientation of the gradient (here computed directly from the values of the "djikstra distance map") with atan2(G_y,G_x), but the results weren't convincing enough for my taste and the computing time was overkill for a fast pathfinding algorithm. The fact that the gradient we are looking for is the gradient of a distance map (from a point of the grid), is the main argument that allows me to use any decreasing function as the "kernel convolution operator", because it approximate the gradient orientation relatively well for this case. But I think I'm going to write a latex document on the subject for further explanation of the processes behind the algorithm and the intuition that led to such choices !
"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.
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)
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!
The target node needs to have distance to target marked as 0 and "visited" marked as "true" from the beginning of searching process. In the video, the target node distance to target is 2 because it thinks it has to go left and then right again to reach target (or similar back and forth movement).
Great explanation! Recently I've been working on a A* pathfinding algorithm and I can't see how calculating a vector field for all the tiles every time you search for a path is faster than A*. Because after making the map you still have to run some algorithm to get the optimal path, right? The vector field just makes it easier. Although I can see how it's useful for games like Age of Empires where units come spawn from the same place.
you could store the vector map for each item after computing. It will probably be a pain in terms of memory but as long as the map doesnt change often this should not be too expensive. At this point, you have a path drawn from every point in the map
Unwakable tiles are just simply not computed in the kernel convolution but after more investigation i found out that it's not the best option when you decrease your tile size. I will soon post a latex link in the description to give more explanation of the algorithm and give its full pseudocode.
When I implemented a version of this I simply used a very large number. In my case a map had 62500 points (250x250 grid) so I initialized all points to 90000 (arbitrarily chosen to be well above total nodes) Walls are always longer, even if the path hits every single node, which would mean no walls so an impossible scenario anyway. There are better ways but this is functional
Hi, thanks for your interest! As for your question, after creating a list that contains all the nodes of your grid (or tile if you prefer), when launching the djikstra algorithm (which pseudocode you can find here en.wikipedia.org/wiki/Dijkstra%27s_algorithm ), for each iteration over a tile of the open_list, this is when you mark the cell visited when looking at the neighbors of the current_tile.
This method should produce the same path as A*, or at least a very similar one, however for a static target and multiple entities using a vector field means you only need to run the search algorithm once and just have all entities access the vector field for pathfinding.
Indeed, like Matthew said, any algorithm like A* or BFS are suitable to compute the distance of each tile of the grid from the target tile. I like to use djisktra because of it's time complexity and simplicity.
@@matthewparker9276 , I mean we could just go through the graph using BFS starting from our destination without searching specific node, putting a pointer to the node we came into each current node. And when we need to find actual path, we could just use those pointers Am I missing something? Why do we need heat maps and calculating vectors, if we can just do this?
@@eugenekuzmenko4716 Well first, using pointers in BFS doesn't guarantee you that the path you found is the shortest path (thus not answering the requirement of a shortest path algorithm). However, if you take as your kernel convolution function the minimum value among the neighbor nodes (as shown in the optimization part of the video), it approach your idea of using BFS and pointers.
@@pdn-pasdenom4979 , I thought BFS would guarantie shortest path because in the you always advance one "layer" at the time, so resulting path takes few steps as possible
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.
Late, but at 3:09, is dist.n or selected node, one of the neighboring nodes? Or is it the selected node from open? Edit: Also, a, being distance between 2 nodes, is that corner nodes? So for example with Manhattan, 2, or distance from the current node, being 1 or 2 with Manhattan?
Don't understand +a part, i.e. is it the distance between the two tiles (based on the distance thing) or if for example, since I chose manhattan, would I add +1 or +2, or what?
Thanks for your comment. There are basically two ways to deal with walls: the first one (that i explain in the video) is simply to not acknowledge them by creating a dead-zone around them that will not be computed in the kernel convolution (if neighbor is a wall then skip to the next neighbor). Another way to counter this issue is to set as the distance from the target node of the wall, a big value like 10^6 for instance (this value should depend on the size of your tile relatively to the size of your screen or map) so that the arrow will point in the opposite direction of the wall. However this last method isn't the most relevant because it will fastly create weird behaviors in the movement of the entity that will follow the vectorfield. Other methods might exist to deal with this issue but i can't think of anything better.
If you want to calculate the best path for one agent, A* is clearly better (because the vector field algorithm already implent the Djikstra Algorithm, having almost the same time complexity as A*). However for multiple agents, the time complexity of the Vectorfield Algorithm becomes better than multiple A* for each agent.
@@pdn-pasdenom4979 if multiple objects trying find a path, they should generate a full map of directions for every object and keep it until the path is complete? I find it pretty heavy method comparing to a* processing faster (if path is possible) and returning only turning points as a path looks much more lighter. Maybe having colliding units and forced (by outer forces) movements makes it better. am i wrong?
@@nightyonetwothree Well it depends. First A* has a greater time complexity than the Djikstra algorithm because it uses a better heuristic which make the computation more complex. However you could, indeed, make a single A* pass on the grid (like we do here with the Djikstra Algorithm) and then, to find the path for each agent, look at each tile parent (meaning the neighbor with the smaller distance to the target node basically) : by following this "trail" you create a path. In this specific case, the vectorfield algorithm has a higher complexity than A* because of its additionnal layer of kernel convolution to compute the direction of each tile. Nevertheless, firstly their time complexity are comparable which doesn't disadvantages vectorfield that much and secondly (and for me the most important argument) the ouput path for each agent isn't optimal in terms of smoothness and ways to be aware of obstacles. The reason why vectorfield algorithm were invented was to make pathfinding on bigger map and greater number of agent simpler and faster to implement which it does ! Like I said in other comments, I'm still working on a web post to fully explain this algorithm (in term of complexity compared to other methods, its math regarding the optimal convergence of the paths, in which case it is relevant and how to optimize it when following a spec sheet).
The animation is nice, but your explanation that it's better for pathfinding is completely wrong. Dijkstra's Algorithm already gives the shortest path to any goal from any point and step 1 in this video is to generate the distances to the end goal - which you do via Dijkstra's. So you're already done. You already know all the shortest paths and which direction to go from any cell. There is no reason to do all the extra vector calculations.
It allows for more degrees of freedom and will smooth out the movement. This is especially noticable when crossing an open area, where the agent will move along a line towards the next corner instead of the next tile.
