--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 na-oma: -- Challenge4: Maze with Pathfinding?! myMap = nil --TODO: table for all tiles to make all tile with same coords have the same object? function ai.foundDestination(train) dropPassenger(train) end function ai.blocked(train, possibleDirections, prevDirection) --print("Blocked train: ", train, " @ ", train.x, ", ", train.y, " tablelength(possibleDirections) ", tablelength(possibleDirections)) end function ai.foundPassengers(train, passengers) -- a,b = getNumberOfLines() -- print("Lines: curr: " .. a .. " max: " .. b) if train.passenger then return end bestPassenger = passengers[1] --take the first VIP you can find for _, passenger in pairs(passengers) do if string.find(passenger.name, "VIP") then bestPassenger = passenger break end end ai.passengerBoarded(train, bestPassenger) return bestPassenger end function ai.chooseDirection(train, directions) local destination = nil if not train.passenger then --we are empty get good passenger location as destination local bestDistance = math.huge local bestPassenger = nil for name, passenger in pairs(passengerList) do local distance = calculateHeuristicPathScore(train, {x = passenger.x, y = passenger.y}) if distance < bestDistance then bestDistance = distance bestPassenger = passenger end end --return chooseRandomDirection(directions) destination = {x = bestPassenger.x, y = bestPassenger.y} else destination = {x = train.passenger.destX, y = train.passenger.destY} end --print("destination") --printTable(destination) shortestPath = findPath({x = train.x, y = train.y}, destination) --printTable(shortestPath) if #shortestPath <= 2 then --the crossing itself is the target return chooseRandomDirection(directions) end local crossingTile = shortestPath[#shortestPath - 1] local afterCrossingTile = shortestPath[#shortestPath - 2] if crossingTile.x < afterCrossingTile.x then return "E" elseif crossingTile.x > afterCrossingTile.x then return "W" elseif crossingTile.y < afterCrossingTile.y then return "S" elseif crossingTile.y > afterCrossingTile.y then return "N" end end function ai.enoughMoney(money) while money >= 25 do -- 25c is cost of one train buyTrain(random(myMap.width), random(myMap.height)) money = money - 25 end end function ai.init(map, money, maximumTrains) -- a,b = getNumberOfLines() -- print("Lines: curr: " .. a .. " max: " .. b) myMap = map ai.enoughMoney(money) --listA = {"A", "B", "C", "D"} --listA[2] = nil --printTable(listA) -- source = {x = 1, y = 1} -- target = {x = 9, y = 9} -- if myMap[target.x][target.y] ~= "C" then -- target = exploreTiles(target, {})[1] -- end -- findPath(source, target) --a,b = getNumberOfLines() --print("Lines: curr: " .. a .. " max: " .. b) end -- function bestGuess(currentTile, target) -- minDistance = math.huge -- minTile = nil -- tilesToCheck = { -- {x = currentTile.x + 1, y = currentTile.y}, -- {x = currentTile.x, y = currentTile.y + 1}, -- {x = currentTile.x - 1, y = currentTile.y}, -- {x = currentTile.x, y = currentTile.y - 1}} -- for _, tileToCheck in ipairs(tilesToCheck) do -- printTable(tileToCheck) -- if myMap[tileToCheck.x][tileToCheck.y] and myMap[tileToCheck.x][tileToCheck.y] == "C" then -- local distanceSquared = distanceSquared(tileToCheck.x , tileToCheck.y, target.x, target.y) -- if distanceSquared < minDistance then -- minDistance = distanceSquared -- minTile = tileToCheck -- end -- end -- end -- return minTile -- end function exploreTiles(tile, closedList) validTiles = {} --TODO switch check vs closedList with check vs Map tilesToCheck = { {x = tile.x + 1, y = tile.y}, {x = tile.x, y = tile.y + 1}, {x = tile.x - 1, y = tile.y}, {x = tile.x, y = tile.y - 1}} --print("size tilesToCheck: " .. #tilesToCheck) -- print("tilesToCheck @ 4 3") -- if tile.x == 4 and tile.y == 3 then -- printTable(tilesToCheck) -- end for _, tileToCheck in pairs(tilesToCheck) do -- if tile.x == 4 and tile.y == 3 then -- print("tileToCheck", tileToCheck) -- printTable(tileToCheck) -- print("myMap[tileToCheck.x][tileToCheck.y]", myMap[tileToCheck.x][tileToCheck.y]) -- end if myMap[tileToCheck.x][tileToCheck.y] and myMap[tileToCheck.x][tileToCheck.y] == "C" then table.insert(validTiles, tileToCheck) --if tileToCheck.x == 3 and tileToCheck.y == 3 then --print("inserting tileToCheck @ 3 3 from tile " .. tile.x .. "," .. tile.y) --printTable(validTiles) --end end end for closedTile, _ in pairs(closedList) do for i, _ in pairs(validTiles) do --print("tilesToCheck") --printTable(tilesToCheck) --print("closedTile") --printTable(closedTile) if validTiles[i].x == closedTile.x and validTiles[i].y == closedTile.y then validTiles[i] = nil end end end -- print("size tilesToCheck: " .. #tilesToCheck) -- if tile.x == 4 and tile.y == 3 then -- print("tilesToCheck") -- printTable(tilesToCheck) -- end -- if tile.x == 3 and tile.y == 3 then -- print("validTiles @ 3 3") -- printTable(validTiles) -- end return validTiles end function calculateKnownPathScore(parent, closedList, tile) -- print("AAAAAAA") -- for a, b in pairs(closedList) do -- print(a, b) -- end --print("parent: ", parent) -- print("BB") --printTable(closedList[parent]) --print("CC") if parent == 0 then return 0 else return closedList[parent][1] + 1 end end function calculateHeuristicPathScore(tile, target) --print("tile.x", tile.x, "tile.y", tile.y, "target.x", target.x, "target.y", target.y) return manhattanDistance(tile.x, tile.y, target.x, target.y) --return distanceSquared(tile.x, tile.y, target.x, target.y) end function calculateTotalPathScore(parent, closedList, tile, target) --print("calculateKnownPathScore(parent, closedList, tile): " .. calculateKnownPathScore(parent, closedList, tile)) --print("calculateHeuristicPathScore(tile, target) :" .. calculateHeuristicPathScore(tile, target)) return calculateKnownPathScore(parent, closedList, tile) + calculateHeuristicPathScore(tile, target) end function findPath(source, target) local closedList = {} --backup to be able to check easily if any tile is already in the open set and at which score local openSet = {} local openList = {} --Source has the distance 1 due to lua lists starting at 1 local openListMaxValue = calculateTotalPathScore(0, closedList, source, target) openList[openListMaxValue] = {} openList[openListMaxValue][source] = 0 openSet[source] = openListMaxValue --local validTiles = exploreTiles(source, closedList) --openList[1][source] = nil --closedList[source] = {1, nil} -- --print("SHHHHH") -- --printTable(closedList[source]) -- --print("SHHHHH2") -- for _, tile in pairs(validTiles) do -- local pathScore = calculateTotalPathScore(source, closedList, tile, target) -- --print(pathScore) -- --printTable(tile) -- if not openList[pathScore] then -- openList[pathScore] = {} -- openListMaxValue = pathScore > openListMaxValue and pathScore or openListMaxValue -- end -- openList[pathScore][tile] = source -- end --printLists(openList, openListMaxValue, closedList) -- for score, openTiles in ipairs(openList) do -- print("B") -- end local debugLastAdditions = "" --TODO: fix lastAdditionToClosedList == nil @line 348 local lastAdditionToClosedList = nil while linesRemaining() > 800 do --print("----------------") local didSomething = false --find the openTiles with lowest score for score = 1, openListMaxValue do local openTiles = openList[score] if openTiles then --print("here") --print("score: " .. score) --printTable(openTiles[1]) --printTable(openTiles) --print("here1") for openTile, parent in pairs(openTiles) do --print("openTile: ", openTile) --printTable(openTile) --print("parent: ", parent) --printTable(parent) --print("here2") local validTiles = exploreTiles(openTile, closedList) closedList[openTile] = {calculateKnownPathScore(parent, closedList, openTile), parent} lastAdditionToClosedList = openTile openList[score][openTile] = nil --print("A") for _, tile in pairs(validTiles) do local pathScore = calculateTotalPathScore(openTile, closedList, tile, target) --print("pathScore: " .. pathScore) --printTable(tile) local doAddStuff = true local openSetOldTileWithSameCoords = nil for k, _ in pairs(openSet) do if k.x == tile.x and k.y == tile.y then openSetOldTileWithSameCoords = k break end end if openSetOldTileWithSameCoords then --we got an earlier version in the openList if openSet[openSetOldTileWithSameCoords] > pathScore then --the old version is worse than the new => delete old stuff before adding openList[openSet[openSetOldTileWithSameCoords]][openSetOldTileWithSameCoords] = nil openSet[openSetOldTileWithSameCoords] = nil else --the old version is better => do not add new version doAddStuff = false end end --if tile.x == 3 and tile.y == 3 then --print("pathScore: " .. pathScore) --print("openSet[tile]: " .. (openSet[tile] and openSet[tile] or "nil")) --if doAddStuff then -- print("DOPPEL") --end --end if doAddStuff then if not openList[pathScore] then openList[pathScore] = {} openListMaxValue = pathScore > openListMaxValue and pathScore or openListMaxValue end --add stuff to both openList and openSet openList[pathScore][tile] = openTile openSet[tile] = pathScore end end didSomething = true break end end if didSomething then break end end if lastAdditionToClosedList.x == target.x and lastAdditionToClosedList.y == target.y then break end --printLists(openList, openListMaxValue, closedList) --printOpenList(openList, openListMaxValue) --print("last addition: (" .. lastAdditionToClosedList.x .. "," .. lastAdditionToClosedList.y .. ")") --debugLastAdditions = debugLastAdditions .. lastAdditionToClosedList.x .. "," .. lastAdditionToClosedList.y .. " " end if lastAdditionToClosedList.x == target.x and lastAdditionToClosedList.y == target.y then --print("DONE") --print("Total Distance: " .. closedList[lastAdditionToClosedList][1]) returnValue = {target} local parent = closedList[lastAdditionToClosedList][2] line = "Path: " while parent ~= 0 do table.insert(returnValue, parent) line = line .. "(" .. parent.x .. "," .. parent.y .. ")" parent = closedList[parent][2] end --print(line) else --out of time returnValue = {} local parent = closedList[lastAdditionToClosedList][2] while parent ~= 0 do table.insert(returnValue, parent) parent = closedList[parent][2] end --print("oot, #returnValue:", #returnValue) end --print(debugLastAdditions) -- listA = {} -- innerList = {1, 2} -- listA[innerList] = "AAA" -- print(listA[{1, 2}]) --nextTile = bestGuess(source, target) --printTable(nextTile) --print() --table.insert(openList, nextTile) --nextTile = bestGuess(openList[#openList], target) --printTable(nextTile) return returnValue end ----------------------------------------------------------------- passengerList = {} -- create an empty list to save the passengers in function ai.newPassenger(name, x, y, destX, destY) -- create a new table which holds the info about the new passenger: local passenger = {x=x, y=y, destX=destX, destY=destY} -- save the passenger into the global list, to "remember" him for later use. -- use the name as an index to easily find the passenger later on. passengerList[name] = passenger --if x == 4 and y == 4 then --print("New Passengetr @ 4 4: ") --printTable(passenger) --end end function ai.passengerBoarded(train, passengerName) --print("Boarded: ") --printTable(passengerList[passengerName]) -- set the entry in the passengerList for the passenger to nil. This is the accepted way of "deleting" the entry in Lua. passengerList[passengerName] = nil end ----------------------------------------------------------------- function printLists(openList, openListMaxValue, closedList) printOpenList(openList, openListMaxValue) printClosedList(closedList) end function printOpenList(openList, openListMaxValue) print("OpenList") for i = 1, openListMaxValue do if openList[i] then for k, v in pairs(openList[i]) do line = "Est Tot Distance " .. i .. ": (" .. k.x .. "," .. k.y .. ") Parent: " if type(v) == "number" then line = line .. v else line = line .. "(" .. v.x .. "," .. v.y .. ")" end print(line) end end end --printTable(openList) end function printClosedList(closedList) print("ClosedList") if closedList then for tile, content in pairs(closedList) do line = "(" .. tile.x .. "," .. tile.y .. ")" .. " Tot Score: " .. content[1] .. " Parent: " if (not content[2]) or content[2] == 0 then line = line .. "0" else line = line .. "(" .. content[2].x .. "," .. content[2].y .. ")" end print(line) end else print("Empty") end end function tablelength(T) local count = 0 for _ in pairs(T) do count = count + 1 end return count end function printTable(table, lvl) if not type(table) == "table" then print("not a table!") return end 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 end function distanceSquared(x1, y1, x2, y2) return (x1-x2)^2 + (y1-y2)^2 end function manhattanDistance(x1, y1, x2, y2) return math.abs(x1-x2) + math.abs(y1-y2) end function chooseRandomDirection(possibleDirections) local dirTable = {} if possibleDirections["N"] then table.insert(dirTable, "N") end if possibleDirections["S"] then table.insert(dirTable, "S") end if possibleDirections["E"] then table.insert(dirTable, "E") end if possibleDirections["W"] then table.insert(dirTable, "W") end return dirTable[random(#dirTable)] end function linesRemaining() local currentLines, maxLines = getNumberOfLines() return maxLines - currentLines end