Formation pathfinding [was: Analysing performance problems]

[Ykkrosh]

Currently the game occasionally has terrible performance. I want to improve that, but first need to work out what situations are particularly problematic.

I tried a 20 minute qbot-vs-qbot match on Oasis II (in replay mode with no graphics), and got the profiler output here. With some extensions to the newer profiler it's possible to drill down into the data, which looks like this in the slowest sections. That indicates most time is in the long-range pathfinder ("ComputePath"), and the "steps: 40001" indicates that it's failing to find a path to the destination so it tries searching every reachable tile in the map before hitting the arbitrary limit of 40000 and giving up. I need to look into why it's unreachable - it could be that the destination is in the middle of a building, or maybe it's an unreachable resource or something. Then need to work out how to make it better.

[Ykkrosh]

I need to look into why it's unreachable

I looked. (Only tested in Firefox; won't work in all browsers.) (Red lines are expensive (unreachable destination) pathfind requests; cyan lines are cheap ones.)

That makes the problem fairly clear - a formation is circumnavigating the oasis, and the units on the right half of the formation think they ought to be standing in the water in order to match the formation, so they are repeatedly trying (and failing) to pathfind their way into it. New question: How should this be solved?

[Chakakhan]

Hi Philip, I did a little research on how formations work in AoM and AoEo (which are almost identical in the way they handle formations by the way). I am not suggesting this is the correct way, just want to bring it up for possible discussion seeing as these games both do some nice pathing stuff that feels right. So the following list indicates how both of these games handle formations:

1. Anytime you move one or more units they are automatically in formation. The melee up front, then ranged, with the squishies (healers, etc) in the middle.

2. Units in formation can pass through one another while they are getting into position in the formation.

3. Units do not wait until they are in formation to begin moving towards the destination. All units start heading towards the destination and gradually move into formation as they go.

4. There is no "wheeling" of the formation. The units re-position themselves when they make a 180 degree turn. They do NOT swap ends when they turn in place like our formation currently does (they simply turn around).

5. They break formation when they are in range of an enemy when on attack move. The melee engage with the ranged hanging back at their max range and firing from a distance.

6. Otherwise, they stop in formation when they reach the destination.

7. Formations are generally less wide when moving (they narrow down to several columns wide), thickening back up as they reach the location (this is more true in AoEo than AoM).

8. They break formation to path through locations that are too small for formation. Looks like the units individually path in this situation and can pass through each other while doing so.

9. Formations are somewhat malleable. If the formation moves up next to an obstacle the end of the formation "smashes" inward so that the formation can move by as intact as possible. In the case on the units on the oasis map, where they are between the trees and the water, both ends would shrink up to fit in between the trees and the water. In really tight situations see #8 above.

An improvement that AoEo makes on their formations is that units are some percentage (30-40%) smaller so the formations look tighter and take up a little less space. This ends up making them look and act a little better in most situations. Also AoEo recognizes a tight path sooner and starts thinning out the formation earlier than AoM, so there is a lot less thrashing in really tight spots.

Hope that is helpful, Cheers!

[Mythos_Ruler]

There are a lot of things I wished formations would do. For instance, the column formation should "snake" along its path rather than continually wheeling around in a desperate attempt to maintain a straight line. The wheeling around looks pretty bad and unnatural. Usually soldiers would just follow the leader. Perhaps this would help pathfinding? Because all you have to do is calculate the path for the dudes at the head of the column and those behind just follow that.

[fcxSanya]

<...> the "steps: 40001" indicates that it's failing to find a path to the destination so it tries searching every reachable tile in the map before hitting the arbitrary limit of 40000 and giving up.

I looked. (Only tested in Firefox; won't work in all browsers.) (Red lines are expensive (unreachable destination) pathfind requests; cyan lines are cheap ones.)

<...> the units on the right half of the formation think they ought to be standing in the water in order to match the formation, so they are repeatedly trying (and failing) to pathfind their way into it.

I think individual units when they are in the formation should not search the path on so long distances. This does not make sense even if they will be successful. For example if the formation moving along the wall (or some other relative thin obstruction) in one moment formation controller can order some unit to move in the other side of wall and the unit will find the path over half of the map. Can we just limit the pathfinding distance for units in the formation to some small area near the center of the formation?

[Ykkrosh]

Hi Philip, I did a little research on how formations work in AoM and AoEo (which are almost identical in the way they handle formations by the way).

Thanks for looking into this! Have you tried the config settings mentioned here? (I forget which file they go into; I think it was something a bit like startup/user.cfg on AoM; I have no idea if AoEO still supports this.) That might give some more indication of the internal workings in tricky situations.

An improvement that AoEo makes on their formations is that units are some percentage (30-40%) smaller so the formations look tighter and take up a little less space.

Making formations narrower seems like the easiest way to make them behave better. In this test with qbot it looks like the formations are 20x3 units, and I think it'll be pretty much impossible to make such wide formations work well in complex environments (with lakes and trees and hills etc) - they're just too unwieldy.

Assuming we want to include proper formations like in Rome Total War, rather than Age of *'s much smaller and less cohesive groups, I was thinking that maybe we should intentionally make them poorly maneuverable. That's the cost the player pays for formation combat bonuses: the formation can only march slowly over fairly clear ground, and will refuse to even attempt to walk through a forest or around a lake, but if you manage to get it into position then it's a very powerful force.

In that case, normal movement of groups of units would be more Age-like - smaller and narrower shapes (I think they supported at most 8 files and maybe 5 ranks? and in most cases it would switch to column shapes with maybe 4 files? and with no user-selectable formation types) which are therefore more maneuverable and flexible and can cope with walking through busy environments. We'd probably still want some improvements to the current pathfinder so it avoids sending the group through confined spaces, but much less major changes than trying to make it cope sensibly with massive formations.

the column formation should "snake" along its path rather than continually wheeling around in a desperate attempt to maintain a straight line.

Yeah, columns should definitely do that.

Usually soldiers would just follow the leader. Perhaps this would help pathfinding? Because all you have to do is calculate the path for the dudes at the head of the column and those behind just follow that.

That's close to what we do already - there's a single 'formation controller' which finds a path to the destination and walks along that path, and then every unit chases after that controller (plus an offset corresponding to their slot in the formation). (The formation controller is actually invisible and not a real unit, but it acts a lot like a real unit.)

I think individual units when they are in the formation should not search the path on so long distances. This does not make sense even if they will be successful. For example if the formation moving along the wall (or some other relative thin obstruction) in one moment formation controller can order some unit to move in the other side of wall and the unit will find the path over half of the map.

What if a player selects a group of units, half of which are standing just inside their city wall and half just outside, and tells them to move to the middle of the map? I think they'd expect all the selected units to obey the order, and the ones inside the wall should run around to the nearest gate and join up with the other units - it seems bad if half the units get stuck inside and will never come out because they're unwilling to look for long paths.

[quantumstate]

A few random ideas that I have had about this. As Mythos mentioned for his snaking idea it would be good for units to move relative to the surrounding units, I think it would be better to use all adjacent units rather than just the one in front though. This would require a notion of whether a unit is in formation or not since there is no point trying to follow adjacent units if the adjacent units aren't in formation.

An idea for efficiently determined possible positions for units is to use a range limited flood fill algorithm from the formation controllers position, then only allow units to be placed inside of this generated region, this will stop them trying to walk to the other side of a wall.

The hard thing seems to be working out how to rearrange the formation so it can fit through a gap. One idea is to take the flood filled map section, then calculate a vector of the direction of travel v, move along v in roughly cell sized steps and count the number of passable cells perpendicular to v, call this n_i. Take some typical minimum value of the n_i, e.g. average the 3 smallest to smooth things out a bit. Use this for your formations width. You could also use the counts to the left and right of v to roughly centre the formation.

I made a picture to make things clearer (hopefully). Black is a lake/wood/... Red hashing shows the area too far away from the formation controller for unit placement (generated by the flood fill).

[iap]

Hi, I have a suggestion that maybe can be applied here.

It's taken from the field of Flock simulation, where you have a simulation of lots of individuals following simple rules like "distance from the nearest neighbor" or "number of neighbors" to create a complex behavior.

To create a formation, while keeping all the flexibility of the troops, you can make them behave like a very strict flock.

Let me Explain:

Now, as you described, you have an invisible "leader" and all the others are following him "blindly" with the matrix that defines the distances and angles. But what if they will not follow blindly.

The matrix of the formation restrictions, instead of being definitions of locations, they should be "Optimal Places", and the troops will walk to these places, while keeping other restrictions, like distance from nearby troops and so on. The pathfinding should be applied individually to each troop, to walk to it's optimal place, and to the invisible leader to go to the desired location.

This way, any obstacle in the way will make all the troops to rearrange to fit, while keeping their desire to return as soon as possible to their "optimal place".

If, they're walking near water, the troops will make their best effort to keep the formation, because of the "optimal place", but will not drown because of the pathfinding algorithm that will keep them out.

If the leader is turning and walking in a non straight path, the troops will try to follow him as they can, and rearrange themselves to get to the best location near the "optimal place".

One last things:

The "places" can be configured for each formation if it's specific for a unit, or can take any unit. This way if they are "loose" fit, then when turning 180 degrees, will just make all the troops turn around, but if they are "strict", the entire formation will rearrange to the new direction.

Hope this gives you an idea. I'm sorry I can't aid by actual coding, I first have to understand how all the things fits together in this game (in the sense of the AI JS files)...

[Ykkrosh]

I experimented a little bit with flocking here a while ago. That doesn't use a static formation layout to determine each unit's target, though - they all target the same point, and the distance constraints make them prefer a square grid pattern around that target point.

I think the main problem I had was that it feels too springy - the units are meant to be intelligent humans, so it might look weird if they're sliding around and bouncing backwards and forwards, and I couldn't see an obvious way to avoid that.

Maybe it would be best to revisit this kind of approach, instead of doing everything with perfect geometrical shortest paths (like the current implementation and like the Age games). If the units target appropriate points in the formation layout, that should stop them springing outwards when reaching the destination and losing the central attractive force. Then maybe some tweaking of parameters, and/or some kind of smoothing filter on the positions of the units' graphical models, would make it look good enough?

Maybe I'll try playing around with my JS prototype a bit more to see if it can work better. (Other prototypes are also welcome )

[iap]

Hi, first af all, it looks cool

As you said, if not all of them will go to the same point, but rather go to the positions already calculated to them by the existing formations algorithms, then it will reduce bounciness.

And on the other hand, while not suitable for all purposes, I really like this kind of behavior, and you can fix it by adding a threshold that will stop the simulation when the micro motion gets to small...

[fcxSanya]

What if a player selects a group of units, half of which are standing just inside their city wall and half just outside, and tells them to move to the middle of the map? I think they'd expect all the selected units to obey the order, and the ones inside the wall should run around to the nearest gate and join up with the other units - it seems bad if half the units get stuck inside and will never come out because they're unwilling to look for long paths.

Units can check that they can reach the formation entity using the same limited pathfinder, if they can't - this means either their path blocked by something or they are too far away from the main part of the formation; in this case they can use individual pathfinder to approach the formation first.

[Ykkrosh]

I played a tiny bit with BFME2 for comparison. (Not tested it extensively so this may be wrong.) Units are naturally in groups (hordes?) with e.g. 20 members. You can't control individual members, only the whole group. When moving a group, it seems to do a usual A*-over-tile-grid style thing for a group leader (don't know if there's an actual leader unit or a virtual leader), and the members run around to stay roughly in the appropriate formation slot. Members never get split up: if the leader goes around the left of an obstacle, all the members will go to the left (even if going around the right would be straighter and shorter for them).

Units can (and usually do) walk straight through each other, including through enemies. If you send a group through a one-tile-wide gap, the units all squash up (and stand on top of each other) to fit through. If you select multiple groups and tell them to move, they seem to all find independent paths. Groups often don't go where you tell them to go - their target position seems to avoid getting too close to other groups or to obstructions (e.g. you can't make the group stop in the middle of a narrow gap, they'll always try to find a wider space).

I'm not quite sure how building placement works - it seems they're squares oriented at either 0 or 45 degrees (depending on building type), and usually (but not always) you can't put them close enough together to block units getting between them. The map design guide says you should avoid creating narrow gaps and mazes etc, because they confuse the pathfinder or cause poor performance.

Apparently there's some pathfinder exploits like clumping (normally only the front ranks can reach a target, but you can trick it into getting all the group's units into range), and people complain about the pathfinding being generally rubbish (although people complain about that in pretty much every RTS game ever made).

---

I think the problem with our currently implemented game design is that we let players make giant formations and then send them across the map and expect them to stay in that formation and move sensibly. That's never going to be possible (unless someone can provide a counterexample, e.g. a game that already does this nicely) - complex obstructions will always require a formation to break up because it just won't fit, and our maps have lots of complex obstructions (rocks, forests, valleys, bridges, etc). Currently they break up in messy inefficient ways, and we need to handle it in a more controlled way instead.

I think the following would be realistically implementable option (though still a bit vague):

* When doing normal movement of a group of units, they always adopt a narrow column formation. (No more than perhaps 3 tiles wide (4 infantry units, or fewer larger units), which avoids most of the nasty edge cases when pathfinding). Column formations move with snaking (each unit basically follows the footprints of the unit in front of it), so they can be arbitrarily long and can follow bendy paths with no problem. They can fit through 1-tile-wide gaps by squashing up a bit, so the pathfinder doesn't need to avoid those gaps (though it should prefer to stay a tile or two away from obstructions when it has the choice).

* When the group reaches its target, it'll spread out into a wider rough box shape if there's enough space to do so. (This would be a bit like what quantumstate suggested, searching sideways to find how much space is available, though only when stationary (which makes it a simpler problem since it doesn't interact with the pathfinder).)

* If the movement target is very close (like half a screen width) and reachable in pretty much a straight line (not blocked by a river etc), the units in the group might just run towards it individually instead of forming up into a column first.

* You can put a group of units into a battle formation (line, wedge, etc), which can be as large and as wide as we want to allow, and which provide combat bonuses. You can only do that if there's enough empty space for the formation. Battle formations don't do any pathfinding: they just turn to face the right direction and then head directly towards wherever you click. (You can shift-click waypoints if you want). If there are large obstacles in the way (larger than a lone tree), the formation will stop. The formation will persist until it's explicitly disbanded by the player, and you can't command an individual unit while it's in a formation. It's the player's responsibility to only activate battle formations when they are on an open battlefield and are willing to do more micromanagement of unit movement. It's the map designer's responsibility to ensure there are open battlefields where formations will be useful.

The important thing is that we can have either good pathfinding in complex environments, or large formations, but not both at once. Since we want both, there needs to be a switch between the good-pathfinding-but-very-simple-formation and complex-formation-but-no-pathfinding modes, then each mode can implemented and optimised and tweaked independently.

If there's no better option, I think the first steps in implementing this would be to focus on the non-battle-formation mode - remove the current formation buttons, implement usable columns for moving groups (including some minor pathfinder changes), and implement some spreading out at the destination. Battle formations can then be designed in more detail later.

[WhiteTreePaladin]

BFME2 hordes for the "good" civs are ten units. I think the "evil" ones are also ten. In BFME 1, the good hordes were 5 and the bad ones were 10. (I think there were a few exceptions.)

[Mythos_Ruler]

BFME2 hordes for the "good" civs are ten units. I think the "evil" ones are also ten. In BFME 1, the good hordes were 5 and the bad ones were 10. (I think there were a few exceptions.)

Pretty sure in BfME2 the battalions (of swordsmen, for example) are generally 15 units, 5 wide x 3 rows. I actually prefer the battalion system to separate soldiers, but no one else seems to (although this may be self-selected, since most of our fans were Age of Empires fanatics). Oh well.

[Shield Bearer]

Pretty sure in BfME2 the battalions (of swordsmen, for example) are generally 15 units, 5 wide x 3 rows. I actually prefer the battalion system to separate soldiers, but no one else seems to (although this may be self-selected, since most of our fans were Age of Empires fanatics). Oh well.

I'm with you on this, man. I would prefer it to. But only when they are in formation.

[Thorfinn the Shallow Minded]

I agree likewise.

[Yves]

I think the problem with our currently implemented game design is that we let players make giant formations and then send them across the map and expect them to stay in that formation and move sensibly. That's never going to be possible (unless someone can provide a counterexample, e.g. a game that already does this nicely) - complex obstructions will always require a formation to break up because it just won't fit, and our maps have lots of complex obstructions (rocks, forests, valleys, bridges, etc). Currently they break up in messy inefficient ways, and we need to handle it in a more controlled way instead.

I think the following would be realistically implementable option (though still a bit vague):

* When doing normal movement of a group of units, they always adopt a narrow column formation. (No more than perhaps 3 tiles wide (4 infantry units, or fewer larger units), which avoids most of the nasty edge cases when pathfinding). Column formations move with snaking (each unit basically follows the footprints of the unit in front of it), so they can be arbitrarily long and can follow bendy paths with no problem. They can fit through 1-tile-wide gaps by squashing up a bit, so the pathfinder doesn't need to avoid those gaps (though it should prefer to stay a tile or two away from obstructions when it has the choice).

* When the group reaches its target, it'll spread out into a wider rough box shape if there's enough space to do so. (This would be a bit like what quantumstate suggested, searching sideways to find how much space is available, though only when stationary (which makes it a simpler problem since it doesn't interact with the pathfinder).)

* If the movement target is very close (like half a screen width) and reachable in pretty much a straight line (not blocked by a river etc), the units in the group might just run towards it individually instead of forming up into a column first.

* You can put a group of units into a battle formation (line, wedge, etc), which can be as large and as wide as we want to allow, and which provide combat bonuses. You can only do that if there's enough empty space for the formation. Battle formations don't do any pathfinding: they just turn to face the right direction and then head directly towards wherever you click. (You can shift-click waypoints if you want). If there are large obstacles in the way (larger than a lone tree), the formation will stop. The formation will persist until it's explicitly disbanded by the player, and you can't command an individual unit while it's in a formation. It's the player's responsibility to only activate battle formations when they are on an open battlefield and are willing to do more micromanagement of unit movement. It's the map designer's responsibility to ensure there are open battlefields where formations will be useful.

I fully agree that we should have two separate modes as you described. First, movement of single units and groups of units and second, units grouped to formations and movement of formations. The tricky thing about gameplay will be how we present these differences, limitations and benefits to the player in a self-explanatory way.

Some basic thoughts about this:

* No single units can be selected in a formation

* Every formation has a leader who is visually identifiable (by carrying a flag, having some decoration on his helmet or whatever...)

* When forming up, there's some kind of progress-bar (on top of the leader?) and units won't attack or defend themselves until the progress is completed or aborted.

This could also be a button like for training units that monitors the progress...

* When a formation of units is selected, the cursor already indicates whether you can move the formation to a certain location or not.

* There's some sort of "glow" below the units for all the bonuses they get (like in BFME).

The tricky things are always the details and I think we need a clear design document about how this is intended to work.

Depending on the details, this could have other effects on gameplay.

One example (if there's a leader of formations):

Should the leader of a formation be chosen randomly? Should a hero or a unit of a certain rank be required for commanding the formation?

Can the player choose which unit is the leader? Does the leader give any special bonuses to his formation?

Such questions need to be answered and clear before any changes to the system take place, or there will be time wasted for changing things afterwards.

[quantumstate]

This generally sounds good to me. It seems like it would be fairly realistic as well as helping with the pathfinding.

I don't know the process for designing large features like this. Is there a large forum discussion which eventually gets put into a solid proposal or ...?

[Ykkrosh]

Pretty sure in BfME2 the battalions (of swordsmen, for example) are generally 15 units, 5 wide x 3 rows.

I checked again and it looks like the basic goblins are 5x4 with some jitter so they don't line up neatly, and the basic dwarves are 5x3 in neat rows. (I'm using the demo with skirmish maps for this.)

I actually prefer the battalion system to separate soldiers, but no one else seems to

I suppose it's more appropriate for games that focus more on combat than on economy (like BFME appears to). Seems tricky to e.g. combine it with the citizen-soldier concept - you probably don't want an entire battalion chasing after a chicken, so the units need to be controllable individually to let players allocate them to appropriate roles. But I suppose it's mostly a matter of taste, so we just have to pick one option and then do it as well as possible

The tricky thing about gameplay will be how we present these differences, limitations and benefits to the player in a self-explanatory way.

Yeah, designing the user interface is probably harder than actually implementing the algorithms. I think a common criticism of formations in RTS games is that they take more effort than they're worth - if you're micromanaging formation movement on a battlefield, it distracts you from developing your economy, so you might lose to an opponent who doesn't bother with tactics but can throw twice as many units at you. So it needs to be intuitive and easy to learn (else most players won't bother), and efficient to use (so experienced players can multitask while using it), and needs to give enough gameplay benefit (combat bonuses etc) to be worthwhile (but not so much that it's overpowered).

* No single units can be selected in a formation

That's what I'm thinking, like BFME or Rome Total War etc - you can only select the formation as a whole, and can only attack an enemy formation as a whole.

* When a formation of units is selected, the cursor already indicates whether you can move the formation to a certain location or not.

This seems important if we're effectively forcing the user to do pathfinding themselves. I imagine it could display the outline of the current formation, and the outline of where the formation will stop moving (either green where the cursor is pointing, or red where it would hit an obstruction and stop), either when clicking or just when moving the cursor around the screen, so you can see where it's safe to move.

One example (if there's a leader of formations):

Should the leader of a formation be chosen randomly? Should a hero or a unit of a certain rank be required for commanding the formation?

Can the player choose which unit is the leader? Does the leader give any special bonuses to his formation?

By the general principle of making it simple to learn and easy to use, I think leaders shouldn't exist (except perhaps as a purely graphical effect, like in RTW where an arbitrary surviving unit carries a flag which you can click to select the formation) - they would add more complexity and micromanagement, and would make formations usable in fewer cases, whereas we want people to use them more.

Hopefully most design questions can be answered by those principles and by technical feasibility. I'm not sure it's ideal to try to write down a fully detailed design in advance: the only way to see what gameplay works in practice is by playtesting, so we need a working prototype (with a willingness to change it later) before settling on a design; and with a relatively complex technical problem like pathfinding it's necessary to base the design on what is possible to implement efficiently, and we can't really know that until having tried implementing it. So I think in this case we need more of an iterative process to find something that works from both a technical perspective and from a gameplay perspective.

I don't know the process for designing large features like this. Is there a large forum discussion which eventually gets put into a solid proposal or ...?

I think the common approach is to discuss ideas on the forum until there's rough consensus on the basic concept, and then someone implements it and makes lots of minor design decisions themselves (or asks on the forums or IRC etc for input on those decisions), and then people test it and suggest changes or extensions. Then it's either good enough, or a year later we decide it's too broken and can see a better way of doing it and rewrite it, like in the current situation with formations

[Mythos_Ruler]

I checked again and it looks like the basic goblins are 5x4 with some jitter so they don't line up neatly, and the basic dwarves are 5x3 in neat rows. (I'm using the demo with skirmish maps for this.)

I would definitely like to see something like this (the jitter) with less disciplined troops, like skirmishers and such.

[Wijitmaker]

Good discussion, sorry if this has been brought up...

When the group reaches its target, it'll spread out into a wider rough box shape if there's enough space to do so.

What if the formation does not reach it's target, if it is confronted by an attack or comes to a unpassable object (wall/water/forrest), will it stay in column, or assume the designated formation?

[fabio]

I didn't follow all this thread, just want to let you know about the open source game BosWars: http://www.boswars.org/

IIRC it didn't have formations but I remember pathfinding was pretty fast, maybe there is something useful there.

[WhiteTreePaladin]

Pretty sure in BfME2 the battalions (of swordsmen, for example) are generally 15 units, 5 wide x 3 rows. I actually prefer the battalion system to separate soldiers, but no one else seems to (although this may be self-selected, since most of our fans were Age of Empires fanatics). Oh well.

I prefer battalions for actually fighting also. I think the reason selecting individual units is popular is because it makes custom scenarios easier (think RPG style). For actual fighting, individual units is a lot of micromanagement, so I actually prefer battalions. We could probably make it possible to place battalions and individual units in the editor and just make buildings train battalions. If someone wanted to train individual units, it would just be a simple mod to get it done.

As for 15 units for swordsmen - you may be right. I tend to only train archers though.

[edit] Battalions don't have to all be the same size.

[Mythos_Ruler]

[edit] Battalions don't have to all be the same size.

Right. Line infantry could have more (maybe 20-30), while skirmishers and cavalry battalions would have less. Persian battalions could have more, but individually be weaker, etc.

[Pureon]

I actually prefer the battalion system to separate soldiers, but no one else seems to (although this may be self-selected, since most of our fans were Age of Empires fanatics). Oh well.

battalions =

Yep, AOE fanatic here