MazerEvolver

From BerryBots Wiki
Jump to: navigation, search
BerryBots
See a replay of MazerEvolver in action: click here to watch

A sample Game Runner packaged with BerryBots as runners/mazer/mazerevolver.lua. It uses a genetic algorithm to evolve a ship that can solve a maze.

It's a silly way to solve a maze, but a good demo of how to write genetic algorithms using the Game Runner API.

Source code

mazerevolver.lua

-- A Game Runner that uses a genetic algorithm to evolve a ship that can solve a
-- maze.
--
-- The maze is a version of sample.maze2 modified to give additional
-- metrics as results: percentage of the stage visited, % seen (i.e., by line
-- of sight), and % zones seen. Any maze could be outfitted with the same
-- metrics. But to solve many mazes, you would probably need to improve upon
-- this program. Fitness is calculated by the fitnessValue() function.
--
-- The "DNA" string is a series of bits that represents a sequence of
-- movements. 2 bits = 4 options = up / down / left / right. Each movement
-- has ACCEL_TIME ticks of acceleration, specified in mazerbase.lua.txt. This is
-- a fairly silly way to solve a maze and not a terribly efficient genetic
-- algorithm.
--
-- Other metrics could help, like penalizing back-tracking or total
-- displacement. Even better would be a system where the bit string is inputs
-- into an algorithm that dictates behavior - e.g., get this close to a wall,
-- follow it for this long, always follow an opening to the south if you see
-- one, etc. That might be more capable of improvement through crossover.
-- With the bit string as a movement sequence, most improvement probably happens
-- via mutation.
 
POPULATION_SIZE = 20
MUTATION_RATE = 0.001
CROSSOVER_RATE = 0.95
MAX_GENERATIONS = 10000
 
CHUNK_SIZE = 2  -- 2 bits to represent up, down, left, right
BITS = CHUNK_SIZE * 512
MOVES = {}
MOVES["00"] = "0"
MOVES["01"] = "(math.pi / 2)"
MOVES["10"] = "math.pi"
MOVES["11"] = "(math.pi * 3 / 2)"
 
function run(runner, form, files)
  runner:setThreadCount(3)
  files:writeStage("maze2e.lua", files:read("mazer/maze2e.lua.txt"))
 
  local members = createPopulation(POPULATION_SIZE)
  for i = 1, MAX_GENERATIONS do
    members = nextGeneration(members, runner, files)
  end
end
 
function createPopulation(size)
  local members = {}
  for i = 1, size do
    table.insert(members, randomBitString())
  end
  return members
end
 
function nextGeneration(members, runner, files)
  local memberDataMap = {}
  for i = 1, (# members) do
    local filename = "mazer" .. i .. ".lua"
    memberDataMap["runners/" .. filename] = {bits = members[i]}
    files:writeBot(filename, mazerCode(members[i], files))
    runner:queueMatch("runners/maze2e.lua", {"runners/" .. filename})
  end
 
  while (not runner:empty()) do
    local result = runner:nextResult()
    local name = result.teams[1].name
    local stats = result.teams[1].stats
    memberDataMap[name].name = name
    memberDataMap[name].fitnessValue = fitnessValue(stats["Grid Visible"],
        stats["Zone Visible"], stats["Grid Visited"], (result.winner ~= nil))
    print("Member data: " .. memberDataMap[name].fitnessValue
          .. string.len(memberDataMap[name].bits))
  end
 
  local memberData = {}
  for i, memberDatum in pairs(memberDataMap) do
    table.insert(memberData, memberDatum)
  end
  sortMemberData(memberData)
  print("--------")
  print("  members = {")
  for i, memberDatum in ipairs(memberData) do
    print("    \"" .. memberDatum.bits .. "\",")
  end
  print("  }")
  print("--------")
  print("Best fitness: " .. memberData[1].fitnessValue)
 
  print()
  return breedAndMutate(memberData)
end
 
function fitnessValue(gridVisible, zoneVisible, gridVisited, win)
  local value = gridVisible + gridVisited + (1000 * zoneVisible)
  if (win) then
    value = value + 1000000
  end
  return value
end
 
function sortMemberData(memberData)
  table.sort(memberData, memberDataSorter)
end
 
function memberDataSorter(memberDatum1, memberDatum2)
  return memberDatum1.fitnessValue > memberDatum2.fitnessValue
end
 
function breedAndMutate(memberData)
  setRouletteRanges(memberData)
  local len = (# memberData)
  local members = {}
  while ((# members) < len) do
    local member1 = rouletteMember(memberData, math.random())
    local member2 = nil
    local tries = 0
    repeat
      member2 = rouletteMember(memberData, math.random())
      tries = tries + 1
    until (member1 ~= member2 or tries > 1000)
    if (member1 == member2) then
      member2 = memberData[math.floor(math.random() * len) + 1]
    end
 
    if (math.random() < CROSSOVER_RATE) then
      local numNewMembers = math.min(2, len - (# members))
      for i = 1, numNewMembers do
        local newMember = mutate(crossover(member1, member2))
        table.insert(members, newMember)
      end
    else
      table.insert(members, member1.bits)
      table.insert(members, member2.bits)
    end
  end
 
  return members
end
 
function crossover(memberDatum1, memberDatum2)
  local crossoverPoint = math.floor(math.random() * (string.len(memberDatum1.bits) - 1)) + 1
  local members = {memberDatum1.bits, memberDatum2.bits}
  local x = 1
  if (math.random() < 0.5) then
    x = 2
  end
 
  local s = string.sub(members[x], 1, crossoverPoint)
  x = ((x - 1) * -1) + 2
  return s .. string.sub(members[x], crossoverPoint + 1, (# members[x]))
end
 
function mutate(member)
  local len = string.len(member)
  for i = 1, len do
    if (math.random() < MUTATION_RATE) then
      local bitSections = {}
      if (i > 1) then
        table.insert(bitSections, string.sub(member, 1, i - 1))
      end
 
      local bit = string.sub(member, i, i)
      if (bit == "0") then
        table.insert(bitSections, "1")
      else
        table.insert(bitSections, "0")
      end
 
      if (i < len) then
        table.insert(bitSections, string.sub(member, i + 1, len))
      end
      member = table.concat(bitSections, "")
    end
  end
  return member
end
 
function setRouletteRanges(memberData)
  local min = math.huge
  for i, memberDatum in ipairs(memberData) do
    min = math.min(min, memberDatum.fitnessValue)
  end
 
  local sum = 0
  for i, memberDatum in ipairs(memberData) do
    sum = sum + math.max(0, memberDatum.fitnessValue - min)
  end    
 
  local rangeSum = 0
  for i, memberDatum in ipairs(memberData) do
    memberDatum.rouletteRange =
        rangeSum + (math.max(0, memberDatum.fitnessValue - min) / sum)
    rangeSum = rangeSum + memberDatum.rouletteRange
  end
end
 
function rouletteMember(memberData, rouletteValue)
  local numMembers = (# memberData)
  for i = 1, numMembers do
    if (i == numMembers or ((rouletteValue >= memberData[i].rouletteRange)
            and (rouletteValue < memberData[i + 1].rouletteRange))) then
      return memberData[i]
    end
  end
  return nil
end
 
function mazerCode(bitString, files)
  local m = {}
  local len = (# bitString) / CHUNK_SIZE
  for i = 1, len do
    local moveBits =
        string.sub(bitString, (i * CHUNK_SIZE) - 1, (i * CHUNK_SIZE))
    table.insert(m, MOVES[moveBits])
  end
 
  return files:read("mazer/mazerbase.lua.txt") .. "\nmoves = {"
      .. table.concat(m, ", ") .. "}\n"
end
 
function randomBitString()
  local s = {}
  for i = 1, BITS do
    if (math.random() < 0.5) then
      table.insert(s, "0")
    else
      table.insert(s, "1")
    end
  end
  return table.concat(s, "")
end

mazerbase.lua.txt

ACCEL_TIME = 6
 
ship = nil
world = nil
 
heading = nil
moveTimer = 0
moving = false
moveIndex = 1
 
moves = {0, 0, 0}
 
function init(shipArg, worldArg)
  ship = shipArg
  world = worldArg
end
 
function run()
  if (ship:speed() < 0.0001) then
    moving = false
  end
 
  if (not moving and moveTimer == 0 and moveIndex <= (# moves)) then
    heading = moves[moveIndex]
    moveIndex = moveIndex + 1
    moveTimer = moveTimer + ACCEL_TIME
    moving = true
  end
 
  if (moving and moveTimer > 0) then
    ship:fireThruster(heading, 1)
    moveTimer = moveTimer - 1
  else
    ship:fireThruster(ship:heading() + math.pi, ship:speed())
  end
end

maze2e.lua.txt

-- A reasonably complex single player maze. Ship starts in middle left and needs
-- to get to top right corner without hitting any walls.
--
-- Sample ships that can solve this maze: WallHugger and Snail.
 
require "samplestage"
 
function configure(stageBuilder)
  stageBuilder:setSize(1200, 600)
  stageBuilder:addStart(25, 300)
  stageBuilder:addWall(75, 350, 4, 250)
  stageBuilder:addWall(75, 0, 4, 250)
  stageBuilder:addWall(75, 350, 450, 4)
  stageBuilder:addWall(625, 350, 4, 150)
  stageBuilder:addWall(200, 500, 925, 4)
  stageBuilder:addWall(300, 450, 4, 50)
  stageBuilder:addWall(450, 350, 4, 75)
  stageBuilder:addWall(1025, 350, 4, 100)
  stageBuilder:addWall(1125, 500, 4, 100)
  stageBuilder:addWall(625, 350, 500, 4)
  stageBuilder:addWall(1125, 250, 4, 104)
  stageBuilder:addWall(750, 350, 4, 100)
  stageBuilder:addWall(900, 400, 4, 100)
  stageBuilder:addWall(75, 250, 150, 4)
  stageBuilder:addWall(300, 250, 825, 4)
  stageBuilder:addWall(200, 175, 604, 4)
  stageBuilder:addWall(800, 100, 4, 75)
  stageBuilder:addWall(875, 100, 4, 150)
  stageBuilder:addWall(800, 96, 175, 4)
  stageBuilder:addWall(200, 100, 4, 75)
  stageBuilder:addWall(200, 96, 225, 4)
  stageBuilder:addWall(550, 0, 4, 75)
  stageBuilder:addWall(675, 75, 4, 100)
  stageBuilder:addWall(1050, 100, 150, 4)
  stageBuilder:addWall(1050, 175, 4, 75)
  stageBuilder:addWall(875, 175, 175, 4)
  stageBuilder:addZone(1150, 550, 50, 50)
end
 
world = nil
ships = nil
admin = nil
wallLines = nil
visibilityGrid = nil
visibilityZones = nil
visitingGrid = nil
 
function init(shipsArg, worldArg, adminArg)
  ships = shipsArg
  world = worldArg
  admin = adminArg
  visibilityGrid = makeVisibilityGrid(world:width(), world:height(), 50)
  visibilityZones = makeVisibilityZones(world:zones())
  visitingGrid = makeVisitingGrid(world:width(), world:height(), 30)
  wallLines = initWalls(world:walls())
end
 
function run()
  samplestage.checkSinglePlayer(ships, admin)
 
  for i, ship in pairs(ships) do
    updateVisibility(visibilityGrid, wallLines, ship:x(), ship:y())
    updateVisibility(visibilityZones, wallLines, ship:x(), ship:y())
    updateVisited(visitingGrid, ship:x(), ship:y())
    if (ship:alive() and world:touchedAnyZone(ship)) then
      admin:setWinner(ship)
      admin:setStatistic(ship, "Time", world:time())
      admin:setStatistic(ship, "Grid Visible", seenCount(visibilityGrid))
      admin:setStatistic(ship, "Zone Visible", seenCount(visibilityZones))
      admin:setStatistic(ship, "Grid Visited", visitedCount(visitingGrid))
      admin:gameOver()
      local timeLine = "Time: " .. world:time()
      print(timeLine)
    elseif (ship:hitWall() or world:time() > 10000) then
      admin:setStatistic(ship, "Time", world:time())
      admin:setStatistic(ship, "Grid Visible", seenCount(visibilityGrid))
      admin:setStatistic(ship, "Zone Visible", seenCount(visibilityZones))
      admin:setStatistic(ship, "Grid Visited", visitedCount(visitingGrid))
      admin:gameOver()
    end
  end
end
 
function makeVisibilityGrid(width, height, interval)
  local grid = {}
  local x = interval
  while (x < width) do
    local y = interval
    while (y < height) do
      local vertex = {x = x, y = y, seen = false}
      table.insert(grid, vertex)
      y = y + interval
    end
    x = x + interval
  end
  return grid
end
 
function makeVisibilityZones(zones)
  local zonePoints = {}
  for i, zone in ipairs(zones) do
    local vertex = {x = zone.left + (zone.width / 2),
        y = zone.bottom + (zone.height / 2), seen = false, visited = false}
    table.insert(zonePoints, vertex)
  end
  return zonePoints
end
 
function makeVisitingGrid(width, height, interval)
  local grid = {}
  local x = interval
  while (x < width) do
    local y = interval
    while (y < height) do
      local vertex = {x = x, y = y, visited = false}
      table.insert(grid, vertex)
      y = y + interval
    end
    x = x + interval
  end
  return grid
end
 
function updateVisibility(points, wallLines, x, y)
  for i, vertex in ipairs(points) do
    if (not vertex.seen) then
      if (isVisible(wallLines, x, y, vertex.x, vertex.y)) then
        vertex.seen = true
      end
    end
  end
end
 
function updateVisited(points, x, y)
  for i, vertex in ipairs(points) do
    if (not vertex.visited) then
      if (math.abs(vertex.x - x) < 15 and math.abs(vertex.y - y) < 15) then
        vertex.visited = true
      end
    end
  end
end
 
function seenCount(points)
  local seen = 0
  for i, vertex in ipairs(points) do
    if (vertex.seen) then
      seen = seen + 1
    end
  end
  return (seen / (# points))
end
 
function visitedCount(points)
  local visited = 0
  for i, vertex in ipairs(points) do
    if (vertex.visited) then
      visited = visited + 1
    end
  end
  return (visited / (# points))
end
 
function newLine(x1, y1, x2, y2)
  local wallLine = { }
  if (x1 == x2) then
    wallLine.m = math.huge
    wallLine.b = math.huge
    wallLine.xMin, wallLine.xMax = x1, x1
  else
    wallLine.m = (y2 - y1) / (x2 - x1)
    wallLine.b = y1 - (wallLine.m * x1)
    wallLine.xMin = math.min(x1, x2)
    wallLine.xMax = math.max(x1, x2)
  end
  wallLine.yMin = math.min(y1, y2)
  wallLine.yMax = math.max(y1, y2)
  wallLine.x1, wallLine.y1, wallLine.x2, wallLine.y2 = x1, y1, x2, y2
 
  return wallLine
end
 
function initWalls(walls)
  local wallLines = { }
  for i, wall in pairs(walls) do
    local x1, y1 = wall.left, wall.bottom
    local x2, y2 = wall.left + wall.width, wall.bottom
    local x3, y3 = wall.left + wall.width, wall.bottom + wall.height
    local x4, y4 = wall.left, wall.bottom + wall.height
    table.insert(wallLines, newLine(x1, y1, x2, y2))
    table.insert(wallLines, newLine(x2, y2, x3, y3))
    table.insert(wallLines, newLine(x3, y3, x4, y4))
    table.insert(wallLines, newLine(x4, y4, x1, y1))
  end
  return wallLines
end
 
function isVisible(wallLines, x1, y1, x2, y2)
  local visionLine = newLine(x1, y1, x2, y2)
  for i, wallLine in pairs(wallLines) do
    if (intersects(wallLine, visionLine)) then
      return false
    end
  end
  return true
end
 
function intersects(line1, line2, buffer)
  if (buffer == nil) then
    buffer = 0
  end
  local m1 = line1.m
  local m2 = line2.m
  if (m1 == m2) then
    return false
  elseif (m1 == math.huge or m2 == math.huge) then
    if (m1 == math.huge and m2 == 0) then
      return (line1.xMin >= line2.xMin - buffer
          and line1.xMax <= line2.xMax + buffer
          and line1.yMin <= line2.yMin + buffer
          and line1.yMax >= line2.yMax - buffer)
    else
      return intersects(inverse(line1), inverse(line2), buffer)
    end
  end
 
  local x = (line2.b - line1.b) / (line1.m - line2.m)
  local y = line1.m * x + line1.b
  return (x >= line1.xMin - buffer and x <= line1.xMax + buffer
      and x >= line2.xMin - buffer and x <= line2.xMax + buffer
      and y >= line1.yMin - buffer and y <= line1.yMax + buffer
      and y >= line2.yMin - buffer and y <= line2.yMax + buffer)
end
 
function inverse(line)
  return newLine(line.y1, line.x1, line.y2, line.x2)
end
 
function sign(x)
  if (x > 0) then
    return 1
  elseif (x < 0) then
    return -1
  else
    return 0
  end
end
 
function distance(x1, y1, x2, y2)
  return math.sqrt(distanceSq(x1, y1, x2, y2))
end
 
function distanceSq(x1, y1, x2, y2)
  return square(x1 - x2) + square(y1 - y2)
end
 
function square(x)
  return x * x
end
 
function normalRelativeAngle(x)
  while (x >= math.pi) do
    x = x - (2 * math.pi)
  end
  while (x < -math.pi) do
    x = x + (2 * math.pi)
  end
  return x
end
 
function normalAbsoluteAngle(x)
  while (x >= 2 * math.pi) do
    x = x - (2 * math.pi)
  end
  while (x < 0) do
    x = x + (2 * math.pi)
  end
  return x
end
 
function absoluteBearing(x1, y1, x2, y2)
  return math.atan2(y2 - y1, x2 - x1)
end
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox