Formation pathfinding [was: Analysing performance problems]

[Android_]

This is what he wants:

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.

This is Rise and Fall. [He adds to that by introducing the space bar to manually group/regroup units and in addition, just like we all want it to be, he wants to give formations a meaningful purpose (e.g. Testudo).]

Selection/deselection, the issuing of orders, pathfinding etc. would work like in R+F.

Edited December 7, 2011 by Android_

[Mythos_Ruler]

This is what he wants:

This is Rise and Fall. [He adds to that by introducing the space bar to manually group/regroup units and in addition, just like we all want it to be, he wants to give formations a meaningful purpose (e.g. Testudo).]

Selection/deselection, the issuing of orders, pathfinding etc. would work like in R+F.

I envision something more along the lines of Rome:Total War or Battle for Middle Earth II, actually. Only difference is that you can create and disband your battalions at-will. And if you batch train 20+ units, they will come out as a battalion. BfME2's battalions were very easy to use. The problem with R&F's "battalions" is that they didn't act like coherent units. This is nothing like how I want 0 A.D.'s battalions to behave. The ease of pathfinding and control from BfME2, with the formation cohesiveness and tactics of Rome:Total War, plus our own little touches, is how I envision them working.

(another thing I love about BfME2 is its wall system--it's nearly perfect if you ask me, but that's a different discussion)

[Android_]

I envision something more along the lines of Rome:Total War or Battle for Middle Earth II, actually. Only difference is that you can create and disband your battalions at-will. And if you batch train 20+ units, they will come out as a battalion. BfME2's battalions were very easy to use. The problem with R&F's "battalions" is that they didn't act like coherent units. This is nothing like how I want 0 A.D.'s battalions to behave. The ease of pathfinding and control from BfME2, with the formation cohesiveness and tactics of Rome:Total War, plus our own little touches, is how I envision them working.

I see, thanks for clarifying . If the battalions you envision stick together like glue (and only then) it might indeed be reasonable to bind the units together in order to act as a whole. What I like about the idea (if I understand it correctly) is that loose AoE-style formations can coexist with those tightly-knitted battalions at the player's will.

Back to pathfinding: It has just come to my mind that AoEO neatly manages to move large masses of units around, maybe somebody wants to check that out (I myself can't play the game on my computer).

Edited December 7, 2011 by Android_

[Chakakhan]

Back to pathfinding: It has just come to my mind that AoEO neatly manages to move large masses of units around, maybe somebody wants to check that out (I myself can't play the game on my computer).

Yes, it does a great job at moving around hundreds of units. This is one of many games we are studying. According to an article I read, this is the same basic pathing code that was in AoK (hence AoE3, AoM). There are some configuration options in AoM and AoE3 that allow you to look at some of the pathfinding data dynamically (as a graphical overlay).

[Zeta1127]

I like Mythos_Ruler's battalion ideas, because one doesn't train thousands of individual troops, one trains armies in units such as battalions, before sending them to war.

(The one gripe I had with BfME2's wall system was the exorbitant cost, but other than that, it worked fairly well.)

[WhiteTreePaladin]

I like BFME2's battalions/control and walls, so definitely some good things there. I like Michael's earlier comment about tying in batch training and battalions. If you train them in batch, then they come out as a battalion. Individual units could still be placed in a battalion, and battalions could always be split up, but doing it automatically could really streamline things.

[Mythos_Ruler]

Unrelated discussion of walls:

(The one gripe I had with BfME2's wall system was the exorbitant cost, but other than that, it worked fairly well.)

The cost wouldn't have bothered me so much if they weren't so darn weak. Seemed like any Uruk with a crossbow could take down a section of the wall. The Uruk siege weapon too was outrageously strong.

[WhiteTreePaladin]

Yeah, stronger walls that actually work are better. Cheap walls aren't any good if you have to keep rebuilding them; it's too much micromanagment.

[Enrique]

On topic:

I'm not sure if this info can be useful or not... I don't have a lot of how-pathfinding-works knowledge but reading some Philip's posts it seems it's an A*algorithm based one.

I found this document on the web about the Fringe Search. It stands the following: " Experimental results show that Fringe Search runs roughly 10-40% faster than highly-optimized A* in our application domain of pathfinding on a grid". -- If it's compatible with the current pathfinding system or not is out of my scope

Here is the link to the document:

http://webdocs.cs.ua...ions/fringe.pdf

[wraitii]

Adding my two cents about formations and formation movement and gameplay addition. Something I remember from Rise Of Nations was that unit got "entrenched" after standing still for some time. This allowed for one thing that I have found in no other RTS: actual flanking. Now while entrenching is likely out of scope for 0 AD, the formation system, if it is kept fairly robust, à la R:TW can simulate such a thing: formations should get a bonus against "front attack", "side defense" or whatever, so it makes sense to use them, and should remain fairly consistent: breaking them up should not be instant ( since this would negate "flanking" ).

A way to implement this would be to have some sort of trigger for each unit which would have different states: "Free", ie not in a formation, "in a formation", and "making/breaking formation".

Now I'm not sure how the combat system works in 0 AD, but I don't think units individually receive differentiated damage depending on where it's coming (flank/front/rear)... If so, then very well. If not, then it would be a really cool thing to implement.

Anyway, units "free" would behave normally, units "in a formation" would get damage depending on what the strong/weak points of the formation are, and basic combat. Units forming or breaking, on the other hand, would be fairly defenseless and would receive much bigger damage.

As for how this relates to pathfinding: formations should be a bit slower than normal walking (which would help the pathfinding too), and remain fairly tight when moving forward. I think it should absolutely remain so until it has to "break". The specifics of when it has to break are tricky to choose... I think the most straightforward way to do it is that if keeping the formation deviates the path from more than X degrees from the optimal path, the formation will break (something like 30° seems reasonable). Breaking can be handled in two ways... The ugly one is simply to make each unit behave individually, but this is a nightmare and really not nice.

A much better way to "break" a formation is to divide it into smaller "sub-formations", until the sub-formation can go through the obstacles (I'm taking the corridor example here). SO a 8x8 turtle formation could break into 4 4x4 smaller formations, and each would go through one at a time and then reform. This would be the optimal way to manage such a thing, methinks.

Of course, with the problem of an object getting partly in the way (such as what was drawn on page 1), a simpler solution of "moving away from the obstacle" should be adopted.

Edited December 24, 2011 by wraitii