Monday, 23 March 2009

Optimisation and the dangers of too-elaborate thinking.

Magellan over at Roguetemple has simultaneously stopped me acting like an idiot and in the process has reduced my calculating/refresh times by a factor of close to 100. How? By pointing out (the now obvious point!) that there is no need to recalculate the terrain costs for the pathing algorithm for every single monster.

Originally I wanted to recalculate for every monster because I had the idea fixed in my head that some monsters have different terrain costs than others (an ice-based creature in a fire-based environment for example), but there is no current need for a Giant Bat to have differing terrain costs than a Giant Rat, for example.

By this single change, the downtime between player turns due to processing is reduced; in the unfortunate (for the @) situation below the time for processing is reduced from ~60 ms to under 1 ms.

There are several other optimisations that could be achieved here as well - the relevant section of the recalculation code is as follows:

for x:= 1 to DUNGEONSIZEX do
for y:= 1 to DUNGEONSIZEY do
if (Dungeon.Walkable[X, Y]) then
if (Dungeon.Effects[X, Y] > 0) then
Dungeon.TerrainCost[X, Y] := TC_TOUGH
else Dungeon.TerrainCost[X, Y] := TC_NOCOST;
Dungeon.TerrainCost[X, Y] := TC_IMPASSABLE;



Dungeon.TerrainCost[PlayerX, PlayerY] := TC_IMPASSABLE;

and then later on, whenever a monster moves:

Dungeon.Monsters[NewX, NewY] := Dungeon.Monsters[LocalMonster.X, LocalMonster.Y];
Dungeon.TerrainCost[NewX, NewY] :=
Dungeon.Monsters[LocalMonster.X, LocalMonster.Y] := 0;
Dungeon.TerrainCost[LocalMonster.X, LocalMonster.Y] :=

Instead of just blindly iterating through the entire dungeon, a quick array of currently active Dungeon.walkable squares could be held elsewhere, since this does not change that often (currently only with tunneling and opening doors). One alternate solution would be to make Dungeon.Terraincosts merely calculated from Dungeon.Walkable but this would mean having to implement differential terrain costs for certain monsters in a different way.

Incidentally, I'd like to have at some point "push-past" rules to govern which monsters can push past another (as ever, the excellent Andrew Doull offers an extremely workable solution to this), and which ones can also open doors (which would necessitate a recalculation of terrain costs).

No comments: