Formation pathfinding [was: Analysing performance problems]

[WhiteTreePaladin]

I like using individual units, but it's a real mess during battles... I never use formations though, too much work.

[Mythos_Ruler]

battalions =

Yep, AOE fanatic here

LOL

I do think a "battalion" mindset should be the way to go as far as battles/formations are concerned. But when it comes to economics, then individual units are the way to go. And that's not to say it wouldn't be possible to fight without using battalions/formations, but you would be rewarded for using them.

I propose using a prominent hotkey, such as SPACE BAR, to form and break battalions easily and quickly. We can also put buttons for this purpose in the UI, but I personally would probably use a hotkey.

[Android_]

battalions =

Yep, AOE fanatic here

Same here haha. I think with a bit of creativity we could combine the two systems though. For example we could have individual units just like they are now, but every time they execute orders they receive as a group (so either by box-selection or by control groups) you could make them act like battalions (receiving certain bonuses, moving in special formations or whatever you have in mind). This could be indicated graphically also, for instance by an additional and funky selection circle around these groups. (These battalions could also stay together as long as the player doesn't sort individuals out. A minimum size for battalions of approx. 10 units would also seem reasonable.)

This way you'd always preserve control over individual units, but battalions would emerge quite frequently (as group orders are issued quite often). If the player has a preference for a specific group he can save it in a control group just like he can do now. What do you think?

(Even if you're not pleased by this outline I think we should look in the direction of integrated solutions; i.e. how to have battalions while maintaining maximum control).

[Pedro Falcão]

LOL

I do think a "battalion" mindset should be the way to go as far as battles/formations are concerned. But when it comes to economics, then individual units are the way to go. And that's not to say it wouldn't be possible to fight without using battalions/formations, but you would be rewarded for using them.

I propose using a prominent hotkey, such as SPACE BAR, to form and break battalions easily and quickly. We can also put buttons for this purpose in the UI, but I personally would probably use a hotkey.

Agreed i'd even suggest to think about a new feature to groups of control, they are very useful, but i think they could have some automation to prevent the boring and repetitive action of assigning units to a control group. I'd like for a control group to be refilled with that type of unit right when they are trained, for a sample.

[errt]

* 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 don't think formations should stop if there is an obstacle, as this would surely disappoint players who sent their formation in some direction and then went to another location and when returning have to find out that the formation only moved part of the way it was sent. It's not realistic either. They should change formation to something more appropriate to pass the obstacle (should be a column formation for most if not all situations) and then rearrange their initial formation after passing the obstacle. I can see a wedge formation approaching a small gap between two mountains: The first units will start to form a column, while the rest waits for them to pass the gap, then follow in column formation, too, while behind the gap the wedge form again from the units that already passed. Should not be too hard to implement, just give every formation type the abilty to move formation->column->formation and do a little work to identify obstacles before being too close.

[Chakakhan]

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

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?

The way AoEo handles this when attack moving is as follows: when a unit/building(s) come in their line of site they break out of formation (basic group movement formation) and attack them. If they are not in attack move then they will respond if attacked as well.

[Android_]

To add to my draft above, please take your time to study this piece of art haha:

[Ykkrosh]

How does this automatic battalion proposal (edit: Android_'s proposal in particular) differ from how the game currently works, where groups of units join together into a formation when you tell them to move?

[feneur]

I'm also mostly a fan of the way AoE does things =) But with this I'm definitely starting to lean more towards doing things like this: units are created as individual units (and in terms of promotion etc always are), when doing economic tasks they stay as individual units, even if you've given them a group order (perhaps even give them some "spread out" unitAI to avoid all gathering from the same tree etc, and more importantly to avoid having to individually order them to gather from individual trees, to avoid issues with units gathering in places where you really don't want them they should probably just spread out within LOS of the spot you initially ordered them to gather from).

When you want to move larger groups they get put into a column "formation", which is as thin as required depending on the obstacles and "snakes" around obstacles on the way. If they are attacked during the way they break out as individual units and respond (only if they are within LOS of the attack, if some units in the column aren't they just keep on walking, if they later come within LOS of the enemy - depending on stance and whether or not you're using attack move - they also respond to the attack).

True formations should only be used on the battle field (i.e. big open spaces), and be a "battalion". Their movement would be restricted (slow, takes time to turn around), but they would be greatly bonused in other ways. I'm thinking they should still keep individual experience (they might have been part of another formation earlier etc), but should probably lose hitpoints evenly. Or perhaps the formation could be split in a couple of areas for damage purposes? That way the direction you attack the formation would matter, but it wouldn't matter exactly which unit was hit. In fact you'd only be able to attack the formation as a whole/per section rather than individually.

If you want to get units back to economic purposes you'd turn off formations and perhaps also if you want to pursue fleeing enemy units (as most if not all formations should be slower than individual units moving around).

It would be really nice if it is possible to have the units automatically go back and forth between "proper" formation and a column for movement. That way it would be more likely for players to actually use them, while allow the game to benefit from the good things of using a column for movement. Not sure whether that's reasonably easy to do though

[Android_]

How does this automatic battalion proposal differ from how the game currently works, where groups of units join together into a formation when you tell them to move?

Sorry should have made this clearer . Well, the automatic battalions (red) benefit from any bonuses that make them meaningful formations as opposed to simple AoE-style groups (a key objective of 0AD if I understand it correctly): Think of graphical changes, like units moving and fighting in an actual phalanx for example, or of statistical advantages (higher HP etc.), special attack actions... you name it. Think of a Testudo for instance.

My idea is just a layout on how to make meaningful formations possible while keeping individual control.

[They] should probably lose hitpoints evenly

Well your concept would imply letting go of individual control, a sacrifice that 'Agers' are not willing to make ... Some nice ideas there though.

Edited December 4, 2011 by Android_

[Ykkrosh]

That sounds like it doesn't address the problem that started this thread, which is that it's too hard to have wide formations walking around the map. Groups need to be narrow flexible column formations (at least as narrow as the BFME hordes) so that pathfinding works sensibly, or else need to not depend on sensible pathfinding (e.g. by refusing to automatically route around complex obstructions while in large poorly-maneuverable formations), or some non-simultaneous mixture of those. I don't think automatically creating battalions from arbitrarily large selections of units could work, since it would either make a wide formation which would be unsuitable for moving around the map, or a narrow formation which would not be generally useful if it contains more than about 20 units.

[Mythos_Ruler]

I think Erik pretty much has the right idea going, except I don't think units in a formation should take damage evenly. This doesn't occur in Battle for Middle Earth 2, nor does it in Rome:Total War. Even with 5000 soldiers on the screen in a Total War game, each soldier still has individual stats (attack, defense, life points), except where fatigue, morale, movement, etc. are concerned.

I think generally, units should act as they do now as individuals, even when selected and tasked as a group, but if you want to really "group" them all together into a coherent unit, you can use Spacebar to auto-group the selected units into a battalion. Once in this battalion they get assigned the next free control group number and generally act as one entity as far as selection and movement are concerned. I also think manually putting a group of selected units into a formation auto-groups them into a battalion as well. Basically, any kind of input, whether clicking a formation button or using Spacebar, puts these units into a battalion that is selected by one click. The selection rings are even like in BfME2 where they merge to show you that they are indeed one battalion. Spacebar would also break up a selected battalion back into individual usable soldiers. A battalion sent to gather could either auto-break (while the soldiers retain their control group number) or still maintain their battalion features (group select and movement), but still spread out and gather as individuals. I think any group of units that is batch trained 20+ soldiers (or 10+ cav) should auto-group into a battalion. Things like this can help immensely.

This brings up the problem of grouping multiple types of units in one battalion, like say 10 archers, 5 hoplites, and 7 skirmishers. In this situation I think we should come up with some more custom formations like the 'Formation12' formation we have already in-game. Select half dozen battalions and click a battle line formation button that puts archers behind, pikes in front, cavalry on the wings (Call this an 'Alexandrian Battle Line'). We can have multiple versions of these too.

A couple more things:

-- I really hate how the "scatter" formation is currently working. Right now it's either useless or just plain broken.

-- I think column formation shouldn't even be a selectable formation. It's simply a formation that units default to when moving over long distances. Gives a speed bonus, but also an armour de-bonus.

As far as movement goes, I'd like to see a large formation of units just collapse down into a column to pass through an obstacle. I'm thinking some of this will need to be implemented and rigorously playtested at the implementation stage. Could it be possible for a large 50+ formation of soldiers to break up into multiple groups of columns to pass through multiple pathways around obstacles?

[WhiteTreePaladin]

I think any group of units that is batch trained 20+ soldiers (or 10+ cav) should auto-group into a battalion. Things like this can help immensely.

I think this is an excellent idea, although I would apply it to all batches.

[Mythos_Ruler]

Here, the soldiers would sidestep the obstacles while maintaining formation.

Obstacles bigger than this, the formation would fall into pathing groups and move around it. Though, now, we'll need some way for them to know that they'll meet back up together at an acceptable distance, or else they would just choose to fall into a snaking column to move around it.

[Android_]

That sounds like it doesn't address the problem that started this thread, which is that it's too hard to have wide formations walking around the map. Groups need to be narrow flexible column formations (at least as narrow as the BFME hordes) so that pathfinding works sensibly, or else need to not depend on sensible pathfinding (e.g. by refusing to automatically route around complex obstructions while in large poorly-maneuverable formations), or some non-simultaneous mixture of those. I don't think automatically creating battalions from arbitrarily large selections of units could work, since it would either make a wide formation which would be unsuitable for moving around the map, or a narrow formation which would not be generally useful if it contains more than about 20 units.

That's true I said nothing about pathfinding sorry. If I had to I'd probably go for a snake-y kind of movement though simply because it's probably easiest to implement. I think formations/battalions still need some fundamental debate as a whole though before advancing in their implementation, that's why I joined in. In the end pathfinding will depend on WFG's overall formation/battalion concept too I guess so maybe we should flesh that out first?

Michael the spacebar thingie is a neat idea although a solution that combines battalions with uncompromised Age-style control over individual units would be best . What do you think of my suggestions? If WFG decides not to try itself at such a compromise I'd go with your idea too though.

Edited December 4, 2011 by Android_

[historic_bruno]

One thing I hate about formations in most games I've played, there's no retreat feature! If you want to run away from a battle, you select all the units, and move them in the opposite direction, but because of how formations are arranged, units like archers are placed in back and right in the heat of the battle, making them very easy targets. Instead there should be a way to retreat, either orderly with the formation moving away backwards (at the cost of moving slower), or disorderly with every unit just running away as fast as they can with no organization.

[Mythos_Ruler]

One thing I hate about formations in most games I've played, there's no retreat feature! If you want to run away from a battle, you select all the units, and move them in the opposite direction, but because of how formations are arranged, units like archers are placed in back and right in the heat of the battle, making them very easy targets. Instead there should be a way to retreat, either orderly with the formation moving away backwards (at the cost of moving slower), or disorderly with every unit just running away as fast as they can with no organization.

You would still need to tell them which direction to "retreat."

[historic_bruno]

You would still need to tell them which direction to "retreat."

Right, and I wouldn't consider a high priority feature, but I'm sure we could come up with a hotkey for it

Edit: another thing, it should be possible to stop a formation's movement, in fact to stop any unit's current orders, to return it to the idle state, maybe with the ESC key and a UI button.

[historic_bruno]

What about siege units? They're bigger than human units and will have different attack behavior. How will they interact with formations? Treating them like human units taking up slots in the proposed "battle formations" doesn't sound appropriate at all.

[Mythos_Ruler]

What about siege units? They're bigger than human units and will have different attack behavior. How will they interact with formations? Treating them like human units taking up slots in the proposed "battle formations" doesn't sound appropriate at all.

probably treat them like in BfME2... as their own entities. Essentially they'd work like they do now. And we'd probably prevent them from joining a battalion with "meat" units. Reminds me, we need to stop rams from attacking meat units. They kill units with one blow. lol

[feneur]

Essentially they'd work like they do now.

(But preferably with some more space between them =) Right now they squish together/overlap a bit too much But yeah, I think they should be completely outside any formations in that sense. Perhaps if you select them together they'd move along behind the formation, either spread out behind it or in a line behind it depending on what space there is.)

[Mythos_Ruler]

(But preferably with some more space between them =) Right now they squish together/overlap a bit too much But yeah, I think they should be completely outside any formations in that sense. Perhaps if you select them together they'd move along behind the formation, either spread out behind it or in a line behind it depending on what space there is.)

Yeah, you could task them along with a formation of soldiers, but they wouldn't join the battalion.

[Ykkrosh]

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.

Thanks for the pointer. It seems to just be doing bog-standard A* over tiles (via engine/pathfinder/astar.cpp), and unit movement is constrained to tiles, and there's no special handling of group movement (the behaviour seems quite messy when you tell a large group to move to a point), so I don't think it helps here

[Badmadblacksad]

Hi. Here is a link to a video a game called Praetorians.

You can see how are their formations. No sure if it will be usefull, but it might give you some ideas. (I don't like the fact that their formations can overlap, but other than that I think its a pretty good system. Of course I also like our individual units. A combination of both system would be great imho.)

The great thing with their system is that they only need to do one long pathfinding for the entire formation. A player can not order a formation to go somewhere if there is not enough room for it there. The formation temporarily tightens (some units in the formation overlaps) if there is not enough room around it. There is also a "snake" effect in the curves. The formation size is limited (to 6*5 units). We can't see it in this video, but Praetorians formations can be splitted

Just to let you know what impressive work these Spanish guys did back in the day.

[Chakakhan]

Hi. Here is a link to a video a game called Praetorians. ...

Hi Martin, I remember that game! It looked fantastic at the time and I loved the way the camera view was zoomed so that you had a great overview of the battlefield. Most games kept the camera zoomed in pretty close in those days. I think It ended up dying because there was a multi-player exploit that ruined online play.

They took some obvious liberties to simplify their algorithm, such as units can pass through almost anything - including enemy units. I really didn't like it at first, but I did get used to it after a while. The units always ended up where I wanted them, even if they went through a forest to get there . I actually liked the way the game worked in the end. The question is would this method of pathfinding with all its short cuts been acceptable to the masses? Hard to tell because it died off so quickly. I did like the ability to hide units in the trees so that you could ambush troops walking by. That was also useful to hide some lone archers until the melee troops arrived.

I guess we have decided to implement the AoE style pathfinding in the game as it seems to be the one that irritates people the least. I think I prefer it to most, but that doesn't mean we shouldn't consider/discuss alternatives.