[glob2-devel] Split calculation

[Bradley Arsenault]

I've ran into a bit of a delima in my ai, Nicowar. Nicowar uses very
heavy algorithms when its deciding where to place a building, or
exploration flag. At times, it can freeze for a quarter or half a
second when thinking about it. I tried to fix this by building a split
calculation framework, where a module could request extra ticks for a
particular calculation. However, I've run into a delima: the amount of
calculation done, and thus how much it should be split, depends on a
good many factors. Particularly, in the terms of building placement,
how much lag the ai goes through depends on the size of the map its
operating in. Larger maps will require much more calculation, and have
a good deal more lag. On a 512x512 map, splitting the calculation in
two won't cut it, the calculation would have to be cut into about 5
before you would see the lag gone completely. Yet the lag could be
properly hidden split into 2 on a 128x128 map. The lag is non existant
on a 64x64 map.

Whats worse, is that part of the problem is that this expensive
calculation is done repedietely with slightly different variables each
time, specifically during building placement searches because it
chooses where to place a building differently for each building. So
this calculation is done several times. It would be difficult to split
the execution of calculations into multiple sections if they are in a
loop. Further in pain, the calculation itself that chooses where to
place a building does 3 loops, the expensive ones being the first and
second. And these loops further call a function that examines a
particular section of the grid, yet two more nested loops. However, a
profile a while back showed that it was not the function that polled
the sections of the grid for a particular piece of information that
was taking up all the calculation time, but it seems that the function
that examines this generated data (the one I was talking about a
moment ago) is the one taking up the time.

Its obvious that the grid polling calculation should be split up, but
so many factors are involved, its hard to know how. How much the
calculation should be split up varies on several factors, mainly map
size. Splitting up the function involves deviding up loop
calculations, and further more, the main lag is because the function
is called multiple times (generally once per building type, and once
again for each building placed, stopping). I managed to get a little
speed up when I had the algorithm only executed when there was "space"
for it. Meaning if there was nowhere to place a smaller building, then
there is certainly no where to place this building. That saved some
execution time, but the problem still persists.