Group pathing

Our current pathfinding solution is inadequate – we do massive amounts of redundant work, our formations are messy and “string out” even when adequate space is available, and we block on things that are going to move out of the way.

This is my new plan, for handling a Move order – processed on the issuing client at UOG level (so the entire selection is available):

• Split selection into subgroups based on UMT, other caps, isolation. All units within a subgroup should be capable of following the same path, (whether they actually DO or not is irrelevant)

• For each subgroup, use connected-components to select a suitable actual destination point, and a source reference point relative to the subgroup’s current location.

• For each unit within the subgroup, translate the relative displacement from the group’s reference point to the group’s destination. If this point is unreachable, replace it via connected-components with a suitable point that is reachable.

• For each unit, label it with a tag for its subgroup.

• For each unit, compute a path to its personal destination point, ignoring for pathing purposes all units which have the same tag.

• On colliding with another unit, if it has the same tag, WAIT [up to some timeout, to eliminate the possibility of perpetual jams]. If the tag differs, REPATH.