Smarter AI: global pathfinding using distance maps

[darkgod]

Next beta will probably feature an update to ActorFOV that uses the (CPU hungry) FOV calculations to creation distance maps for all actors at a low cost.

A distance map is a in memory map for each actor that stores a value equal to "game.turn + LOS_radius - distance from source".
Since we can compute it with FOV it's nearly free to do so, and we can use it for fun things:
* Easy pathfinding, just take the value at your coord on your target's distance map, andcheck all directions for a value higher than yours, if there is, go there. You'l lthus "follow the track" of your target, and get lost if it teleports away (which is good)
* Easy fear: do the same but for lower value and you will naturally flow to unseen areas

There will be a new "move_dmap" AI that does just that.

I think I'll use it on most T4 monsters.

Comments, improvments?

[yufra]

How about general excitement? Sounds really cool and I would like to test it out.

[darkgod]

I've commited it.
To use it set __do_distance_map=true in your Actor class (make it a global field of the class you dont have to set it for each actor) and then you can use move_dmap, flee_dmap and dmap AIs

[yufra]

I copied the new ActorFOV and simple AI lua files into my beta9b, and then modified my AI to use "move_dmap" and "flee_dmap" instead of "move_simple." I had to make a few changes to simple.lua to get it to work the way I thought it should. Basically the Actor:hasLOS was expecting coordinates and not an actor, and the flee ai needed to not default to move_simple when there is LOS and flip the inequality to move down the distance gradient. Simple testing was quite pleasing, with doctors and nurses attacking zombies until they were at 50% health and then turning tail and running.

Code: Select all

Index: simple.lua
===================================================================
--- simple.lua	(revision 1041)
+++ simple.lua	(working copy)
@@ -32,7 +32,7 @@
 newAI("move_dmap", function(self)
 	if self.ai_target.actor then
 		local a = self.ai_target.actor
-		if self:hasLOS(a) then return self:runAI("move_simple") end
+		if self:hasLOS(a.x, a.y) then return self:runAI("move_simple") end
 
 		local c = a:distanceMap(self.x, self.y)
 		if not c then return end
@@ -50,7 +50,7 @@
 newAI("flee_dmap", function(self)
 	if self.ai_target.actor then
 		local a = self.ai_target.actor
-		if self:hasLOS(a) then return self:runAI("move_simple") end
+--		if self:hasLOS(a.x, a.y) then return self:runAI("move_simple") end
 
 		local c = a:distanceMap(self.x, self.y)
 		if not c then return end
@@ -58,7 +58,7 @@
 		for i = 1, 9 do
 			local cd = a:distanceMap(util.coordAddDir(self.x, self.y, i))
 			print("looking for dmap", dir, i, "::", c, cd)
-			if cd and cd > c then c = cd; dir = i end
+			if cd and cd < c then c = cd; dir = i end
 		end
 
 		return self:moveDirection(util.coordAddDir(self.x, self.y, dir))

[darkgod]

Yeah I saw those just after posting sorry

[yufra]

I grabbed the revision 1048 simple AI files and think the flee_dmap is still buggy. I was getting "number compared to nil" and tracked the problem to c being set to nil when cd turns up nil during the direction checking. This patch should fix it, and looks nearly identical to the last line of the move_dmap AI. Am I missing a reason flee_dmap shouldn't just be the opposite equality but otherwise the same as move_dmap?

Code: Select all

Index: simple.lua
===================================================================
--- simple.lua	(revision 1048)
+++ simple.lua	(working copy)
@@ -59,7 +59,7 @@
 			local sx, sy = util.coordAddDir(self.x, self.y, i)
 			local cd = a:distanceMap(sx, sy)
 --			print("looking for dmap", dir, i, "::", c, cd)
-			if not cd or (cd < c and self:canMove(sx, sy)) then c = cd; dir = i end
+			if cd and cd < c and self:canMove(sx, sy) then c = cd; dir = i end
 		end
 
 		return self:moveDirection(util.coordAddDir(self.x, self.y, dir))