Here's a heuristic to keep units grouped.
*Select a target to attack
*Find the 5 units closest to the target
*Measure the distance between the 5th and the 1st closest unit
*If the distance is more than some threshold, order the tanks to move to the position of the third unit
*Otherwise order the units to move to the target
The behavior is to form a pack of 5 which pushes into the enemy. Other units will move towards it over time. If the two leading tanks are destroyed, new tanks will keep moving towards the remaining pack. If a third tank is destroyed, the pack will retreat towards the new third-closest unit, which is probably back at base somewhere.
Computationally it runs in Od, where d is number of attacking units
Memorywise, it uses constant memory O.
Heuristic to keep units grouped
Moderators: hoijui, Moderators
Would it not be easier to maintain a list of all units to be grouped, then when checking 1 unit, randomly select 2 other units, if neither of them are within a certain radius, find the average location and issue it as a move order, and repeat at set intervals for any units not already engaged in combat.
Well, they have O(n^2) time complexity if implemented the naive way (ie. if each flock member has to calculate its distance from every other before separation/alignment/cohesion rules can be tested), but you can sort of work around that with spatial binning and bring the complexity down to a more manageable O(n * k). That's of course not counting the extra costs of terrain analysis, which would need to be similarly optimized to use them in the first place...
If geese can figure out how to move in echelon formation, surely we can get an AI to bunch up units. Not only that but these bunches should move with little to no effort. Spacing should be fairly easy to maintain as far as keeping them packed, since you can plot them to move relative to a key member.
Think how the goose in front of the pack is the key member of the formation. From there geese fall in, usually in a righthanded arrangement. But there are some geese that prefer to fly offset on the lefthand side of the lead. After so many geese are in formation then sometimes you get confused goose that makes a break away from the leader, moving off to a new route or destination, and you end up with a whole new group due to everyone behind him following him away from the original group.
If you define the leader unit, that's half the battle. Then you want a pecking order for the rest of the group. You could have it use several methods to determine how you want the bunch to move. Sometimes bunching is inefficient, say for marching across a map. In these cases its better to play follow the leader, with the pecking order in tow. After a group gets to four or nine you would probably want to use sub-groups for easy of formation alignments. Traditionally for military units they are usually based on progressive hierarchy of groupings in sub-units with 2-5 members. You start with teams and move to squads, to sections, to platoons, etc., as a unit grows.
At other times you may just want a group cascading back into smaller sub-groups, like in a pincer attack. (One grouping goes left, one right, the last down the middle.) In some cases you might want a simple team / pair of non-alike units to break off together and act as a wingman-wingleader team. Working together these two units may be far more potent than as individuals. Unfortunately you'd almost have to define the best teams in a cfg file for each mod.
You should be able to define some pretty complicated formations using a pecking order for your groups, rather than simply trying to get a disorganized fustercluck to move in unison.
Think how the goose in front of the pack is the key member of the formation. From there geese fall in, usually in a righthanded arrangement. But there are some geese that prefer to fly offset on the lefthand side of the lead. After so many geese are in formation then sometimes you get confused goose that makes a break away from the leader, moving off to a new route or destination, and you end up with a whole new group due to everyone behind him following him away from the original group.
If you define the leader unit, that's half the battle. Then you want a pecking order for the rest of the group. You could have it use several methods to determine how you want the bunch to move. Sometimes bunching is inefficient, say for marching across a map. In these cases its better to play follow the leader, with the pecking order in tow. After a group gets to four or nine you would probably want to use sub-groups for easy of formation alignments. Traditionally for military units they are usually based on progressive hierarchy of groupings in sub-units with 2-5 members. You start with teams and move to squads, to sections, to platoons, etc., as a unit grows.
At other times you may just want a group cascading back into smaller sub-groups, like in a pincer attack. (One grouping goes left, one right, the last down the middle.) In some cases you might want a simple team / pair of non-alike units to break off together and act as a wingman-wingleader team. Working together these two units may be far more potent than as individuals. Unfortunately you'd almost have to define the best teams in a cfg file for each mod.
You should be able to define some pretty complicated formations using a pecking order for your groups, rather than simply trying to get a disorganized fustercluck to move in unison.
The issue is where will the formation form exactly? The problem ehre is:
The AI has a mass of random units that form an attack group, yet they're randomly distributed across the AI territory. Put them in a group and keep them in that group, no formations or patterns required, just keep the untis close together as efficiently as possibly.
The AI has a mass of random units that form an attack group, yet they're randomly distributed across the AI territory. Put them in a group and keep them in that group, no formations or patterns required, just keep the untis close together as efficiently as possibly.
If you have a cluster of units that move as a blob they will not advance well into battle. Why? Because you want maximum firepower for the space available. If the defense can catch the group spread out they have maximum chances to be successful since the defense will win the battle of numbers.
You unequivocally need maintenance of formation for maximum firepower.
You unequivocally need maintenance of formation for maximum firepower.
The point is that your talking about formations, we're talking about simple grouping behaviors, and while I understand the concept of maximum firepower, the fact remains that that is a different topic and requires situational context and other things to determine things like formation shape and direction and unit placement for maximum effect. Whereas this thread is about simple easy to understand grouping behaviors to help new people.
And you seem to have this spread across 3 AI threads, so please either stick to the formation group AI thread, or start a new general AI formations thread, because its making a mess and distorting and cluttering everything, I keep confusing these two threads myself and I'm not sure if I should say something because I'm not entirely sure of the context anymore.
And you seem to have this spread across 3 AI threads, so please either stick to the formation group AI thread, or start a new general AI formations thread, because its making a mess and distorting and cluttering everything, I keep confusing these two threads myself and I'm not sure if I should say something because I'm not entirely sure of the context anymore.
A current computer is nowhere near in perception and thinking capability to a goose. :)
But it might be worth testing, this flocking ai. There are theories about it, basically it's just one bird trying to stay close to its neighbors and somehow still taking input from the environment on where to go. When every bird does it, there's this emergent behaviour and the whole flock moves like a big blob.
But it might be worth testing, this flocking ai. There are theories about it, basically it's just one bird trying to stay close to its neighbors and somehow still taking input from the environment on where to go. When every bird does it, there's this emergent behaviour and the whole flock moves like a big blob.
-
hughperkins
- AI Developer
- Posts: 836
- Joined: 17 Oct 2006, 04:14
Of course then you lose the simplicity and delegation that was the beauty of the original flocking algorithm.Well, they have O(n^2) time complexity if implemented the naive way (ie. if each flock member has to calculate its distance from every other before separation/alignment/cohesion rules can be tested), but you can sort of work around that with spatial binning and bring the complexity down to a more manageable O(n * k). That's of course not counting the extra costs of terrain analysis, which would need to be similarly optimized to use them in the first place...
There are perhaps two ways to create a formation efficiently, ie in Od time:If geese can figure out how to move in echelon formation, surely we can get an AI to bunch up units. Not only that but these bunches should move with little to no effort. Spacing should be fairly easy to maintain as far as keeping them packed, since you can plot them to move relative to a key member.
*each unit is assigned a sequence number within a larger formation. Each unit must maintain its position within that sequence.
*a formation is drawn on the ground. each unit is ordered to go directly to their position in the formation, regardless of where other units are
The first runs in Od time, because each unit only needs to consider the two or three units adjacent to it in the formation, which will run in constant time O. Multiplied by d units this gives Od. This is different from pure flocking, which runs in O(d*d), because each unit only needs to consider its assigned neighbors.
The second runs in Od time, because the difficulty of drawing the formation on the ground is probably independent of number of units, and because once that formation is decided each unit gets a simple move order directly to their assigned position.
In behavior, the first is how a real army unit works on the whole: each unit maintains its spacing wrt its adjacent colleagues.
The second is possibly easiest and most efficient for an AI?
Note that there is the possibility of "holes" in the formation, so probably only units right up at the battlefront should be considered for the formation. The units are moved to the front and grouped together using one of the earlier grouping heuristics presented.
Do we really need a formation at all???
For "mob" units like flashes and slashers, formations may hold little advantage and merely serve to dilute the concentration of fire?
For squads of bulldogs and lugers, formations are more important. At least, lugers should not be in the front line with the bulldogs. In addition, lugers cant fire over units in front of them, so they need to be arranged in a line.
If there is "perfect scouting" of the enemy in front of the bulldogs, the lugers can simply stay at their maximum attack range, with no particular formation except to avoid standing behind other lugers. In TA this is not always the case, so the lugers need to hold their position wrt the bulldogs.
Not covered by formations per se, but crucial to a successful attack: we probably need some really cheap scout troops, that will rush forward one by one to get LOS on the enemy?
-
hughperkins
- AI Developer
- Posts: 836
- Joined: 17 Oct 2006, 04:14
Addendum: for the scout troops, this can be added to the formation by creating a single unit position a certain distance in front of the bulldogs, to be filled by one scout unit. The other scout units hang out at the back.
As the troop moves forward unimpeded, the scout unit remains alive, and continues to scout in front of the main attack force. Each time it dies, it is replaced by a new scout. This can be done automatically by the formation algorithm, which treats the scout's position as just another vacant space to be filled.
As the troop moves forward unimpeded, the scout unit remains alive, and continues to scout in front of the main attack force. Each time it dies, it is replaced by a new scout. This can be done automatically by the formation algorithm, which treats the scout's position as just another vacant space to be filled.
Hugh. I like your scout idea. I think its also important to consider group makeup when assigning grouping behaviors.
Level one raiding units like the flash and instigator are very good at firing on the move. A human controlled flash will be most effective in a line astern formation with waypoints given so that the line moves in a circular fashion around its target. The defender has to hit moving targets while the moving attacker gets to hit a sitting duck.
Level two tanks, because they tend to shoot more potent shots for longer range, are better at line abreast advance. The heavier units don't tend to be all that nimble and their splash damage makes them a hazard in close-in combat. A single atacker that gets closed in on by a defender need not endanger the whole group since its spread out.
So for different types of units you'll want vastly different behaviors.
Level one raiding units like the flash and instigator are very good at firing on the move. A human controlled flash will be most effective in a line astern formation with waypoints given so that the line moves in a circular fashion around its target. The defender has to hit moving targets while the moving attacker gets to hit a sitting duck.
Level two tanks, because they tend to shoot more potent shots for longer range, are better at line abreast advance. The heavier units don't tend to be all that nimble and their splash damage makes them a hazard in close-in combat. A single atacker that gets closed in on by a defender need not endanger the whole group since its spread out.
So for different types of units you'll want vastly different behaviors.
The issue with that is that it just isn't efficient.
A group of 7 sumos heads towards an enemy, and a group fo 9 or 10 peeper scout planes is under the algorithm you defined. Each peeper goes forward and outruns the sumos in second and gets blown up, 10 seconds later there are no peepers and the sumos have barely travelled 2% of their journey.
Instead simply finding a target then sending 1 scout to asses it then targeting the position it was blown up if it was destroyed mid-route, would be a far better algorithm, and much less expensive computationally.
Your algorithm also encourages stop and start syndrome.
A group of 7 sumos heads towards an enemy, and a group fo 9 or 10 peeper scout planes is under the algorithm you defined. Each peeper goes forward and outruns the sumos in second and gets blown up, 10 seconds later there are no peepers and the sumos have barely travelled 2% of their journey.
Instead simply finding a target then sending 1 scout to asses it then targeting the position it was blown up if it was destroyed mid-route, would be a far better algorithm, and much less expensive computationally.
Your algorithm also encourages stop and start syndrome.
-
hughperkins
- AI Developer
- Posts: 836
- Joined: 17 Oct 2006, 04:14
By the way, now is perhaps a good time to mention a possible AI exploit.
When a unit appears on the radar, the AI is given a reference number for that unit, the unit's deployedid. If the AI gets LOS on that unit, it can determine the type of that unit.
If that unit leaves radar and reenters radar, the AI is given exactly the same reference number as before, so it knows the unittype.
So, if we fly a peeper over the enemy occasionally, we can determine the deployedid of all his units. When they later appear on the radar near our base, we know straightaway what the unittypes are.
When a unit appears on the radar, the AI is given a reference number for that unit, the unit's deployedid. If the AI gets LOS on that unit, it can determine the type of that unit.
If that unit leaves radar and reenters radar, the AI is given exactly the same reference number as before, so it knows the unittype.
So, if we fly a peeper over the enemy occasionally, we can determine the deployedid of all his units. When they later appear on the radar near our base, we know straightaway what the unittypes are.