-- moving crate without moving any other crates

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
--?   Real_print('--')
--?   vdump_path(path)
  pending_moves = unwind_steps_to_move_crate(path, {})
  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}}
  -- 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]))
  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 find_path_for_crate(level, player, crate, dst)
  local done = initialize_array(false, lh, lw)
  local cands = {}
--?   local i=0
  table.insert(cands, {crate={x=crate.x, y=crate.y}, player={x=player.x, y=player.y}, path_length=0})
--?   io.stdout:write('---\n')
  while #cands > 0 do
    local min_index = shortest_path(cands)
    local cand = table.remove(cands, min_index)
    local p, c = cand.player, cand.crate
--?     i = i+1
--?     io.stdout:write(tostring(i)..' '..tostring(crate.x)..','..tostring(crate.y)..' '..tostring(crate.id)..' '..tostring(p.x)..','..tostring(p.y)..' '..tostring(c.x)..','..tostring(c.y)..' ')
--?     dump_path(cand)
    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 (c.y == crate.y and c.x == crate.x)) and (curr ~= CELL_CRATE_ON_TARGET or (c.y == crate.y and c.x == crate.x)) then
        -- try to push crate left, by first getting to the right of it
        local moves = find_assumed_empty_path_to_empty_cell(level, p, {x=c.x+1, y=c.y}, --[[empty]] crate, --[[occupied]] c)
        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, path_length=cand.path_length+moves.path_length})
        end
        -- try to push crate right
        moves = find_assumed_empty_path_to_empty_cell(level, p, {x=c.x-1, y=c.y}, crate, c)
        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, path_length=cand.path_length+moves.path_length})
        end
        -- try to push crate up
        local moves = find_assumed_empty_path_to_empty_cell(level, p, {x=c.x, y=c.y+1}, crate, c)
        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, path_length=cand.path_length+moves.path_length})
        end
        -- try to push crate down
        moves = find_assumed_empty_path_to_empty_cell(level, p, {x=c.x, y=c.y-1}, crate, c)
        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, path_length=cand.path_length+moves.path_length})
        end
      end end end end


-- like find_empty_path, but always allow going through empty_cell and never allow going through occupied_cell, regardless of what level says
function find_assumed_empty_path_to_empty_cell(level, src, dst, empty_cell, occupied_cell)
  if not is_assumed_empty(level, dst.x, dst.y, empty_cell, occupied_cell) then
    return
  end
  local done = initialize_array(false, lh, lw)
  local cands = {}
--?   Real_print('find', src.x, src.y, '-', dst.x, dst.y, '-', empty_cell.x, empty_cell.y, '-', occupied_cell.x, occupied_cell.y)
  table.insert(cands, {x=src.x, y=src.y, path_length=0})
  while #cands > 0 do
    local cand = table.remove(cands, 1)
    local x,y, p = cand.x, cand.y, cand.path_length
    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
      if is_assumed_empty(level, x,y, empty_cell, occupied_cell) then
        table.insert(cands, {x=x-1, y=y, dir='left', prev=cand, path_length=p+1})
        table.insert(cands, {x=x+1, y=y, dir='right', prev=cand, path_length=p+1})
        table.insert(cands, {x=x, y=y-1, dir='up', prev=cand, path_length=p+1})
        table.insert(cands, {x=x, y=y+1, dir='down', prev=cand, path_length=p+1})
      end end end end

function is_assumed_empty(level, x,y, empty, occupied)
  if empty.y ~= occupied.y or empty.x ~= occupied.x then
    if x == empty.x and y == empty.y then
      return true
    end
  end
  if x == occupied.x and y == occupied.y then
    return false
  end
  return is_empty(level, x,y)
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 shortest_path(cands)
--?   Real_print('', #cands)
  local min, minscore = 1, cands[1].path_length
  for i=2,#cands do
    local iscore = cands[i].path_length
--?     Real_print('', i, iscore, '<=>', min,minscore)
    if iscore < minscore then
      min, minscore = i, iscore
    end
  end
  return min
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