Spring RTS Engine

Has anyone written any kind of "is that a blob of enemy units & radar blips? if so, where is it headed and will it hurt me?" algorithm?

So far I've got each enemies' movement vector average over the last ten seconds (and therefore its predicted position). I was going to just check all of those vectors for intersection with any blobs of buildings (already stored w/ radii for defense purposes) within the next thirty seconds. But an indirect attack path of any kind would make that useless. Surely there's a better way.

too complicated imo
you already need something like a territorial ownership quadmap -> you iter all units, put them into the corresponding quad and increase a allyunit counter in there. The higher it gets the more ownership you got. And if there are multiple enemy allies in one quad it's marked as war front.
Now you can also calculate an average movement vector for each ally inside such a quad and so predict attack direction.

You cannot predict this even as a human player, but you cannot afford not to act anyway, so...

One could also calculate "defense levels" for each of those quads, based on army value versus eco value.

Then calculate "threat levels" based on how huge is enemy blob and how reachable are low-defense high-eco positions from the immediate-movegoal of the hostile blob.

If threat level is above certain threshold, you should move to protect the quad at greatest value-risk.

It doesn't matter if enemy never presses the attack, it's wrong to do otherwise.

jK wrote: you already need something like a territorial ownership quadmap -> you iter all units, put them into the corresponding quad

A territorial ownership map function would be interesting to have. This is quite expensive to do via lua (iterate over map and read LOS). I wonder how the AI:s do this, as to me this seems to be something quite basic in a rts game.

Jools wrote:This is quite expensive to do via lua (iterate over map and read LOS). I wonder how the AI:s do this, as to me this seems to be something quite basic in a rts game.

It's not, CAI does so and all other LuaAIs too afaik. It's a simple There is no need for LOS checking either, just call Spring.GetAllUnits via CallAsTeam, if you need to limit LOS.

Anarchid wrote:how reachable are low-defense high-eco positions from the immediate-movegoal of the hostile blob.

i like this. i think i'll combine this with if the hostiles movegoal is behind my "lines" (perpendicular to the angle from one of my base blobs to their unit's position). i've already got a threat quad map (it's true, this is not prohibitively expensive), but only immediately under threat (within enemy weapon range). a territory map seems to me another kind of thing, because it needs to be contiguous (come to think of it, a convex hull might do, which apparantly there are algorithms for).

jK wrote:There is no need for LOS checking either, just call Spring.GetAllUnits via CallAsTeam, if you need to limit LOS.

i'm doing this in Shard btw. it's not a gadget. so i don't just need to check for LOS, i'm simulating it!

As far as I understand it, adding LoS info to Shard itself would be better performance-wise. After all, engine already has all that calculated. Not sure if c++ AIs can get it though.

But LOS is an area and unit positions are points. Is there a fucntion to get that area other than manually checking all map?

Jools wrote:But LOS is an area and unit positions are points. Is there a fucntion to get that area other than manually checking all map?

checking each unit's sight, radar, and sonar radii, and creaing a quad map with circular fill: https://github.com/zoggop/Shard/blob/ma ... andler.lua (of course, this means the AI sees through hills. in other words you're right there isn't :-P)

yuritch wrote:As far as I understand it, adding LoS info to Shard itself would be better performance-wise. After all, engine already has all that calculated. Not sure if c++ AIs can get it though.

it would be much better in every way, but i wasn't sure when AF would add it, i'm not sure how to do so myself, and hm now you make me wonder if c++ the interface even allows for it

- afaik Shard had some way to marshall information from LuaRules to the cpp part to the lua-logic part
- Lua can access the los specialtexture (and perform calculations on it, or even force a shader to perform those)
- maybe it's possible to write a gadget to enable shards/cpp-ai's access to proper losmap?

everyone hates heuristics - or educated guessing (aka random + symetric probs)?

Lua rules <-> AI comms are broken. Somewhere in the C/CPP Wrappers there's a bug, I don't know the specifics of the bug, I don't know if anyone else does either, or how long it has been broken ( many moons ago it worked apparently ).

OTAI took the same approach with predicted movement goals. There is some merit but 10 seconds isn't enough, a bunched up group of units on patrol would cause the AI to panic every 2 minutes. OTAIs code for this never went beyond experimental. There's also merit in maps of control, but I always took the approach that the entire map is your base and the enemy is merely an infestation. The moment you concede that a part of the map belongs to someone else, you've lost part of the game.

reacting to where enemy clusters are and what they can do seems most relevant.

the orders they have actually been given, not so much (can be deceptive).

how about using what the player knows about the game to antecipate what the clusters of units would do if the player were their owner.

example: if an enemy has a cluster of mobile attack units that is stronger than my cluster of units and that is also closer to them than to every other possible cluster it has the ability to fight, i assume they will attack my cluster.

(could also take the into account the economic value of the clusters that might be targeted)

what im currently using is maybe not exactly what you mean by quad(tree?) map but should work similarly.
the idea was to make the whole ai based on this map.
ill just explain what zkmbai is using in case someone is interested or wants to help me improve it:

the ai divides the map into 8x8 rectangles, each of these has 3 states, which is either neutral, allied or hostile, additionally, rectangles that are being attacked or that are soon to be attacked (enemy troops incoming) will be marked as contested.

now the ai has two kinds of troops: defenders and attackers.
defenders will be split up among the allied territories(rectangles) whereat contested and border areas will get higher weight. if an area is attacked, units from nearby areas will assist in the defense. the damage that the enemy has done will be stored for each area seperately and be used for weighting and deciding where to build defenses(beside height bonuses for defense)
attackers will group into squads (which act like one unit) and attack an enemy area. preferably the one with the smallest estimated enemy strength. as soon as the first area is captured, they'll move to one of the nearby areas.

allied and hostile areas expand once in a while into nearby neutral areas, but they'll never expand to an area that touches a hostile area(this is to prevent defenders from suiciding into hostile defenses).
beside this shadow expansion, an area is instantly set to hostile as soon as an enemy building is spotted in it.
allied areas in which the defenders are outgunned by the enemies will be set to neutral(for both sides), which results in a retreat and more time to gather nearby defenders to push back the enemy.

these areas are also useful to aim superweapons and to manage constructors, although areas are only used for targeting as fallback when there are no enemy clusters(managed by another map).
the arbitrary borders can end up in weird behaviour and not so clean code sometimes(for example zk's OD grid, which is based on a graph).

Something that hit me last night when reading this thread- if you ran two instances of the same AI and one would be purely virtual, basically a opponent only the AI can see.. and it reacts to that AIs behaviour.

It wouldnt be to far away from what a human actually does, would lead to funny phails sometimes, and also to spectacular "How did it guess that" moments.