Request for Advanced Formation AI

[Gabba]

The more epic Spring gets - if 100 Units are moved , the more the real strategy disappears, and the Units send over the Map (even when moving at speed of the slowest) just form a huge bulk - easy to attack, self blockading and not controllable. With simple Formation you archieve a sort of controll, but i still saw AntiAir & Con Units in Front while the Warriors stood far behind.

Therefore i like to ask if one of the Programmers is up to the Task of Producing a Advanced Formation AI.

I agree that we need some smarter unit control. If some people want to micromanage their units to death, fine - they'll still get a big advantage since they are smarter than a computer (hopefully).

SupCom has already implemented something similar to what you say. In the beta, ctrl-right-clicking makes unit move in formation, with units placed somewhat smartly. You can even change formations by left-clicking while you're still holding the right button.

Maybe this can be implemented with somewhat smart unit behavior rather than a real formation. Units should be aware of others that share the same orders ("group"), and if ordered by the player, should try to stay rougly as a group. That is, the group should not cover more than a certain area, depending on how many units are in, and on a tight/loose setting (that's for those who are afraid of being vulnerable to area of effect fire). Then the following behaviors should happen by themselves within the "group":
- tankers tend to face known enemy positions and especially to get between them and weak units.
- artillery and large missile units try to get in range of enemy positions, but without leaving the cover of tanker units.
- vulnerable units such as constructors, jammers, radar, etc generally try to stay safe (far from enemies and surrounded by friendlies)
- scouts and fast units should act as skirmishers, as you said, to provide LOS, kill mexxes, and harass slow units while drawing enemy fire. But they should not be suicidal, ie. they don't wander more than a certain distance from the group, and they return to it when in serious trouble.

All this should feel very natural, and doesn't prevent you from controlling your artillery (or *insert favorite unit here*) yourself by keeping it in a separate group. These behaviors above would emerge especially when you send a hodge-podge group of units at the enemy.They will act as if they had some will to survive, that's all. And you'll still have control of how much they move within the group with the hold position/roam/manoeuver setting.

As far as CPU use is concerned, I think a lot of the above can be done with flocking behavior, that Spring already incorporates, at least to help units avoid each other. Basically it works with attractors/repulsors: currently units tend to move away from each other (like electrons), but this force decreases a lot with distance. So add attraction/repulsion points toward the edge of the group, known enemy positions and the safest spot in the group, and you've pretty much achieved all of the above. I doubt that using the current pathfinding system in a different way would result in much more overhead, even though there are more variables to take into consideration.

Now if I was a programmer (I'm learning, maybe one day).....

[AF]

Theres no way to add attraction and repulsion values to the pathfinder, infact some of the pathfinder callbacks are labelled as computationally expensive, and some of them are commented out to return 0 regardless of parameters

The only thing you can do si create a move path and look at the waypoints along the way, durign whcih the pathfinder has to calculate the entire path rather than progressively calcualting it which si much faster.

The pathfinder also ahs no means of using virtual/theoretical move orders, such as 'if I wanted to go here what route would I have to take', which is one of the reasons krogothe said he included a custom pathfinder in KAI.

Also, the spring pathfinder cannot deal with arbitrary shaped formations, only squares. It's also not very good at organised movement such as formations. Order a big mass of peewees into a 5x5 square and they'll push eachother over and never manage to get into a nice neat formation. So gabbas suggestion would just lead to a big bumbling mass of units with some units more likely to be near the centre.

As for repulsion, springs pathfinder doesnt do that, instead it makes units that're too close push eachother away, which can lead to units being pushed onto blocked squares making them immobile. It was only yesterday I had a lvl 1 conbot get pushed too close to a metalmaker and it got stuck, and its been known to happen with factories too. Infact I have a screenshot of 50 fidos occupying the same position next to some wrecks after I sent 300 through a small passage.

[Tobi]

Note that the pathfinder has nothing to do with units pushing each other (which is collision detection, not pathfinding) or with units getting stuck into each other (collision detection too).

There's no difference between calculating a path in waypoints, and a virtual path in waypoints, with the exception that it may be less likely you actually use the last one.

Further, arbitrary formation pathfinding (and moving/steering) is a really tough topic, don't underestimate it. For example if there's only a small path, your pathfinder and movement code has to understand it should split up the formation before the pass and reform the formation afterwards. But if there's a wider path too, it should incorporate time(cost) to break and create the formation and decide whether it may be faster to take a slightly longer route that doesn't need to break up the formation. Also, you don't want it spending time on reforming the formation if it has to break it up almost immediately for a next small pass. Basically you have a (few) extra degrees of freedom (besides the 8 conventional ones).

[PicassoCT]

How about the AI Pre-Pathfinding and then starting the Convoy? That way (just waiting for 4 Secs befor the Things start to move) it could split the GPU use into acceptable pieces..

[Triaxx2]

Would it be possible to make the Pathfinder produce way points at the lowest points along a route? So instead of marching across a mountain range, you go through the valley along side it?

[MadRat]

Didn't TA use a leader and then assigned up to eight more into a pecking order position around the leader according to pecking tht order?

1...2...3
8...L...4
7...6...5

or maybe its more like

8...1...2
7...L...3
6...5...4

and when moving they also moved in the same order, only in-line

L...1...2...3...4...5...6...7...8

$'s = pecking order, for follower units 1-8
L = leader

What was interesting in TA was how the loss of a team member didn't really affect the pecking order. All of the units moved up in the order to fill the newly vacated position.

I'm not sure, but what seemed also key to a group moving in TA was that the mass would unfurl nicely and move in-line without much fuss. I think they did it by direction, with the closest unit to the destination becoming the new leader and the units higher up dropping to the back of the formation. Let's say the group looks like this:

8...1...2
7...L...3
6...5...4

If they had a destination straight north then 1 moves first followed sequentially be the others, only the leader in the middle is now following 8. If they moved straight south, it gets more complicated because L, 1, 2, 3, and 4 effectively renumber themselves behind 8 and suddenly the group looks like below just before the mass moves.

4...6...8
3...5...7
2...1...4

[AF]

Actually there was no pecking order in OTA, and the very nice line of follow the leader is actually one of the most militarily unreliable formations and is actively seen as a bug not a feature in RTS games. I think you're seeing formations when actually it's just a more efficient pathfinder.

And OTA didn't always do follow the leader style movement either, but when it did it wasn't deliberate but rather a flaw in its pathfinder. Although it wasn't as serious since in OTA units fire through each other which isnt the case in spring unless you use some tags that yeha added recently.

[MadRat]

TA used follow the leader, Chris Taylor said they did in one of his old interviews, in order to speed up group movements. Line astern is the fastest way to move a group. Line abreast is one of the best ways to defend. You certainly wouldn't want a fustercluck formation for either event. You either want maximum movement through terrain or maximum guns on target. Neither instance should a clustered box of unit be more efficient due to obvious reasons..

[AF]

But in OTA you always have max guns on the target as units can fire through each other so the only blocking is from terrain.

Either way putting units into lines following a leader would be suicide because then you have a simple job defending, blow the first one up, repeat, and since the first one blocks the second one and the second blocks the third firing etc, your effectively destroying them 1 by 1.

AAI and NTai have in the past accidentally gotten the line of unit behavior and its had devastating consequences on their offensive skill. Perkins states this behavior as the root cause of AAI's inability to defeat CSAI, and it is one fot eh main changes in the next AAI, and was a huge blow to earlier NTai versions that had this error too.

[Lindir The Green]

In OTA I always tried to move my army at a 90 degree angle to the enemy once it was in range so that it would have maximum firepower bearing down on the enemy, and hopefully the firepower against my formation wouldn't be concentrated.

So yeah moving in a straight line is suicide if you are charging straight towards the enemy, but not if you are moving parallel to the enemy. Sorta like how ships in RL have the most firepower firing sideways.

And in Spring units follow the leader too, because of how the pathfinder works. So if you want the units spaced out you have to keep manually spreading them out every few seconds with click + drag.

[Tobi]

Would it be possible to make the Pathfinder produce way points at the lowest points along a route? So instead of marching across a mountain range, you go through the valley along side it?

That's a matter of assigning different costs to different heights. Can't to that through the interface tho, all costs are hardcoded iirc.

[Gabba]

Also, the spring pathfinder cannot deal with arbitrary shaped formations, only squares. It's also not very good at organised movement such as formations. Order a big mass of peewees into a 5x5 square and they'll push eachother over and never manage to get into a nice neat formation. So gabbas suggestion would just lead to a big bumbling mass of units with some units more likely to be near the centre.

I thought that K-man had mentioned that Spring's pathfinding/collision detection did use steering behaviors.

Anyways from reading you post, it seems that what I'm proposing is effectively impossible with the current Spring engine.

Tobi: I agree, there are a lot of things to consider in real-time when dealing with moving a group. I think that for that you need a map analysis algorithm that finds all the chokepoints in advance, along with the roughness of terrain in those chokepoints. Basic A* pathfinding that only takes into account the terrain cost can't really evaluate how much room there's for a group to pass, AFAIK.

[AF]

gabba, k-man knows a lot of things that he never got into the spring pathfinder. The spring pathfinder is a horrible mess that nobody dares touch, and I'm sure even k-man would rather rewrite it than fix or tweak it.

The spring pathfinder is just an A* algorithm tied to terrain speed multipliers, unit movement classes, and terrain heightmaps for blocking maps. There's no fancy movement or repulsion or follow the leader, or any of that, and the A* algorithm tiself isnt very well done, it could be done much better and give much faster code and eliminate many flaws in pathfinding results.

[Gabba]

Thanks AF for the precisions. It's good to know.

This is one more reason to be happy with the rewrite!

[Lefty]

Hi !
I wonder if anyone plans this feature. I think custom formation is nice, but doesn't solve this whole problem. Maybe LuaWidget for several predefined formations would be very handy...

[AF]

Use jks custom formation drawing AI, and you can have almost compelte control of how the formation is set up. You literally draw the formation on the map, allowing custom size distribution and proportions.

[Lefty]

Use jks custom formation drawing AI, and you can have almost compelte control of how the formation is set up. You literally draw the formation on the map, allowing custom size distribution and proportions.

I have already tried this widget, but it just lets me draw a line of units. Its good for a line of same units, but less usable for several types of units (hide artillery behind bulldogs and so). Maybe I haven't explored some 'hidden' feature (hold something while dragging) ...

[CaptainMaim]

If you can't create your own formations, and the units are in predictable places, once I identified this formation I'd just aim my bertha at the predicted location and start blowing up whatever units I wanted. In a usual mishmash of units you pretty well have to destroyed the whole column to make sure you got what you were after. Or you spot it and then destroy the whole column.

Though it works in theory, I don't see it working in practice. Simply slowing units down so they don't overshoot each other should be more than enough to keep things together. Plus you forgot radar jammers in your formation. And who knows what one might need for a given situation. K-Bots might be better than tanks if there's hills.

If I were you, I'd make some hot keys to divide your teams up into halves and thirds and then use that to split up groups and use multiple group numbers to organize things. For your formation it would probably only take 4 groups. 1 forward, 2 sides and one center. To make the construction units follow in the middle just tell them to guard the units in front of them. Now if we could guard a group that would solve a the whole repair and follow problem.

It can be done this way and it's far more fluid and dynamic. Leave the tactics to the humans. Don't send a bot to do a man's job.

[AF]

This sort of thing would be more suited to a lua widget than a groupAI as its much heavier on the GUI, and groupAI have next to no GUI abilities at all in comparison to the wealth of APIs available to lua widgets.

Go post in jks widget thread, I'm sure he can add some features if you ask nicely and theyre not too big.

[kiki]

Does groupai = lua?

Otherwise, I am planning to make some formation lua stuff. I should probably begin within the next few weeks. Funny, the fancy lua will be done before the basic foundations of my mod....

Essentially, I want to make a better rectangular formation that is not always orthagonal to north south east west. In addition, it sticks together. By changing the speed of units in different areas of the formation, the formation will keep its shape. Then, there will be a nice interface that allows you to drag and drop the order of the lines of units. For example, you could drag the aa unit icon to the back to make it take up the rear. It would basically be a nice little stack. Besides rectangle, there would be a circle (think concentric rings) and then maybe a formation where you can put a certain type of unit on the sides of the formation. The tricky thing is getting the ai to figure out how to get the formation through a choke point. One way would be to have the ai/lua make a thinner collumn. I have an idea in my head for this but I am not sure how to describe it. My other idea is to have a flanking maneuver. Groups would be assigned to the left and the right flanking squads. The enemy front line would be calculated, and the flanking sqauds would, well flank. Dont worry, I have an algorithm for calculating the front.