-- moving player without moving any crates

function draw_crate_to_move()
  if crate_to_move == nil then return end
  color(1,0,0)
  local x,y = crate_to_move.x, crate_to_move.y
  rect('line', left+(x-1)*side, top+(y-1)*side, side, side)
end

function animate_pending_moves()
  if next_pending_move and Current_time >= next_pending_move then
    local dir = table.remove(pending_moves)
    move(dir, --[[add to undo]] false)
    if #pending_moves > 0 then
      next_pending_move = Current_time + 0.1
    end
  end
end

function make_all_pending_moves()
  while #pending_moves > 0 do
    local dir = table.remove(pending_moves)
    move(dir, --[[add to undo]] false)
  end
end

function plan_move_to_empty_space(y, x)
  local path = find_empty_path(level_state, player, {y=y, x=x})
  if path == nil then return end
  pending_moves = unwind_steps(path, {})
  local src = level_state[player.y][player.x]
  local dest = level_state[y][x]
  local u = {
    {x=player.x, y=player.y, cell=src},
    {x=x, y=y, cell=dest}}
  table.insert(undo_history, u)  -- add to undo without making move yet
  next_pending_move = Current_time
end

function find_empty_path(level, src, dst)
  if not is_empty(level, dst.x, dst.y) then
    return
  end
  local done = initialize_array(false, lh, lw)
  local cands = {}
  table.insert(cands, {x=src.x, y=src.y})
  while #cands > 0 do
    local cand = table.remove(cands, 1)
    local x,y = cand.x, cand.y
    if x == dst.x and y == dst.y then return cand end
    if y >= 1 and y <= lh and x >= 1 and x <= lw and not done[y][x] then
      done[y][x] = true
      local curr = level[y][x]
      if curr ~= CELL_WALL and curr ~= CELL_CRATE and curr ~= CELL_CRATE_ON_TARGET then
        table.insert(cands, {x=x-1, y=y, dir='left', prev=cand})
        table.insert(cands, {x=x+1, y=y, dir='right', prev=cand})
        table.insert(cands, {x=x, y=y-1, dir='up', prev=cand})
        table.insert(cands, {x=x, y=y+1, dir='down', prev=cand})
      end end end end

function is_empty(level, x,y)
  local curr = level[y][x]
  return curr ~= CELL_WALL and curr ~= CELL_CRATE and curr ~= CELL_CRATE_ON_TARGET
end

function unwind_path(c)
  local result = {}
  while c do
    table.insert(result, {x=c.x, y=c.y})
    c = c.prev
  end
  return result
end

function unwind_steps(c, out)
  -- insert steps in reverse order
  while c do
    table.insert(out, c.dir)
    c = c.prev
  end
  return out
end

function initialize_array(val, dim, ...)
  local result = {}
  local other_dims = {...}
  if #other_dims == 0 then
    for i=1,dim do
      table.insert(result, val)
    end
  else
    for i=1,dim do
      table.insert(result, initialize_array(val, ...))
    end
  end
  return result
end

function dump_path(c)
  if c == nil then return end
  if not c.dir then
    assert(not c.moves)
    assert(not c.prev)
    io.stdout:write('\n')
    return
  end
  io.stdout:write('p'..c.dir..' ')
  local c2 = c.moves
  while c2 do
    if c2.dir then
      io.stdout:write('m'..c2.dir..' ')
    end
    c2 = c2.prev
  end
  dump_path(c.prev)
end