Hey guys,

I'm working on a game where you can control regiments consisting of several units similar to the Total War series. My problem is that I'm not satisfied with how these regiments reform when giving an order that requires rotation of the current formation. The way it is now is not game breaking but really not optimal. What I basically do is allow the unit that is furthest from the destination to pick its preferred spot. That would result in low cost solutions if it weren't for collision. It also just doesn't look right. Here is an image to illustrate an instance that I feel needs improvement.

As you see the unit in the front crosses the path of nearby units which causes collisions and delays. What I need is for units to not cross other's paths if it would cause complications. The problem is that similiar constellation need different solutions depending on unit positions. In this image we have two similiar constellations that need different solutions because otherwise there would be collisions.

In the first case you wouldn't want them to cross their paths because you might risk collision although that means a longer distance for the unit that is already behind. In the second case however you would want them cross their paths. There is no risk of collision as they are too far apart and you shorten the distance for the unit that is behind. They even have to cross paths because otherwise the unit that is behind would collide with the one in the front when trying to move past it on its way to its destination.

So what is the best way to guarantee a smooth flow of units without unnecessary path crossings? It works perfectly in the Total War games. I'd really like to know how to do it.

I'm pretty sure there are established solutions to this in the industry. I'm just too uneducated in programming to know them.

I actually have a slightly optimised version now. I added additional costs for moving orthogonally to the overall direction of the regiment and it seems to help but it's nowhere near what I'd like it to be.

I think the magic words here are "cooperative path finding"

eg http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf (a random entry I opened) but there is much much more

I don't know about documented approaches but it's often enough to apply an iterative improvement algorithm to these problems. e.g.

attempts = 20; // or whatever
while (attempts-- > 0)
{
    auto unit1 = pick_random_unit_from_formation();
    auto unit2 = pick_random_unit_from_formation();

    if (unit1 != unit2 && paths_cross(unit1.current_path, unit2.current_path))
    {
        swap_destinations(unit1, unit2);
    }
}

It's not optimal, but it is cheap, and often that is good enough.

I don't know about documented approaches but it's often enough to apply an iterative improvement algorithm to these problems. e.g.

attempts = 20; // or whatever
while (attempts-- > 0)
{
    auto unit1 = pick_random_unit_from_formation();
    auto unit2 = pick_random_unit_from_formation();

    if (unit1 != unit2 && paths_cross(unit1.current_path, unit2.current_path))
    {
        swap_destinations(unit1, unit2);
    }
}

It's not optimal, but it is cheap, and often that is good enough.

Unfortunately that doesn't work because it often makes units from back of the formation come to the front which results in a lot of collisions. Though I do use that method selectively.

My code works quite well now. What I do is calculate the distance for every possible assignement with orthogonal movement to the regiment direction being weighted more heavily. After that I check for units that are at about the same distance to the destination for crossings paths and also for units that are further apart for the before mentioned problem of units moving to the front. The result is often very good. But it's very patchworky and still not optimal.

I think the magic words here are "cooperative path finding"

eg http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf (a random entry I opened) but there is much much more

Thanks. I'll take look at that and try to implement it when I have the time. I'll post my results.

Thanks. I'll take look at that and try to implement it when I have the time. I'll post my results.

Like I said, there are lots of references on it.