--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 honk: function neighbours(map, x, y) local links = {} if map[x-1][y] == "C" then table.insert(links, {x=x-1, y=y}) end if map[x+1][y] == "C" then table.insert(links, {x=x+1, y=y}) end if map[x][y-1] == "C" then table.insert(links, {x=x, y=y-1}) end if map[x][y+1] == "C" then table.insert(links, {x=x, y=y+1}) end return links end function randomDirection(possibleDirections, prevDirection) possibleDirections[prevDirection] = false local dirs = {} for dir, avail in pairs(possibleDirections) do if avail then table.insert(dirs, dir) end end return dirs[math.random(#dirs)] end choseDirectionAt = nil BLOCK_WAIT = 3 BLOCK_WAIT_PANIC = 15 function ai.blocked(train, possibleDirections, prevDirection) if trains[train.ID].choseDirectionAt == nil then print("woot? no direction chosen yet!") elseif trains[train.ID].choseDirectionAt + BLOCK_WAIT_PANIC < os.clock() then --try again at the beginning print("really really stuck since"..trains[train.ID].choseDirectionAt.."(".. (trains[train.ID].choseDirectionAt + BLOCK_WAIT_PANIC - os.clock()).."s): " .. train.ID .. " at "..train.x..":"..train.y.." -> "..train.nextX..":"..train.nextY) return randomDirection(possibleDirections, prevDirection) end local directions = {} local x = train.nextX local y = train.nextY if train.passenger ~= nil then local passenger = train.passenger if x == passenger.destX and y == passenger.destY then --TODO choose route to next passenger return randomDirection(possibleDirections, prevDirection) end for dir, avail in pairs(possibleDirections) do if avail then local nextX, nextY = getToNode(x, y, dir) local route = findRoute(nextX, nextY, x, y, passenger.destX, passenger.destY) directions[dir] = {} directions[dir].route = route directions[dir].dir = dir -- don't go around, when we have to loop anyway! if checkForLoop(x, y, route) then directions[dir] = nil end end end else --no passenger local passengersXY = {} for i,passenger in pairs(passengers) do passengersXY[passenger.x..":"..passenger.y] = passenger end local trainInfo = trains[train.ID] if trainInfo == nil then --no route chosen yet return randomDirection(possibleDirections, prevDirection) end local plannedRoute = trainInfo.plannedRoute local plannedTarget = trainInfo.plannedTarget for dir, avail in pairs(possibleDirections) do if avail then local nextX, nextY = getToNode(x, y, dir) local route = findRoute(nextX, nextY, x, y, plannedTarget.x, plannedTarget.y) directions[dir] = {} directions[dir].route = route directions[dir].dir = dir local nextPassenger = #route for i = #route, 1, -1 do node = route[i] if passengersXY[node.x..":"..node.y] ~= nil then --there's a passenger earlier nextPassenger = #route - i break end end while #route - nextPassenger > 0 do table.remove(route, 1) end -- don't go around, when we have to loop anyway! if checkForLoop(x, y, route) then directions[dir] = nil end end end end bestChoice = nil for dir, dirRoute in pairs(directions) do local quality = 0 if dir == prevDirection then quality = BLOCK_WAIT end quality = quality + #dirRoute.route dirRoute.quality = quality if bestChoice == nil or bestChoice.quality > quality then bestChoice = dirRoute end end if bestChoice ~= nil then return bestChoice.dir end end function checkForLoop(x, y, route) local loop = false --don't allow going there, if this route leads over this point again! for i,node in pairs(route) do if node.x == x and node.y == y then return true end end return false end function mapToGraph(map) --printMap(map) local nodes = {} local firstNode = nil for x = 1, map.width do nodes[x] = {} visitedNodes[x] = {} graphNodes[x] = {} for y = 1, map.height do graphNodes[x][y] = {} visitedNodes[x][y] = {} if map[x][y] == "C" then local links = neighbours(map, x,y) local node = {} node.links = links node.x = x node.y = y nodes[x][y] = node if firstNode == nil and #node.links >= 2 then firstNode = node end --endnodes: 1->2 --straight: 1->1 2->2 --point: 1-1,1 2->2,2 end end end --print("left: ", getNumberOfLines()) graph = createGraph(nodes, firstNode, firstNode.links[1]) end graph = nil visitedNodes = {} graphNodes = {} X = 5 Y = 1 --todo split into parts when too large function createGraph(nodes, node, from) if visitedNodes[node.x][node.y][from.x .. from.y] ~= nil then return visitedNodes[node.x][node.y][from.x .. from.y] end local graphNode = {} graphNode.x = node.x graphNode.y = node.y graphNode.link = {} visitedNodes[node.x][node.y][from.x .. from.y] = graphNode for i, link in ipairs(node.links) do if not (link.x == from.x and link.y == from.y and #node.links > 1) then -- can't turn local target = createGraph(nodes, nodes[link.x][link.y], node) table.insert(graphNode.link, target) end end graphNodes[graphNode.x][graphNode.y][from.x ..":".. from.y] = graphNode return graphNode end function printMap(map) str = {} for j = 1, map.height do str[j] = "" for i = 1, map.width do if map[i][j] then str[j] = str[j] .. map[i][j] .. " " else str[j] = str[j] .. "- " end end end for i = 1, #str do print(str[i]) end end originalMap = nil initialBuy = 0 function ai.init(map, money) originalMap = map mapToGraph(map) initialBuy = money/25 --[[while money>=25 do buyTrain(map.width/2,map.height/2) money = money - 25 end--]] end function ai.newTrain(train) trains[train.ID] = {} trainDelivered = os.clock() end trains = {} comparisonPosition = {} activeTrain = -1 function ai.chooseDirection(train, possibleDirections) trains[train.ID].choseDirectionAt = os.clock() if train.passenger ~= nil then if train.passenger.destX ~= train.nextX or train.passenger.destY ~= train.nextY then local route = findRoute(train.nextX, train.nextY, train.x, train.y,train.passenger.destX, train.passenger.destY) --local dir = findRouteOld(train, train.passenger) if #route == 0 then print("null route: ("..train.x..":"..train.y..")"..train.nextX..":"..train.nextY.." to "..train.passenger.destX..":"..train.passenger.destY) end local dir = getDirection(train.nextX, train.nextY, route[#route].x, route[#route].y) return dir end else if trains[train.ID].plannedTarget ~= nil then --remove in case we change target trains[train.ID].plannedTarget.pickingUpAt[train.ID] = nil end comparisonPosition.x = train.nextX comparisonPosition.y = train.nextY activeTrain = train.ID table.sort(passengers, comparePassengers) --print("timeleft: ", getNumberOfLines()) local minDist = 9999 for i = 1, math.min(5, #passengers) do if getNumberOfLines() > 4000 then break end local route = findRoute(train.nextX, train.nextY, train.x, train.y, passengers[i].x, passengers[i].y) --print ("route length to:", passengers[i].x..":"..passengers[i].y, #route) if #route + vipFactor(passengers[i]) + pickupFactor(passengers[i], #route) < minDist then minDist = #route + vipFactor(passengers[i]) + pickupFactor(passengers[i], #route) train.plannedRoute = route train.plannedTarget = passengers[i] end end if train.plannedRoute ~= nil then if #train.plannedRoute == 0 then --reaching pickup point - go to passenger's target train.plannedRoute = findRoute(train.nextX, train.nextY, train.x, train.y,train.passenger.destX, train.passenger.destY) return end local route = train.plannedRoute local dir = getDirection(train.nextX, train.nextY, route[#route].x, route[#route].y) --print("train: ", train.x..":".. train.y,"->",train.nextX..":"..train.nextY.."\n".. -- " goto:", train.plannedTarget.x..":"..train.plannedTarget.y, "=>", dir) trains[train.ID].plannedTarget = train.plannedTarget trains[train.ID].plannedRoute = train.plannedRoute if train.plannedTarget.pickingUpAt == nil then train.plannedTarget.pickingUpAt = {} end train.plannedTarget.pickingUpAt[train.ID] = os.clock() + #route --arrival time return dir end end end function vipFactor(a) local vipFactor = 0 if buyingTrains then if a.vipTime ~= nil then local diff = os.clock() - a.placed local vipTime = a.vipTime - diff vipFactor = math.max(-5, a.minDistance - vipTime) else vipFactor = 10 end end return vipFactor end function pickupFactor(passenger, distance) if passenger.pickingUpAt == nil then return 0 end local pickupTime = os.clock() + distance local factorAll = 0 for train, otherPickupTime in pairs(passenger.pickingUpAt) do if not (train == activeTrain) then --10 penalty + time difference (may be negative) - but add only when positive local factor = 10 + (pickupTime - otherPickupTime) factorAll = factorAll + math.max(0, factor) end end return factorAll end function comparePassengers(a, b) local distanceAX = comparisonPosition.x - a.x local distanceAY = comparisonPosition.y - a.y local distanceBX = comparisonPosition.x - b.x local distanceBY = comparisonPosition.y - b.y distanceA = math.sqrt(distanceAX*distanceAX+distanceAY*distanceAY) distanceB = math.sqrt(distanceBX*distanceBX+distanceBY*distanceBY) return distanceA + a.minDistance/2 + vipFactor(a) + pickupFactor(a, distanceA) < distanceB + b.minDistance/2 + vipFactor(b) + pickupFactor(b, distanceB) end routeCache = {} function findRoute(x, y, fromX, fromY, destX, destY) --special case: next cell if (x==destX and y==destY) then local route = {} table.insert(route, {x=destX, y=destY, markFrom={x=x, y=y}}) return route end if routeCache[x..":"..y.."-"..fromX..":"..fromY.."-"..destX..":"..destY] ~= nil then return routeCache[x..":"..y.."-"..fromX..":"..fromY.."-"..destX..":"..destY] end local start = graphNodes[x][y][fromX..":"..fromY] local finish = findRouteDepthFirst(start, destX, destY, nil, nil) local route = {} local node = finish --while node.markFrom.x ~= x or node.markFrom.y ~= y do while node.markFrom ~= start do table.insert(route, node) node = node.markFrom end table.insert(route, node) routeCache[x..":"..y.."-"..fromX..":"..fromY.."-"..destX..":"..destY] = route return route end function getDirection(x, y, nextX, nextY) if x < nextX then return "E" end if x > nextX then return "W" end if y < nextY then return "S" end if y > nextY then return "N" end end findRouteRun = 0 --function findRouteDepthFirst(start, x, y, fromX, fromY) function findRouteDepthFirst(start, x, y) findRouteRun = findRouteRun + 1 local queue = {} table.insert(queue,start) start.mark = findRouteRun while #queue > 0 do node = table.remove(queue, 1) if node.x == x and node.y == y then return node end for i, link in pairs(node.link) do if link.mark ~= findRouteRun then --markedTracks = markedTracks + 1 link.mark = findRouteRun link.markFrom = node table.insert(queue, link) end end end end function getToNode(x, y, dir) local toX = x if dir == "E" then toX = toX + 1 end if dir == "W" then toX = toX - 1 end local toY = y if dir == "N" then toY = toY - 1 end if dir == "S" then toY = toY + 1 end return toX, toY end function getFromNode(x, y, dir) local fromX = x if dir == "E" then fromX = fromX - 1 end if dir == "W" then fromX = fromX + 1 end local fromY = y if dir == "N" then fromY = fromY - 1 end if dir == "S" then fromY = fromY + 1 end return fromX, fromY end DROP_WHEN_FURTHER = 3 function ai.foundPassengers(train, localPassengers) --TODO pick up new passenger, if it's a lot better local toX, toY = getToNode(train.x, train.y, train.dir) local broken = nil local pick = nil for i, localPassenger in pairs(localPassengers) do local found = false for j, passenger in pairs(passengers) do if passenger.name == localPassenger.name then found = true local route = passenger.routeOver[toX..":"..toY] --works as planned if route == nil then print("passenger at", train.x..":"..train.y, "doesn't have a route for:", toX..":"..toY) end if pick == nil or (route ~= nil and #route < #pick.route) then pick = localPassenger localPassenger.route = route localPassenger.index = j end break end end if not found then print("missing passenger entry for: ", localPassenger.name) broken = localPassenger end end if pick == nil and broken ~= nil then return broken end --if pick == nil then -- print("couldn't pick anyone at", train.x, train.y) --end if train.passenger == nil then if pick ~= nil then local test = table.remove(passengers, pick.index) end return pick else local currentDistance = #findRoute(toX, toY, train.x, train.y, train.passenger.destX, train.passenger.destY) if currentDistance > #pick.route + DROP_WHEN_FURTHER then --3 further? repick! --print("dropped off: ", train.passenger.name, "at", train.x, train.y,"\n", -- "saved distance: ", currentDistance-#pick.route) dropPassenger(train) return pick end end end function ai.foundDestination(train) dropPassenger(train) end trainBought = nil trainDelivered = nil TRAIN_TIMEOUT = 1 buyingTrains = true function ai.enoughMoney(money) if trainBought ~= nil then --print("buying train at: "..os.clock().." last bought: "..trainBought.." last delivered: "..trainDelivered) if trainDelivered == nil and trainBought + TRAIN_TIMEOUT < os.clock() then --no train was ever delivered --print("no train ever") buyingTrains = false return end if trainDelivered ~= nil and trainBought - trainDelivered > TRAIN_TIMEOUT then --last train wasn't delivered within 20 seconds --print("no train within 20s") buyingTrains = false return end end while money >= 25 do buyingTrains = true trainBought = os.clock() buyOptimalTrain() money = money - 25 end end function ai.passengerBoarded(train, passengerName) --TODO remove passenger form list for i,passenger in pairs(passengers) do if passenger.name == passengerName then table.remove(passengers, i) break end end end function randomPrevTrack(x, y) if x == nil or y == nil then return end local neighbours = neighbours(originalMap, x, y) local pick = neighbours[math.random(#neighbours)] local dir = getDirection(pick.x, pick.y, x, y) return pick.x, pick.y, dir end function buyOptimalTrain() if #passengers >= 1 then local pick = passengers[1] for i, passenger in pairs(passengers) do if passenger.minDistance + vipFactor(passenger) + pickupFactor(passenger, 5) < pick.minDistance + vipFactor(passenger) + pickupFactor(passenger, 5) then pick = passenger if pick.minDistance < 3 then break end end end --TODO pick direction and start point optimally local minRoute = pick.minRoute local output = "" --print(printRoute(minRoute)) local x, y, dir = pickSpawn(pick) print("Buying train for passenger at", pick.x..":"..pick.y, "going to", pick.destX..":"..pick.destY) print(" spawning at", x..":"..y, "going", dir) buyTrain(x, y, dir) else buyTrain(originalMap.width/2, originalMap.height/2, randomDirection()) end end function pickSpawn(target) x = target.x y = target.y nextInRouteX = target.minRoute[#target.minRoute].x nextInRouteY = target.minRoute[#target.minRoute].y local neighbours = neighbours(originalMap, x, y) if #neighbours == 1 then --only one place to spawn at a dead end return neighbours[1].x, neighbours[1].y, getDirection(neighbours[1].x, neighbours[1].y, x, y) end local pick = nil for i,neighbour in pairs(neighbours) do if not (neighbour.x == nextInRouteX and neighbour.y == nextInRouteY) then --don't select the way we want to go pick = neighbour break end end return pick.x, pick.y, getDirection(pick.x, pick.y, x, y) end function randomDirection() local dirs = {"N", "E", "S", "W"} return dirs[math.random(#dirs)] end passengers = {} function ai.newPassenger(name, x, y, destX, destY, vipTime) --todo store passengers local passenger = {name=name, x=x, y=y, destX=destX, destY=destY, vipTime=vipTime} passenger.placed = os.clock() passenger.routeOver = {} --print("new passenger: ", x, y, "to", destX, destY) local neighbours = neighbours(originalMap, x, y) local minDist = 9999 for i, nextDir in pairs(neighbours) do local route = findRoute(nextDir.x, nextDir.y, x, y, destX, destY) --print("time left: ", getNumberOfLines(), "\nroute length: ", #route) passenger.routeOver[nextDir.x ..":".. nextDir.y] = route if #route < minDist then minDist = #route minRoute = route end end passenger.minDistance = minDist passenger.minRoute = minRoute table.insert(passengers, passenger) if initialBuy > 0 then if (#passengers >= 3) --3 passengers spawned or one of the first two has a short route or (passengers[1] and #passengers[1].minRoute <= 5) or (passengers[2] and #passengers[2].minRoute <= 5) then initialBuy = initialBuy -1 buyOptimalTrain() end end end function printGraph(node) if node.mark == "print" then return "" end node.mark = "print" local output = node.x .. ":" .. node.y .. "->" for i, link in pairs(node.link) do output = output .. link.x .. ":" .. link.y .. "," end for i, link in pairs(node.link) do output = output .. " | " output = output .. printGraph(link) end return output end function printRoute(route) local output = "" for i,node in pairs(route) do output = output .. "->" .. node.x..":"..node.y end return output end