Faster Move Testing (for AI)

[Hachem_Muche]

The current test for weather an actor can move to a square is often done with:

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
end

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):

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
end

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.

[nate]

How much of its time does ToME currently spend inside that function?

[aristalis]

Great job