Formation pathfinding [was: Analysing performance problems]

[Ykkrosh]

I think my current uncertainty is caused by there being lots of different gameplay restrictions that will make things technically feasible, but not knowing what restrictions or combinations of restrictions would be acceptable from the gameplay perspective.

E.g.:

* Don't support formations at all. (By "formations" here I mean anything that involves a group of units acting as a coherent whole.)

* Let each unit split off and act independently whenever it wants to, instead of forcing them to stay in a formation/battalion/etc with other units.

* Restrict maximum formation size to maybe 6x5 units. (Any larger selections would consist of multiple formations that move independently.)

* Make the environment very simple; allow units to pass through trees, don't have any narrow chokepoints, enforce large gaps between buildings, etc.

* Allow units to pass freely through all friendly units and/or enemy units.

* Don't try too hard to make units go exactly where the player clicked.

Most open source RTS games don't seem to support formations at all - every unit moves individually to the target. AoM (and other Age games) lets units act independently (the formations are temporary and easily break up), and the maximum formation size is 6x5 (because you can only select 30 units), and units get blocked by everything (except other units in their own formation). Praetorians is apparently limited to 6x5 and units can walk through pretty much anything (including trees). BFME2 has similarly limited size and units can walk through friendly/enemy units. Rome Total War has very large formations which can walk straight through friendly units, and try to walk straight through enemy units (but get stopped when they hit them), and formations ignore trees (though individual units walk around them); the only semi-interesting pathfinding is inside cities, which have large gaps the formations can easily fit down.

I suppose the fundamental question (which I'm still totally unsure about) is: what are our goals for the gameplay? There's some basic things like "don't be irritating for most players" (which a lot of commercial games have failed at), but what else should we aim for? There's a thousand designs that would be technically feasible to implement decently (including the designs from any existing game we can test and clone, and a small proportion of novel designs), so I think we need a structured way to evaluate which would be a good fit for our game. Otherwise I think the danger is of just saying "I like X", "I can't implement X, what about Y", "I don't like Y, what about Z", ... and ending up with a dozen random ideas but never reaching a good solution.

The baseline for the current design is the Age games - what problems do they have that we'd like to improve on? Do we want formations to provide an extra layer of tactics to combat, because Age-style combat (throwing masses of units into a giant melee soup, as far as I'm aware) is too simplistic; or is Age-style combat fine, and we should avoid making it more complex? Do we want more or less micromanagement in combat? Do we want battles to be slower and more turtley, with a strong defensive formation able to block enemies at a chokepoint, or faster with enemies able to easily circumvent any defenders? Does supporting large numbers of units and/or large formations of units make the game better in some way, vs smaller (more easily controllable) armies? Do we want fancy formations so we're more historically accurate, or so we look cool, even if they don't improve gameplay?

I assume people will have differing opinions about all these concerns, but I think it would be valuable to sort out those differences now and come up with a coherent set of design priorities. Then it'll be possible to come up with specific design ideas and evaluate them more objectively from both technical and gameplay perspectives, and end up with a solution that's as good as it can be.

[plumo]

I would improve the AOE- design further. A melee soup is not what I'd prefer. MAybe for celts this is realistic, but I expect Hellenes and Romans to have formations. Woohoow new RTS feature invented: Civ-specific pathfinding.

[WhiteTreePaladin]

I never liked the mess that was an AoK battle. BFME2 handled it better, but it didn't have much of an economy. Economy seems to be the main thing against battalions.

[Mythos_Ruler]

Economy seems to be the main thing against battalions.

Only in our game, where soldiers and gatherers are one in the same. :/ The only reason BfME2's economic system was so dumbed down was because the game was designed for console, not PC.

[Mythos_Ruler]

30 unit selection seems so low. What about 40? I could see having a 40 unit selection, hitting the space bar, then they become one "entity" (i.e., battalion), then if you have multiple battalions you can select them (meaning you can actually select more than 40 soldiers this way). You can task battalions together, but they path separately. Or, if we have a larger unit selection, say 100, you can task them all to the same place, but they'll split up into multiple smaller groups (30/ 30/ 40?) for pathing.

[Android_]

I think Philip made an excellent point in his last post - 0AD doesn't have a clear idea yet on how formations and combat should look like. So it doesn't make sense to set the programmers off on formations when no minimum consensus on these issues has been reached yet. This is where the community and the game design department need to step in first, so it's good we're having this discussion now.

Now, to add my own ideas: In terms of pathfinding I guess we have to acknowledge the fact that no RTS yet has made it possible to command a single formation with 100+ units across the map without ignoring obstacles like trees, other units, etc as if they were ghosts. Considering that we don't want our units to do this I think Michael's proposol would be an excellent fix:

if we have a larger unit selection, say 100, you can task them all to the same place, but they'll split up into multiple smaller groups (30/ 30/ 40?) for pathing.

This is probably a very efficient and reasonable solution. The only alternative involving arbitrarily large groups of units that I can think of would be snake-like movement (possibly producing very large snakes). Snakes are more or less amorphous though so I can see big problems coming up in terms of when and how these snakes should regroup into formations.

Second, on formation combat: I think I made quite a good proposal on dynamic battalions that act as a whole (enabling advanced formation behaviour, like, for example, a Testudo) but do not cancel out individual unit command in this thread. Maybe you might want to discuss this. These battalions could enable advanced 'formation combat' (like a Testudo crashing into a Phalanx) as opposed to the AoE-style melee pool. [On a sidenote, we should really cut down the number of formations that are available to the player in order to make them meaningful alternatives (again as opposed to the senseless choice of formations that AoE offered/that 0AD offers now) and, probably even more important, not to overburden our programmers. I would be fine with, say, about two formation types per civ, as long as they are actually meaningful. Testudo and Phalanx are good examples of this.]

Edited December 6, 2011 by Android_

[Mythos_Ruler]

I could see battalions of 100 being possible, if they broke up into "companies" that attempt to maintain proximity while moving through and around obstacles. Over long distances the whole formation falls into a column and snakes to the destination.

[ribez]

another game to see his implementation of formation is Cossacks 2:

i've never played it, so i add it just for reference

OT: i like how units follow the road when there is one: probably there are heavy heavy modifier to choose the road instead the grassland

[Enrique]

Nice thoughts on this thread.

For pathfinding I think what Michael said sounds good.

I'd like to add my opinion about combat balance/design. I think not aimming towards a little battle management/tactics through bonuses on the formations (besides unit types forces/weaknesses) will hurt on gameplay side. E.g. in AOE, you can send the meat to do what they can on the "hot spot", and it's almost over. There is no sense of "if you know what you are doing on the battlefield", even a small group of soldiers can hurt badly a big bunch of soldiers that the player has sent with a rightclick to kill whatever they see and focus on another battle or resource gathering or wichever other task needed.

A little example of basic stances/formations. Each one may have different look for each civ for uniqueness touch.

-Charge/attack formation: to start the attack, if the enemies that are being attacked have not a "defense or wait for attack formation", they will have disadvantage, (surprise attack tactic)

-Defense/waiting incoming attack : slowest formation. Sending troops to travel large areas with this formation should take them forever.

-Travel formation : fastest formation, weakest formation....

¿resting formation? - ¿idle / default /gathering and construction formation? ¿maybe regenerates "stamina" for formations?

This is just an idea, it may be not too complex for the player but somewhat have a meaning on the battle to scratch some numbers to the enemy if you use them properly adding an extra layer of tactics .

[Mythos_Ruler]

Well, we generally already have formations decided. Some will have to have different behaviors, yeah, e.g. Phalanx will be slower than Line, and should only attack when tasked to do so. And there could be additional formations once you've selected multiple battalions. This could be context sensitive. Select one battalion, you get a battalion-level set of formations; select multiple battalions, you get army-level formations, we'll call "Battle Lines" for now. At any rate, if you have multiple battalions selected and task them over a long distance, they'll fall out of their battle line and form a column to move to their destination. If the battle line is too wide for them to form a column in a timely manner or without looking dumb, then they can form their own columns and march their own path to the destination and reform the battle line.

I think it would be useful to pathing to have specific instances where your units can just pass right through each other. One instance is shuttling resources back to the dropsite when gathering. Units should pass right through each other in this instance. Another is when forming up into the different formations. One thing I would like not to see is soldiers walking right through trees or right through enemy soldiers. When in a formation, perhaps the unit's actor can dither left or right around an obstacle like a tree.

Second, on formation combat: I think I made quite a good proposal on dynamic battalions that act as a whole (enabling advanced formation behaviour, like, for example, a Testudo) but do not cancel out individual unit command in this thread. Maybe you might want to discuss this. These battalions could enable advanced 'formation combat' (like a Testudo crashing into a Phalanx) as opposed to the AoE-style melee pool. [On a sidenote, we should really cut down the number of formations that are available to the player in order to make them meaningful alternatives (again as opposed to the senseless choice of formations that AoE offered/that 0AD offers now) and, probably even more important, not to overburden our programmers. I would be fine with, say, about two formation types per civ, as long as they are actually meaningful. Testudo and Phalanx are good examples of this.]

Thing is, I don't want to have to select a standard bearer dude in order to select the whole battalion. I want to select the whole battalion whenever I select any of the dudes within the battalion (e.g. Battle for Middle Earth 2). It would be easy enough to bind and unbind battalions with Space Bar. I do like the idea of cutting down the number of formations. One thing I would like to see is context sensitive stuff, like if you have a mixed formation, then there should be no reason to even show the cavalry-only formation buttons, only the ones you are able to use. Or if we want to show all the buttons, then hitting the wedge formation, for instance, will move the cavalry out of the mixed battalion into their own battalion utilizing the wedge formation. (Alternatively we can give Wedge to infantry too--they'd just form up behind the cavalry who will act like the "spear tip" of the wedge.)

Snakes are more or less amorphous though so I can see big problems coming up in terms of when and how these snakes should regroup into formations.

With the 100-member battalion example, I could see the front parts of the snake breaking off from the column and forming their formation as they approach the destination. They'd do this in clumps (or companies). What if this ginormous battalion gets attacked while half of it is still coming up in column formation and the forward half is formed up for battle? I could see these "companies" auto-forming their own battalions when they are attacked, 15-30 units at a time to deal with the attackers.

[Badmadblacksad]

Praetorians is apparently limited to 6x5 and units can walk through pretty much anything (including trees).

That statement is not fully accurate, in Praetorians some units cannot go into forest (mounted units (apart from some Barbarians ones) and pikemen), some other cannot walk in shallow water (heavy infantry like legionnaries).

I know nothing about BFME2, I will watch some videos.

I think that formation is the killing feature 0ad miss. Whatever we choose to do, we should do it well. IMHO having only the same system than AoE would be disappointing.

[Android_]

I could see battalions of 100 being possible, if they broke up into "companies" that attempt to maintain proximity while moving through and around obstacles. Over long distances the whole formation falls into a column and snakes to the destination.

For pathfinding I think what Michael said sounds good.

With the 100-member battalion example, I could see the front parts of the snake breaking off from the column and forming their formation as they approach the destination. They'd do this in clumps (or companies). What if this ginormous battalion gets attacked while half of it is still coming up in column formation and the forward half is formed up for battle? I could see these "companies" auto-forming their own battalions when they are attacked, 15-30 units at a time to deal with the attackers.

I agree that some sort of snake movement that can break up into small groups would be the best pathfinding solution gameplay-wise. As I said though, in practice it might remain a potential problem to decide on the exact circumstances in which the snake has to break up into groups (it would probably give us a lot of trial&error to do during development). Secondly I guess it is a lot harder to implement technically than just having large masses of units breaking up into groups of 30-40 from the start when being issued a command [a good temporary fix for now?]. I guess we need some expertise from our programmers here though to discuss these feasibility issues. Philip et al. ?

EDIT: Make large masses of units break down into groups of 40 that follow each other in a snake-like movement!!! Easy as that !

Thing is, I don't want to have to select a standard bearer dude in order to select the whole battalion. I want to select the whole battalion whenever I select any of the dudes within the battalion (e.g. Battle for Middle Earth 2). It would be easy enough to bind and unbind battalions with Space Bar.

I hate standard bearers too . Your space bar solution is preferable to them, it's also quite easy to handle, but I argue that it lacks control of the individual units. My proposal would be dynamic battalion creation that relies on box selection/control groups (keys 1-9) only: Have a look at my magnificent sketch again . (To paraphrase my sketch: In AoE, rudimentary formations form when a group of units is issued a command. In 0AD, I want meaningful formations to be formed when a group of units is issued a command; i.e. in the same automatic way but with actual gameplay impact. Example: Box-selection of a couple of Greek hoplites -> attack command issued -> hoplites use phalanx formation automatically while attacking. So quite simple really but very effective.) The advantages are:

- Battalions that can act as a whole (indicated in red).

- No sacrificing of individual control (a must for any Age gamer).

- Dynamic and 'on the spot' creation and dissolution of battalions.

- Consequently, formations will be used widely.

I do like the idea of cutting down the number of formations. One thing I would like to see is context sensitive stuff, like if you have a mixed formation, then there should be no reason to even show the cavalry-only formation buttons, only the ones you are able to use. Or if we want to show all the buttons, then hitting the wedge formation, for instance, will move the cavalry out of the mixed battalion into their own battalion utilizing the wedge formation. (Alternatively we can give Wedge to infantry too--they'd just form up behind the cavalry who will act like the "spear tip" of the wedge.)

Agreed: +1 for a context sensitive choice of formations.

I think it would be useful to pathing to have specific instances where your units can just pass right through each other. One instance is shuttling resources back to the dropsite when gathering. Units should pass right through each other in this instance. Another is when forming up into the different formations. One thing I would like not to see is soldiers walking right through trees or right through enemy soldiers. When in a formation, perhaps the unit's actor can dither left or right around an obstacle like a tree.

Agreed.

I think that formation is the killing feature 0ad miss. Whatever we choose to do, we should do it well. IMHO having only the same system than AoE would be disappointing.

Agreed! Formations are a good opportunity for 0AD to shine.

Edited December 7, 2011 by Android_

[feneur]

As per Philip's suggestion it's probably a good idea to try and figure out a bit more what exactly it is we want with the formations before we've spent several months just listing our ideas on formations and what they might be like.

I'm getting sleepy so I'm just going to copy Philip's questions and try and give my opinion on them, please feel free to fill in the blanks and add any additional aspects.

The baseline for the current design is the Age games - what problems do they have that we'd like to improve on?

The main thing is the one that's been frequently mentioned before: the moshpit fighting. So, regardless of exactly how we end up doing formations I believe this is one of the main things we shold avoid. I don't remember the formations giving much of a benefit/incentive to use anything other than the basic one, so that's another issue we should keep in mind.

Do we want formations to provide an extra layer of tactics to combat, because Age-style combat (throwing masses of units into a giant melee soup, as far as I'm aware) is too simplistic; or is Age-style combat fine, and we should avoid making it more complex?

Imho formations definitely should add an extra layer of tactics to combat. In the Age games it's generally more about producing troops and getting them to the battle field, and doing it more quickly than your enemy, than actually using your units in a good and effective way.

Do we want more or less micromanagement in combat? Do we want battles to be slower and more turtley, with a strong defensive formation able to block enemies at a chokepoint, or faster with enemies able to easily circumvent any defenders?

I would like both More fun micromanagement and less boring. Seriously though, this is partly why I suggested doing something like having the battalion/formation divided into sections/sides. Now I never learned too much about the micromanagement in the Age games as I mostly played against the default AIs, but to me it's a bit tedious gaining a slight benefit from things like having all/many archers aiming at the same enemy unit. To some extent my answer is similar to the second question: I think having formations that actually block enemy movement effectively is one of the things that would help making them useful/fun. That way they would actually be useful compared to just units standing there in some random order. On the other hand I think they should not block too much, because that would rule out flanking/attacking from the rear etc which would help make eg the horse units useful in a way they aren't now.

In fact, one of the major reasons why I think we should have useful formations in general, regardless of exactly how we implement them/what they do, is to give some benefit/use to melee units. Currently ranged units are way more useful. I guess the alternative would be to make ranged units less useful (i.e. less accurate, doing less damage etc), but having units being less useful sounds like less fun. At least above a certain level of balancing.

Does supporting large numbers of units and/or large formations of units make the game better in some way, vs smaller (more easily controllable) armies? Do we want fancy formations so we're more historically accurate, or so we look cool, even if they don't improve gameplay?

In general I think large formations doesn't add much more than coolness/looks, but they do offer a value in the sense that they would for example block off larger areas. But that probably just means relatively large and not insanely large =)

[Android_]

Actually, in one sentence, I'd like 0AD formations to work exactly like the Age formations, with the decisive difference that the term 'formation' implies more than units just walking in line and instead having formations that actually do something (visually forming a phalanx; recieving bonuses, blocking other units' way as Erik just said, etc.).

_{In terms of pathfinding see my last post.}

Edited December 7, 2011 by Android_

[Mythos_Ruler]

but I argue that it lacks control of the individual units

The point of putting a bunch of units into a battalion/formation is so they act as one and you control them as one.

[WhiteTreePaladin]

Yeah, it's not for appearance, it's for control. Group selection is much easier to manage, but it's too much effort to manually make groups. Individual selection is nice, but not so much in the middle of battle. It's kind of like renewable resources; they're a neat idea, but really just make things more complicated rather than fun.

[Android_]

The point of putting a bunch of units into a battalion/formation is so they act as one and you control them as one.

Yeah, it's not for appearance, it's for control. Group selection is much easier to manage, but it's too much effort to manually make groups. Individual selection is nice, but not so much in the middle of battle.

It is in fact harder to manage because you have to manually make+break formations (e.g. using the space bar) instead of just box-selecting units. So having an AoE-style management of formations (with the difference that formations will actually do something) is easier.

Also I'm surprised you guys don't value individual control as much as I do. Have you ever felt that it was a hindrance 'in the middle of battle' of the Age games? I guess not? On the other hand, what do you think about the Rise+Fall formations? Those actually are exactly like Michael suggested 0AD's to be (the only difference being that they're not created manually but that's irrelevant here). I found them very frustrating as you cannot control your guys precisely, you can only vaguely order a group of units around. In AoE you could always mess around with a couple of guys by ordering them to attack something specific, to sneak around something, to withdraw if they're damaged (a situation that at the moment occurs all the time in 0AD), etc. etc. R+F was frustrating partly because it took away all these options from the player.

I think being able to control all units separately is a very distinctive feature of the Age series that we should keep.

Edited December 7, 2011 by Android_

[Chakakhan]

IMHO having only the same system than AoE would be disappointing.

I think that the AoE style unit control (especially as implemented in AoEo) is still the best out there in the RTS realm. The units do reasonable things in most situations, so you can send units to fight and go back to your town to manage your economy, or you can manage a battle on multiple fronts, or start a new town center, or build a forward base. It allows you to multitask and have mostly reasonable behavior.

In AoEo (and AoM) the units feel very responsive and controlling them is straight forward and simple and units tend to do reasonable things in most cases. These should be main concerns. Without this, formations are irrelevant because no one is going to play the game if the basic unit control doesn't work well.

So I like the idea of having a basic unit control mode similar to the AoE stuff and something entirely different for formations that you can use if you want to micro manage a battle, but you don't have to use them if you have too much other stuff going on.

I think being able to control all units separately is a very distinctive feature of the Age series that we should keep.

So I totally agree with this Android!

[Mythos_Ruler]

I think that the AoE style unit control (especially as implemented in AoEo) is still the best out there in the RTS realm. The units do reasonable things in most situations, so you can send units to fight and go back to your town to manage your economy, or you can manage a battle on multiple fronts, or start a new town center, or build a forward base. It allows you to multitask and have mostly reasonable behavior. <br style="color: rgb(51, 51, 51); font-size: 13px; line-height: 19px; background-color: rgb(250, 250, 250); "><br style="color: rgb(51, 51, 51); font-size: 13px; line-height: 19px; background-color: rgb(250, 250, 250); ">In AoEo (and AoM) the units feel very responsive and controlling them is straight forward and simple and units tend to do reasonable things in most cases. These should be main concerns. Without this, formations are irrelevant because no one is going to play the game if the basic unit control doesn't work well.

The basic unit control already works well. What we have is the AOEO/AOE/AOM system. We are looking for ways to make it better and unique. Age of Empires should inspire us, but we should not be beholden to it.

[Android_]

In AoEo (and AoM) the units feel very responsive

Exactly, and that is where all the fun comes in!

Michael, I would very much like to hear your opinion on R+F's formations, because that is what you are suggesting .

Edited December 7, 2011 by Android_

[Chakakhan]

The basic unit control already works well. What we have is the AOEO/AOE/AOM system. We are looking for ways to make it better and unique. Age of Empires should inspire us, but we should not be beholden to it.

I disagree. It currently doesn't work very well at all. Pathing is not very good and it is slow and eats up way too much CPU. Also, units don't do smart things (unit AI is not very good / not complete). If we had movement / pathing as good as AoEo it would be a much more fun game to play. I would go so far as to say I think pathing / movement / unit AI is the most broken part of the game.

I totally agree with adding elements to make game play unique, but I think we need to handle the basics really well first.

Not trying to stifle the creativity, just when people start saying AoE is just one way to do it... I think, well... it is a pretty darn good way to do it and most RTS games try to emulate it at a certain degree and it is still the baseline that all RTS games get compared to.

EDIT: I didn't mean for that to sound like a rant, but it kinda sorta does

[Mythos_Ruler]

I meant low level unit behavior is almost exactly at the AOE1 AOE2 level right now.

[Chakakhan]

I meant low level unit behavior is almost exactly at the AOE1 AOE2 level right now.

Ah, I got ya. You were speaking of the basic behavior ignoring the shortcomings of the current implementation. Then I think we are basically in agreement.

I am loading up Rise and Fall to refresh my memory about their implementation of formations.

[Android_]

Michael, could we get a comment from you on Rise and Fall's formations please? Because in terms of control and pathfinding that is the system you are suggesting.

[quantumstate]

I remember finding Rise and Fall's formations difficult to work with, never being quite suer how to put units into or out of formation, or finding much benefit of formations at all. What I imagine Michaels idea to be like would be to have units behaving similarly to AoE but with only a basic block formation type (since nobody ever seemed to use other formations anyway). Then hitting space would toggle to real formation mode which would feel more like total war with carefully organized formations giving bonuses and allowing you to attack flanks with a real effect.