Hey everyone! Hope you found this video helpful, if you did I'd appreciate if you would share it with someone (or a group of people) who might find it helpful as well 😊 Of course if you run into any problems or have any questions, please let me know! Keep on creating 👊👊
Honestly? Never have watched a better explained algorithm on youtube. The way you go step by step, make everything simple, write actually optimised code with logical naming, makes learning this seem way to easy. Thank you very much for this video it's really heavily underrated in my opinion!
Also, good pace, for how you progress through the video, without going off on a tangent, without losing track of your explanations or stumbling with the words. I'd say you could describe your style of explanation as precise. From a mathematician and logic programmer, thats a big compliment. :)
You are impressively good at explaining these concepts. I think it has to do mostly with how you structure the videos, making concepts follow a logical order and build upon each other. Thanks for these videos.
@@TurboMakesGames I'm curious to see how performant it is in my current project. I tried Unitys NavMesh before, then I recreated the whole thing using A* path finding with ECS (way to complex for me atm) and now I found your approach. All good things come in threes I guess. I tagged you in my recent twitter post - A funny bug came up that stacks all the units. Cheers
Thank you! A well-explained, clearly laid out tutorial, it works perfectly. Looking forward to seeing more from you. Have to check out the ECS content you mentioned.
@@TurboMakesGames Hey Turbo, I have one question that I hope you could help me out with. I was wondering how the size and position of the flow field grid could be changed from code, depending on the surface I want to map it onto. So, for instance, if I have a plane that is positioned somewhere in the world (some x/y/z coordinate), and it's of a certain size, how would I modify your code to make the grid of the same size and positioned over the plane? I assume the CreateGrid function needs to be changed, but could you nudge me in the right direction?
Firstly, thank you for this great explanation! Really appreciate it as before I was using A* and had some performance problems. I've been trying to mess around with this and am new to Unity, but not to programming. My issue is with how my game is set up. I have a 3d space with a perspective camera at a 45 degree angle, like most RTS games, and for some reason the points on the grid don't ever have the correct values for where I click in the world. I've tried to change some values to Vector3, but that doesn't make sense since the grid needs to be an normal x,y graph representation. I'm not sure how to access the cell in a 3d x,y,z world with the Camera.main.ScreenToWorldPoint(mousePos) as the debug values I'm getting don't make any sense. I'm new to how Unity handles these things and have been trying to read through documentation, but am getting quite stumped with how this will work.
Glad you found this video helpful and you've implemented a flow field in your project! The thing with ScreenToWorldPoint is that it always goes at a fixed distance from the camera. One thing you might want to try is to do a Camera.ScreenPointToRay and then using the Ray you get from that in a Raycast - you can filter your Raycast so that it only collides with things on the grid layer so you can better access the grid cell you are clicking on. Hope that helps!
Very inspiring. I'm working on a way to make RTS unit groups havng that kind of behavior, and what you show here really helps me figure out where to start. Cheers mate
I have figured out how to make a flowfield work on one grid (as you do in your video). However, I never could figure out how to do multiple grids connected together. Do you know how to make multiple grids work with a flowfield properly? I would love to see a tutorial on that if possible. Thank you for your video!
There are many different approaches you can take and there are some articles out there where people talk about how they accomplished this - one way you could do is use an A* pathfinding across the multiple grids, then do flow field pathfinding inside each grid to move units to the next.
Hey again, I actually do have another question ... within your debug code you have a ClearCellDisplay() function ... is there something similar to delete / refresh the Handle.Label stuff which is showing the numbers of costfield and integration field? (I know its just a minor thing, but I cant find a solution - maybe because of my little knowledge ...) Thanks for your help!
Not quite sure what you're trying to do, but the Handles method lives in OnDrawGizmos() which updates every frame. Sounds like you might just be calling the handles.label function for both the costfield and the integration field. I have it setup in a switch statement so it will only display one or the other. Hope that helps, let me know if you still have any questions
@@TurboMakesGames so its done every frame and each frame is displaying a new refreshed version of the source-information (e.g. integrationfield)? hm ... then my source information must be bugged ... I have somehow several "0" values in my integration field (everytime I swipe/define a new destinationCell - the old destinationCells and respectivly their "0" value in the integrationfield wont get changed. I dont see why - and I guess you wont be available for a sharescreen? *smile*
Yeah I definitely think that would be a great use case for flow fields. This video is really just a basic implementation, but there are so many ways you can expand these to make them better for different situations.
@@TurboMakesGames It could be a great AI idea. The AI autonomously comes up with its waypoints. If you draw a line through the vector flows, each point of intersection becomes a waypoint.
I know it may happen really rarely in game situation, but anyway, it may happen that your "repeatable" breadth-first search implementation may run too slow, because you can visit same cell up to exponentially many times. If you want to avoid such rare occasions you should consider to use dijkstra instead.
another question popping up ... what if different units have different destinations - do I just recreate the integrationfield over and over again? or do I need to have several versions of the flowfield to have one integrationfield for each destination at the same time (e.g. hero moving to mouse-click-position ... but monsters moving to hero and not the mouse-click-position)? thanks!
Good question, and that is where you can start to get really complex with how you make these flow fields. Your cost field can be the same for each destination as that isn't changing (unless your terrain or obstacles in the world are changing) however you will need to calculate a new integration field and flow field for each destination. You can store these flow fields in a collection and have different untis reference different flow fields. You can even save these flow fields throughout the duration of the game, so you don't need to recalculate the flow field should you need to re-use a destination.
@@TurboMakesGames oh the part of storing and reusing sounds very interesting since in my case this is totaly valid but for a beginner like me ... how would you store it? can I have a List of flow fields? O.o
Note, if your downloading the code to have a quick play, you need to set the layers 8 to Impassible and layer 9 to RoughTerrain for it to calculate the costs
Hey there, thanks for your tutorial and example. I used the code to establish a flowfield with a costfield based on a texture map (where every cell represents one pixel). Now I want to "move" my map ... which is part of one game mechanic - but I am not sure how to move/update the flowfield to have it stay in place with my map. Is it the right way to actually move the flowfield or would you suggest to delete and recreate a new one? or should I create a flowfield which covers the total area of movement and only use it at the active part of my map? Not sure if flowfield is even ment to be moved since player unit and enemy unit positions are also connected to this?
short update ... I think I already found the way to manipulate the actual cells of my flowfields grid - but the debug view does not update could you point me in the right direction what I would have to do regarding the "OnDrawGizmos()" to also keep the displayed "WireCubes" of the debug up-to-date regarding their position? Thanks
I ve made mine in 2D, couldnt used boxOverlap so if anyone else looking for replace, I ve put Collider2D[] wallsColliders = Physics2D.OverlapCircleAll(cellCenter, cellRadius * .5f, wallFloor); instead Many thanks for the tutorial again, so helpful
How easy is it to add multiple destinations to a flowfield or to generate two flowfields for entities to use, one for reaching multiple destinations and one flowfield for returning to a set point/home location? Sorry im new to coding.
No need to apologize, that's a great question actually 😊 Wouldn't be too difficult actually, one approach would be to have a "cell values" struct that contains all the values like cost, best direction, etc. and have each cell have a list of cell values. Each time you generate a particular flow field, you'd set the cell values at the same index on each of the cells. Then when you move your objects around, they would just need to know the index of the particular flow field they are representing and can look up the values associated with that flow field - so when they are going to their destination they can reference one flow field and when they are returning home, they can reference the other. Hope that helps!!
I've spent the last two days playing around with this (most of the time spent debugging errors and googling solutions because I'm a coding noob). I've discovered that the Cost Field is the most 'costly' in terms of performance loss. I ran a timer between creating the flow, cost, integration fields to see how long they were taking to process. (FlowField is 100 * 100 in size) Create Flow Field: 0.002s Create Cost Field: 0.014s Create Integration Field: 0.004s Main Thread (Full Loop): 0.024s Seems Physics.OverlapBox is killing performance in the Cost Field. I decided to use BoxcastCommand to batch all the overlapbox's into a job (multi-threading?) to see if it helps. And it did. (FlowField is 100 * 100 in size) Create Flow Field: 0.002s Create Cost Field: 0.003s Create Integration Field: 0.003s Main Thread (Full Loop): 0.013s That's a 5x performance increase. However, that did not reflect on the overall performance which only increased by 2x (as seen with Main Thread times) when creating a new flow field every update (obviously you wouldn't do this in game, I'm just doing this for benchmark purposes). I thought combining the create flow field and create cost field into the one loop would help boost performance slightly but there was no performance benefits of doing this.
Used Gizmos to create a gradient field of all the cells bestCost instead of displaying the actual bestCost number (Link to image below). Gives a nice representation of the cost of each cell that is further away from the destination cell. The black squares are where the cell cost is byte.MaxValue (I created an if statement that sets the cell to that value when I click the right mouse button). imgur.com/IVzUjCa Will be working on this a little more to see if I can optimize it. I've been reading up on Compute Shaders recently. Might be useful for processing agents alongside DOTS (I haven't yet looked into agents yet but apart from collision avoidance hopefully shouldn't be too difficult to implement). I'm planning on using DOTS to efficiently loop through all the agents and use Computer Shaders to process their movement. Should hopefully see some impressive results, assuming I can get it to work.
Awesome to hear you've been doing more experimentation on your own with flow field pathfinding. Yes, the cost field is going to be the most costly part as that is where all the calculations are taking place. It is also the only step you can't multithread because it depends on and influences values of other cells throughout. I agree that the gradient visualization looks much better and is easier to get a sense of how the flow field is laid out. Great to hear that you want to implement this in DOTS as well. Would love to see your progress so feel free to share on our Discord community - tmg.dev/discord Cheers!
there is much better solution: just dont use collider detections in methods which used in update. Just use map grid with static values of static obstacles and terrain pathing and update it only if terrain changes/obstacles moved/destroyed etc. Separate map grid (which can contain other game-specific map-cells-logic) from flowfield's grids (which can still use data from map grid to get their cost right).
Would you like to talk about joints in ecs?i have seen some examples of joints in physics exampela from unity but it isn't any system of joint,only work arounds and bridging from mono to ecs(it isn't possible at this stage of ecs?)
Glad to know that you are interested in learning more about physics joints in ECS. I will definitely look into it and see what the different options are.
Its not working, I downloaded the project files and I also reassigned the layers but it they still don't path find also the grid doesn't show up in game view, maybe its an issue with new unity versions?
Thanks! Before you replace your current pathfinding, make sure that this will actually benefit your game. Flow Fields are good when you have many objects that need to navigate to one point, but it is going to be a bit slower than other pathfinding algorithms that specialize in finding the best path for one object to a destination (I talk about the benefits/use cases of the FF in the intro vid). Anyways I do hope you play around with them, they're a ton of fun 😊
It depends. If you only have a small number of objects that will move towards the player, then it probably wouldn't be the most efficient because you need to regenerate the integration field and flow field each time the player is above a new destination cell. That being said, it would still probably be your best option if you have many object that need to make their way to the player.
Good tutorial. Watching DOTS edition now. However, I think I'll give a try for a little other concept - instead of calculating costs like in A* to create flowfield, I wonder if I could divide such field of costs to "layers" (first for terrain costs, second for distance-to-target + danger-zones), and to get final flowfield I would need to sum values from all layers, analogical to merging layers in 2D graphics editor (Photoshop, Gimp). I've sketched two example scenarios on paper and it looks quite promising. Time to code :D
Hey great video! I am looking to do something like this for an rts. And so I am currently also looking into flow fields for the more complex scenarios: multiple destinations for same units & multiple destinations for different units; might be cool if you also consider having this cases in your project!
Glad you liked the video! If I do revisit the flow field series, I'd definitely want to explore more topics like this as there are so many cool things you can do with flow fields. If you look around online, you can come across some good resources that talk about how these things are implemented in flow fields or goal based vector fields.
Just throwing out ideas here as I haven't actually done this, but maybe you could have a "formation entity" that keeps track of the relative position of where each individual entity needs to be in the formation. The formation entity is the thing that follows the flow field and each of the individual entities use the position they are supposed to be at in the formation entity as a target so if they ever get bumped out of formation, they can work themselves back into the formation. Cool question though!
@@TurboMakesGames that makes sense. It would probably also make sense to have some sort of local avoidance capable of overriding the position within the formation, right? There's some nice examples in the second half of this clip: ruclips.net/video/iHuFCnYnP9A/видео.html
you went over the grid debug class quickly at around 7.13 how did you make it set so it drew the grid at this time. i have looked at the class however the end code of the grid debug class is mainly for the end? ++ thanks for this video it really helped w my TD game
Drawing the actual grid is done in the OnDrawGizmos() function in the GridDebug.cs script. There's a link to this script in the description of the video - again it's not the main focus of this video, which is why I didn't talk about it too much, but take a look at it and let me know if you still have any questions!
its still has the performance problem in building cost map, for loop neighbors for every single grid cost a lot while its a big map, maybe need some pretreatment like the theory paper, but there is not too much detail or example in paper. So Im confused now
Good videos. It does appear however that the standard approach to this flow field setup integrates a rather cpu intensive check against physics collisions, also, a check being repeated many times when it could be done just once. It would be a lot faster to parse the map beforehand, and find the cells which have an obstruction, done pretty much however you like, and maybe have this set up so that the addition of more objects which can provide collision responses, then this list of cells is recalculated, then during the management of the flow field, instead of checking against the physics, you instead check against a preset list of collidable positions which you then remove frm the flow field open list, before running any of the algorithm, and if you wanted to make this a little faster again you could even use a subset list of which column and row coordinates possess collisions, which means if you know that the x or y coordinate exists in a line where there are collidable objects, then you do the list comparison. The would mean you avoid all the physics overlap box checks that would happen during the algorithm's progress, and, have a chance to avoid any long list comparison by checking the x/y coordinates independently. The x/y co-ordinates being seperated would do best in applying an easy early out for those grid points for whom either x/y is unobstructed across the entire map, leading you to know that the grid being checked cannot be blocked.
Obviously the above comment is mostly aimed at large scale implementations of this algorithm, and as a further thought i thought you might be able to make use of a linked list arrangement. As you are using classes for the grid cells, this means you can pass around references, and, each cell can possess a reference to each adjacent cell. This means you could avoid any iterative processing of lists and arrays when requesting the adjacent cells.
Currently trying to think of a way to make the cells more persistent in the world, whilst also trying to keep it possible to maintain multiple sets of flow field data for different goal positions.
If you do happen to read these comments, i'd be interested to discuss the topic further - i've done ecs, and dots, in some cases it's cool, but mostly i use the burst compiler directly and offload the data processing into burst jobs, whilst using them to move and control the normal monobehaviour objects, as this means you dont lose the power of the original game creation pipeline. Yes the ecs setup renders much faster, so, using jobs and burst isnt as fast when considered to benchmark using simple systems and object counts, but, you also need to remember that sometimes the amount of processing per object is much higher, and this means the bottleneck of rendering is less of a worry, like when pathfinding is involved, and, that can be handled using direct graphics calls if desired. Jobs plus burst however is cleaner, it doesnt feel like you are beating your head against somebody else's ideas of how it should function.
The entities all appear to be avoiding each other although I couldn't see which part of the code controls that. Can you explain why they avoid each other?
It's not controlled by the code, they all just have Colliders and Rigidbodies attached to them, which has the benefit of them not overlapping each other.
@@TurboMakesGames Ok I see, but if you had a building on your map with a small door and they were in the building, I bet they'd have a lot of trouble getting out of there through the door?
To do that, you'd basically just need to calculate the flow field multiple times per destination. You can use the same cost field every time though. Then the units would just reference the flow field for the destination they are travelling to. Plus you could always pre-calculate a few common destinations and save the ones calculated at runtime
Coming a little bit late for this tutorial, great stuff, not the best explanation, you could loosen the voice a little - it was better sounding in the few "funny bits". But! The code also explains itself extremely well so thank you from the heart for sharing the code, because it is a lot of hard work. Subscribed and liked :)
Yes and no. It is basically a backward pathfinding algorithm, but one difference from A* is that all locations on the map are calculated - in A*, once the path is found, the program terminates even if not every location on the map had been visited.
@@TurboMakesGames I see as if you were to construct the path data and send them to each individual agent to follow (that's the A* version). Instead you leave it there so even if new agents are added you could use the previous calculation (which is really smarter and probably can't be done if you were to calculate from the agent).
I have Problems with importing the whole Project File because i wanna have the GridDebug File can u maybe also lin it seperatley, otherwise you make great tutorials? : )
You can unzip UnityPackage files to view their contents. But I've also added the GridDebug.cs file into the video description - pastebin.com/r6JDJbz9 Glad you've been liking the videos!
I did everything right all up to the integration field, that when I messed up, so I just downloaded the project files like a good boy! I just have a couple of questions regarding this: First: Is it possible to have the units not all bombard on the destination but stop a little bit back? Second: Is it possible to make smooth steering instead of just going in 8 directions? If so, how? Third: Is flowfield better than A* and Navmesh (Performance-wise, organisation wise, and difficulty) Final: Is it possible to have the nits updating their path if an obstacle has come in their way (while they're going to the destination)? Sorry if these questions are really basic but if I'm being honest, I am a complete nub. If anyone could help me I would be really grateful!
Glad to hear you downloaded the files and are experimenting with them - that's the best way to learn! 1. Yes, but it does require a bit more setup. This video from Code Monkey might be helpful for you: ruclips.net/video/mCIkCXz9mxI/видео.html 2. Yes, it does get a bit more difficult - you can find some good resources online if this is something you are really trying to do. 3. It all depends on what you are trying to do. Flow field is better for many units going to a single destination, while A* and NavMesh would be better for individual units going to a unique destination. In my intro to flow fields video I talk about this a bit. 4. Yes, in that case you would need to update the cost field with the new position of the obstacle and thus regenerate the integration field and flow field. All good questions!!
this is great and all, but i am having issues with my charactesr walking over walls. so trying to push them over when they can't collide with walls is driving me insane. lol. Ok so i figured it out. here's my code to have it move AROUND walls. if this makes sense. it's a npc not bunches of units collisionX = Physics2D.BoxCast(transform.position, boxCollider.size, 0f, new Vector2(moveDelta.x, 0), Mathf.Abs(moveDelta.x * Time.deltaTime), LayerMask.GetMask("Blocking")); if (collisionX.collider == null) { transform.Translate(moveDelta.x * Time.deltaTime, 0, 0); } else if (moveDelta.y == 0) { float y = cellBelow.worldPos.y - transform.position.y ; Debug.Log((y, cellBelow.worldPos.y, transform.position.y)); if (y < 0) { transform.Translate(0, -1 * Time.deltaTime, 0); } else if (y > 0) { transform.Translate(0, 1 * Time.deltaTime, 0); } } this way, if the cell it's in won't let my collision move up, it determines am i going right or left. and does the appropriate move
You can do that as well, you just need to manage breaking up your whole map into sub-grids. You can then do something like A* pathfinding to find the most efficient path between sub-grids to your destination then only run the flow field on the applicable sub-grids. Hope that helps!
![How to Use 2D Native Arrays for Use in Unity ECS - Flattening 2D Arrays [Old Version of ECS]](http://i.ytimg.com/vi/Mt4HmReBFsE/mqdefault.jpg)
![How to Use 2D Native Arrays for Use in Unity ECS - Flattening 2D Arrays [Old Version of ECS]](/img/tr.png)
Hey everyone! Hope you found this video helpful, if you did I'd appreciate if you would share it with someone (or a group of people) who might find it helpful as well 😊
Of course if you run into any problems or have any questions, please let me know! Keep on creating 👊👊
It's REALLY useful. It seems you're the only one on youtube even teaching this kind of pathfinding too.
Honestly?
Never have watched a better explained algorithm on youtube.
The way you go step by step, make everything simple, write actually optimised code with logical naming, makes learning this seem way to easy.
Thank you very much for this video it's really heavily underrated in my opinion!
Hey thank you so much for the high praise - so glad to hear this was helpful to you 😀
Also, good pace, for how you progress through the video, without going off on a tangent, without losing track of your explanations or stumbling with the words. I'd say you could describe your style of explanation as precise. From a mathematician and logic programmer, thats a big compliment. :)
You are impressively good at explaining these concepts. I think it has to do mostly with how you structure the videos, making concepts follow a logical order and build upon each other. Thanks for these videos.
Awesome, really appreciate the positive feedback on this 😊
Brilliant explanation and not just for Unity - this will work for any engine. Thank you a lot!
Glad it was helpful 😊
How does this only have 1200 views and 25 comments - amazing tutorial! Easy to understand and resources are provided. Subbed!
So glad you found this helpful 😀
@@TurboMakesGames I'm curious to see how performant it is in my current project. I tried Unitys NavMesh before, then I recreated the whole thing using A* path finding with ECS (way to complex for me atm) and now I found your approach. All good things come in threes I guess. I tagged you in my recent twitter post - A funny bug came up that stacks all the units. Cheers
holy smokess!! 25 minutes of goodness! Will watch this tonight!
Awesome, hope you enjoy 😀
Thanks!
Hey thank you so much for the support 😀
You are amazing Turbo !
Thanks haha!!
Thanks man for the great explanations was able to follow this through to make C++ version keep up the good work :D
Nice! Great to hear that you were able to get this working in C++ 😀 Best of luck with the rest of your project!
Great video! Do you think this is more expensive than normal pathfinding from Unity? Also, what about 3D levels?
Thank you! A well-explained, clearly laid out tutorial, it works perfectly. Looking forward to seeing more from you. Have to check out the ECS content you mentioned.
Awesome, glad this video helped you out! Hope you find the others valuable as well 😊
@@TurboMakesGames Hey Turbo, I have one question that I hope you could help me out with. I was wondering how the size and position of the flow field grid could be changed from code, depending on the surface I want to map it onto. So, for instance, if I have a plane that is positioned somewhere in the world (some x/y/z coordinate), and it's of a certain size, how would I modify your code to make the grid of the same size and positioned over the plane? I assume the CreateGrid function needs to be changed, but could you nudge me in the right direction?
Excellent video! What's the best practice for this now 4 years on?
?
Firstly, thank you for this great explanation! Really appreciate it as before I was using A* and had some performance problems. I've been trying to mess around with this and am new to Unity, but not to programming. My issue is with how my game is set up. I have a 3d space with a perspective camera at a 45 degree angle, like most RTS games, and for some reason the points on the grid don't ever have the correct values for where I click in the world. I've tried to change some values to Vector3, but that doesn't make sense since the grid needs to be an normal x,y graph representation. I'm not sure how to access the cell in a 3d x,y,z world with the Camera.main.ScreenToWorldPoint(mousePos) as the debug values I'm getting don't make any sense.
I'm new to how Unity handles these things and have been trying to read through documentation, but am getting quite stumped with how this will work.
Glad you found this video helpful and you've implemented a flow field in your project! The thing with ScreenToWorldPoint is that it always goes at a fixed distance from the camera. One thing you might want to try is to do a Camera.ScreenPointToRay and then using the Ray you get from that in a Raycast - you can filter your Raycast so that it only collides with things on the grid layer so you can better access the grid cell you are clicking on. Hope that helps!
Very inspiring. I'm working on a way to make RTS unit groups havng that kind of behavior, and what you show here really helps me figure out where to start.
Cheers mate
So glad to hear this helped out! This is perfect for something like an RTS game. Enjoy development!!
I have figured out how to make a flowfield work on one grid (as you do in your video). However, I never could figure out how to do multiple grids connected together. Do you know how to make multiple grids work with a flowfield properly? I would love to see a tutorial on that if possible. Thank you for your video!
There are many different approaches you can take and there are some articles out there where people talk about how they accomplished this - one way you could do is use an A* pathfinding across the multiple grids, then do flow field pathfinding inside each grid to move units to the next.
Hey again, I actually do have another question ... within your debug code you have a ClearCellDisplay() function ... is there something similar to delete / refresh the Handle.Label stuff which is showing the numbers of costfield and integration field? (I know its just a minor thing, but I cant find a solution - maybe because of my little knowledge ...) Thanks for your help!
Not quite sure what you're trying to do, but the Handles method lives in OnDrawGizmos() which updates every frame. Sounds like you might just be calling the handles.label function for both the costfield and the integration field. I have it setup in a switch statement so it will only display one or the other. Hope that helps, let me know if you still have any questions
@@TurboMakesGames so its done every frame and each frame is displaying a new refreshed version of the source-information (e.g. integrationfield)? hm ... then my source information must be bugged ... I have somehow several "0" values in my integration field (everytime I swipe/define a new destinationCell - the old destinationCells and respectivly their "0" value in the integrationfield wont get changed. I dont see why - and I guess you wont be available for a sharescreen? *smile*
Great video! This idea can be used to create Waypoints dynamically for self driving NPC cars or other object
Yeah I definitely think that would be a great use case for flow fields. This video is really just a basic implementation, but there are so many ways you can expand these to make them better for different situations.
@@TurboMakesGames It could be a great AI idea. The AI autonomously comes up with its waypoints. If you draw a line through the vector flows, each point of intersection becomes a waypoint.
I know it may happen really rarely in game situation, but anyway, it may happen that your "repeatable" breadth-first search implementation may run too slow, because you can visit same cell up to exponentially many times. If you want to avoid such rare occasions you should consider to use dijkstra instead.
Thanks for the tip!
another question popping up ... what if different units have different destinations - do I just recreate the integrationfield over and over again? or do I need to have several versions of the flowfield to have one integrationfield for each destination at the same time (e.g. hero moving to mouse-click-position ... but monsters moving to hero and not the mouse-click-position)?
thanks!
Good question, and that is where you can start to get really complex with how you make these flow fields. Your cost field can be the same for each destination as that isn't changing (unless your terrain or obstacles in the world are changing) however you will need to calculate a new integration field and flow field for each destination. You can store these flow fields in a collection and have different untis reference different flow fields. You can even save these flow fields throughout the duration of the game, so you don't need to recalculate the flow field should you need to re-use a destination.
@@TurboMakesGames oh the part of storing and reusing sounds very interesting since in my case this is totaly valid
but for a beginner like me ... how would you store it? can I have a List of flow fields? O.o
Note, if your downloading the code to have a quick play, you need to set the layers 8 to Impassible and layer 9 to RoughTerrain for it to calculate the costs
Yep, thanks for sharing! It's a bit annoying how Unity doesn't save tags/layers in Unity Packages
Oh man, thanks a lot
Would this be useful for a tower defense game?
Yes definitely - especially for something like Fieldrunners where there isn't a pre-defined path for units to follow
Hey there,
thanks for your tutorial and example. I used the code to establish a flowfield with a costfield based on a texture map (where every cell represents one pixel). Now I want to "move" my map ... which is part of one game mechanic - but I am not sure how to move/update the flowfield to have it stay in place with my map. Is it the right way to actually move the flowfield or would you suggest to delete and recreate a new one? or should I create a flowfield which covers the total area of movement and only use it at the active part of my map? Not sure if flowfield is even ment to be moved since player unit and enemy unit positions are also connected to this?
short update ...
I think I already found the way to manipulate the actual cells of my flowfields grid - but the debug view does not update
could you point me in the right direction what I would have to do regarding the "OnDrawGizmos()" to also keep the displayed "WireCubes" of the debug up-to-date regarding their position? Thanks
gridDebug.SetFlowField ... right?
next time I wont ask before testing some basics *smile*
Hey there, thanks for watching! Sounds like you were able to resolve the issues you were having, but let me know if anything else has come up since!
Truly awesome
I ve made mine in 2D, couldnt used boxOverlap so if anyone else looking for replace, I ve put
Collider2D[] wallsColliders = Physics2D.OverlapCircleAll(cellCenter, cellRadius * .5f, wallFloor);
instead
Many thanks for the tutorial again, so helpful
Thanks for sharing what you did! Glad the video helped you out 😊
How easy is it to add multiple destinations to a flowfield or to generate two flowfields for entities to use, one for reaching multiple destinations and one flowfield for returning to a set point/home location?
Sorry im new to coding.
No need to apologize, that's a great question actually 😊
Wouldn't be too difficult actually, one approach would be to have a "cell values" struct that contains all the values like cost, best direction, etc. and have each cell have a list of cell values. Each time you generate a particular flow field, you'd set the cell values at the same index on each of the cells. Then when you move your objects around, they would just need to know the index of the particular flow field they are representing and can look up the values associated with that flow field - so when they are going to their destination they can reference one flow field and when they are returning home, they can reference the other. Hope that helps!!
I've spent the last two days playing around with this (most of the time spent debugging errors and googling solutions because I'm a coding noob). I've discovered that the Cost Field is the most 'costly' in terms of performance loss. I ran a timer between creating the flow, cost, integration fields to see how long they were taking to process.
(FlowField is 100 * 100 in size)
Create Flow Field: 0.002s
Create Cost Field: 0.014s
Create Integration Field: 0.004s
Main Thread (Full Loop): 0.024s
Seems Physics.OverlapBox is killing performance in the Cost Field. I decided to use BoxcastCommand to batch all the overlapbox's into a job (multi-threading?) to see if it helps. And it did.
(FlowField is 100 * 100 in size)
Create Flow Field: 0.002s
Create Cost Field: 0.003s
Create Integration Field: 0.003s
Main Thread (Full Loop): 0.013s
That's a 5x performance increase. However, that did not reflect on the overall performance which only increased by 2x (as seen with Main Thread times) when creating a new flow field every update (obviously you wouldn't do this in game, I'm just doing this for benchmark purposes).
I thought combining the create flow field and create cost field into the one loop would help boost performance slightly but there was no performance benefits of doing this.
Used Gizmos to create a gradient field of all the cells bestCost instead of displaying the actual bestCost number (Link to image below). Gives a nice representation of the cost of each cell that is further away from the destination cell. The black squares are where the cell cost is byte.MaxValue (I created an if statement that sets the cell to that value when I click the right mouse button).
imgur.com/IVzUjCa
Will be working on this a little more to see if I can optimize it. I've been reading up on Compute Shaders recently. Might be useful for processing agents alongside DOTS (I haven't yet looked into agents yet but apart from collision avoidance hopefully shouldn't be too difficult to implement). I'm planning on using DOTS to efficiently loop through all the agents and use Computer Shaders to process their movement. Should hopefully see some impressive results, assuming I can get it to work.
Awesome to hear you've been doing more experimentation on your own with flow field pathfinding. Yes, the cost field is going to be the most costly part as that is where all the calculations are taking place. It is also the only step you can't multithread because it depends on and influences values of other cells throughout.
I agree that the gradient visualization looks much better and is easier to get a sense of how the flow field is laid out. Great to hear that you want to implement this in DOTS as well. Would love to see your progress so feel free to share on our Discord community - tmg.dev/discord
Cheers!
there is much better solution: just dont use collider detections in methods which used in update. Just use map grid with static values of static obstacles and terrain pathing and update it only if terrain changes/obstacles moved/destroyed etc. Separate map grid (which can contain other game-specific map-cells-logic) from flowfield's grids (which can still use data from map grid to get their cost right).
Would you like to talk about joints in ecs?i have seen some examples of joints in physics exampela from unity but it isn't any system of joint,only work arounds and bridging from mono to ecs(it isn't possible at this stage of ecs?)
Glad to know that you are interested in learning more about physics joints in ECS. I will definitely look into it and see what the different options are.
Its not working, I downloaded the project files and I also reassigned the layers but it they still don't path find also the grid doesn't show up in game view, maybe its an issue with new unity versions?
This is epic, I will definitely have to replace my current pathfinding with this one in the future.
Thanks! Before you replace your current pathfinding, make sure that this will actually benefit your game. Flow Fields are good when you have many objects that need to navigate to one point, but it is going to be a bit slower than other pathfinding algorithms that specialize in finding the best path for one object to a destination (I talk about the benefits/use cases of the FF in the intro vid). Anyways I do hope you play around with them, they're a ton of fun 😊
@@TurboMakesGames how good do you think it would be for finding the shortest path to a moving object e.g a player.
@@TurboMakesGames how good do you think it would be for finding the shortest path to a moving object e.g a player.
It depends. If you only have a small number of objects that will move towards the player, then it probably wouldn't be the most efficient because you need to regenerate the integration field and flow field each time the player is above a new destination cell. That being said, it would still probably be your best option if you have many object that need to make their way to the player.
Nice video Turbo :)
Would This be good for TD game?
Im trying to make and 3D version, but i need something to detect if user tries to Block path
Good tutorial. Watching DOTS edition now.
However, I think I'll give a try for a little other concept - instead of calculating costs like in A* to create flowfield, I wonder if I could divide such field of costs to "layers" (first for terrain costs, second for distance-to-target + danger-zones), and to get final flowfield I would need to sum values from all layers, analogical to merging layers in 2D graphics editor (Photoshop, Gimp). I've sketched two example scenarios on paper and it looks quite promising. Time to code :D
Sounds like a fun experiment! I'd love to hear about how it goes, feel free to share in our Discord community tmg.dev/Discord
Hey great video!
I am looking to do something like this for an rts. And so I am currently also looking into flow fields for the more complex scenarios: multiple destinations for same units & multiple destinations for different units; might be cool if you also consider having this cases in your project!
Glad you liked the video! If I do revisit the flow field series, I'd definitely want to explore more topics like this as there are so many cool things you can do with flow fields. If you look around online, you can come across some good resources that talk about how these things are implemented in flow fields or goal based vector fields.
Does this consider local avoidance?
how would you go about maintaining a formation while moving?
Just throwing out ideas here as I haven't actually done this, but maybe you could have a "formation entity" that keeps track of the relative position of where each individual entity needs to be in the formation. The formation entity is the thing that follows the flow field and each of the individual entities use the position they are supposed to be at in the formation entity as a target so if they ever get bumped out of formation, they can work themselves back into the formation. Cool question though!
@@TurboMakesGames that makes sense. It would probably also make sense to have some sort of local avoidance capable of overriding the position within the formation, right? There's some nice examples in the second half of this clip: ruclips.net/video/iHuFCnYnP9A/видео.html
@@yanhildebrand Yes, definitely think having some kind of local avoidance would be a good to have for that as well
you went over the grid debug class quickly at around 7.13 how did you make it set so it drew the grid at this time. i have looked at the class however the end code of the grid debug class is mainly for the end? ++ thanks for this video it really helped w my TD game
Drawing the actual grid is done in the OnDrawGizmos() function in the GridDebug.cs script. There's a link to this script in the description of the video - again it's not the main focus of this video, which is why I didn't talk about it too much, but take a look at it and let me know if you still have any questions!
its still has the performance problem in building cost map, for loop neighbors for every single grid cost a lot while its a big map, maybe need some pretreatment like the theory paper, but there is not too much detail or example in paper. So Im confused now
Another great tutorial with great explanation but I am unable to download the project files :(
Glad you found the video helpful. Just sent you an email with the updated link, thanks for letting me know 😊
Very interesting way to handle this. I wonder how you would do that with godot. Inspiring. Thanks!
Glad you enjoyed it! Should be pretty similar to this implementation on a theoretical level 😊
Good videos. It does appear however that the standard approach to this flow field setup integrates a rather cpu intensive check against physics collisions, also, a check being repeated many times when it could be done just once. It would be a lot faster to parse the map beforehand, and find the cells which have an obstruction, done pretty much however you like, and maybe have this set up so that the addition of more objects which can provide collision responses, then this list of cells is recalculated, then during the management of the flow field, instead of checking against the physics, you instead check against a preset list of collidable positions which you then remove frm the flow field open list, before running any of the algorithm, and if you wanted to make this a little faster again you could even use a subset list of which column and row coordinates possess collisions, which means if you know that the x or y coordinate exists in a line where there are collidable objects, then you do the list comparison. The would mean you avoid all the physics overlap box checks that would happen during the algorithm's progress, and, have a chance to avoid any long list comparison by checking the x/y coordinates independently. The x/y co-ordinates being seperated would do best in applying an easy early out for those grid points for whom either x/y is unobstructed across the entire map, leading you to know that the grid being checked cannot be blocked.
Obviously the above comment is mostly aimed at large scale implementations of this algorithm, and as a further thought i thought you might be able to make use of a linked list arrangement. As you are using classes for the grid cells, this means you can pass around references, and, each cell can possess a reference to each adjacent cell. This means you could avoid any iterative processing of lists and arrays when requesting the adjacent cells.
Currently trying to think of a way to make the cells more persistent in the world, whilst also trying to keep it possible to maintain multiple sets of flow field data for different goal positions.
If you do happen to read these comments, i'd be interested to discuss the topic further - i've done ecs, and dots, in some cases it's cool, but mostly i use the burst compiler directly and offload the data processing into burst jobs, whilst using them to move and control the normal monobehaviour objects, as this means you dont lose the power of the original game creation pipeline. Yes the ecs setup renders much faster, so, using jobs and burst isnt as fast when considered to benchmark using simple systems and object counts, but, you also need to remember that sometimes the amount of processing per object is much higher, and this means the bottleneck of rendering is less of a worry, like when pathfinding is involved, and, that can be handled using direct graphics calls if desired. Jobs plus burst however is cleaner, it doesnt feel like you are beating your head against somebody else's ideas of how it should function.
I understood nothing, but cool very nice.
😆😆Glad you enjoyed anyhow!!
The entities all appear to be avoiding each other although I couldn't see which part of the code controls that. Can you explain why they avoid each other?
It's not controlled by the code, they all just have Colliders and Rigidbodies attached to them, which has the benefit of them not overlapping each other.
@@TurboMakesGames Ok I see, but if you had a building on your map with a small door and they were in the building, I bet they'd have a lot of trouble getting out of there through the door?
how would one make this work for more then one destination?
To do that, you'd basically just need to calculate the flow field multiple times per destination. You can use the same cost field every time though. Then the units would just reference the flow field for the destination they are travelling to. Plus you could always pre-calculate a few common destinations and save the ones calculated at runtime
@@TurboMakesGames thank you :D
Coming a little bit late for this tutorial, great stuff, not the best explanation, you could loosen the voice a little - it was better sounding in the few "funny bits". But! The code also explains itself extremely well so thank you from the heart for sharing the code, because it is a lot of hard work. Subscribed and liked :)
Thanks for the feedback, always looking into how I can improve my videos! Glad to hear you found this video helpful 😀
My debug grid does not align with my (0,0,0) plane, can i make it so that the grid aligns with the plane like it did in the video?
You should just be able to add an offset to each of the vertices on the debug grid to get it to line up where you want
can we have a multiple destination in flow field ?
There are many ways to expand upon the basic flow field - this is one of them. Hopefully I can expand more on this soon
I see you basically makes A* for the destination instead of for the agent
Yes and no. It is basically a backward pathfinding algorithm, but one difference from A* is that all locations on the map are calculated - in A*, once the path is found, the program terminates even if not every location on the map had been visited.
@@TurboMakesGames I see as if you were to construct the path data and send them to each individual agent to follow (that's the A* version). Instead you leave it there so even if new agents are added you could use the previous calculation (which is really smarter and probably can't be done if you were to calculate from the agent).
Thank you so much!
Jesus is coming back, God bless all!
I have Problems with importing the whole Project File because i wanna have the GridDebug File can u maybe also lin it seperatley, otherwise you make great tutorials? : )
You can unzip UnityPackage files to view their contents. But I've also added the GridDebug.cs file into the video description - pastebin.com/r6JDJbz9
Glad you've been liking the videos!
@@TurboMakesGames Thanks man : )
I did everything right all up to the integration field, that when I messed up, so I just downloaded the project files like a good boy! I just have a couple of questions regarding this:
First: Is it possible to have the units not all bombard on the destination but stop a little bit back?
Second: Is it possible to make smooth steering instead of just going in 8 directions? If so, how?
Third: Is flowfield better than A* and Navmesh (Performance-wise, organisation wise, and difficulty)
Final: Is it possible to have the nits updating their path if an obstacle has come in their way (while they're going to the destination)?
Sorry if these questions are really basic but if I'm being honest, I am a complete nub. If anyone could help me I would be really grateful!
Glad to hear you downloaded the files and are experimenting with them - that's the best way to learn!
1. Yes, but it does require a bit more setup. This video from Code Monkey might be helpful for you: ruclips.net/video/mCIkCXz9mxI/видео.html
2. Yes, it does get a bit more difficult - you can find some good resources online if this is something you are really trying to do.
3. It all depends on what you are trying to do. Flow field is better for many units going to a single destination, while A* and NavMesh would be better for individual units going to a unique destination. In my intro to flow fields video I talk about this a bit.
4. Yes, in that case you would need to update the cost field with the new position of the obstacle and thus regenerate the integration field and flow field.
All good questions!!
@@TurboMakesGames Thanks!
Hi mate ,i need to know How much Cost 1 Game like TOP WAR To do,BUT WITH Big Change Upgrade ....Let me know in Privat,Tack CARE Mate Stay SAFE..
this is great and all, but i am having issues with my charactesr walking over walls. so trying to push them over when they can't collide with walls is driving me insane. lol.
Ok so i figured it out. here's my code to have it move AROUND walls. if this makes sense. it's a npc not bunches of units
collisionX = Physics2D.BoxCast(transform.position, boxCollider.size, 0f, new Vector2(moveDelta.x, 0),
Mathf.Abs(moveDelta.x * Time.deltaTime), LayerMask.GetMask("Blocking"));
if (collisionX.collider == null)
{
transform.Translate(moveDelta.x * Time.deltaTime, 0, 0);
}
else if (moveDelta.y == 0)
{
float y = cellBelow.worldPos.y - transform.position.y ;
Debug.Log((y, cellBelow.worldPos.y, transform.position.y));
if (y < 0)
{
transform.Translate(0, -1 * Time.deltaTime, 0);
}
else if (y > 0)
{
transform.Translate(0, 1 * Time.deltaTime, 0);
}
}
this way, if the cell it's in won't let my collision move up, it determines am i going right or left. and does the appropriate move
Great, thanks for sharing what worked for you!
Its not efecient to use if u have a large map
I want to calculate small portion of map instead of whole map
You can do that as well, you just need to manage breaking up your whole map into sub-grids. You can then do something like A* pathfinding to find the most efficient path between sub-grids to your destination then only run the flow field on the applicable sub-grids. Hope that helps!
>Shows a breakdown/pointers of the tutorial before starting
Based.