-- moving crate without moving any other crates
-- idea 1
--? function find_path_for_crate(level, src, crate_to_move, dst)
--?   local done = {}
--?   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})
--?       elseif curr == CELL_CRATE and crate_id[y][x] == cid then
--?         -- TODO: actually simulate a real move of a crate
--?         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 find_path_for_crate(level, player, crate, dst)
  local done = initialize_array(false, lh, lw)
  local cands = {}
  table.insert(cands, {crate={x=crate.x, y=crate.y}, player={x=player.x, y=player.y}})
  while #cands > 0 do
    local cand = table.remove(cands, 1)
    local p, c = cand.player, cand.crate
    if c.x == dst.x and c.y == dst.y then return cand end
    if c.y >= 1 and c.y <= lh and c.x >= 1 and c.x <= lw and not done[c.y][c.x] then
      done[c.y][c.x] = true
      local curr = level[c.y][c.x]
      if curr ~= CELL_WALL and (curr ~= CELL_CRATE or crate_id[c.y][c.x] ~= crate.id) and (curr ~= CELL_CRATE_ON_TARGET or crate_id[c.y][c.x] ~= crate.id) then
        -- try to push crate left, by first getting to the right of it
        local moves = find_almost_empty_path(level, p, {x=c.x+1, y=c.y}, crate.id)
        if moves or (p.x == c.x+1 and p.y == c.y) then
          -- after the push, both player and crate have moved
          table.insert(cands, {player={x=c.x, y=c.y}, crate={x=c.x-1, y=c.y}, dir='left', moves=moves, prev=cand})
        end
        -- try to push crate right
        moves = find_almost_empty_path(level, p, {x=c.x-1, y=c.y}, crate.id)
        if moves or (p.x == c.x-1 and p.y == c.y) then
          table.insert(cands, {player={x=c.x, y=c.y}, crate={x=c.x+1, y=c.y}, dir='right', moves=moves, prev=cand})
        end
        -- try to push crate up
        local moves = find_almost_empty_path(level, p, {x=c.x, y=c.y+1}, crate.id)
        if moves or (p.x == c.x and p.y == c.y+1) then
          table.insert(cands, {player={x=c.x, y=c.y}, crate={x=c.x, y=c.y-1}, dir='up', moves=moves, prev=cand})
        end
        -- try to push crate down
        moves = find_almost_empty_path(level, p, {x=c.x, y=c.y-1}, crate.id)
        if moves or (p.x == c.x and p.y == c.y-1) then
          table.insert(cands, {player={x=c.x, y=c.y}, crate={x=c.x, y=c.y+1}, dir='down', moves=moves, prev=cand})
        end
      end end end end

function find_almost_empty_path(level, src, dst, cid)
  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 or crate_id[y][x] ~= cid) and (curr ~= CELL_CRATE_ON_TARGET or crate_id[y][x] ~= cid) 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 unwind_steps_to_move_crate(c, out)
  -- insert steps in reverse order
  while c do
    table.insert(out, c.dir)
    unwind_steps(c.moves, out)
    c = c.prev
  end
  return out
end

function plan_move_crate(y, x)
  local path = find_path_for_crate(level_state, player, crate_to_move, {y=y, x=x})
  if path == nil then return end
  pending_moves = unwind_steps_to_move_crate(path, {})
  for i=#pending_moves,1,-1 do print(pending_moves[i]) end
  local src = level_state[player.y][player.x]
  local crate_cell = level_state[crate_to_move.y][crate_to_move.x]
  local dest = level_state[y][x]
  local u = {
    {x=player.x, y=player.y, cell=src},
    {x=crate_to_move.x, y=crate_to_move.y, cell=crate_cell},
    {x=x, y=y, cell=dest}}
  print('player initial', player.x, player.y, src)
  print('crate initial', crate_to_move.x, crate_to_move.y, crate_cell)
  print('crate final', x, y, dest)
  -- we also need to save the initial state of the final position of the player
  local fpy,fpx = compute_cell(y,x, opposite_dir(pending_moves[1]))
  print('player final', fpx, fpy, level_state[fpy][fpx])
  table.insert(u, {x=fpx, y=fpy, cell=level_state[fpy][fpx]})
  table.insert(undo_history, u)  -- add to undo without making move yet
  next_pending_move = Current_time
end

function compute_cell(y, x, dir)
  if dir == 'up' then
    return y-1, x
  elseif dir == 'down' then
    return y+1, x
  elseif dir == 'left' then
    return y, x-1
  elseif dir == 'right' then
    return y, x+1
  end end
function opposite_dir(dir)
  if dir == 'up' then
    return 'down'
  elseif dir == 'down' then
    return 'up'
  elseif dir == 'left' then
    return 'right'
  elseif dir == 'right' then
    return 'left'
  end end

      -- TODO: do something here

      plan_move_crate(y, x)