Group movement and other stuf...

[alik83]

In the code in SelectedUnitsAI file it looks like if you order a group of units to move with CTRL pressed, all units should move with a maxSpeed of the slowest unit. However testing in game shows that it doesn't really happen.
I think rather then moving units in a group with minMaxspeed (with CTRL), units should during their move keep the distance between them (or distance to some calculated group center) not more then a certain value, so they really move "together".
Maybe I'll code that sometime later.
Also: If you order a moving unit a new move order, it will first slow down, then accelerate again...

One more thing: can you define a key, with which you can push orders to the front of buildQue, not the back?
Like you have a long build order and you want to order one little thing now and then continue with that big order.

[jouninkomiko]

but, you can't cut to the front of a queue! CUTTER!

[Archangel of Death]

Sometimes its important to cut something to the front of the queue. Like the old man who just had a heart attack, no one will mind that he gets cut infront of the person who smashed their finger in their car door.

Their are often times I wish I could do this, like when I need another constructor, but have several dozen peewees and other support units already queued up.

[SJ]

Alt pushes to front in factory build ques

[zwzsg]

That one is not in the readme. Looks like Spring needs a fatter doc. (And an automatic tips dispenser )

[alik83]

I tried ALT key to issue a command to be completed before the given command que and it DOESN'T work.
Anybody got it to work? Zwzsg?
Do you have to define smth in the uiconfig.txt file?

Sorry, didn't notice this was implemented only for factories, why not any commands?

[zwzsg]

It worked, but the current slasher that was half built was discarded and the cons built at once when I alt-clicked on the cons buildpic.

[Gabba]

Alt pushes to front in factory build ques

Now this would be interesting to have for ALL unit orders.
But eventually I hope we can have a pop-up menu that shows you a unit's order queue, and if you click before/after an order in the queue, new orders are inserted there. If it's done well it would be a great help to gameplay... something to consider for the new GUI...

Alik83: Group movement still needs a lot of work in Spring, I'm reading up on that right now. It would be great if the SY explained us which principles/methods they used for the pathfinding/group AI, that would help understand the code better.

edit: two good papers that are worth reading:
Steering Behaviors For Autonomous Characters
Formation-Based Pathfinding for Real-World Vehicles

[AF]

Or you could read the sourc code and figure it out yourself..

[Gabba]

Or you could read the sourc code and figure it out yourself..

I am reading the source code, but knowing which AI principles the SY were trying to implement would help immensely in understanding it.

[AF]

In which case I retract my comment and apologise to Gabba

[b1ind]

Gabba, looks like an A* algorithm. There path costs that are calculated for every new map seem to give that away. If you look hard, there is a list of visited(by pathfinder) squares and other such things giving away the algorithm.

[el_muchacho]

Yes SJ confirmed to me it's "mostly standard A* but with multiple different versions layered on top of each other, each layer "upward" working on a lower res version of the map".

On this very informative page on A*, the author writes

Path requests do not arrive evenly distributed. A common situation in a real-time strategy game is for the player to select multiple units and order them to move to the same goal. This puts a high load on the pathfinding system.

In this situation, it is very likely that the path found for one will be useful for other units. One idea is to find a path P from the center of the units to the center of the destinations. Then, use most of that path for all the units, but replace the first 10 steps and the last 10 steps by paths that are found for each individual unit. Unit i will receive a path from its starting location to P[10], followed by the shared path P[10..len(P)-10], followed by a path from P[len(P)-10] to the destination.

The paths found for each unit are short (approximately 10 steps on average), and the long path is shared. Most of the path is found only once and shared among all the units. However, the user may not be impressed if he sees all the units moving on the same path. To improve the appearance of the system, make the units follow slightly different paths. One way to do this is to alter the paths themselves, by choosing adjacent locations.

Another approach is to make the units aware of each other (perhaps by picking a "leader" unit randomly, or by picking the one with the best sense of what's going on), and only find a path for the leader. Then use a flocking algorithm to make them move in a group.

Yet another approach is to take advantage of A*'s intermediate state. This state can be shared among multiple units traveling to the same goal, as long as those units share the same heuristic and cost functions. When the main loop exits, do not erase the OPEN and CLOSED sets; instead, start the next loop (with the starting position of the next unit) with the OPEN and CLOSED sets from the previous invocation of A*. (This can be considered a generalization of the Interruptible Algorithm and the Early Exit sections.)

See Also: Putting paths together is called path splicing in another section of these notes.

I like the idea of a flocking algorithm (algorithm that simulates group movements, like herds or schools of fishes) in Spring. A* behaves poorly when an era is overcrowded, like in a base; one can often see the units bumping in each other. If a flocking algorithm is cheaper than A* for each unit, that may look nice. Look at the video in the middle to see how the group behaves in presence of obstacles.

For a group of 20 units, instead of computing 20 paths with A*, one would compute the path for 3 units wisely chosen in the group, and the one with the best path would be the leader, then one would use a flocking algorithm (believed to run in constant time, maybe woth OpenSteer) to follow him. Of course, the only problem is, if the leader gets killed during the displacement, one would need to choose another leader.

Finally, one would need to choose which units obey to the flocking algorithm. Ground units of course, and maybe submarines and maybe² some airplanes like Brawlers, but not other airplanes (for which A* is probably efficient anyway as they face few obstacles).

NB: OpenSteer has a nice demo that shows off a few of its possibilities, like turning units at low speed (for boats) or avoidance.

[mongus]

sweeeeet! (about the alt key)
That movement stuff looks complex... (4 me)

[zwzsg]

Oh noes! Someone made a post with nice content and useful information instead of mindless stupid gameplay-killing un-original ideas!