Title is self explanatory.
But if you want and explanation as to why I did this
I initially wanted to create something for my game for the Infractions that will allow the player to control a large number of Units. I found that I will have to implement a pathfinding script but since I wanted to increase the number of units the player was able to control from 32 to 64 I thought what happens if I want to add even more. So I had the stupid idea to create some group pathfinding. I went down the rabbit hole and I ended up with this.
I decided instead of adding this to my game and calling it a Devlog I would make a separate post. Here it is. It took me around 2 Days to make. Code is mostly factorized it works pretty well and only sometimes ends up with the error script execution time exhausted
Steps:
- Poisson Disc Distribution. Create objects in grid
There are a few spots on the edges where the things don’t seem to line up.
The algorithm is able to compute a grid size of 1024 with a disc radius of ~7.07 with 1024 tries in around 4 seconds. So, I am happy with that. It may not be super fast. But for this case the time is fine.
-
Perlin noise. I use a threshold value of .1 to determine whether or not I place a value
Granted, I could have done this while generating points which would lessen the load, but I would like to keep the modules seperate for now.
-
Turn the field into grid and then detect obstacles in the grid.
I made a grid and also detected if a part was inside that grid.
I also spawned a target location and some agents to test with too. -
Pathfind from each spot to the target
If the spot is colliding with the obstacle or if there is not solution then the agents are ordered to stop.
You may have noticed already but once thing that does bug me is the fact that the default pathfinding fails when there are already agents. To be honest I should have used A* but I didn’t get around to doing it yet.
- Apply Velocity to agents that are in the flow field.
It isn’t perfect. But it can comfortably handle 300 Agents pathfinding. I feel like it can do a lot more if I actually wrote a proper A* Pathfinding script and actually refactored my code but for now that is it?
Maybe in the future
There are a few…noticable problems with the algorithm.