FOV path caches and slowdowns

[Hachem_Muche]

I've been working on a fairly complex event that includes a number of xorns and umber-hulks burrowing through rock and walls to engage the player. The walls are designed to block actors with the can_pass.pass_wall = xx attribute but to crumble in the process. If the can_pass attribute of the walls is higher than that of the actors, there is a substantial slowdown in the AI.

Digging (oops!) into this I think the source of the problem lies with the way Path Strings (a function in text form that generates a table of movement attributes) and level.map._fovcache are used to determine viable paths. The purpose of the fovcache code is to precompute the ability of all terrain on the map to block the movement of actors with a specified path string, and then to retrieve that information via a simple lookup function. _M:addPathString(ps) in engine.Map.lua creates and indexes each cache with a call to core.fov.newCache) as needed in order to speed up actor pathfinding.

From tome/class/Grid.lua:

Code: Select all

function _M:block_move(x, y, e, act, couldpass)
	-- Path strings
	if not e then e = {}
	elseif type(e) == "string" then
		e = loadstring(e)()
	end

	-- Open doors
	if self.door_opened and e.open_door and act then
		if self.door_player_check then
			if e.player then
				Dialog:yesnoPopup(self.name, self.door_player_check, function(ret)
					if ret then
						game.level.map(x, y, engine.Map.TERRAIN, game.zone.grid_list[self.door_opened])
						game:playSoundNear({x=x,y=y}, {"ambient/door_creaks/creak_%d",1,4})

						if game.level.map.attrs(x, y, "vault_id") and e.openVault then e:openVault(game.level.map.attrs(x, y, "vault_id")) end
					end
				end, "Open", "Leave")
			end
		elseif self.door_player_stop then
			if e.player then
				Dialog:simplePopup(self.name, self.door_player_stop)
			end
		else
			game.level.map(x, y, engine.Map.TERRAIN, game.zone.grid_list[self.door_opened])
			game:playSoundNear({x=x,y=y}, {"ambient/door_creaks/creak_%d",1,4})

			if game.level.map.attrs(x, y, "vault_id") and e.openVault then e:openVault(game.level.map.attrs(x, y, "vault_id")) end
		end
		return true
	elseif self.door_opened and not couldpass then
		return true
	elseif self.door_opened and couldpass and not e.open_door then
		return true
	end

	-- Pass walls
	if self.can_pass and e.can_pass then
		for what, check in pairs(e.can_pass) do
			if self.can_pass[what] and self.can_pass[what] <= check then return false end
		end
	end

	-- Huge hack, if we are an actor without position this means we are not yet put on the map
	-- If so make sure we can only go where we can breathe
	if e.__is_actor and not e.x and not e:attr("no_breath") then
		local air_level, air_condition = self:check("air_level"), self:check("air_condition")
		if air_level and (not air_condition or not e.can_breath[air_condition] or e.can_breath[air_condition] <= 0) then
			return true
		end
	end

	if e and act and self.does_block_move and e.player and game.level.map.attrs(x, y, "on_block_change") then
		local ng = game.zone:makeEntityByName(game.level, "terrain", game.level.map.attrs(x, y, "on_block_change"))
		if ng then
			game.zone:addEntity(game.level, ng, "terrain", x, y)
			game.nicer_tiles:updateAround(game.level, x, y)
			if game.level.map.attrs(x, y, "on_block_change_msg") then game.logSeen({x=x, y=y}, "%s", game.level.map.attrs(x, y, "on_block_change_msg")) end
			game.level.map.attrs(x, y, "on_block_change", false)
			game.level.map.attrs(x, y, "on_block_change_msg", false)
		end
	end

	return self.does_block_move
end

where e is the actor or other criteria to determine whether the terrain (self) can be crossed. I haven't tracked down all of the issues, but a (substantial) part of the slowdown seems be caused when path strings are passed to this function invoking a loadstring call at the first elseif statement. This statement requires the string to be compiled, and the resulting function executed to return a table of values that is referenced in the rest of the function. This section of code is callled frequently during regular actor movement. Here is an example of a series of stack traces taken during routine movement of 32 actors on a 92Wx61H level (out of combat) where this section of code was called more than 150 times in one turn:

mod.classGridstacktrace.txt

(97.85 KiB) Downloaded 370 times

(The Infinite500 code called here is the same as that of the non-modified game - SVN 6523.) Most of the calls are from updateMap as a result of normal movement of an actor from one tile to the next or from pathfinding. Some of the path strings (like "{can_pass={pass_wall=0,}}", which just means the actor has no special movement capabilities) appear to be incorrect or superfluous. I think performance could be improved by making more use of the fovpathcaches for routine movement, short-circuiting "do-nothing" path strings, and only recompiling the path strings as a fallback when other methods fail. It might also be advantageous to add a link to the associated pathcache code directly into each actor instance, reducing call stack depth appreciably.

In addition, path strings are only generated during level changes (_M:changeLevelReal in mod/class/Game.lua) and not for new actors that are added to a level later (like summons). This could be added to the add entity code.

Has anyone had similar experiences with this or have other suggestions on how to improve things here?

[darkgod]

fixed