I spent some of the May Day weekend trying to reduce the CPU impact of my CC2 mods. I had this grand idea that I could drastically cut the time spent looking for nearby units.

Quite a lot of the bits of Revolution work by finding the nearest carrier, nearest seal/walrus/bear, nearest needlefish/sworldfish or “the nearest aircraft with a RADAR” and other things like that.

As a computing problem it is quite a good one. I have n objects, each has a position in 2D space. What is the fastest way of finding the nearest object to one randomly selected object? Do that x times?

The most important use of this in Revolution is working out what the nearest hostile RADAR is to any particular unit. That is then used for a variety of things, in the HUD it is used to show the RWR direction, in the other screens it is used to unmask ships and aircraft near a player owned needlefish, or to provide the altitude range-boost for an aircraft fitted with an AWACS.

There are a few other “find the nearest X” things such as “find the nearest friendly lifeboat” or “find the nearest friendly ground unit that isnt docked” that could benefit if I found a way to make this faster.

The basic algorithm for this is.

• for each vehicle
  • if hostile vehicle has a radar, add to hostile_radars list
• for each radar
  • for each vehicle
    • calc dist between radar and vehicle
      • save vehicle if dist is smaller than last

Basically, for every radar, we have to compute the distance to every single hostile unit on the map and then remember which radar gave the shortest distance

If there was 1 radar and 10 other units, this is 10 distance checks.

If there was 2 radar and 10 other units, 20 distance checks

5 radars, 50 checks,

You can see how this gets big. A busy game can have far more than 10 units in play, especially if it is a PvP game. A fully loaded carrier itself represents 18 total units. Attack a single 1 shield island and that is perhaps another 15-20 units. If we have 3 RADARs out, that is 114 checks just for 1 island and 1 player carrier.

I started to think about how to reduce the number of combinations. The lua scripting frequently iterates the whole list of map units for a variety of other things (drawing them one by one, working out if your mouse is hovering over one, etc) so I wondered if I could so a primitive form of location hashing.

I decided to make a 2D matrix, for each unit, I’d work out which 20km box it was in, and remember that.

I’d essentially end up with a table of tables:

g_nearby[x][y][vid] = true

Using this, given a single unit, I can quickly find all the other units in the same box! Great!

for vid, _ in g_nearby[x][y] do
  local v = update_get_map_vehicle_by_id(vid)
  if v and v:get() then
    -- do something with vehicle v
  end
end

Excellent!

Hmm.. But what if my unit is at x=13999,y=1 it will be in box x=13,y=0 but the units at x=14001 are 2m away but in a different box? Ok, simple. I’ll record each that I’m “near” the adjacent boxes too..

g_nearby[x-1][y][vid] = true
g_nearby[x][y][vid] = true
g_nearby[x+1][y][vid] = true
g_nearby[x-1][y-1][vid] = true
g_nearby[x][y-1][vid] = true
g_nearby[x+1][y-1][vid] = true
g_nearby[x][y][vid] = true
g_nearby[x-1][y+1][vid] = true
g_nearby[x][y+1][vid] = true
g_nearby[x+1][y+1][vid] = true

Yeah.. starting to not look efficient… meh, its fun, lets keep going!!

After a while of this I was able to limit my “is there a radar near me” search space! I added some debug visualisations to test this and show what was being considered on each radar “sweep”

The white squares are the grid squares being considered when checking the nearby contacts of MNT17. The red squares are all the hostile units in those boxes.

Notice how the other red units near Vulcan and Bachus aren’t being considered! SUCCESS!!!

There is A LOT of units in those boxes! But far fewer than are currently on this map.

If I hover over the ALB near Vulcan. You can see the other objects on the map:

Great! Better random access and answer to the “what stuff am I near?” question.

But.. This save I’m using for testing is quite a big map. The islands are all 4-shield and there are 2 AI carriers. My CPU is pegged at 90% for most of the time. If I hop into MNT17 to fly it. I just start to get a noticeable slowdown.

I need to profile this to really see if I’ve made things better or worse.

So I needed to write a primitive profiler for this new chunk of code and the radar sweep using it.

Going back to the previous version of the radar sweep without my search boxes idea. I did still feel some lag (again this is a very big and busy save), but “feel” isn’t very scientific. I need to know, but how?

CC2 does not have a high resolution clock. There are only two mechanisms for measuring the passage of time. Ticks and epoch-seconds. Ticks is useless for my purposes here, the tick value remains constant for the whole update() call. I need to measure something with millisecond durations. Hmm..

Then I remembered, one of the reasons why CPU usage in CC2 Lua is so important, is if you spend too much time doing it, you can slow down, or even pause the game until your lua call has finished. So, using this. Instead of timing my sweep call and printing how many milliseconds it took, I’d flip it around and count how many times I can do a sweep in 10 seconds of elapsed clock time.

    if false and g_screen_name == "screen_veh_m" and g_timed == 0 then
        g_timed = 120
        local start = update_get_time_since_epoch()
        print("starting timed run", start)
        local stop = start + 10
        local count = 0
        -- run for 10 seconds, count how many updates we can do for all
        while stop > update_get_time_since_epoch() do
            do_radar_scan(false, true)
            count = count + 1
        end
        print("done", count)
    end

Calling this little chunk from update() gave me the results I was after!

Using the current rev-1.5 radar sweep code we got the following results!

starting timed run	1746566862
done	2471
starting timed run	1746566876
done	2396
starting timed run	1746566890

Excellent. In 10 sec, we could do about 2433 updates. So 243 ops/sec.

Great! I have something to compare at last.

So. I wired in my “nearby” box code to the radar sweep, instead of scanning all possible units on the map, it’d only scan the units in the 9 grid boxes around my chosen radar. Let’s get the times!

Drumroll!!

starting timed run	1746569789
done	132
starting timed run	1746569804
done	129
starting timed run	1746569818
done	120

WHAT!? That is 20 times slower???!

AAAAAA

My optimised spatial search is terrible!

But … why?

I can’t be totally sure, but after reading this SO post my money is on how lua stores things in tables.

My table indices values are integers, I’m not actually using very many either. For the example above There were only ever about 12 boxes in play, That was actually a table with 4 keys, where for each of those the value was another table with 3 values, with each a table where each key was a vehicle ID. Due to my neighbouring change, that grows, to basically about 18 tables, with an average of 20 vehicle IDs in each (plus the outer 12 tables).

That is starting to sound like a lot of tables. But the memory usage is not the problem here.

When accessing a table by index, lua treats each index as a key, to actually lookup the content in the table it has to compute the hash of that object. So even if the key is ‘3’, Lua computes a 40 byte hash as part of the table lookup. Just the same as if we put “foo” in the table and used that as the key.

So, I wasn’t simply treating this whole thing as a multi-dimensional array, it was an associative array (a hash for you Perl fans out there). Every read/write incurred a hash computation for the key. An operation which is hugely more expensive it turns out than simply iterating the big list of units again and calculating the distances.

What was the lesson here?

If you are optimising something, measure it before and after!

If you are still curious, the code for my awful slow box experiment can be found at https://github.com/cc2modteam/revolution-mod/compare/exp/inb/nearby-box-experiment?expand=1