-- Dyna Blaster: Copperline's AI player, as a Lua bot.
--
-- A port of ~/mydev/amiga/dynabot: the planner (crates/dynabot, a search over
-- tiles and frames that knows nothing about Amigas) and the seat
-- (crates/dynaseat: eyes from the game's RAM, Copperline's pilot steering).
-- The Rust is the reference; this follows it function by function, with the
-- same tie-breaks, so the two decide alike. Runs in the emulator's bot sandbox
-- (od-unix/netplay_bot.cpp): ram.* to read, frame() answers joystick bits.

---------------------------------------------------------------------------
-- The planner (dynabot)
---------------------------------------------------------------------------

local FLOOR, BRICK, PILLAR, UNKNOWN = 0, 1, 2, 3

-- Steps in a fixed order, so a tie is broken the same way every time.
local NORTH, SOUTH, EAST, WEST = 1, 2, 3, 4
local STEPS = { NORTH, SOUTH, EAST, WEST }
local DX = { 0, 0, 1, -1 }
local DY = { -1, 1, 0, 0 }
local OPPOSITE = { SOUTH, NORTH, WEST, EAST }

local FLEEING, ATTACKING, DIGGING, HUNTING, HOLDING = "fleeing", "attacking", "digging", "hunting", "holding"

-- An arena: cols, rows, and tiles[r * cols + c + 1].
local function inside(a, c, r)
  return c >= 0 and r >= 0 and c < a.cols and r < a.rows
end

local function tile_at(a, c, r)
  if not inside(a, c, r) then return PILLAR end
  return a.tiles[r * a.cols + c + 1]
end

local function walkable(a, c, r)
  return tile_at(a, c, r) == FLOOR
end

local function index(a, c, r)
  return r * a.cols + c + 1
end

-- Which tiles a bomb's blast covers, stopping at the first wall along each
-- arm and taking a brick with it. Cells as {c, r}.
local function blast_cells(a, c0, r0, power)
  local cells = { { c0, r0 } }
  for _, s in ipairs(STEPS) do
    for d = 1, power do
      local c, r = c0 + DX[s] * d, r0 + DY[s] * d
      if not inside(a, c, r) then break end
      local t = tile_at(a, c, r)
      if t == PILLAR or t == UNKNOWN then break end
      cells[#cells + 1] = { c, r }
      if t ~= FLOOR then break end     -- a brick is caught and stops it
    end
  end
  return cells
end

local function cells_contain(cells, c, r)
  for _, x in ipairs(cells) do
    if x[1] == c and x[2] == r then return true end
  end
  return false
end

-- When every tile is on fire: per tile, a list of {from, to} windows.
-- Chains are a fixpoint: a bomb caught by another's blast goes off early.
local function danger(a, bombs, rules)
  local goes_off = {}
  for i, b in ipairs(bombs) do goes_off[i] = b.fuse_left end
  local cells = {}
  for i, b in ipairs(bombs) do cells[i] = blast_cells(a, b.c, b.r, b.power) end
  for _ = 0, #bombs do
    local moved = false
    for i = 1, #bombs do
      for j = 1, #bombs do
        if i ~= j and cells_contain(cells[i], bombs[j].c, bombs[j].r) and goes_off[i] < goes_off[j] then
          goes_off[j] = goes_off[i]
          moved = true
        end
      end
    end
    if not moved then break end
  end
  local windows = {}
  for k = 1, a.cols * a.rows do windows[k] = {} end
  for i, b in ipairs(bombs) do
    local at = goes_off[i]
    for _, cell in ipairs(cells[i]) do
      local w = windows[index(a, cell[1], cell[2])]
      w[#w + 1] = { at, at + rules.blast_frames }
    end
    -- The bomb's own tile cannot be walked through while it is there.
    local w = windows[index(a, b.c, b.r)]
    w[#w + 1] = { 0, at }
  end
  return { a = a, windows = windows }
end

local function windows_at(d, c, r)
  if not inside(d.a, c, r) then return {} end
  return d.windows[index(d.a, c, r)]
end

local function lethal_between(d, c, r, from, to)
  for _, w in ipairs(windows_at(d, c, r)) do
    if from <= w[2] and w[1] <= to then return true end
  end
  return false
end

local function next_flame(d, c, r, from)
  local best
  for _, w in ipairs(windows_at(d, c, r)) do
    if w[2] >= from then
      local f = math.max(w[1], from)
      if best == nil or f < best then best = f end
    end
  end
  return best
end

local function blocked_has(blocked, c, r)
  return blocked[c .. "," .. r] == true
end

-- Coordinates compare column first, then row, as Rust's (i32, i32) does.
local function coord_less(c1, r1, c2, r2)
  return c1 < c2 or (c1 == c2 and r1 < r2)
end

-- The earliest frame each tile can be reached from (fc, fr), walking only
-- through tiles clear for the whole of the step that enters them.
local function earliest_arrival(a, d, fc, fr, now, rules, blocked)
  local best, came = {}, {}
  if not inside(a, fc, fr) then return best, came end
  best[index(a, fc, fr)] = now
  local frontier = { { fc, fr } }
  while #frontier > 0 do
    local pick = 1
    for i = 2, #frontier do
      local x, p = frontier[i], frontier[pick]
      local ta, tb = best[index(a, x[1], x[2])], best[index(a, p[1], p[2])]
      if ta < tb or (ta == tb and coord_less(x[1], x[2], p[1], p[2])) then pick = i end
    end
    local cell = frontier[pick]
    frontier[pick] = frontier[#frontier]   -- swap_remove
    frontier[#frontier] = nil
    local at = best[index(a, cell[1], cell[2])]
    for _, s in ipairs(STEPS) do
      local nc, nr = cell[1] + DX[s], cell[2] + DY[s]
      if walkable(a, nc, nr) and not blocked_has(blocked, nc, nr) then
        local arrive = at + rules.frames_per_tile
        if not lethal_between(d, nc, nr, at, arrive) then
          local slot = index(a, nc, nr)
          if best[slot] == nil or arrive < best[slot] then
            best[slot] = arrive
            came[slot] = cell
            local present = false
            for _, f in ipairs(frontier) do
              if f[1] == nc and f[2] == nr then present = true break end
            end
            if not present then frontier[#frontier + 1] = { nc, nr } end
          end
        end
      end
    end
  end
  return best, came
end

-- The first move of the path the search found to (tc, tr).
local function first_step_of(came, a, fc, fr, tc, tr)
  local c, r = tc, tr
  while true do
    local prev = came[index(a, c, r)]
    if prev == nil then return nil end
    if prev[1] == fc and prev[2] == fr then
      local dx, dy = c - fc, r - fr
      for _, s in ipairs(STEPS) do
        if DX[s] == dx and DY[s] == dy then return s end
      end
      return nil
    end
    c, r = prev[1], prev[2]
  end
end

-- The best refuge reachable from (fc, fr): nearest, then not a pocket, then
-- most slack, then position.
local function find_refuge(a, d, fc, fr, now, rules, blocked)
  local arrivals, came = earliest_arrival(a, d, fc, fr, now, rules, blocked)
  local best, bk
  for r = 0, a.rows - 1 do
    for c = 0, a.cols - 1 do
      local arrive = arrivals[index(a, c, r)]
      if arrive ~= nil and not lethal_between(d, c, r, arrive, now + rules.horizon_frames) then
        local f = next_flame(d, c, r, arrive)
        local slack = f and (f - arrive) or rules.horizon_frames
        local exits = 0
        for _, s in ipairs(STEPS) do
          if walkable(a, c + DX[s], r + DY[s]) then exits = exits + 1 end
        end
        local pocket = exits <= 1 and 1 or 0
        local key = { arrive, pocket, -slack, c, r }
        local better = bk == nil
        if not better then
          for k = 1, 5 do
            if key[k] ~= bk[k] then better = key[k] < bk[k] break end
          end
        end
        if better then
          best = { c = c, r = r, first = first_step_of(came, a, fc, fr, c, r), arrive = arrive, slack = slack }
          bk = key
        end
      end
    end
  end
  return best
end

-- Tiles a foe stands on, and those within foe_clearance steps of one.
local function foe_tiles(view, rules)
  local out = {}
  local list = {}
  local function add(c, r)
    local k = c .. "," .. r
    if not out[k] and not (c == view.mc and r == view.mr) then
      out[k] = true
      list[#list + 1] = { c, r }
    end
  end
  for _, f in ipairs(view.foes) do add(f.c, f.r) end
  for _ = 1, math.max(rules.foe_clearance, 0) do
    local grown = {}
    for _, x in ipairs(list) do grown[#grown + 1] = x end
    for _, x in ipairs(grown) do
      for _, s in ipairs(STEPS) do
        local nc, nr = x[1] + DX[s], x[2] + DY[s]
        if walkable(view.arena, nc, nr) then add(nc, nr) end
      end
    end
  end
  return out
end

-- Whether dropping a bomb here leaves a way out with margin to spare.
local function bomb_is_survivable(view, rules)
  local bombs = {}
  for i, b in ipairs(view.bombs) do bombs[i] = b end
  bombs[#bombs + 1] = { c = view.mc, r = view.mr, power = math.max(rules.assumed_power, rules.own_power), fuse_left = rules.fuse_frames }
  local after = danger(view.arena, bombs, rules)
  local refuge = find_refuge(view.arena, after, view.mc, view.mr, 0, rules, foe_tiles(view, rules))
  return refuge ~= nil and not (refuge.c == view.mc and refuge.r == view.mr) and refuge.slack >= rules.slack_frames
end

-- Decide what to do this frame: {step, drop_bomb, reason}.
local function plan(view, rules)
  local now = 0
  local live = danger(view.arena, view.bombs, rules)
  local blocked = foe_tiles(view, rules)

  -- 1. Is the tile under us going to burn, and when?
  local doomed = next_flame(live, view.mc, view.mr, now)
  if doomed ~= nil then
    local touching = {}
    for _, f in ipairs(view.foes) do touching[f.c .. "," .. f.r] = true end
    local escape
    for _, avoid in ipairs({ blocked, touching, {} }) do
      local r = find_refuge(view.arena, live, view.mc, view.mr, now, rules, avoid)
      if r and r.first then escape = r break end
    end
    if escape == nil then
      return { step = nil, drop_bomb = false, reason = HOLDING }
    end
    if doomed <= escape.arrive + rules.frames_per_tile + rules.slack_frames then
      return { step = escape.first, drop_bomb = false, reason = FLEEING }
    end
  end

  -- 2. Is a bomb here worth placing, and survivable?
  if view.bombs_spare > 0 and bomb_is_survivable(view, rules) then
    local hits = blast_cells(view.arena, view.mc, view.mr, rules.own_power)
    for _, f in ipairs(view.foes) do
      if f.killable and cells_contain(hits, f.c, f.r) then
        return { step = nil, drop_bomb = true, reason = ATTACKING }
      end
    end
    for _, h in ipairs(hits) do
      if tile_at(view.arena, h[1], h[2]) == BRICK then
        return { step = nil, drop_bomb = true, reason = DIGGING }
      end
    end
  end

  -- 3. Walk towards the nearest thing worth reaching.
  local arrivals, came = earliest_arrival(view.arena, live, view.mc, view.mr, now, rules, blocked)
  local tcost, tc, tr
  for r = 0, view.arena.rows - 1 do
    for c = 0, view.arena.cols - 1 do
      local cost = arrivals[index(view.arena, c, r)]
      if cost ~= nil and not (c == view.mc and r == view.mr) then
        local worth = false
        for _, f in ipairs(view.foes) do
          if f.killable and math.abs(f.c - c) + math.abs(f.r - r) <= rules.own_power then worth = true break end
        end
        if not worth then
          for _, s in ipairs(STEPS) do
            if tile_at(view.arena, c + DX[s], r + DY[s]) == BRICK then worth = true break end
          end
        end
        if worth and (tcost == nil or cost < tcost or (cost == tcost and coord_less(c, r, tc, tr))) then
          tcost, tc, tr = cost, c, r
        end
      end
    end
  end
  if tcost ~= nil then
    local step = first_step_of(came, view.arena, view.mc, view.mr, tc, tr)
    if step then return { step = step, drop_bomb = false, reason = HUNTING } end
  end
  if doomed ~= nil then
    for _, avoid in ipairs({ blocked, {} }) do
      local r = find_refuge(view.arena, live, view.mc, view.mr, now, rules, avoid)
      if r and r.first then return { step = r.first, drop_bomb = false, reason = FLEEING } end
    end
  end
  return { step = nil, drop_bomb = false, reason = HOLDING }
end

---------------------------------------------------------------------------
-- The seat (dynaseat): eyes from RAM, Copperline's pilot
---------------------------------------------------------------------------

local RECORD0, STRIDE, MAX_PLAYERS = 0x44f08, 0x28, 4
local F_X, F_Y, F_MAX_BOMBS, F_BLAST, F_BOMBS_OUT = 0x00, 0x02, 0x10, 0x12, 0x14
local MAZE, COLS, ROWS, COLUMN_BYTES = 0x4682e, 13, 11, 26
local T_FLOOR, T_BRICK, T_PILLAR = 0x3c, 0x3b, 0x27
local TILE_PX = 16
local CLOCK, CLOCK_STILL = 0x439b1, 75
local FIRE_HOLD, FIRE_GAP, REPLAN_AT_LEAST_EVERY = 3, 8, 40
local PROMPT_TAP_EVERY, PROMPT_TAP_HOLD = 75, 10

-- Measured on this game in WinUAE; rounded the cautious way.
local rules = {
  frames_per_tile = 14, fuse_frames = 120, blast_frames = 30,
  own_power = 2, assumed_power = 3, slack_frames = 15,
  horizon_frames = 240, foe_clearance = 1,
}

local me, players = 0, 4
local tick = 0
local prev_out = { 0, 0, 0, 0 }
local bombs = {}          -- {owner, c, r, power, placed, gone_off}
local was_c, was_r = nil, nil
local planned_at = 0
local off_x, off_y = 0.5, 0.5
local current = { step = nil, drop_bomb = false, reason = HOLDING }
local held, held_since = nil, 0
local fire_for, fire_gap = 0, 0
local clock, clock_moved = nil, 0
local stats = { rounds = 0, drops = 0, playing = false }

local function u16(s, i)                    -- big-endian word at 0-based offset
  return s:byte(i + 1) * 256 + s:byte(i + 2)
end

local function clamp(v, lo, hi)
  if v < lo then return lo elseif v > hi then return hi else return v end
end

local function read_players()
  local s = ram.bytes(RECORD0, STRIDE * players)
  if not s then return nil end
  local all = {}
  for p = 0, players - 1 do
    local b = p * STRIDE
    all[p + 1] = {
      x = u16(s, b + F_X), y = u16(s, b + F_Y),
      bombs_out = clamp(u16(s, b + F_BOMBS_OUT), 0, 8),
      max_bombs = clamp(u16(s, b + F_MAX_BOMBS), 1, 8),
      blast = clamp(u16(s, b + F_BLAST), 1, 8),
    }
  end
  return all
end

-- The maze, column-major in RAM; nil unless the pillar lattice is all there.
local function read_maze()
  local s = ram.bytes(MAZE, COLUMN_BYTES * COLS)
  if not s then return nil end
  local tiles = {}
  for c = 0, COLS - 1 do
    for r = 0, ROWS - 1 do
      local v = u16(s, c * COLUMN_BYTES + 2 + r * 2)
      local pillar_slot = (c % 2 == 1) and (r % 2 == 1)
      if pillar_slot ~= (v == T_PILLAR) then return nil end
      local t = FLOOR                         -- a bomb, a flame, a power-up
      if v == T_BRICK then t = BRICK elseif v == T_PILLAR then t = PILLAR end
      tiles[r * COLS + c + 1] = t
    end
  end
  return { cols = COLS, rows = ROWS, tiles = tiles }
end

local function tile_of(s)
  return (s.x + TILE_PX // 2) // TILE_PX, (s.y + TILE_PX // 2) // TILE_PX
end

-- Every bomber's count of live bombs: up is a bomb under it, down is its
-- oldest gone off.
local function track_bombs(all)
  for p = 1, #all do
    local s, before = all[p], prev_out[p]
    if s.bombs_out > before then
      local c, r = tile_of(s)
      for _ = before + 1, s.bombs_out do
        bombs[#bombs + 1] = { owner = p, c = c, r = r, power = s.blast, placed = tick }
      end
    elseif s.bombs_out < before then
      for _ = s.bombs_out + 1, before do
        local oldest
        for _, b in ipairs(bombs) do
          if b.owner == p and b.gone_off == nil and (oldest == nil or b.placed < oldest.placed) then oldest = b end
        end
        if oldest then oldest.gone_off = tick end
      end
    end
    prev_out[p] = s.bombs_out
  end
  local kept = {}
  for _, b in ipairs(bombs) do
    local keep
    if b.gone_off then keep = tick - b.gone_off <= rules.blast_frames
    else keep = tick - b.placed <= rules.fuse_frames * 2 + rules.blast_frames end
    if keep then kept[#kept + 1] = b end
  end
  bombs = kept
end

local function make_view(all, arena)
  local s = all[me + 1]
  local mc, mr = tile_of(s)
  off_x = ((s.x + TILE_PX // 2) % TILE_PX) / TILE_PX
  off_y = ((s.y + TILE_PX // 2) % TILE_PX) / TILE_PX
  if inside(arena, mc, mr) then arena.tiles[index(arena, mc, mr)] = FLOOR end
  local foes = {}
  for p = 1, #all do
    if p ~= me + 1 then
      local c, r = tile_of(all[p])
      foes[#foes + 1] = { c = c, r = r, killable = true }
    end
  end
  local vb = {}
  for _, b in ipairs(bombs) do
    local fuse
    if b.gone_off then fuse = -(tick - b.gone_off) else fuse = rules.fuse_frames - (tick - b.placed) end
    vb[#vb + 1] = { c = b.c, r = b.r, power = b.power, fuse_left = fuse }
  end
  return { arena = arena, mc = mc, mr = mr, bombs = vb, foes = foes, bombs_spare = math.max(s.max_bombs - s.bombs_out, 0) }
end

-- A turn across the axis of travel waits until lined up with the corridor.
local function steer()
  local step = current.step
  if step == nil then return nil end
  local LINED_UP = 0.25
  local aligned
  if step == NORTH or step == SOUTH then aligned = math.abs(off_x - 0.5) <= LINED_UP
  else aligned = math.abs(off_y - 0.5) <= LINED_UP end
  if aligned then return step end
  if step == NORTH or step == SOUTH then
    return off_x < 0.5 and EAST or WEST
  end
  return off_y < 0.5 and SOUTH or NORTH
end

local STEP_BITS = { [NORTH] = bits.UP, [SOUTH] = bits.DOWN, [EAST] = bits.RIGHT, [WEST] = bits.LEFT }

function init(port, n)
  me = ({ [2] = 0, [3] = 1, [1] = 2, [0] = 3 })[port] or 0
  players = clamp(n, 2, MAX_PLAYERS)
  if me >= players then me = players - 1 end
  print(("dynablaster.lua: port %d, record %d of %d"):format(port, me, players))
end

function frame(n)
  tick = tick + 1
  local all = read_players()
  if not all then return 0 end
  track_bombs(all)

  -- In play only while the round clock moves: the maze stays in RAM, and a
  -- valid lattice, on every screen between rounds.
  local raw = ram.bytes(CLOCK, 5)
  local cl = raw and (raw:sub(1, 1) .. raw:sub(3, 3) .. raw:sub(5, 5))   -- M, S, S
  if cl ~= clock then clock, clock_moved = cl, tick end
  local arena = (tick - clock_moved < CLOCK_STILL) and read_maze() or nil
  local playing = arena ~= nil
  if playing ~= stats.playing then
    if playing then
      stats.rounds = stats.rounds + 1
      was_c, held = nil, nil
      current = { step = nil, drop_bomb = false, reason = HOLDING }
    end
    stats.playing = playing
  end
  if not playing then
    return (tick % PROMPT_TAP_EVERY < PROMPT_TAP_HOLD) and bits.FIRE or 0
  end

  local view = make_view(all, arena)
  local arrived = not (was_c == view.mc and was_r == view.mr)
  local crowded = false
  for _, f in ipairs(view.foes) do
    if math.abs(f.c - view.mc) + math.abs(f.r - view.mr) <= 2 then crowded = true break end
  end
  local threatened = crowded or lethal_between(danger(view.arena, view.bombs, rules), view.mc, view.mr, 0, rules.frames_per_tile * 3)
  local stale = tick - planned_at >= REPLAN_AT_LEAST_EVERY
  if arrived or threatened or stale then
    local fresh = plan(view, rules)
    local step_still_clear = false
    if current.step then
      local dc, dr = view.mc + DX[current.step], view.mr + DY[current.step]
      step_still_clear = true
      for _, f in ipairs(view.foes) do
        if math.abs(f.c - dc) + math.abs(f.r - dr) <= 1 then step_still_clear = false break end
      end
    end
    local keep_old = not arrived and not stale and current.reason == HUNTING and fresh.reason == HUNTING
      and not fresh.drop_bomb and step_still_clear
    if not keep_old then current = fresh end
    planned_at = tick
    was_c, was_r = view.mc, view.mr
  end

  if current.drop_bomb and fire_for == 0 and fire_gap == 0 and view.bombs_spare > 0 then
    fire_for, fire_gap = FIRE_HOLD, FIRE_HOLD + FIRE_GAP
    stats.drops = stats.drops + 1
  end
  local firing = fire_for > 0
  fire_for = math.max(fire_for - 1, 0)
  fire_gap = math.max(fire_gap - 1, 0)

  local want = steer()
  -- The turnaround debounce: no walking straight back over ground just
  -- covered, unless fleeing.
  if current.reason ~= FLEEING and want and held and want == OPPOSITE[held]
      and tick - held_since <= rules.frames_per_tile * 2 then
    want = nil
  end
  local out = firing and bits.FIRE or 0
  if want then
    out = out | STEP_BITS[want]
    if held ~= want then held, held_since = want, tick end
  end
  return out
end