On Github: https://github.com/wraitii/0ad/tree/motionmanager
This implements (very naively) unit pushing each other when moving, instead of relying entirely on the short-range pathfinder for avoidance.
Design goals:
- Movement looks more natural in crowds.
- Fewer short path requests making the game faster in general (despite pushing taking some time to compute - I think it's an easy win overall).
- Less reliance on the short-pathfinder reducing the # of issues with it.
- Ideally be thread-able.
Conceptual drawbacks:
- Fundamentally might make it harder to avoid units "phasing" through each other.
- Fundamentally introduces more movement in units, which might look odd sometimes.
- Still needs the short range pathfinder to exist to get around some types of obstacle.
Open design questions:
- How much to push?
- Should some units be unpushable? Should enemy units be un-pushable?
Open implementation questions:
- How to know when we can't "push through" and need to trigger an "obstructed" call. It looks weird when ordering many units to clump together.
Implementation-wise, this has two main components:
- A unitMotionManager that splits unit Motion in phases, so that we can have a "middle" phase where units don't send messages and can be used for pushing safely and quickly.
- Actually pushing stuff.
My current implementation is braindead, and basically compares all units with all other units (once), essentially a n^2 algorithm. It remains pretty fast however. I think some subdivision will be necessary to avoid the n^2 exploding too much, but since the short-pathfinder is n^3+ we have a fairly good margin to work with.