This is essentially Dijkstra's algorithm used a little bit creatively. The problem with that is that it is painfully sequential. I wonder if there is another algorithm that could build flow fields in parallel. In the perfect world - on a GPU.
Yes definitely, I've came across some people online who've taken this even further and implemented the flow fields in interesting ways - one such way is to break the world up into multiple flow fields and cache the results of them so that if some entities just need to pass through a flow field, you can just load the saved results.
Whoa I used to do some stuff with particle swarm optimization that superficially looks similar. The idea was to mimic how birds in flight move as a flock, but to add some variables to keep your particles from getting stuck. Different field, different purpose I know.
Can't wait for the next episodes! Is this usable in 3d-environment too? for example if you have a block and a ramp to get on top of the block (or ladders) the block would be impassable but after going along the ramp or ladders it would be passable.
Yes this is absolutely usable in 3D environments. In the case you described, one approach could be to have the edges of the block be impassible, but the full top as walkable - then your ramp/ladders could connect the ground to the top of the block. Depending on your game, you could even increase the cost of traversing on the ladders or ramps.
@@TurboMakesGames this sounds amazing! Can you elaborate (maybe on video) how you can make unpassable thin lines on the grid? Or is it even possible to do that (instead of whole gridblocks being taken)? Is it possible to make the character jump off the ledge but not on the ledge (one way gridblocks)?
Yeah definitely. The flow fields are cool because they are highly configurable to your needs and they can be combined with other pathfinding algorithms and other features can be dropped in. Once I've got the basics out there, I'm thinking I might do a follow up video going in to some of these additional configurations you can do 😊
Hey John, new to Unity! Found your vids, nice! Paused at the integration calc where you talk about adding the calculation algorithm as "adding to lists"... this reminded me of a more efficient "flood fill" algorithm... which I think from the sound of it would boost that speed. Be interested in hearing your thoughts.
Also, since the final flow matrix is a per pixel and neighbouring pixel... could we not antialiase the flow so instead of the adjacent pixel giving us 8 directions... we look 2 or 3 cells away... essentially antialiasing the flow... little more costly but would allow smoother flow angles.
Glad you've been enjoying the videos! The integration field is a bit more complex than a flood fill, because if a shorter path is found, then some values will need to be recalculated. Shaders are still a weak spot in development for me, but I would love to start learning more about GPU programming because I think there are a lot of good use cases for it - will definitely check out the GPU-FlowField! Yes, you can definitely get more "accurate" with your flow fields by looking at cells a few units a way. This is just a simple implementation of a flow field, but it can get much more complex from here 😊
Thanks for the positive feedback! The obstacle avoidance done here is based off the Flow Field, but the nice thing about this algorithm is that it can easily be combined with other pathfinding algorithms and concepts if your project requires them.
Ive started the journey to learn ECS, no navmesh, A* is aight, but was curious about how supcom 2 does it, several rabbit holes later I find "How to make flow fields specifically in Unity ECS". Lol, this could not have been more perfect.
Hah, glad you found what you were looking for. Actually there are a few navmesh pathfinding options in Unity ECS, though they are not completely stable/easy to use. Unity has a NavMeshQuery which is very low-level and complex - the user Forging Station has some videos on this. There is also a library on GitHub called DOTSNAV, which has some nice features, but is also limited to movement on a 2D plane and was a bit challenging for me to setup. The best one I've came across is a library from Reese (available on GitHub) and he's got a navigation library as well as a lightweight one that just does pathfinding - both use navmeshes and I was actually just using the navigation one in a project, I'll be talking more about it in my next video (should be out Monday!)
What happens if an object spawns into a section of the map where the destination can't be reached? Also, is it possible to use this in 3D when there are mountain slopes and overpasses?
If there was some terrain or objects blocking the path to a destination, then the flow field calculation would never touch those tiles, so in this case the units would just stay in place. Yes, this would definitely work for a 3D environment, then you could have the slope of the terrain add to the cost of traversal to adjacent tiles - i.e. steeper terrain would be more costly and likely avoided by units.
Hey, I have a simple question. Is this algorithm better when using multiple target points, or is it only better than traditional A* when using a single destination point? BTW, I recently discovered your channel, and I must say, you have excellent content!
Good question - this algorithm performs best when you have many agents that need to navigate to a single point. It still will work well if you have multiple destination points, but you will have to keep track of multiple flow fields to do this. If that is the case, then you just need to make sure you aren't recalculating a bunch of different flow fields at once as that is when you'll start to run into performance issues. Hope that helps!
Hi Turbo, first of all, thanks for the tut, it helps immensely. I had an idea and I wanted to ask you if it's feasible. when each point is being calculated for distance or cost in the integration phase, could you raycast each previous entry in the open list from the current tile to find the lowest cost tile within line of sight? The reason I ask is could you use that to direct agents from one tile to the lowest cost tile in sight instead of the previous low-cost tile to create a more direct path, in a way kind of smoothing out the map, or is this too costly?
That's a cool thought but I'm thinking that all those raycasts would be extremely costly. In my research I've came across some other ways so smooth out the map and you aren't limited in movement in just 8 directions. Hoping I can explore those concepts later 😊
@@TurboMakesGames Thanks for the reply, that sounds interesting, I'd love to see it if you ever get around to making a video on it. I have one other question - are all of those directions saved into an array or object and then given to all the directed gameobjects at once? so, for example, if you have two different groups given different objectives, is the 'map' of tiles attached to them? or the grid itself? sorry if I worded that badly
Nice! Flow Fields seem to fit with the DOTS framework really well. Interested to hear about how your differs from mine, but we'll get there in a few weeks 😉
To optimize Flow Field generation while also creating more of trail between two points.... Could you use A* to draw a path, then only create a .bestcost and .bestdirection a certain amount of cells perpendicular to the A* path? Im envisioning 10,000 or more boids traveling from point A to point B in the most performance friendly and organic looking way possible.
That makes sense to me. I'd just be extra cautious that you make your path wide enough so that one of the boids doesn't get knocked off the path and ends up not moving any further. Also just be certain that when widening the path, you don't create a path that could push some boids near the edges of the path right into a wall and get stuck
Hello, if the cost field were to change from an obstacle being destroyed or added would you need to recalculate the entire flow field or could you get away with just doing the area that changed and its surroundings?
Great question - yes, in this case you'd have to recalculate the whole cost field. Though if you were doing this for a much larger game world you could optimize by breaking your whole map up into chunks, then you'd only need to recalculate the flow field for that chunk. Lots of other benefits of chunking out the world too
good, great tutorial, thanks!!! question: when I make a RTS, this flow field should be created for each group of units that quests for path, so if the player select only one unit and put goal in map, the game need create an entire grid for that unit; if the player take for example 5 units, they need one grid to move, and so. is it correct? or there are another optimal form?
Yes, each group moving will need its own flow field. However the cost field will be the same for each of them. If you are struggling with performance, especially on larger maps, you could break up your flow field into sections and share portions of the flow field if groups are headed in similar directions, even if they have a different destination. This can get quite complicated though but there are some good resources online if you look around.
how can I improve the 8 direction to more precise, convert the integration field to the curved surface and calcute the each grid's minimum gradient? Is there any better way?
Haven't actually done this myself, but maybe a good solution would be to look at the cost of neighboring cells and the cells two or even three units away
I wish i knew the name of that algorithm 3 month ago, because i have researched almost the same one. I started with traditional A* and played with it over and over again, after all changes it become something similar to flowfield. I wasted sooooo much time on thing already existed :(
You didn't waste time, I'm sure you learned a ton of things during that process. Now you know two different pathfinding algorithms that solve different problems 😊
The flow field is based off of Dijkstra's algorithm - in Dijkstra's it is still focused on finding the best path from point A to point B; so it starts at point A then spiders out. Once point B is reached, the algorithm stops and it calculates the lowest cost path. In a flow field, it's kind of the opposite - it starts at the destination an spiders out from there visiting every single node on the grid. Once complete it has the shortest path from any given point on the grid to the destination.
I was just looking for a refresher on Flow Field Pathfinding and found this great video! 3 years old but still very useful!
When is that going to be added to the DOTS course? Very much looking forward to it :)
I cannot explain how happy i am that this video finally exists
So glad to hear this 😀😀
This is exactly what I've been looking for, I can't wait to see more. it will be very helpful
Awesome, glad to hear you are excited for this as well. Should be a fun series 😀
I was looking for a pathfinding algorithm tutorial for months, and now there it is.
Can't wait to see more...
Awesome, glad to hear you're excited as well 😀😀
This looks cool. I always find it interesting how game path finding works.
Absolutely, pathfinding is fun because there are so many different ways to do it to optimize for your own use cases.
Thanks, I programmed this into my game, lots of help : )
Awesome, glad you were able to implement this in your game!!
@@TurboMakesGames Thanks again, don't stop making great videos : )
Awesome vid, I've been thinking about using flow fields for my prototype. Cant wait for the others episodes.
Nice! I've been having fun playing around with Flow Fields over the past few weeks - think they are really useful for certain applications 😊
Great tutorial. Deffinitely looking forward to the next episode
Fantastic, glad you're ready!!
Thank you! I was looking for a long time. It's good that there is a translation, I understood almost everything.
Awesome, so glad to hear this!
The important thing in crowd navigation is local avoidance, not everyone's pathfinding. More explanation about ORCA or RVO is needed.
This is essentially Dijkstra's algorithm used a little bit creatively. The problem with that is that it is painfully sequential. I wonder if there is another algorithm that could build flow fields in parallel. In the perfect world - on a GPU.
Yes definitely, I've came across some people online who've taken this even further and implemented the flow fields in interesting ways - one such way is to break the world up into multiple flow fields and cache the results of them so that if some entities just need to pass through a flow field, you can just load the saved results.
That’s very good work man, very useful for my own project as well!
That's awesome to hear! Feel free to come share you project in our Discord community - tmg.dev/discord
Fantastic explanation, thanks a ton
Whoa I used to do some stuff with particle swarm optimization that superficially looks similar. The idea was to mimic how birds in flight move as a flock, but to add some variables to keep your particles from getting stuck. Different field, different purpose I know.
Oh nice, yeah if you want you could even combine this with a flocking algorithm to make the individual units appear to move a bit more naturally
Can't wait for the next episodes! Is this usable in 3d-environment too? for example if you have a block and a ramp to get on top of the block (or ladders) the block would be impassable but after going along the ramp or ladders it would be passable.
Yes this is absolutely usable in 3D environments. In the case you described, one approach could be to have the edges of the block be impassible, but the full top as walkable - then your ramp/ladders could connect the ground to the top of the block. Depending on your game, you could even increase the cost of traversing on the ladders or ramps.
@@TurboMakesGames this sounds amazing! Can you elaborate (maybe on video) how you can make unpassable thin lines on the grid? Or is it even possible to do that (instead of whole gridblocks being taken)? Is it possible to make the character jump off the ledge but not on the ledge (one way gridblocks)?
Yeah definitely. The flow fields are cool because they are highly configurable to your needs and they can be combined with other pathfinding algorithms and other features can be dropped in. Once I've got the basics out there, I'm thinking I might do a follow up video going in to some of these additional configurations you can do 😊
Excellent explanation here. Thanks for the video!
Fantastic, glad you found it useful 😀
Nice presentation!
Thanks! Glad it was helpful to you
Hey John, new to Unity! Found your vids, nice! Paused at the integration calc where you talk about adding the calculation algorithm as "adding to lists"... this reminded me of a more efficient "flood fill" algorithm... which I think from the sound of it would boost that speed. Be interested in hearing your thoughts.
Also... new to shaders... could a shader not also perform the same matrix calc... ? Ahh... turns out we can... look for GPU-FlowField
Also, since the final flow matrix is a per pixel and neighbouring pixel... could we not antialiase the flow so instead of the adjacent pixel giving us 8 directions... we look 2 or 3 cells away... essentially antialiasing the flow... little more costly but would allow smoother flow angles.
Glad you've been enjoying the videos! The integration field is a bit more complex than a flood fill, because if a shorter path is found, then some values will need to be recalculated. Shaders are still a weak spot in development for me, but I would love to start learning more about GPU programming because I think there are a lot of good use cases for it - will definitely check out the GPU-FlowField! Yes, you can definitely get more "accurate" with your flow fields by looking at cells a few units a way. This is just a simple implementation of a flow field, but it can get much more complex from here 😊
Cool explanation!
Glad you liked it!
Well explained! You should be a teacher!
Will you also discuss the obstacle avoidance within the units it self? That looks really cool!
Thanks for the positive feedback! The obstacle avoidance done here is based off the Flow Field, but the nice thing about this algorithm is that it can easily be combined with other pathfinding algorithms and concepts if your project requires them.
@@TurboMakesGames looking forward to it! I will try to combine the obstacles avoidance with the A* star pathfinding!
Ive started the journey to learn ECS, no navmesh, A* is aight, but was curious about how supcom 2 does it, several rabbit holes later I find "How to make flow fields specifically in Unity ECS". Lol, this could not have been more perfect.
Hah, glad you found what you were looking for. Actually there are a few navmesh pathfinding options in Unity ECS, though they are not completely stable/easy to use. Unity has a NavMeshQuery which is very low-level and complex - the user Forging Station has some videos on this. There is also a library on GitHub called DOTSNAV, which has some nice features, but is also limited to movement on a 2D plane and was a bit challenging for me to setup. The best one I've came across is a library from Reese (available on GitHub) and he's got a navigation library as well as a lightweight one that just does pathfinding - both use navmeshes and I was actually just using the navigation one in a project, I'll be talking more about it in my next video (should be out Monday!)
@@TurboMakesGames Thanks for all the additional resources. I've been on a ECS pathfinding binge this last week. I look forward to seeing that video.
Very helpful, Thank you for easy tutorial!
Glad to hear it helped you out!
What happens if an object spawns into a section of the map where the destination can't be reached? Also, is it possible to use this in 3D when there are mountain slopes and overpasses?
If there was some terrain or objects blocking the path to a destination, then the flow field calculation would never touch those tiles, so in this case the units would just stay in place. Yes, this would definitely work for a 3D environment, then you could have the slope of the terrain add to the cost of traversal to adjacent tiles - i.e. steeper terrain would be more costly and likely avoided by units.
@@TurboMakesGames awesome! Thanks!
really cool idea to implement it in both ways! What do you use for video editing?
Thanks! Should be interesting to compare the performance between the two. I use Adobe Premiere Pro for editing.
Thank you!
Sure thing!
You have a new subscriber, this looks really interesting
Awesome, glad to hear you like it! Welcome to the channel 😊
Your videos are great
Appreciate it, glad to hear you've been enjoying them 😊
Hey, I have a simple question. Is this algorithm better when using multiple target points, or is it only better than traditional A* when using a single destination point?
BTW, I recently discovered your channel, and I must say, you have excellent content!
Good question - this algorithm performs best when you have many agents that need to navigate to a single point. It still will work well if you have multiple destination points, but you will have to keep track of multiple flow fields to do this. If that is the case, then you just need to make sure you aren't recalculating a bunch of different flow fields at once as that is when you'll start to run into performance issues. Hope that helps!
Very good video
Appreciate it, glad you enjoyed 😀
Hi Turbo, first of all, thanks for the tut, it helps immensely. I had an idea and I wanted to ask you if it's feasible. when each point is being calculated for distance or cost in the integration phase, could you raycast each previous entry in the open list from the current tile to find the lowest cost tile within line of sight? The reason I ask is could you use that to direct agents from one tile to the lowest cost tile in sight instead of the previous low-cost tile to create a more direct path, in a way kind of smoothing out the map, or is this too costly?
That's a cool thought but I'm thinking that all those raycasts would be extremely costly. In my research I've came across some other ways so smooth out the map and you aren't limited in movement in just 8 directions. Hoping I can explore those concepts later 😊
@@TurboMakesGames Thanks for the reply, that sounds interesting, I'd love to see it if you ever get around to making a video on it. I have one other question - are all of those directions saved into an array or object and then given to all the directed gameobjects at once? so, for example, if you have two different groups given different objectives, is the 'map' of tiles attached to them? or the grid itself? sorry if I worded that badly
Recently I have implemented a flow filed using DOTS, I am curious what solution you have come up with.
Nice! Flow Fields seem to fit with the DOTS framework really well. Interested to hear about how your differs from mine, but we'll get there in a few weeks 😉
To optimize Flow Field generation while also creating more of trail between two points.... Could you use A* to draw a path, then only create a .bestcost and .bestdirection a certain amount of cells perpendicular to the A* path? Im envisioning 10,000 or more boids traveling from point A to point B in the most performance friendly and organic looking way possible.
That makes sense to me. I'd just be extra cautious that you make your path wide enough so that one of the boids doesn't get knocked off the path and ends up not moving any further. Also just be certain that when widening the path, you don't create a path that could push some boids near the edges of the path right into a wall and get stuck
Wou realy wonderfull.
Thank you! 😊
Hello, if the cost field were to change from an obstacle being destroyed or added would you need to recalculate the entire flow field or could you get away with just doing the area that changed and its surroundings?
Great question - yes, in this case you'd have to recalculate the whole cost field. Though if you were doing this for a much larger game world you could optimize by breaking your whole map up into chunks, then you'd only need to recalculate the flow field for that chunk. Lots of other benefits of chunking out the world too
good, great tutorial, thanks!!!
question:
when I make a RTS, this flow field should be created for each group of units that quests for path, so if the player select only one unit and put goal in map, the game need create an entire grid for that unit; if the player take for example 5 units, they need one grid to move, and so. is it correct? or there are another optimal form?
Yes, each group moving will need its own flow field. However the cost field will be the same for each of them. If you are struggling with performance, especially on larger maps, you could break up your flow field into sections and share portions of the flow field if groups are headed in similar directions, even if they have a different destination. This can get quite complicated though but there are some good resources online if you look around.
@@TurboMakesGames please share some link or example about pretreatment and portions, Im now just really struggle about performance problem
how can I improve the 8 direction to more precise, convert the integration field to the curved surface and calcute the each grid's minimum gradient? Is there any better way?
Haven't actually done this myself, but maybe a good solution would be to look at the cost of neighboring cells and the cells two or even three units away
I wish i knew the name of that algorithm 3 month ago, because i have researched almost the same one. I started with traditional A* and played with it over and over again, after all changes it become something similar to flowfield. I wasted sooooo much time on thing already existed :(
You didn't waste time, I'm sure you learned a ton of things during that process. Now you know two different pathfinding algorithms that solve different problems 😊
Hi sir,can you make video tutorial fluid simulation step by step?😇🙏
Cool, glad to know you'd be interested in something like that. Noted!
Is this dijkstra's algorithm, or is there something I'm missing that makes it different?
The flow field is based off of Dijkstra's algorithm - in Dijkstra's it is still focused on finding the best path from point A to point B; so it starts at point A then spiders out. Once point B is reached, the algorithm stops and it calculates the lowest cost path. In a flow field, it's kind of the opposite - it starts at the destination an spiders out from there visiting every single node on the grid. Once complete it has the shortest path from any given point on the grid to the destination.