How to increase number of comparisons per tick?

[WC3Wonderer]

Hi. I'm working on AI for my map. AI editor does not fit. I decided to write custom AI and discovered that computation power is too poor to make it right.

Basic AI:
1. Pick 1 unit.
2. Find nearby enemy/ally units.
3. Analyze situation and order to attack/retreat/cast spell/etc.

Let's say we have 4 players. 100 units in total on the map including creeps.

2. To find nearby units I need to iterate over all units on the map and compare distance between picked unit and all other units. It's 100 real comparisons + 100 functions calls to GetDistanceBetweenUnits(unitA, unitB). Function is very simple so we can think that it another 100 real comparisons. So at this point I need 200 real comparison to find nearby units.

3. Picked unit is archmage. He is in the center of the combat and surrounded by 50 units in 1000 range around him. He's about to cast Blizzard. Best target is surrounded by most enemies and least allies in Blizzard Area of Effect circle. To find best target I need to repeat steps in section 2 for each of these 50 units and make additional comparisons. 50 units X 200 real comparisons = 10.000 real comparisons. Additional comparisons from each iteration: Is Alive Or Not / Ally Or Enemy / Magic immune or not. To make it simple I suggest to convert them to another 10.000 real comparisons. Total: 20.000 Real comparisons.

Archmage needs 20 200 Real comparisons (200 + 20 000) to cast blizzard when there are 50 units nearby and 100 units on the map.

Then I decided to check how much computation power is given by the engine. I wrote an empty loop with 1 comparison in each iteration and execute it every 0.01 second. Then I enbaled FPS meter and started to check performance.

• set index = 1
  • loop
    • exitwhen index > 20000
    • set index= index+ 1
• endloop

20.000 Iterations ..... 3 FPS
10.000 Iterations ..... 15 FPS
5.000 Iterations ..... 28 FPS
2.000 Iterations ..... 59 FPS

Only 2000 iterations per 0.01 second! Am I doing something wrong? It's impossible to write AI with such poor performance. I can play all modern games on high/ultra. My CPU can handle 115 GFlops.

Any suggestions/ideas/tweaks how to increase number of comparisons per tick? Or how to write it in another way?

 

[Nichilus]

I think step #1 would be to use natives. Instead of having code like this:

• Unit Group - Pick every unit in (Units in (Playable map area)) and do (Actions)
  • Loop - Actions
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • (Distance between (Position of (Triggering unit)) and (Position of (Picked unit))) Less than or equal to 420.00
      • Then - Actions
      • Else - Actions

i.e. code where I pick all units in map and manually compare their distances to get all units within range of triggering unit, you should do this:

• Unit Group - Pick every unit in (Units within 420.00 of (Position of (Triggering unit)).) and do (Actions)
  • Loop - Actions

Since that is internally using GroupEnumUnitsInRangeOfLoc native. Natives are always faster/more performant since they are executed inside the engine.

 

[Uncle]

What Nichilus said.

Then to POSSIBLY get better performance you can try to reduce the number of calculations by using something like a Quadtree and Unit Groups that actively Add/Remove nearby units. Warcraft 3 is probably doing something like this already so I can't guarantee that this would help, but based on my own experience it would. I don't want to waste your time so remember that before making any decisions... Anyway, here's the breakdown:

The map is broken up into regions, each region has it's own associated Unit Group(s). As Units enter and leave these regions they're added/removed from the associated Unit Groups. You can get a region from a unit, so they'll be paired together using a variable/hashtable. At any point in time you'll be able to run some logic like "Get Archmage's current region -> Loop over units inside that region's Unit Group -> Run desired logic on them". If your map is large and battles are happening everywhere then this could help reduce the number of checks you have to make. For example, there's a chance that the Archmage is alone and is the only one in his region's Unit Group, which would mean little to no calculations would be necessary.

Then moving onto your AI logic, you will likely want to make some tradeoffs to optimize for performance. The AI doesn't have to always target the absolute BEST unit, a good enough target should be... good enough. Furthermore, manage your calculations in a way where you don't ask unnecessary questions. In other words, if your Archmage's Blizzard can only target enemy ground units then order your Conditions so that you first check if it's an Enemy, then you check if it's a Ground Unit. Then check for more generic Conditions after. So you would check if the nearby units are enemy ground units, add them to a "valid target" group, then loop over that group to check if they're able to be targeted by the ability (alive, vulnerable, visible, etc) and remove targets that don't meet these Conditions.

Example:
Using this new approach, if you found 20 nearby units, then 5 valid targets, this would result in you running 2 Conditions per 20 units (40), then 4 Conditions per 5 units (20) which results in up to 60 function calls. If you had used the lazy approach with 6 Conditions per 20 units then you would potentially run up to 120 Conditions. Although, remember that once a Condition fails the rest of them are ignored so this may be unnecessary. There's also the cost of using 2 Unit Groups instead of 1 to take into consideration.

Returning to the region concept, you could have separate Unit Groups for Ground Units and Air Units. Of course there would be a cost for Adding/Removing units to and from these groups, and the more groups you have the more costly this would be, but it may be worth it. The idea is to leverage system memory and spread the function calls out over time. As far as I know you should be able to store a massive amount of Unit Groups without having any noticeable cost on game performance. It's the complicated processes like doing Distance checks on many units at once that really hurts performance.

Anyway, just my 2 cents, can't guarantee any of this would help.

 

[WC3Wonderer]

For now we have:
1. GroupEnumUnitsInRange. Speed up search of nearest units.
2. Dividing playing field into sectors. May help in some situations if map is large.
3. Smart filters. Good idea to reduce number of conditions.

All of these may improve performance. However I think that we should have enough power to handle all units per tick, but we don't have enough for one of them.

 

[blufflegendaire]

Also make your own distance check function that takes distance to be checked against into argument and raise it to x*x instead of sqrt distance.

ie.

Distance(A, B) < 1000

DistanceCheck(A, B, 1000) == true
=> it internally checks for

SquareDistance(A, B) <= (1000*1000)