Faster Move Testing (for AI)
Posted: Mon Mar 18, 2013 12:23 am
The current test for weather an actor can move to a square is often done with:
This simple section of code is deceptively complex! What happens whenever it's run (generally without the terrain_only flag) is:
canMove calls checkAllEntities.
checkAllEntities calls a special function (_check_entities) embedded in each individual grid table.
_check_entities then looks at the TERRAIN, TRAPS, ACTOR, PROJECTILE, and OBJECT layers of the map table.
For each layer present, _check_entities calls a built in entity.check function, looking for the "block_move" field.
If it's present, entity.check tries execute it as a function if possible to generate a TRUE (blocked) or FALSE (unblocked) result which is then returned back up the call chain to get a result for canMove.
This function or the equivalent checkAllEntities call is run extensively by AI routines and can slow down the game noticeably, especially on slower computers on complex levels.
The attempt to execute a possible block_move function is a nice feature, but it is not actually used anywhere in the game currently. (I discovered recently that using it can result in a huge slow down in the game.) The main reason is the call depth needed.
I have rewritten canMove as a one-deep function call that only looks at actors and terrain (the only things currently checked):
This code generally runs 5 - 8 x faster (As tested on various npcs with varying movement flags on various levels), even when fovpathcaches are available.
The extra functionality accessed by the current function is not actually needed, since special actions for various terrain (like levers and doors) are invoked by the engine.Actor.move method when an actor actually tries to move to a spot on the map, and the few places that can use the feature execute checkAllEntities instead anyway. Also, almost all of the functionality can be duplicated with an on_move function (like is used for traps, lore, etc) with an extra step to move the actor back to its old position (e.old_x, e.old_y) after the action.
If we can live with the loss of this unutilized feature, I think a switch to this faster function and revising a few key AI routines to use it (rather than checkAllEntities calls) can yield a significant speed up in AI pathing.
Code: Select all
--- Can the actor go there
-- @param terrain_only if true checks only the terrain, otherwise checks all entities
function _M:canMove(x, y, terrain_only)
if not game.level.map:isBound(x, y) then return false end
if terrain_only then
return not game.level.map:checkEntity(x, y, Map.TERRAIN, "block_move")
else
return not game.level.map:checkAllEntities(x, y, "block_move", self)
end
endcanMove calls checkAllEntities.
checkAllEntities calls a special function (_check_entities) embedded in each individual grid table.
_check_entities then looks at the TERRAIN, TRAPS, ACTOR, PROJECTILE, and OBJECT layers of the map table.
For each layer present, _check_entities calls a built in entity.check function, looking for the "block_move" field.
If it's present, entity.check tries execute it as a function if possible to generate a TRUE (blocked) or FALSE (unblocked) result which is then returned back up the call chain to get a result for canMove.
This function or the equivalent checkAllEntities call is run extensively by AI routines and can slow down the game noticeably, especially on slower computers on complex levels.
The attempt to execute a possible block_move function is a nice feature, but it is not actually used anywhere in the game currently. (I discovered recently that using it can result in a huge slow down in the game.) The main reason is the call depth needed.
I have rewritten canMove as a one-deep function call that only looks at actors and terrain (the only things currently checked):
Code: Select all
-- faster canMove function that only checks terrain and actors
-- set up target.on_move for entities that need to react to actor movement
-- Actor.move automatically calls entity.block_move if present
--function _M:canMove(self, x, y, terrain_only)
function _M:canMove(x, y, terrain_only)
local Map = game.level.map
if not terrain_only then
local e = Map(x,y,engine.Map.ACTOR)
if e and e.block_move then return false end
end
local ter = Map(x,y,engine.Map.TERRAIN)
if ter then
if ter.does_block_move then
if ter.can_pass then
for what, check in pairs(ter.can_pass) do
if not self.can_pass[what] or self.can_pass[what] < check then return false end
end
return true
end
return false
end
return true
end
endThe extra functionality accessed by the current function is not actually needed, since special actions for various terrain (like levers and doors) are invoked by the engine.Actor.move method when an actor actually tries to move to a spot on the map, and the few places that can use the feature execute checkAllEntities instead anyway. Also, almost all of the functionality can be duplicated with an on_move function (like is used for traps, lore, etc) with an extra step to move the actor back to its old position (e.old_x, e.old_y) after the action.
If we can live with the loss of this unutilized feature, I think a switch to this faster function and revising a few key AI routines to use it (rather than checkAllEntities calls) can yield a significant speed up in AI pathing.