--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 Albatros: --AI by Albatros: rememberPassengers = {} blacklist = {} rememberMap = nil --Name of next Passenger currentPassenger = {} globneighboors = {} function removePassenger(name) --koordinaten des passagiers suchen for key,container in pairs( rememberPassengers ) do if (key == name) then -- print ("remove:" .. tablelength(rememberMap[container.x][container.y].passengers)) rememberMap[container.x][container.y].passengers[name]=nil -- print ("remove:" .. tablelength(rememberMap[container.x][container.y].passengers)) end end rememberPassengers[name] = nil end function addpassenger (name,x,y,destx,desty,dis,dir) rememberPassengers[name] = {x=x,y=y,destX=destX,destY=destY,dist = dis,dir=dir,iname=name} rememberMap[x][y].passengers[name]= {x=x,y=y,destX=destX,destY=destY,iname=name,dist=dis,dir=dir} end -- Wird aufgerufen, wenn das Spiel startet function ai.init(map, money) -- print("Albatros starting") -- print("Credits: " .. money) rememberMap = map -- print(getNumberOfLines()) --prepare map for pathfinding for x = 1, map.width, 1 do for y = 1, map.height, 1 do rememberMap[x][y] = {x=x,y=y,content = map[x][y],passengers={},rememberWeg={},neighbor,hotness=0} end end for x = 1, map.width, 1 do for y = 1, map.height, 1 do neighbor_nodes({x=x,y=y},rememberMap) end end end -- called when another player's train picks up a passenger function ai.passengerBoarded(train, passengerName) -- print ("Boarded: " .. passengerName) removePassenger(passengerName) end -- Wird aufgerufen, wenn der Zug am Ziel des Passagiers ankommt function ai.foundDestination(train) -- print ("found Destination" .. train.passenger.name) currentPassenger[train.passenger.name] =nil removePassenger(train.passenger.name) dropPassenger(train) end -- Wird aufgerufen, wenn eine Richtungswahl ansteht -- train [table] -- possibleDirections [table] function ai.chooseDirection(train, possibleDirections) return chooseMyDirection(train, possibleDirections) end -- Wird aufgerufen, wenn der Zug blockiert wird -- (Beispielsweise durch einen anderen Zug) function ai.blocked(train, possibleDirections, lastDirection) local old = lastDirection local new = lastDirection while (old == new) do new = chooseRandom(possibleDirections) end return new end -- Wird aufgerufen, wenn der Zug an einem Passagier vorbeikommt function ai.foundPassengers(train,passengers) local pass = nil local dirpass =nil local dirpassh =nil local i = 1 local shortest = 9999--passagier auswählen local shortestdir = 9999--passagier auswählen local shortestdirh = 9999--passagier auswählen while i <= #passengers do rpass=rememberPassengers[passengers[i].name] d = rpass.dist ---- print ("Distance: " .. d) if (d < shortest) then shortest = d pass = passengers[i] end if (rpass.dir == train.dir)and(d < shortestdir) then shortestdir = d dirpass = passengers[i] end if (rpass.dir == train.dir)and(d < shortestdirh) and (rememberMap[rpass.destX][rpass.destY].hotness>5) then shortestdirh = d dirpassh = passengers[i] end i=i+1 end if (train.passenger==nil) then if (dirpassh) then currentPassenger[dirpassh.name] = rememberPassengers[dirpassh.name] removePassenger(dirpassh.name) return dirpassh end if (dirpass) then currentPassenger[dirpass.name] = rememberPassengers[dirpass.name] removePassenger(dirpass.name) return dirpass end if (pass) then currentPassenger[pass.name] = rememberPassengers[pass.name] removePassenger(pass.name) return pass end else print ("full train") if (dirpassh) then --print ("dirpassh "..dirpassh.name) if (rememberPassengers[dirpassh.name].dist < currentPassenger[train.passenger.name].dist) then currentPassenger[train.passenger.name]=nil dropPassenger(train) currentPassenger[dirpassh.name] = rememberPassengers[dirpassh.name] removePassenger(dirpassh.name) return dirpassh end end if (dirpass) then --print ("dirpass "..dirpass.name.. " dirpass "..rememberPassengers[dirpass.name].dist.." cur ".. currentPassenger[train.passenger.name].dist) if (rememberPassengers[dirpass.name].dist < currentPassenger[train.passenger.name].dist) then currentPassenger[train.passenger.name]=nil dropPassenger(train) currentPassenger[dirpass.name] = rememberPassengers[dirpass.name] removePassenger(dirpass.name) return dirpass end end end end function buytrain() --koordinaten des passagiers suchen local dis = 9999 local start = nil for key,container in pairs( rememberPassengers ) do if ((container.dist < dis)and(container.dist<999)) then dis = container.dist start =container end end if (start ~= nil) then -- print ("Start at " .. start.x .. "/"..start.y.." with dist " .. start.dist ) buyTrain(start.x, start.y,start.dir) end end function ai.enoughMoney(money) buytrain() end -- Wird aufgerufen, wenn ein neuer Fahrgast erscheint function ai.newPassenger(name, x, y, destX, destY) ---- print("new pass") local wegl = nil local dir = "U" gtrain={x=x,y=y} wegl = path ( rememberMap[x][y], rememberMap[destX][destY], rememberMap, ignore_cache, is_valid_node ) dis = 999 if (wegl == nil) then else if (#wegl>1)then dir=getdirofpath(wegl,1) end dis = #wegl end ---- print (tablelength(rememberMap[x][y].passengers)) rememberPassengers[name] = {x=x,y=y,destX=destX,destY=destY,dist = dis,dir=dir,iname=name} rememberMap[x][y].passengers[name]= {x=x,y=y,destX=destX,destY=destY,iname=name,dist=dis,dir=dir} rememberMap[x][y].hotness = rememberMap[x][y].hotness + 1 --print (x .. " ".. y.. "menge: ".. tablelength(rememberMap[x][y].passengers).. "hot: "..rememberMap[x][y].hotness) if (getMoney() >= 25) then -- Ein Zug kostet 25 Credits buytrain() end end -- ------------ -- LOCAL HELPER -- ------------ function tablelength(T) local count = 0 for _ in pairs(T) do count = count + 1 end return count end function printTable(table, lvl) lvl = lvl or 0 if lvl > 2 then return end for k, v in pairs(table) do if type(v) == "table" then -- printTable(table, lvl + 1) else str = "" for i = 1,lvl do str = str .. "\t" end -- print(str, k, v) end end end function chooseRandom(possibleDirections) tbl = {} if possibleDirections["N"] then table.insert(tbl,"N") end if possibleDirections["S"] then table.insert(tbl,"S") end if possibleDirections["E"] then table.insert(tbl,"E") end if possibleDirections["W"] then table.insert(tbl,"W") end return tbl[random(#tbl)] end function invertdir(dir) if (dir == "N") then return "S" end if (dir == "E") then return "W" end if (dir == "S") then return "N" end if (dir == "W") then return "E" end end -- Wenn ein Passagier an Board ist wird versucht diesen ans Ziel zu bringen function chooseMyDirection(train, possibleDirections) gtrain={x=train.x,y=train.y} local weg if train.passenger then ---- print("train.passenger destination:", train.passenger.destX, train.passenger.destY) print("train.pos:", train.x, train.y) weg = path ( rememberMap[train.nextX][train.nextY], rememberMap[train.passenger.destX][train.passenger.destY], rememberMap, ignore_cache, is_valid_node ) if (weg == nil) then return chooseRandom(possibleDirections) else if (#weg > 1) then -- print("Kreuzung wird uberfahren") currentPassenger[train.passenger.name].dist = #weg dir = getdirofpath(weg,1) if (dir == invertdir(train.dir)) then print ("Turn needed ".. train.dir) local wegdir = a_star_dir({x=train.x,y=train.y,dir=train.dir},{x=train.x,y=train.y,dir=invertdir(train.dir)},rememberMap) if (wegdir) then dir = getdirofpath(wegdir,2) end end return dir else --krezung = ziel lpass = nil if (tablelength(rememberMap[train.nextX][train.nextY].passengers) >0) then -- print "Fahrgast im naechsten feld!" i = 1 ldist=9999 for key,container in pairs( rememberMap[train.nextX][train.nextY].passengers ) do if (container.dist < ldist) then lpass = rememberMap[train.nextX][train.nextY].passengers[key] ldist =lpass.dist end end end if (lpass== nil)then --kein passagier ---- print (#weg) ---- print ("wegfindung Passagier:" .. weg[#weg].x .. " " .. weg[#weg].y) -- print ("Find Pass running") weg = findPass ( rememberMap[train.nextX][train.nextY], rememberMap,is_valid_node ) -- print ("Find Pass finished") if (weg==nil) then else return getdirofpath(weg,1) end else return lpass.dir end end end else --kein passagier ---- print (#weg) ---- print ("wegfindung Passagier:" .. weg[#weg].x .. " " .. weg[#weg].y) if (tablelength(rememberMap[train.x][train.y].passengers) >0) then -- print "Fahrgast im naechsten feld!" i = 1 ldist=9999 lpass = nil for key,container in pairs( rememberMap[train.nextX][train.nextY].passengers ) do if (container.dist < ldist) then lpass = rememberMap[train.nextX][train.nextY].passengers[key] ldist =lpass.dist end end if (lpass)then return lpass.dir end else -- print ("Find Pass running") weg = findPass ( rememberMap[train.nextX][train.nextY], rememberMap,is_valid_node ) -- print ("Find Pass finished") if (weg==nil) then else return getdirofpath(weg,1) end end end end function getdirofpath(weg,i) if(#weg > i) then -- print ("i: "..weg[i].x.."/"..weg[i].y .." i+1: "..weg[i+1].x.."/"..weg[i+1].y) if (weg[i].x < weg[i+1].x) and (weg[i].y == weg[i+1].y) then --train.dir = "E" return "E" end if (weg[i].x > weg[i+1].x) and (weg[i].y == weg[i+1].y) then --train.dir = "W" return "W" end if (weg[i].x == weg[i+1].x) and (weg[i].y < weg[i+1].y) then --train.dir = "S" return "S" end if (weg[i].x == weg[i+1].x) and (weg[i].y > weg[i+1].y) then --train.dir = "N" return "N" end end end --pathfinding -- ====================================================================== -- Copyright (c) 2012 RapidFire Studio Limited -- All Rights Reserved. -- http://www.rapidfirestudio.com -- Permission is hereby granted, free of charge, to any person obtaining -- a copy of this software and associated documentation files (the -- "Software"), to deal in the Software without restriction, including -- without limitation the rights to use, copy, modify, merge, publish, -- distribute, sublicense, and/or sell copies of the Software, and to -- permit persons to whom the Software is furnished to do so, subject to -- the following conditions: -- The above copyright notice and this permission notice shall be -- included in all copies or substantial portions of the Software. -- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. -- IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY -- CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, -- TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE -- SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -- ====================================================================== ---------------------------------------------------------------- -- local variables ---------------------------------------------------------------- local INF = 1/0 local cachedPaths = nil ---------------------------------------------------------------- -- local functions ---------------------------------------------------------------- function dist ( x1, y1, x2, y2 ) return math.sqrt ( math.pow ( x2 - x1, 2 ) + math.pow ( y2 - y1, 2 ) ) end function dist_between ( nodeA, nodeB ) return dist ( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) end function heuristic_cost_estimate ( nodeA, nodeB ) return dist ( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) end function lowest_f_score ( set, f_score ) local lowest, bestNode = INF, nil for _, node in ipairs ( set ) do local score = f_score [ node ] if score < lowest then lowest, bestNode = score, node end end return bestNode end function lowest_g_score ( set, g_score ) local lowest, bestNode = INF, nil for _, node in ipairs ( set ) do local score = g_score [ node ] if score < lowest then lowest, bestNode = score, node end end return bestNode end function neighbor_nodes ( theNode, nodes ) local neighbors = {} local x = theNode.x local y = theNode.y local node if (rememberMap[x][y].neighbor==nil) then node = nodes[x+1][y] if (node ~= nil) then if (node.content == "C") then ---- print ("count n: ".." x "..node.x.." y "..node.y) table.insert ( neighbors, node ) end end node = nodes[x-1][y] if (node ~= nil) then if (node.content == "C") then ---- print ("count n: ".." x "..node.x.." y "..node.y) table.insert ( neighbors, node ) end end node = nodes[x][y+1] if (node ~= nil) then if (node.content == "C") then ---- print ("count n: ".." x "..node.x.." y "..node.y) table.insert ( neighbors, node ) end end node = nodes[x][y-1] if (node ~= nil) then if (node.content == "C") then ---- print ("count n: ".." x "..node.x.." y "..node.y) table.insert ( neighbors, node ) end end rememberMap[x][y].neighbor =neighbors end return rememberMap[x][y].neighbor end function neighbor_nodes_dir ( theNode, nodes ) local neighbors = {} local x = theNode.x local y = theNode.y local node local startdir = theNode.dir node = nodes[x+1][y] if (node ~= nil) then if (node.content == "C") then if (startdir ~= "W") then if(#rememberMap[x+1][y].neighbor==1) then node.dir = "W" else node.dir = "E" end --print ("W: ".." x "..node.x.." y "..node.y.."node.dir "..node.dir) table.insert ( neighbors, {x=node.x,y=node.y,dir=node.dir} ) end end end node = nodes[x-1][y] if (node ~= nil) then if (node.content == "C") then if (startdir ~= "E") then if(#rememberMap[x-1][y].neighbor==1) then node.dir = "E" else node.dir = "W" end --print ("E: ".." x "..node.x.." y "..node.y.."node.dir "..node.dir) table.insert ( neighbors, {x=node.x,y=node.y,dir=node.dir} ) end end end node = nodes[x][y+1] if (node ~= nil) then if (node.content == "C") then if (startdir ~= "N") then if(#rememberMap[x][y+1].neighbor==1) then node.dir = "N" else node.dir = "S" end --print ("N: ".." x "..node.x.." y "..node.y.."node.dir "..node.dir) table.insert ( neighbors, {x=node.x,y=node.y,dir=node.dir} ) end end end node = nodes[x][y-1] if (node ~= nil) then if (node.content == "C") then if (startdir ~= "S") then if(#rememberMap[x][y-1].neighbor==1) then node.dir = "S" else node.dir = "N" end --print ("S: ".." x "..node.x.." y "..node.y.."node.dir "..node.dir) table.insert ( neighbors, {x=node.x,y=node.y,dir=node.dir} ) end end end return neighbors end function not_in_dir ( set, theNode ) for _, node in ipairs ( set ) do if ((node.x == theNode.x) and (node.y == theNode.y) and (node.dir == theNode.dir)) then return false end end return true end function not_in ( set, theNode ) for _, node in ipairs ( set ) do if node == theNode then return false end end return true end function remove_node ( set, theNode ) for i, node in ipairs ( set ) do if node == theNode then set [ i ] = set [ #set ] set [ #set ] = nil break end end end function unwind_path ( flat_path, lmap, current_node ) if lmap [ current_node ] then table.insert ( flat_path, 1, lmap [ current_node ] ) return unwind_path ( flat_path, lmap, lmap [ current_node ] ) else return flat_path end end function checkfortimeout() linesUsed, lineMax = getNumberOfLines(); ---- print (linesUsed / lineMax) if (linesUsed > lineMax *0.9) then return true end return false end function prozentused() linesUsed, lineMax = getNumberOfLines(); return (linesUsed / lineMax) end ---------------------------------------------------------------- -- pathfinding functions ---------------------------------------------------------------- function a_star ( start, goal, nodes, valid_node_func ) local i = 0 local closedset = {} local openset = { start } local came_from = {} if valid_node_func then is_valid_node = valid_node_func end local g_score, f_score = {}, {} g_score [ start ] = 0 f_score [ start ] = g_score [ start ] + heuristic_cost_estimate ( start, goal ) while #openset > 0 do prozused = prozentused() if (prozused>0.85) then -- print ("timeout runs: "..i) return nil end local current = lowest_f_score ( openset, f_score ) ---- print ("CUrrent" .. current.x .. " " ..current.y.."g "..g_score[current].."f ".. f_score[current]) if (current == goal) then local path = unwind_path ( {}, came_from, goal ) table.insert ( path, goal ) return path end if (prozused > .7) then if (rememberMap[current.x][current.y].rememberWeg[goal.x] == nil) then else if(rememberMap[current.x][current.y].rememberWeg[goal.x][goal.y]==nil) then else local path = unwind_path ( {}, came_from, current ) table.insert ( path, current ) -- print("Zwischenziel gefunden <------------") return path end end end remove_node ( openset, current ) table.insert ( closedset, current ) --local neighbors = neighbor_nodes ( current, nodes ) local neighbors = rememberMap[current.x][current.y].neighbor i =i+1 for _, neighbor in ipairs ( neighbors ) do if not_in ( closedset, neighbor ) then local tentative_g_score = g_score [ current ] + 1--dist_between ( current, neighbor ) if not_in ( openset, neighbor ) or tentative_g_score < g_score [ neighbor ] then came_from [ neighbor ] = current g_score [ neighbor ] = tentative_g_score f_score [ neighbor ] = g_score [ neighbor ] + heuristic_cost_estimate ( neighbor, goal ) if not_in ( openset, neighbor ) then table.insert ( openset, neighbor ) end end end end end return nil -- no valid path end function a_star_dir ( start, goal, nodes) local i = 0 local closedset = {} local openset = { start } local came_from = {} local g_score, f_score = {}, {} g_score [ start ] = 0 g_score [goal]=0 --f_score [ start ] = g_score [ start ] + heuristic_cost_estimate ( start, goal ) while #openset > 0 do prozused = prozentused() if (prozused>0.95) then print ("timeout runs: "..i) return nil end local current = lowest_g_score ( openset, g_score ) --print ("CUrrent" .. current.x .. " " ..current.y.." g "..g_score[current].." dir ".. current.dir) --print ("Goal" .. goal.x .. " " ..goal.y.." dir ".. goal.dir) if (current.x == goal.x)and(current.y==goal.y)and (current.dir==goal.dir) then print("found") local path = unwind_path ( {}, came_from, current ) table.insert ( path, goal ) return path end remove_node ( openset, current ) table.insert ( closedset, current ) --print (current) local neighbors = neighbor_nodes_dir ( current, nodes ) --local neighbors = rememberMap[current.x][current.y].neighbor i =i+1 for _, neighbor in ipairs ( neighbors ) do if not_in_dir ( closedset, neighbor ) then local tentative_g_score = g_score [ current ] + dist_between ( current, neighbor ) if not_in_dir ( openset, neighbor ) or tentative_g_score < g_score [ neighbor ] then came_from [ neighbor ] = current g_score [ neighbor ] = tentative_g_score --f_score [ neighbor ] = g_score [ neighbor ] + heuristic_cost_estimate ( neighbor, goal ) if not_in_dir ( openset, neighbor ) then table.insert ( openset, neighbor ) end end end end end return nil -- no valid path end function findPass ( start, nodes, valid_node_func ) local closedset = {} local openset = { start } local came_from = {} if valid_node_func then is_valid_node = valid_node_func end local g_score = {} g_score [ start ] = 0 while #openset > 0 do if (checkfortimeout()) then -- print "Timeout" return nil end local current = lowest_g_score ( openset, g_score ) ---- print ("Current" .. current.x .. " " ..current.y .. " Anzahl: " .. tablelength(rememberMap[current.x][current.y].passengers)) if (tablelength(rememberMap[current.x][current.y].passengers) > 0) then--or (rememberMap[current.x][current.y].hotness >5)then local path = unwind_path ( {}, came_from, current ) table.insert ( path, current ) return path end remove_node ( openset, current ) table.insert ( closedset, current ) local neighbors = neighbor_nodes ( current, nodes ) for _, neighbor in ipairs ( neighbors ) do if not_in ( closedset, neighbor ) then local tentative_g_score = g_score [ current ] + dist_between ( current, neighbor ) if not_in ( openset, neighbor ) or tentative_g_score < g_score [ neighbor ] then came_from [ neighbor ] = current g_score [ neighbor ] = tentative_g_score if not_in ( openset, neighbor ) then table.insert ( openset, neighbor ) end end end end end return nil -- no valid path end ---------------------------------------------------------------- -- exposed functions ---------------------------------------------------------------- function clear_cached_paths () cachedPaths = nil end function distance ( x1, y1, x2, y2 ) return dist ( x1, y1, x2, y2 ) end function path ( start, goal, nodes, ignore_cache, valid_node_func ) if not cachedPaths then cachedPaths = {} end if not cachedPaths [ start ] then cachedPaths [ start ] = {} elseif cachedPaths [ start ] [ goal ] and not ignore_cache then ---- print "------------------------------Cache Treffer!" return cachedPaths [ start ] [ goal ] end ---- print "no cached path, start searching" weg = a_star ( start, goal, nodes, valid_node_func ) if (weg ~= nil) then --weg gefunden, merken für später if (rememberMap[start.x][start.y].rememberWeg[goal.x]==nil)then rememberMap[start.x][start.y].rememberWeg[goal.x]={} end ---- print ("RememberWeg von "..start.x.."/"..start.y.." bis "..goal.x.."/"..goal.y) rememberMap[start.x][start.y].rememberWeg[goal.x][goal.y] =weg cachedPaths[start][goal] = weg end return weg end