--Prevent standalone execution: if not TRAINSPORTED then print("To prevent players from harm, this file may only be executed by the trAInsported game.") return end --AI by hajo4: -- taxiDriver1.lua --require '_utilities/utilities.lua' -- moved to end of file --require '_jumper/jumper.lua' AI ="taxiDriver by maxxst" -- FU-Berlin -- Example-AI from https://github.com/maxxst/trAInsported-starterkit / 2013-07 -- All-in-1-file, translation, added comments, TODOs & debug: hajo4 2014-02-26 local dbg=1 -- -- Without a passenger, the TaxiDriver-Bot drives randomly around the map. -- When encountering passengers, he picks up the first, then searches -- the shortest path to its destination. -- -- TODO: ai.enoughMoney(), ai.blocked() -- TODO: use getNumberOfLines() to check cpu-quota on bigger maps -- Note: on "Compete"-maps as small as 12x10, we get errors "Taking too long" -- TODO: Do some of the obvious improvements :-) -- #### #### #### railMap = {} -- Gets called at the start of the game. Buy a train here! function ai.init(map, money, maximumTrains) print('AI:', AI) railMap = map2railMap(map) if dbg >= 5 then print('railMap:') printTable(railMap,2) print("used codelines A:", getNumberOfLines() ) -- check cpu-quota end -- init. pathfinding-library: jumperMap = mapToJumperMap(map) local walkable = 1 local Grid = Jumper.Grid local Pathfinder = Jumper.Pathfinder local grid = Grid(jumperMap) myFinder = Pathfinder(grid, 'BFS', walkable) if dbg >= 5 then print("used codelines B:", getNumberOfLines() ) end --TODO: buy train near passenger buyTrain(random(map.width), random(map.height)) end -- Gets called when the train reaches a tile with passengers: function ai.foundPassengers( train, passengers ) local p = nil if train.passenger then -- if the train is full, dont stop. -- TODO: look for VIPs -- TODO: remember passengers myPrint(5,'Train is full !') else p = passengers[1] --take first passenger from list myPrint(3,"pickup:", p.name) -- TODO: choose the "best" passenger end return p end -- Gets called when the train reaches the tile in front of a junction. -- Should return one of the possible directions ("N", "S", "W", "E"). function ai.chooseDirection(train, possibleDirections) local dir = chooseRandomDir(possibleDirections) -- without passenger: random move if train.passenger then -- with passenger: take shortest path to dest. -- calculate best direction local startx, starty = train.x ,train.y local endx, endy = train.passenger.destX, train.passenger.destY local path = myFinder:getPath(startx, starty, endx, endy) if not (endx == path[2].x and endy == path[2].y) then -- avoid error kreuzung = makeLoc( path[2].x, path[2].y, train.dir) nachKreuzung = makeLoc( path[3].x, path[3].y, train.dir ) for d, bool in pairs(possibleDirections) do local test_loc = goDir( railMap, kreuzung, d ) if test_loc.x == nachKreuzung.x and test_loc.y == nachKreuzung.y then dir = d break end end end end if dbg >= 5 then print("used codelines C:", getNumberOfLines() ) end return dir end -- Gets called when a new passenger gets placed on the map: function ai.newPassenger(name, x, y, destX, destY, vipTime) myPrint(1,"new passenger at ("..x..", "..y..")") --TODO: remember passengers end -- Gets called when the train arrives at the destination: function ai.foundDestination( train ) myPrint(3,"drop") dropPassenger(train) print("Money: " .. getMoney()) end function chooseRandom(train, possibleDirections) tbl = {} for dir,bool in pairs(possibleDirections) do tbl[#tbl+1] = dir end return tbl[random(#tbl)] end function mapToJumperMap(map) local jumperMap = {} for i=1, map.width do for j=1, map.height do if not jumperMap[j] then jumperMap[j] = {} end if map[i][j] == 'C' then jumperMap[j][i] = 1 else jumperMap[j][i] = 0 end end end myPrint(5,'jumperMap:') if dbg >= 5 then printTable(jumperMap,2) end return jumperMap end --Debug-print: function myPrint(dbgLevel, ...) if dbg >= dbgLevel then print(...) end end -- #### #### #### #### --[[ For running the AI in matches on the online server, the include-files need to be appended directly: --require '_utilities/utilities.lua' --require '_jumper/jumper.lua' ]]-- -- utilities.lua function map2railMap(map) local railMap = {} for i=1, map.width do railMap[i] = {} for j=1, map.height do if map[i][j] == "C" then railMap[i][j] = true else railMap[i][j] = false end end end railMap.width = map.width railMap.height = map.height return railMap end function getDirections( railMap, loc) x = loc.x y = loc.y dir = loc.dir local directions = {} -- only check if x y is actually a rail if railMap[x][y] then -- lookup: possible directions if y > 1 and railMap[x][y-1] and dir ~= 'S' then table.insert(directions, "N") end if y < railMap.height and railMap[x][y+1] and dir ~= 'N' then table.insert(directions, "S") end if x > 1 and railMap[x-1][y] and dir ~= 'E' then table.insert(directions, "W") end if x < railMap.width and railMap[x+1][y] and dir ~= 'W' then table.insert(directions, "E") end end return directions end function chooseRandomDir( directions ) local tbl = {} for dir,bool in pairs(directions) do tbl[#tbl+1] = dir end return tbl[random(#tbl)] end function depthFirstSearch( level, railMap, location, target ) max_level = 30 -- tinker with this, maybe you can dig deeper! ;) if max_level == level then return "TOOLONG" else if location.x == target.x and location.y == target.y then return {} else local path = {} local min = max_level+100 local dirs = getDirections( railMap, location ) for index, dir in pairs(dirs) do local new_loc = goDir( railMap, location, dir ) local res = depthFirstSearch( level+1, railMap, new_loc, target ) if res ~= "TOOLONG" then table.insert(res, {["x"]=location.x, ["y"]=location.y, ["dir"]=dir}) if #res < min then path = res min = #path end end end return path end end end function goDir( railMap, loc, dir ) h = railMap.height w = railMap.width x = loc.x y = loc.y if dir == "S" then y = y+1 end if dir == "N" then y = y-1 end if dir == "W" then x = x-1 end if dir == "E" then x = x+1 end if x > w or y > h or x < 1 or y < 1 then print("goDir: out of range "..x.." "..y) else return {["x"]=x, ["y"]=y, ["dir"]=dir} end end function loc2String( loc ) return loc.x.." "..loc.y.." "..loc.dir end function makeLoc( x, y, dir) return { ["x"]=x, ["y"]=y, ["dir"]=dir } end function dir2String( map, loc ) x = loc.x y = loc.y dir = loc.dir dirs = getDirections( map, loc ) str = "loc("..x.." "..y.." "..dir..") -> " if dirs[1] then str = str..dirs[1].." " end if dirs[2] then str = str..dirs[2].." " end if dirs[3] then str = str..dirs[2].." " end if dirs[4] then str = str..dirs[2].." " end return str end function manhattanDist(x1, y1, x2, y2) return math.abs(x1-x2) + math.abs(y1-y2) end -- Ausgabehelfer -- Function to print a Table function printTable(table, lvl) if type(table) == "table" then lvl = lvl or 0 for k, v in pairs(table) do if type(v) == "table" then printTable(v, lvl + 1) else str = "" for i = 1,lvl do str = str .. "\t" end print(str, k, v) end end else print('Not a table') end end -- #### #### #### -- jumper.lua -- Raw source, to be prettified later -- Defining core modules ------------------------------ Binary Heaps (local) ------------------------------ -- See: -- * http://en.wikipedia.org/wiki/Binary_heap -- * http://www.policyalmanac.org/games/binaryHeaps.htm local floor = math.floor -- Lookup for value in a table local indexOf = function(t,v) for i = 1,#t do if t[i] == v then return i end end return nil end -- Default comparison function local function f_min(a,b) return a.f < b.f end -- Percolates up local function percolate_up(heap, index) if index == 1 then return end local pIndex if index <= 1 then return end if index%2 == 0 then pIndex = index/2 else pIndex = (index-1)/2 end if not heap.sort(heap.__heap[pIndex], heap.__heap[index]) then heap.__heap[pIndex], heap.__heap[index] = heap.__heap[index], heap.__heap[pIndex] percolate_up(heap, pIndex) end end -- Percolates down local function percolate_down(heap,index) local lfIndex,rtIndex,minIndex lfIndex = 2*index rtIndex = lfIndex + 1 if rtIndex > heap.size then if lfIndex > heap.size then return else minIndex = lfIndex end else if heap.sort(heap.__heap[lfIndex],heap.__heap[rtIndex]) then minIndex = lfIndex else minIndex = rtIndex end end if not heap.sort(heap.__heap[index],heap.__heap[minIndex]) then heap.__heap[index],heap.__heap[minIndex] = heap.__heap[minIndex],heap.__heap[index] percolate_down(heap,minIndex) end end local Heap = function() local newHeap = { __heap = {}, size = 0, sort = comp or f_min, } function newHeap:empty() return (self.size==0) end function newHeap:clear() self.__heap = {} self.size = 0 self.sort = self.sort or f_min return self end function newHeap:push(item) if item then self.size = self.size + 1 self.__heap[self.size] = item percolate_up(self, self.size) end return self end function newHeap:pop() local root if self.size > 0 then root = self.__heap[1] self.__heap[1] = self.__heap[self.size] self.__heap[self.size] = nil self.size = self.size-1 if self.size>1 then percolate_down(self, 1) end end return root end function newHeap:heapify(item) if item then local i = indexOf(self.__heap,item) if i then percolate_down(self, i) percolate_up(self, i) end return end for i = floor(self.size/2),1,-1 do percolate_down(self,i) end return self end return newHeap end ------------------------------ Heuristics (global) ------------------------------ local abs = math.abs local sqrt = math.sqrt local sqrt2 = sqrt(2) local max, min = math.max, math.min local Heuristics = {} function Heuristics.MANHATTAN(dx,dy) return abs(dx)+abs(dy) end function Heuristics.EUCLIDIAN(dx,dy) return sqrt(dx*dx+dy*dy) end function Heuristics.DIAGONAL(dx,dy) return max(abs(dx),abs(dy)) end function Heuristics.CARDINTCARD(dx,dy) dx, dy = abs(dx), abs(dy) return min(dx,dy) * sqrt2 + max(dx,dy) - min(dx,dy) end ------------------------------ Node (global) ------------------------------ local Node = function(x,y) local newNode = {x = x, y = y} return newNode end ------------------------------ Path (global) ------------------------------ local t_insert, t_remove = table.insert, table.remove local Path = function() local newPath = {} function newPath:iter() local i,pathLen = 1,#self return function() if self[i] then i = i+1 return self[i-1],i-1 end end end newPath.nodes = newPath.iter function newPath:getLength() local len = 0 for i = 2,#self do local dx = self[i].x - self[i-1].x local dy = self[i].y - self[i-1].y len = len + Heuristics.EUCLIDIAN(dx, dy) end return len end function newPath:fill() local i = 2 local xi,yi,dx,dy local N = #self local incrX, incrY while true do xi,yi = self[i].x,self[i].y dx,dy = xi-self[i-1].x,yi-self[i-1].y if (abs(dx) > 1 or abs(dy) > 1) then incrX = dx/max(abs(dx),1) incrY = dy/max(abs(dy),1) t_insert(self, i, self.grid:getNodeAt(self[i-1].x + incrX, self[i-1].y +incrY)) N = N+1 else i=i+1 end if i>N then break end end end function newPath:filter() local i = 2 local xi,yi,dx,dy, olddx, olddy xi,yi = self[i].x, self[i].y dx, dy = xi - self[i-1].x, yi-self[i-1].y while true do olddx, olddy = dx, dy if self[i+1] then i = i+1 xi, yi = self[i].x, self[i].y dx, dy = xi - self[i-1].x, yi - self[i-1].y if olddx == dx and olddy == dy then t_remove(self, i-1) i = i - 1 end else break end end end return newPath end -- Search algorithms: ------------------------------ ASTAR ------------------------------ -- See: http://en.wikipedia.org/wiki/A_star local ipairs = ipairs local huge = math.huge -- Updates G-cost local function computeCost(node, neighbour, finder) local mCost = Heuristics.EUCLIDIAN(neighbour.x - node.x, neighbour.y - node.y) if node.g + mCost < neighbour.g then neighbour.parent = node neighbour.g = node.g + mCost end end -- Updates vertex node-neighbour local function updateVertex(finder, node, neighbour, endNode, heuristic, overrideCostEval) local oldG = neighbour.g local cmpCost = overrideCostEval or computeCost cmpCost(node, neighbour, finder) if neighbour.g < oldG then if neighbour.opened then neighbour.opened = false end neighbour.h = heuristic(endNode.x - neighbour.x, endNode.y - neighbour.y) neighbour.f = neighbour.g + neighbour.h finder.openList:push(neighbour) neighbour.opened = true end end -- Calculates a path. -- Returns the path from location `` to location ``. local function ASTARSEARCH(finder, startNode, endNode, toClear, tunnel, overrideHeuristic, overrideCostEval) local heuristic = overrideHeuristic or finder.heuristic finder.openList:clear() startNode.g = 0 startNode.h = heuristic(endNode.x - startNode.x, endNode.y - startNode.y) startNode.f = startNode.g + startNode.h finder.openList:push(startNode) toClear[startNode] = true startNode.opened = true while not finder.openList:empty() do local node = finder.openList:pop() node.closed = true if node == endNode then return node end local neighbours = finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel) for i, neighbour in ipairs(neighbours) do if not neighbour.closed then toClear[neighbour] = true if not neighbour.opened then neighbour.g = huge neighbour.parent = nil end updateVertex(finder, node, neighbour, endNode, heuristic, overrideCostEval) end end end return nil end ------------------------------ BFS ------------------------------ -- See: http://en.wikipedia.org/wiki/Breadth-first_search local t_remove = table.remove -- BFS logic local function breadth_first_search(finder, node, openList, toClear, tunnel) local neighbours = finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel) for i = 1,#neighbours do local neighbour = neighbours[i] if not neighbour.closed and not neighbour.opened then openList[#openList+1] = neighbour neighbour.opened = true neighbour.parent = node toClear[neighbour] = true end end end -- Calculates a path. -- Returns the path from location `` to location ``. local function BFSEARCH(finder, startNode, endNode, toClear, tunnel) local openList = {} -- We'll use a FIFO queue (simple array) openList[1] = startNode startNode.opened = true toClear[startNode] = true local node while (#openList > 0) do node = openList[1] t_remove(openList,1) node.closed = true if node == endNode then return node end breadth_first_search(finder, node, openList, toClear, tunnel) end return nil end ------------------------------ DFS ------------------------------ -- See: http://en.wikipedia.org/wiki/Depth-first_search -- DFS logic local function depth_first_search(finder, node, openList, toClear) local neighbours = finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel) for i = 1,#neighbours do local neighbour = neighbours[i] if (not neighbour.closed and not neighbour.opened) then openList[#openList+1] = neighbour neighbour.opened = true neighbour.parent = node toClear[neighbour] = true end end end -- Calculates a path. -- Returns the path from location `` to location ``. local function DFSEARCH(finder, startNode, endNode, toClear, tunnel) local openList = {} -- We'll use a LIFO queue (simple array) openList[1] = startNode startNode.opened = true toClear[startNode] = true local node while (#openList > 0) do node = openList[#openList] t_remove(openList) node.closed = true if node == endNode then return node end depth_first_search(finder, node, openList, toClear, tunnel) end return nil end ------------------------------ DIJKSTRA ------------------------------ -- See: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm local dijkstraHeuristic = function(...) return 0 end -- Calculates a path. -- Returns the path from location `` to location ``. local function DIJKSTRASEARCH(finder, startNode, endNode, toClear, tunnel) return ASTARSEARCH(finder, startNode, endNode, toClear, tunnel, dijkstraHeuristic) end ------------------------------ JPS ------------------------------ -- See: http://harablog.wordpress.com/2011/09/07/jump-point-search/ local step_first = false local function findNeighbours(finder,node, tunnel) if node.parent then local neighbours = {} local x,y = node.x, node.y -- Node have a parent, we will prune some neighbours -- Gets the direction of move local dx = (x-node.parent.x)/max(abs(x-node.parent.x),1) local dy = (y-node.parent.y)/max(abs(y-node.parent.y),1) -- Diagonal move case if dx~=0 and dy~=0 then local walkY, walkX -- Natural neighbours if finder.grid:isWalkableAt(x,y+dy,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y+dy) walkY = true end if finder.grid:isWalkableAt(x+dx,y,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y) walkX = true end if walkX or walkY then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y+dy) end -- Forced neighbours if (not finder.grid:isWalkableAt(x-dx,y,finder.walkable)) and walkY then neighbours[#neighbours+1] = finder.grid:getNodeAt(x-dx,y+dy) end if (not finder.grid:isWalkableAt(x,y-dy,finder.walkable)) and walkX then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y-dy) end else -- Move along Y-axis case if dx==0 then local walkY if finder.grid:isWalkableAt(x,y+dy,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y+dy) -- Forced neighbours are left and right ahead along Y if (not finder.grid:isWalkableAt(x+1,y,finder.walkable)) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+1,y+dy) end if (not finder.grid:isWalkableAt(x-1,y,finder.walkable)) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x-1,y+dy) end end -- In case diagonal moves are forbidden : Needs to be optimized if not finder.allowDiagonal then if finder.grid:isWalkableAt(x+1,y,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+1,y) end if finder.grid:isWalkableAt(x-1,y,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x-1,y) end end else -- Move along X-axis case if finder.grid:isWalkableAt(x+dx,y,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y) -- Forced neighbours are up and down ahead along X if (not finder.grid:isWalkableAt(x,y+1,finder.walkable)) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y+1) end if (not finder.grid:isWalkableAt(x,y-1,finder.walkable)) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y-1) end end -- : In case diagonal moves are forbidden if not finder.allowDiagonal then if finder.grid:isWalkableAt(x,y+1,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y+1) end if finder.grid:isWalkableAt(x,y-1,finder.walkable) then neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y-1) end end end end return neighbours end -- Node do not have parent, we return all neighbouring nodes return finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel) end local function jump(finder, node, parent, endNode) if not node then return end local x,y = node.x, node.y local dx, dy = x - parent.x,y - parent.y -- If the node to be examined is unwalkable, return nil if not finder.grid:isWalkableAt(x,y,finder.walkable) then return end -- If the node to be examined is the endNode, return this node if node == endNode then return node end -- Diagonal search case if dx~=0 and dy~=0 then -- Current node is a jump point if one of his leftside/rightside neighbours ahead is forced if (finder.grid:isWalkableAt(x-dx,y+dy,finder.walkable) and (not finder.grid:isWalkableAt(x-dx,y,finder.walkable))) or (finder.grid:isWalkableAt(x+dx,y-dy,finder.walkable) and (not finder.grid:isWalkableAt(x,y-dy,finder.walkable))) then return node end else -- Search along X-axis case if dx~=0 then if finder.allowDiagonal then -- Current node is a jump point if one of his upside/downside neighbours is forced if (finder.grid:isWalkableAt(x+dx,y+1,finder.walkable) and (not finder.grid:isWalkableAt(x,y+1,finder.walkable))) or (finder.grid:isWalkableAt(x+dx,y-1,finder.walkable) and (not finder.grid:isWalkableAt(x,y-1,finder.walkable))) then return node end else -- : in case diagonal moves are forbidden if finder.grid:isWalkableAt(x+1,y,finder.walkable) or finder.grid:isWalkableAt(x-1,y,finder.walkable) then return node end end else -- Search along Y-axis case -- Current node is a jump point if one of his leftside/rightside neighbours is forced if finder.allowDiagonal then if (finder.grid:isWalkableAt(x+1,y+dy,finder.walkable) and (not finder.grid:isWalkableAt(x+1,y,finder.walkable))) or (finder.grid:isWalkableAt(x-1,y+dy,finder.walkable) and (not finder.grid:isWalkableAt(x-1,y,finder.walkable))) then return node end else -- : in case diagonal moves are forbidden if finder.grid:isWalkableAt(x,y+1,finder.walkable) or finder.grid:isWalkableAt(x,y-1,finder.walkable) then return node end end end end -- Recursive horizontal/vertical search if dx~=0 and dy~=0 then if jump(finder,finder.grid:getNodeAt(x+dx,y),node,endNode) then return node end if jump(finder,finder.grid:getNodeAt(x,y+dy),node,endNode) then return node end end -- Recursive diagonal search if finder.allowDiagonal then if finder.grid:isWalkableAt(x+dx,y,finder.walkable) or finder.grid:isWalkableAt(x,y+dy,finder.walkable) then return jump(finder,finder.grid:getNodeAt(x+dx,y+dy),node,endNode) end end end local function identifySuccessors(finder,node,endNode,toClear, tunnel) -- Gets the valid neighbours of the given node -- Looks for a jump point in the direction of each neighbour local neighbours = findNeighbours(finder,node, tunnel) for i = #neighbours,1,-1 do local skip = false local neighbour = neighbours[i] local jumpNode = jump(finder,neighbour,node,endNode) -- : in case a diagonal jump point was found in straight mode, skip it. if jumpNode and not finder.allowDiagonal then if ((jumpNode.x ~= node.x) and (jumpNode.y ~= node.y)) then skip = true end end -- Performs regular A-star on a set of jump points if jumpNode and not skip then -- Update the jump node and move it in the closed list if it wasn't there if not jumpNode.closed then local extraG = Heuristics.EUCLIDIAN(jumpNode.x-node.x,jumpNode.y-node.y) local newG = node.g + extraG if not jumpNode.opened or newG < jumpNode.g then toClear[jumpNode] = true -- Records this node to reset its properties later. jumpNode.g = newG jumpNode.h = jumpNode.h or (finder.heuristic(jumpNode.x-endNode.x,jumpNode.y-endNode.y)) jumpNode.f = jumpNode.g+jumpNode.h jumpNode.parent = node if not jumpNode.opened then finder.openList:push(jumpNode) jumpNode.opened = true if not step_first then step_first = true end else finder.openList:heapify(jumpNode) end end end end end end local function JUMPPOINTSEARCH(finder, startNode, endNode, toClear, tunnel) step_first = false startNode.g, startNode.f = 0,0 finder.openList:clear() finder.openList:push(startNode) startNode.opened = true toClear[startNode] = true local node while not finder.openList:empty() do -- Pops the lowest F-cost node, moves it in the closed list node = finder.openList:pop() node.closed = true -- If the popped node is the endNode, return it if node == endNode then return node end -- otherwise, identify successors of the popped node identifySuccessors(finder, node, endNode, toClear, tunnel) end -- No path found, return nil return nil end ------------------------------ Grid Module (global) ------------------------------ -- See: ... local pairs = pairs local next = next local otype = type local _grids = {} -- Local helpers -- Is i and integer ? local isInt = function(i) return otype(i) =='number' and floor(i)==i end -- Override type to report integers local type = function(v) if isInt(v) then return 'int' end return otype(v) end -- Real count of for values in an array local size = function(t) local count = 0 for k,v in pairs(t) do count = count+1 end return count end -- Checks array contents local check_contents = function(t,...) local n_count = size(t) if n_count < 1 then return false end local init_count = t[0] and 0 or 1 local n_count = (t[0] and n_count-1 or n_count) local types = {...} if types then types = table.concat(types) end for i=init_count,n_count,1 do if not t[i] then return false end if types then if not types:match(type(t[i])) then return false end end end return true end -- Checks if m is a regular map local function isMap(m) if not check_contents(m, 'table') then return false end local lsize = size(m[next(m)]) for k,v in pairs(m) do if not check_contents(m[k], 'string', 'int') then return false end if size(v)~=lsize then return false end end return true end -- Is arg a valid string map local function isStringMap(s) if type(m) ~= 'string' then return false end local w for row in s:gmatch('[^\n\r]+') do if not row then return false end w = w or #row if w ~= #row then return false end end return true end -- Parses a map local function parseStringMap(str) local map = {} local w, h for line in str:gmatch('[^\n\r]+') do if line then w = not w and #line or w if not (#line == w) then error('Error parsing map, rows must have the same size!') end h = (h or 0) + 1 map[h] = {} for char in line:gmatch('.') do map[h][#map[h]+1] = char end end end return map end -- Postprocessing : Get map bounds local function getBounds(map) local min_bound_x, max_bound_x local min_bound_y, max_bound_y for y in pairs(map) do min_bound_y = not min_bound_y and y or (ymax_bound_y and y or max_bound_y) for x in pairs(map[y]) do min_bound_x = not min_bound_x and x or (xmax_bound_x and x or max_bound_x) end end return min_bound_x,max_bound_x,min_bound_y,max_bound_y end -- Preprocessing local function buildGrid(map) local min_bound_x, max_bound_x local min_bound_y, max_bound_y local nodes = {} for y in pairs(map) do min_bound_y = not min_bound_y and y or (ymax_bound_y and y or max_bound_y) nodes[y] = {} for x in pairs(map[y]) do min_bound_x = not min_bound_x and x or (xmax_bound_x and x or max_bound_x) nodes[y][x] = Node(x,y) end end return nodes, (min_bound_x or 0), (max_bound_x or 0), (min_bound_y or 0), (max_bound_y or 0) end -- Checks if a value is out of and interval [lowerBound,upperBound] local function outOfRange(i,lowerBound,upperBound) return (i< lowerBound or i > upperBound) end -- Offsets for straights moves local straightOffsets = { {x = 1, y = 0} --[[W]], {x = -1, y = 0}, --[[E]] {x = 0, y = 1} --[[S]], {x = 0, y = -1}, --[[N]] } -- Offsets for diagonal moves local diagonalOffsets = { {x = -1, y = -1} --[[NW]], {x = 1, y = -1}, --[[NE]] {x = -1, y = 1} --[[SW]], {x = 1, y = 1}, --[[SE]] } -- Specialized grids -- Inits a preprocessed grid local function PreProcessGrid(newGrid, map) newGrid.map = map newGrid.nodes, newGrid.min_bound_x, newGrid.max_bound_x, newGrid.min_bound_y, newGrid.max_bound_y = buildGrid(newGrid.map) newGrid.width = (newGrid.max_bound_x-newGrid.min_bound_x)+1 newGrid.height = (newGrid.max_bound_y-newGrid.min_bound_y)+1 function newGrid:getNodeAt(x,y) return self.nodes[y] and self.nodes[y][x] or nil end return newGrid end -- Inits a postprocessed grid local function PostProcessGrid(newGrid, map) newGrid.map = map newGrid.nodes = {} newGrid.min_bound_x, newGrid.max_bound_x, newGrid.min_bound_y, newGrid.max_bound_y = getBounds(newGrid.map) newGrid.width = (newGrid.max_bound_x-newGrid.min_bound_x)+1 newGrid.height = (newGrid.max_bound_y-newGrid.min_bound_y)+1 function newGrid:getNodeAt(x,y) if not x or not y then return end if outOfRange(x,self.min_bound_x,self.max_bound_x) then return end if outOfRange(y,self.min_bound_y,self.max_bound_y) then return end if not self.nodes[y] then self.nodes[y] = {} end if not self.nodes[y][x] then self.nodes[y][x] = Node(x,y) end return self.nodes[y][x] end return newGrid end local Grid = function(map, processOnDemand) map = type(map)=='string' and parseStringMap(map) or map if not (isMap(map) or isStringMap(map)) then error('Bad argument #1. Not a valid map') end if not (type(processOnDemand) == 'boolean' or not processOnDemand) then error(('Bad argument #2. Expected \'boolean\', got %s.'):format(type(processOnDemand))) end local newGrid = {} function newGrid:isWalkableAt(x, y, walkable) local nodeValue = self.map[y] and self.map[y][x] if nodeValue then if not walkable then return true end else return false end if self.__eval then return walkable(nodeValue) end return (nodeValue == walkable) end function newGrid:getWidth() return self.width end function newGrid:getHeight() return self.height end function newGrid:getMap() return self.map end function newGrid:getNodes() return self.nodes end function newGrid:getNeighbours(node, walkable, allowDiagonal, tunnel) local neighbours = {} for i = 1,#straightOffsets do local n = self:getNodeAt( node.x + straightOffsets[i].x, node.y + straightOffsets[i].y ) if n and self:isWalkableAt(n.x, n.y, walkable) then neighbours[#neighbours+1] = n end end if not allowDiagonal then return neighbours end tunnel = not not tunnel for i = 1,#diagonalOffsets do local n = self:getNodeAt( node.x + diagonalOffsets[i].x, node.y + diagonalOffsets[i].y ) if n and self:isWalkableAt(n.x, n.y, walkable) then if tunnel then neighbours[#neighbours+1] = n else local skipThisNode = false local n1 = self:getNodeAt(node.x+diagonalOffsets[i].x, node.y) local n2 = self:getNodeAt(node.x, node.y+diagonalOffsets[i].y) if ((n1 and n2) and not self:isWalkableAt(n1.x, n1.y, walkable) and not self:isWalkableAt(n2.x, n2.y, walkable)) then skipThisNode = true end if not skipThisNode then neighbours[#neighbours+1] = n end end end end return neighbours end function newGrid:iter(lx,ly,ex,ey) local min_x = lx or self.min_bound_x local min_y = ly or self.min_bound_y local max_x = ex or self.max_bound_x local max_y = ey or self.max_bound_y local x, y y = min_y return function() x = not x and min_x or x+1 if x>max_x then x = min_x y = y+1 end if y > max_y then y = nil end return self.nodes[y] and self.nodes[y][x] or self:getNodeAt(x,y) end end function newGrid:each(f,...) for node in self:iter() do f(node,...) end end function newGrid:eachRange(lx,ly,ex,ey,f,...) for node in self:iter(lx,ly,ex,ey) do f(node,...) end end function newGrid:imap(f,...) for node in self:iter() do node = f(node,...) end end function newGrid:imapRange(lx,ly,ex,ey,f,...) for node in self:iter(lx,ly,ex,ey) do node = f(node,...) end end _grids[newGrid] = true if processOnDemand then return PostProcessGrid(newGrid,map) end return PreProcessGrid(newGrid,map) end ------------------------------ Pathfinder Module (global) ------------------------------ -- See: http://en.wikipedia.org/wiki/Pathfinding local _VERSION = "1.8.1" local _RELEASEDATE = "03/01/2013" local function isAGrid(grid) return _grids[grid] or false end local Finders = { ['ASTAR'] = ASTARSEARCH, ['DIJKSTRA'] = DIJKSTRASEARCH, ['BFS'] = BFSEARCH, ['DFS'] = DFSEARCH, ['JPS'] = JUMPPOINTSEARCH, } -- Collect keys in an array local function collect_keys(t) local keys = {} for k,v in pairs(t) do keys[#keys+1] = k end return keys end local toClear = {} local function reset() for node in pairs(toClear) do node.g, node.h, node.f = nil, nil, nil node.opened, node.closed, node.parent = nil, nil, nil end toClear = {} end -- Keeps track of the last computed path cost local lastPathCost = 0 -- Availables search modes local searchModes = {['DIAGONAL'] = true, ['ORTHOGONAL'] = true} local function traceBackPath(finder, node, startNode) local path = Path() path.grid = finder.grid lastPathCost = node.f or path:getLength() while true do if node.parent then t_insert(path,1,node) node = node.parent else t_insert(path,1,startNode) return path end end end local Pathfinder = function(grid, finderName, walkable) local newPathfinder = {} function newPathfinder:setGrid(grid) if not (isAGrid(grid)) then error('Bad argument #1. Expected a \'grid\' object') end self.grid = grid self.grid.__eval = self.walkable and type(self.walkable) == 'function' return self end function newPathfinder:getGrid() return self.grid end function newPathfinder:setWalkable(walkable) if not (('stringintfunctionnil'):match(type(walkable))) then error(('Bad argument #2. Expected \'string\', \'number\' or \'function\', got %s.'):format(type(walkable))) end self.walkable = walkable self.grid.__eval = type(self.walkable) == 'function' return self end function newPathfinder:getWalkable() return self.walkable end function newPathfinder:setFinder(finderName) local finderName = finderName if not finderName then if not self.finder then finderName = 'ASTAR' else return end end if not (Finders[finderName]) then error('Not a valid finder name!') end self.finder = finderName return self end function newPathfinder:getFinder() return self.finder end function newPathfinder:getFinders() return collect_keys(Finders) end function newPathfinder:setHeuristic(heuristic) if not (Heuristics[heuristic] or (type(heuristic) == 'function')) then error('Not a valid heuristic!') end self.heuristic = Heuristics[heuristic] or heuristic return self end function newPathfinder:getHeuristic() return self.heuristic end function newPathfinder:getHeuristics() return collect_keys(Heuristics) end function newPathfinder:setMode(mode) if not (searchModes[mode]) then error('Invalid mode') end self.allowDiagonal = (mode == 'DIAGONAL') return self end function newPathfinder:getMode() return (self.allowDiagonal and 'DIAGONAL' or 'ORTHOGONAL') end function newPathfinder:getModes() return collect_keys(searchModes) end function newPathfinder:version() return _VERSION, _RELEASEDATE end function newPathfinder:getPath(startX, startY, endX, endY, tunnel) reset() local startNode = self.grid:getNodeAt(startX, startY) local endNode = self.grid:getNodeAt(endX, endY) if not (startNode) then error(('Invalid location [%d, %d]'):format(startX, startY)) end if not (endNode and self.grid:isWalkableAt(endX, endY)) then error(('Invalid or unreachable location [%d, %d]'):format(endX, endY)) end local _endNode = Finders[self.finder](self, startNode, endNode, toClear, tunnel) if _endNode then return traceBackPath(self, _endNode, startNode), lastPathCost end lastPathCost = 0 return nil, lastPathCost end newPathfinder:setGrid(grid) newPathfinder:setFinder(finderName) newPathfinder:setWalkable(walkable) newPathfinder:setMode('ORTHOGONAL') newPathfinder:setHeuristic('MANHATTAN') newPathfinder.openList = Heap() return newPathfinder end ------------------------------ Spawns module into the global env ------------------------------ Jumper = { Heuristics = Heuristics, Node = Node, Path = Path, Grid = Grid, Pathfinder = Pathfinder } -- #### #### ####