I have been trying to move units in formation and facing an issue. I used to use NavMesh for the longest time however there was not much I could do with it because of certain known limitations so I decided to switch to A* Project.
I have my own formation tool where I can create the formation and move units to formation cells. It was a pretty easy process to switch from NavMesh to A* Project. The main reason why I switched was agents behaving erratically in crowded spaces. They stopped sometimes for no apparent reason, it was difficult to move them on uneven terrain and such.
So, I just made A* Project work however I am having trouble with units lagging behind, creating many paths and not pooling properly. I am using RichAI on Recast Graph (I changed the name to AIMovement since I will customize it a bit). In the video you can see the oscillating agents as well as the agents being pushed by others so they get away from thjeir next waypoint so they have to go back to it. How do you think I can make this more consistent and prevent all oscillation.
But only looking at this I think a good start would be to change how agents are assigned their destination.
At the moment each position in the formation is fixed to a certain agent, I think you’d already gain some visual improvements by allowing agents to change position within the formation.
In the last example of the video I’d espect the agent right bottom corner to also go to the most right bottom corner on the formation. Even though that was not his original position.
Ps. You recalculating the path every frame seems a bit overkill
So, I totally get your point with having the formation cell targeting be dynamic rather than fixed. That’s a good idea, I have been thinking how to do that and what is the logic behind it. Find the closest pair? Flip cell positions? I am not sure, what do you think is a good logic for it?
I am not actually calculating path every frame. I calculate path whenever there is a change in the position, it compares current cell position with delta position and if there is a change in the position I update the path. If I move the formation by dragging however, then yes, it does calculate it every frame since it changes the position thus changing the delta position. Please let me know if there is a better way to do it however.
I got really interested in this system you showed here and thought about how we could solve the issue you are facing. So I started working on my own formation system also to experiment around
Here is what I got working after a few hours:
As you can see the agent originally in the bottom right, would have walked to the most bottom position of the formation with your system.
I used some simple math to compare rotation of the entire formation, compare it to the original and assign new positions.
There is still a few bugs to work out, but it already proves to be a working system.
Also this example is running without the use of RVO. I wanted to make it look good without RVO before adding it. RVO should in my opinion be added complentary, not as a foundation for a system.
The optimal algorithm for this is called the Hungarian Algorithm. However if you have moderately sized groups then some faster approximation might be better since the hungarian algorithm is a bit slow.
I’ve added the Hungarian Algorithm to my formation manager with amazing results.
I would definitely chose for this approach if you were to do this yourself.
Here is my version in action:
Hey that looks great! I had to work on another tool yesterday, couldn’t reply. So in the game I am working units don’t need to keep changing platforms, they only change to specific, static formations rather than dynamic so I can flip the on X and Z axis to make them not cross each other at all now that I figured. I also fixed the units skipping their waypoint issue by enabling funnel modifier on RichAI. So far it looks good. Today I will test them attack enemies and see how it goes.
But if you can explain how I can implement the hungarian algorithm that would be nice. I am not sure how does one implement an algorithm like that, especially because I do not use matrix. I never used matrix and maybe it is a better approach.
