-- Z-Out (WHDLoad v3.5) bot: dodges what comes at the ship, lines up with
-- the nearest enemy ahead and keeps firing. Made from the R-Type bot
-- (playbooks/rtype/bots/rtype.lua): the same look-ahead search over moves,
-- with Z-Out's own addresses.
--
-- What it reads, all found with probe bots from the AROS start state
-- (playbooks/zout/to-game-aros.script):
--   players     records 0xd4 bytes apart: player 1 at 0x8306, player 2 at
--               0x83da. x = word +0x0c, y = word +0x0e (0x8312/0x8314 for
--               player 1); lives = byte +0x22 (0x8328). The ship moves
--               3 px a frame, x 4..199, y 24..219, and is about 30 x 12 px
--               from (x, y) in the coordinates the objects use.
--   objects     a table of 0x68-byte records from 0x93c0: x, y, w, h words
--               at +0 (x signed: negative is off the left edge), the box of
--               the thing from about (x, y). A free record is 0/0 or parked
--               at 500/500. Fighters are 29 x 7, the ground walkers 22 x 26,
--               their shots 4 x 4 (drawn bigger: 8 x 8). Word +0x16 tells
--               kinds apart (0x22 fighters, 0x20 walkers, 1 shots). The long
--               at +0x10 points into the thing's animation; 0x7abce..0x7abf0
--               are the explosions and the ends of them (0x7abd8, 0x7abe4,
--               0x7abf0), where a thing that is dead or not yet in play sits,
--               keeping its last x, y. Those are ignored. The carrier that leaves a power-up has
--               +0x0c = 0x0007acea.
--   power-ups   the capsule a carrier leaves is not in the table: it is drawn
--               into the picture in the wall colours. The bot follows it there
--               from where its carrier died, flies into it and does not count
--               it as wall. Gone from the picture while touching the ship,
--               it was taken.
--   the picture one 5-plane interleaved bitmap, 220 bytes a line (44 a
--               plane), the copper list at 0x7b2c setting its pointer
--               (BPL1PTH value at 0x7b2e, BPL1PTL at 0x7b32, bit 0 to be
--               dropped) and the fine scroll (BPLCON1 value at 0x7c2e). The
--               background art uses colours 0-15 only; what is drawn over it
--               uses 16-31: the floor pipes and the big structures (walls,
--               16-23 and 28-31), the shots of both sides (orange, 24-27).
--               The ship and the enemies are sprites, not in it. A point
--               (x, y) in object coordinates is pixel (x + 17 - fine scroll,
--               y - vscroll), vscroll the word at 0x83aa (the screen follows
--               the ship up and down).
--   the ship    in the same coordinates covers about x-3..x+27, y+2..y+13.
local REC = { [1] = 0x8306, [0] = 0x83da }
local OBJ, STRIDE, SLOTS = 0x93c0, 0x68, 48
local SPEED = 3
local HORIZON = 16          -- frames looked ahead
-- and further, for the big things that are not shots: a swirl 32 px high
-- has to be got out of the way of early
-- (every frame near, then every other: the search has an instruction budget)
local TIMES = { 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 20, 24, 28, 32 }
local REACH_MAX = 14
local SHIP_W, SHIP_H = 30, 12
local MARGIN = 10           -- keep this much more than touching, when it costs nothing
local X_MIN, X_MAX = 4, 199
local Y_MIN, Y_MAX = 24, 219
local HOME_X = 64           -- where it likes to sit: left, with room to dodge
local ROW, PLANE, LINES = 220, 44, 200
local SCROLL = 0.5          -- terrain comes left half a pixel a frame
local TW, TH = 30, 12       -- the ship's box against terrain, from (x-3, y+2)
local bm, fine, vscroll      -- bm: the picture's address - 1 (for 1-based offsets)
local u8, floor, abs, max, min, sqrt = ram.u8, math.floor, math.abs, math.max, math.min, math.sqrt

local me = 1
local prev, prev2 = {}, {}
local deaths, lives_was = 0, nil
local pickups = 0
local CARRIER = 0x0007acea
local function harmless(r)
  local anim = ram.u32(r + 0x10)
  return anim >= 0x0007abce and anim <= 0x0007abf0
end
local carrier_at = {}       -- record -> where a live carrier was last seen
local capsule               -- { x, y, until_frame }: a power-up being followed

local MOVES = {
  { 0, 0, 0 }, { 0, -1, bits.UP }, { 0, 1, bits.DOWN }, { -1, 0, bits.LEFT }, { 1, 0, bits.RIGHT },
  { -1, -1, bits.UP | bits.LEFT }, { 1, -1, bits.UP | bits.RIGHT },
  { -1, 1, bits.DOWN | bits.LEFT }, { 1, 1, bits.DOWN | bits.RIGHT },
}

function init(port, players)
  me = port
  print("zout bot on port " .. port .. " of " .. players)
end

local function s16(v) if v >= 0x8000 then return v - 0x10000 end return v end

-- The mines (24 x 24) turn as wheels: four round a fifth in the middle, the
-- whole moving across the screen and stopping. Straight-line guesses miss
-- them, so a wheel is one thing: a square as wide as it, moving as its
-- middle mine moves. A middle mine is one with three or more others at
-- about the same distance from it.
local wheels_was = {}
local function wheel(list)
  local mines = {}
  for _, o in ipairs(list) do
    if o.w == 24 and o.h == 24 then mines[#mines + 1] = o end
  end
  local found = {}
  for _, c in ipairs(mines) do
    local rmax, rmin, k = 0, math.huge, 0
    for _, o in ipairs(mines) do
      local d = math.sqrt((o.x - c.x) ^ 2 + (o.y - c.y) ^ 2)
      if d > 30 and d < 75 then k, rmax, rmin = k + 1, math.max(rmax, d), math.min(rmin, d) end
    end
    if k >= 3 and rmax - rmin < 16 then
      -- its mines are the wheel now
      c.member = true
      for _, o in ipairs(mines) do
        local d = math.sqrt((o.x - c.x) ^ 2 + (o.y - c.y) ^ 2)
        if d < 75 then o.member = true end
      end
      local cx, cy = c.x + 12, c.y + 12
      local dx, dy = 0, 0
      for _, w in ipairs(wheels_was) do
        if math.abs(w[1] - cx) < 12 and math.abs(w[2] - cy) < 12 then dx, dy = cx - w[1], cy - w[2] end
      end
      found[#found + 1] = { cx, cy }
      local half = rmax + 14
      list[#list + 1] = { x = cx - half, y = cy - half, w = 2 * half, h = 2 * half, dx = dx, dy = dy,
                          kind = 0, shot = false, wheel = true, cx = cx, cy = cy, r = rmax + 17 }
    end
  end
  wheels_was = found
end

local function objects()
  local list = {}
  for k = 0, SLOTS - 1 do
    local r = OBJ + k * STRIDE
    local x, y = s16(ram.u16(r)), s16(ram.u16(r + 2))
    local w, h = ram.u16(r + 4), ram.u16(r + 6)
    local dead = harmless(r)
    if ram.u32(r + 0x0c) == CARRIER then
      if not dead then carrier_at[r] = { x + 10, y + 10 }
      elseif carrier_at[r] then
        -- shot down: its capsule appears there
        capsule = { x = carrier_at[r][1], y = carrier_at[r][2], left = 250, age = 0 }
        carrier_at[r] = nil
      end
    end
    if not dead and not (x == 0 and y == 0) and not (x == 500 and y == 500) and w > 0 and w < 96 and h > 0 and h < 96
       and x > -64 and x < 400 and y > -64 and y < 300 then
      local p = prev2[r]
      local dx, dy = 0, 0
      if p then dx, dy = (x - p[1]) / 2, (y - p[2]) / 2 end
      prev2[r] = prev[r]
      prev[r] = { x, y }
      if math.abs(dx) < 12 and math.abs(dy) < 12 then
        -- small things are drawn bigger than their box
        local pad = (w < 8 or h < 8) and 4 or 0
        list[#list + 1] = { x = x - pad, y = y - pad, w = w + 2 * pad, h = h + 2 * pad, dx = dx, dy = dy,
                            kind = ram.u16(r + 0x16), shot = w < 8 }
      end
    else
      prev[r], prev2[r] = nil, nil
    end
  end
  wheel(list)
  return list
end

local function read_bitmap()
  local base = ((ram.u16(0x7b2e) << 16) | ram.u16(0x7b32)) & ~1
  if base == 0 or base >= 0x100000 then bm = nil; return end
  -- read in place (ram.u8), not copied: the picture does not change while
  -- frame() runs, and most of it is never looked at
  bm = base - 1
  fine = ram.u16(0x7c2e) & 15
  vscroll = ram.u16(0x83aa)
end

-- A wall at (x, y), object coordinates: drawn on in a wall colour. Off the
-- picture is open (the ship's own limits keep it in).
local function wall_colour(bx, by)
  if bx < 0 or bx >= 352 or by < 0 or by >= LINES then return false end
  local i = by * ROW + (bx >> 3) + 1
  local m = 0x80 >> (bx & 7)
  if u8(bm + i + 4 * PLANE) & m == 0 then return false end
  local c = (u8(bm + i + 3 * PLANE) & m ~= 0 and 8 or 0) | (u8(bm + i + 2 * PLANE) & m ~= 0 and 4 or 0)
  return c ~= 8
end

-- The capsule: the wall-coloured pixels near where it was last seen, their
-- middle. Lost when there are none.
local function track_capsule(sx, sy, n)
  if not capsule or not bm then return end
  capsule.left = capsule.left - 1
  capsule.age = capsule.age + 1
  local ax, ay, c = 0, 0, 0
  local bx0, by0 = math.floor(capsule.x) + 17 - fine, math.floor(capsule.y) - vscroll
  for by = by0 - 14, by0 + 14, 2 do
    for bx = bx0 - 16, bx0 + 16, 2 do
      if wall_colour(bx, by) then ax, ay, c = ax + bx, ay + by, c + 1 end
    end
  end
  -- a handful of pixels, not a wall
  -- the carrier's explosion comes first: wait for the capsule
  if c < 3 and capsule.age < 60 then return end
  if c < 3 or c > 90 or capsule.left <= 0 then
    if c < 3 and math.abs(capsule.x - (sx + 12)) < 26 and math.abs(capsule.y - (sy + 8)) < 20 then
      pickups = pickups + 1; print("power-up " .. pickups .. " at frame " .. n)
    end
    capsule = nil
    return
  end
  capsule.x, capsule.y = ax / c - 17 + fine, ay / c + vscroll
end

-- A wall at (x, y), in two steps for the loops that test many points of
-- a row: row(y) once (where the row starts in the picture, nil off it, and
-- whether the capsule's box takes the row), then wall_at(...) per point.
local function row(y)
  local by = floor(y) - vscroll
  local off = (by >= 0 and by < LINES) and (bm + by * ROW + 1) or nil
  return off, capsule and abs(y - capsule.y) < 16
end
local function wall_at(off, cap_row, x)
  -- the capsule is not wall: it is flown into
  if cap_row and abs(x - capsule.x) < 18 then return false end
  local bx = floor(x) + 17 - fine
  if not off or bx < 0 or bx >= 352 then return false end
  local i = off + (bx >> 3)
  local m = 0x80 >> (bx & 7)
  if u8(i + 4 * PLANE) & m == 0 then return false end
  -- 24-27 are shots
  return not (u8(i + 3 * PLANE) & m ~= 0 and u8(i + 2 * PLANE) & m == 0)
end

-- How much of the ship's box at (px, py) is wall, sampled every 3 px.
local WALL_ROWS = { 0, 3, 6, 9, 12, 15 }
local wall_cache = {}
local function wall(px, py)
  if not bm then return 0 end
  px, py = math.floor(px), math.floor(py)
  local key = px * 1024 + py
  local hit = wall_cache[key]
  if hit then return hit end
  local c = 0
  -- a pixel or two more than the ship all round: touching is dying
  for _, yy in ipairs(WALL_ROWS) do
    local off, cr = row(py + yy)
    if off or cr then
      for xx = -4, TW - 3, 3 do
        if wall_at(off, cr, px + xx) then c = c + 1 end
      end
    end
  end
  wall_cache[key] = c
  return c
end
local WALL_T = { 1, 3, 6, 10 }

-- Wall close round the ship's box at (px, py): a gap between pillars or a
-- ledge is a place to be caught in when something comes.
local near_cache = {}
local function near_wall(px, py)
  if not bm then return 0 end
  px, py = math.floor(px), math.floor(py)
  local key = px * 1024 + py
  local hit = near_cache[key]
  if hit then return hit end
  local c = 0
  for yy = -10, TH + 12, 4 do
    local off, cr = row(py + yy)
    if off or cr then
      for xx = -18, TW + 10, 5 do
        if wall_at(off, cr, px + xx) then c = c + 1 end
      end
    end
  end
  near_cache[key] = c
  return c
end

-- How far right the corridor at height y is clear: the ship's top, middle
-- and bottom rows, until two of the three are wall.
local FREE_MAX = 200
local function free_run(x0, y)
  if not bm then return FREE_MAX end
  local o1, c1 = row(y + 2)
  local o2, c2 = row(y + 2 + TH // 2)
  local o3, c3 = row(y + 1 + TH)
  for d = 0, FREE_MAX, 4 do
    local xa, xb = x0 + d - 3, x0 + d + TW - 4
    local c = 0
    if wall_at(o1, c1, xa) or wall_at(o1, c1, xb) then c = c + 1 end
    if wall_at(o2, c2, xa) or wall_at(o2, c2, xb) then c = c + 1 end
    -- (the third row only decides when the first two split)
    if c == 1 and (wall_at(o3, c3, xa) or wall_at(o3, c3, xb)) then c = 2 end
    if c >= 2 then return d end
  end
  return FREE_MAX
end

-- Where the ship is t frames on, flying move a for SPLIT frames, then b.
local SPLIT = 5
-- how many of TIMES are SPLIT frames on or less
local NEAR = 0
for _, t in ipairs(TIMES) do if t <= SPLIT then NEAR = NEAR + 1 end end
local function at(sx, sy, a, b, t)
  local t1 = math.min(t, SPLIT)
  local t2 = t - t1
  local px = sx + (a[1] * t1 + b[1] * t2) * SPEED
  local py = sy + (a[2] * t1 + b[2] * t2) * SPEED
  return math.max(X_MIN, math.min(X_MAX, px)), math.max(Y_MIN, math.min(Y_MAX, py))
end

-- What each thing in reach is at each moment ahead, worked out once a
-- frame (it is the same for every pair of moves tried): a circle
-- { true, cx, cy, r } or a box { false, middle x, half width, middle y,
-- half height, grow }. Things the search skips at that moment are left out.
local function views_of(list)
  local views = {}
  for ti, t in ipairs(TIMES) do
    local far = t > HORIZON
    local v = {}
    for _, o in ipairs(list) do
      if (far and o.shot) or o.member then
      elseif o.wheel then
        v[#v + 1] = { true, o.cx + o.dx * t, o.cy + o.dy * t, o.r }
      else
        local ox, oy = o.x + o.dx * t, o.y + o.dy * t
        -- the further on, the less sure where it is: things that turn (the
        -- mines go round in circles) get a box that grows with their speed
        local grow = o.shot and 0 or min(16, (abs(o.dx) + abs(o.dy)) * t * 0.2)
        v[#v + 1] = { false, ox + o.w / 2, (SHIP_W + o.w) / 2, oy + o.h / 2, (SHIP_H + o.h) / 2, grow }
      end
    end
    views[ti] = v
  end
  return views
end

-- One moment's danger terms for the ship at (px, py), added to d one by
-- one in a fixed order; with rec, each term is also kept, to be added
-- again later in the same order (so the sums agree to the last bit).
-- Every term is >= 0: once d reaches bound it can only lose, and it stops.
local function step(d, px, py, t, v, bound, rec)
  local far = t > HORIZON
  -- the edges are corners to be caught in
  if px <= X_MIN + 4 or py <= Y_MIN + 4 or py >= Y_MAX - 4 then
    d = d + 2; if rec then rec[#rec + 1] = 2 end
  end
  -- nowhere to back off to on the left: what comes at the ship there
  -- (most things come from the right) can only be dodged up or down
  if px < X_MIN + 30 then
    local e = (X_MIN + 30 - px) * 0.15
    d = d + e; if rec then rec[#rec + 1] = e end
  end
  local mx, my = px + 12, py + 8
  -- (the weights stand for the frames skipped)
  local wt = t > 6 and 2 or 1
  for i = 1, #v do
    local o = v[i]
    local e = 0
    if o[1] then
      -- a circle: the nearest point of the ship's box to its middle
      local cx, cy = o[2], o[3]
      local nx = max(px - 3, min(px + 27, cx))
      local ny = max(py + 2, min(py + 14, cy))
      local gap = sqrt((nx - cx) ^ 2 + (ny - cy) ^ 2) - o[4]
      if gap < 0 then
        e = far and 8 or (HORIZON + 1 - t) * 10 * wt
      elseif gap < MARGIN and not far then
        e = (HORIZON + 1 - t) * 0.5
      end
    else
      local gx = abs(o[2] - mx) - o[3] - o[6]
      -- every term needs gx under MARGIN (under 0, far on): only then is gy
      -- worth working out
      if gx < (far and 0 or MARGIN) then
        local gy = abs(o[4] - my) - o[5] - o[6]
        if far then
          if gx < 0 and gy < 0 then e = 8 end
        elseif gx < 0 and gy < 0 then
          e = (HORIZON + 1 - t) * 10 * wt
        elseif gx < MARGIN and gy < MARGIN then
          e = (HORIZON + 1 - t) * 0.5 * wt
        end
      end
    end
    if e ~= 0 then
      d = d + e; if rec then rec[#rec + 1] = e end
      if d >= bound then return d end
    end
  end
  return d
end

-- How bad flying a, then b, is: the walls the ship meets, then the things.
-- Up to SPLIT frames on, the ship is where a alone takes it, so those
-- moments' terms are the same for every b: worked out with the first b
-- tried and kept in pre[a].
local function danger(sx, sy, a, b, views, bound, pre)
  local d = 0
  for _, t in ipairs(WALL_T) do
    local px, py = at(sx, sy, a, b, t)
    -- the wall comes to the ship: look where the ship will be, that far right
    local c = wall(px + SCROLL * t, py)
    if c > 0 then d = d + (HORIZON + 1 - t) * 8 * c end
  end
  if d >= bound then return d end
  local first = 1
  local kept = pre[a]
  if kept then
    for i = 1, #kept do
      d = d + kept[i]
      if d >= bound then return d end
    end
    first = NEAR + 1
  end
  local rec = not kept and {} or nil
  for ti = first, #TIMES do
    local t = TIMES[ti]
    local px, py = at(sx, sy, a, b, t)
    d = step(d, px, py, t, views[ti], bound, ti <= NEAR and rec or nil)
    if d >= bound then return d end
    if ti == NEAR and rec then pre[a] = rec; rec = nil end
  end
  return d
end

function frame(n)
  local rec = REC[me] or REC[1]
  local lives = ram.u8(rec + 0x22)
  if lives_was and lives < lives_was then deaths = deaths + 1; print("death " .. deaths .. " at frame " .. n) end
  lives_was = lives
  local sx, sy = s16(ram.u16(rec + 0x0c)), s16(ram.u16(rec + 0x0e))
  local list = objects()
  read_bitmap()
  wall_cache = {}
  near_cache = {}
  track_capsule(sx, sy, n)

  -- the enemy to line up with: the nearest thing ahead that is not a shot
  local target, tdist
  for _, o in ipairs(list) do
    if not o.shot and not o.wheel and o.x > sx + 20 and o.x < 320 then
      local aim = o.y + o.h / 2 - SHIP_H / 2
      local dist = (o.x - sx) + math.abs(aim - sy) * 0.5
      if not target or dist < tdist then target, tdist = { x = o.x, y = aim }, dist end
    end
  end
  -- the height to make for: the most open corridor ahead, near where the
  -- ship is; an enemy to line up with only where the way is open
  -- a power-up first: fly into it (the ship's middle onto its middle)
  local home_x = HOME_X
  if capsule and capsule.x > sx - 30 then
    target = { x = capsule.x, y = capsule.y - 8, pickup = true }
    home_x = math.max(X_MIN, math.min(X_MAX, capsule.x - 12))
  end
  local want_y, best_open = sy, -math.huge
  local ys = {}
  for y = math.max(Y_MIN, sy - 60), math.min(Y_MAX, sy + 60), 8 do ys[#ys + 1] = y end
  if target then ys[#ys + 1] = math.max(Y_MIN, math.min(Y_MAX, target.y)) end
  -- a wheel coming: it stops somewhere on the left and turns there, so the
  -- place to be is past it, above or below, whichever side has more room
  local wheel_y
  local nearest
  for _, w in ipairs(wheels_was) do
    if w[1] > sx - 40 and w[1] < sx + 330 and (not nearest or w[1] < nearest[1]) then nearest = w end
  end
  if nearest and nearest[1] - (sx + 27) > 120 then
    -- far enough off: line up with the middle mine and shoot it. The
    -- screen stops scrolling while a wheel's middle mine lives (it sets the
    -- hold flag, 0x784e8, every frame); 23 hits kill it
    wheel_y = nearest[2] - 8
    home_x = X_MIN + 4
  elseif nearest then
    wheel_y = (nearest[2] < (Y_MIN + Y_MAX) / 2) and (Y_MAX - 12) or (Y_MIN + 12)
  else
    -- mines flying in, not yet a wheel: it forms about where they are, so
    -- wait on the other side
    local my, k = 0, 0
    for _, o in ipairs(list) do
      if o.w == 24 and o.h == 24 and o.x < 330 and not o.member then my, k = my + o.y + 12, k + 1 end
    end
    if k > 0 then wheel_y = (my / k < (Y_MIN + Y_MAX) / 2) and (Y_MAX - 20) or (Y_MIN + 20) end
  end
  if wheel_y then ys[#ys + 1] = wheel_y end
  for _, y in ipairs(ys) do
    local run = free_run(sx, y)
    local v = run - math.abs(y - sy) * 0.35
    if wheel_y then v = v - math.abs(y - wheel_y) * 1.5 end
    -- the floor and the ceiling are where the shots and the walls are
    if y > 185 or y < 40 then v = v - 40 end
    if target and run >= math.min(40, math.max(0, target.x - sx - 20)) then
      v = v + (target.pickup and 120 or 60) - math.abs(y - target.y) * (target.pickup and 2.0 or 1.0)
    end
    if v > best_open then best_open, want_y = v, y end
  end

  -- Only what can reach the ship within the horizon matters to the search.
  local reach = {}
  for _, o in ipairs(list) do
    if math.abs(o.x - sx) < (o.shot and 120 or 200) and math.abs(o.y - sy) < 90 then
      o.dist = math.abs(o.x - sx) + math.abs(o.y - sy)
      reach[#reach + 1] = o
    end
  end
  -- the nearest only, when the screen is busy
  if #reach > REACH_MAX then
    table.sort(reach, function(p, q) return p.dist < q.dist end)
    for i = #reach, REACH_MAX + 1, -1 do reach[i] = nil end
  end
  local views, pre = views_of(reach), {}
  local best, best_score = MOVES[1], math.huge
  for _, m in ipairs(MOVES) do
    local nx, ny = sx + m[1] * SPEED, sy + m[2] * SPEED
    -- The score is the danger plus these, all >= 0, added in this order.
    -- Worked out first with a danger of 0, they say whether the move can
    -- still win: if not, its search is skipped, and a follow-up's danger
    -- matters only below the best score (the move picked is the same).
    local nw = near_wall(nx, ny) * 1.5
    local aim = math.abs(ny - want_y) * 1.0
    local home = math.abs(nx - home_x) * (capsule and 0.8 or 0.15)
    local out_of = nx < X_MIN or nx > X_MAX or ny < Y_MIN or ny > Y_MAX
    local floor_score = 0
    if out_of then floor_score = floor_score + 500 end
    floor_score = floor_score + nw
    floor_score = floor_score + aim + home
    if floor_score < best_score then
      -- the move now, judged by the best thing to do after it (the least is
      -- the same whatever order the follow-ups are tried in; the same move
      -- again first usually finds a low one soonest)
      local after = danger(sx, sy, m, m, views, best_score, pre)
      for _, m2 in ipairs(MOVES) do
        if after == 0 then break end
        if m2 ~= m then
          local dd = danger(sx, sy, m, m2, views, math.min(after, best_score), pre)
          if dd < after then after = dd end
        end
      end
      if after < best_score then
        local score = after
        if out_of then score = score + 500 end
        score = score + nw
        score = score + aim + home
        if score < best_score then best, best_score = m, score end
      end
    end
  end
  local out = best[3]
  if n % 4 < 2 then out = out | bits.FIRE end
  return out
end

function results()
  return { deaths = deaths, pickups = pickups }
end