Cycle Finder in Lua

local RPCheckLoop = {}

-- Includes
local RPShapes = require("src/rpshapes")

-- Reseed the floor if there is a loop
function RPCheckLoop:Main()
  -- Local variables
  local game = Game()
  local level = game:GetLevel()
  local stage = level:GetStage()
  local stageType = level:GetStageType()
  local startingRoomIndex = level:GetStartingRoomIndex()
  local rooms = level:GetRooms()

  if stage == LevelStage.STAGE1_1 or -- 1 (Basement 1)
     stage == LevelStage.STAGE4_3 or -- 9 (Blue Womb)
     stage == LevelStage.STAGE7 then -- 12 (The Void)

    -- It is probably not possible to have a loop in Basement 1,
    -- so don't bother checking to make resetting faster on potato computers
    -- There are no loops in the Blue Womb
    -- Don't bother checking for loops in The Void, as the mixing of the floors makes it more complex to detect a loop
    return
  end

  -- Make an empty 13x13 grid and initialize all elements to the value that represents an obstacle
  -- The game uses a 0-indexed grid, but we will use a 1-indexed grid
  local grid = {}
  for i = 1, 13 do
    grid[i] = {}
    for j = 1, 13 do
      grid[i][j] = -1
    end
  end

  -- Get the floor string, i.e. "F1_1"
  -- (this is the index for the RPShapes table)
  local floorNum
  if stage == 1 or stage == 2 then
    floorNum = 1
  elseif stage == 3 or stage == 4 then
    floorNum = 2
  elseif stage == 5 or stage == 6 then
    floorNum = 3
  elseif stage == 7 or stage == 8 then
    floorNum = 4
  elseif stage == 10 then
    floorNum = 5
  elseif stage == 11 then
    floorNum = 6
  end
  local floorString = "F" .. tostring(floorNum) .. "_" .. tostring(stageType)

  -- Also, keep track of basic information about each room
  local roomsData = {}

  -- Make an entry for each room on the floor
  -- (to both the grid and the roomData)
  local startingRoomNum
  for i = 0, rooms.Size - 1 do -- This is 0 indexed
    local roomDesc = rooms:Get(i)
    local roomIndex = roomDesc.SafeGridIndex -- This is always the top-left index
    local roomData = roomDesc.Data
    local roomType = roomData.Type

    -- There will never be a special room in a loop, so we can ignore them to save CPU cycles
    -- Furthermore, we don't want to account for the Secret Room / moon strats
    if roomType == RoomType.ROOM_DEFAULT then -- 5
      local roomDataVariant = roomData.Variant
      while roomDataVariant > 10000 do
        -- The 3 flipped versions of room #1 would be #10001, #20001, and #30001
        roomDataVariant = roomDataVariant - 10000
      end

      local roomShape = RPShapes[floorString][roomDataVariant]
      local x, y = RPCheckLoop:GetXYFromGridIndex(roomIndex)

      -- Fill in the grid with values corresponding to this room index
      grid[y][x] = i
      if roomShape == RoomShape.ROOMSHAPE_1x2 or -- 4 (1 wide x 2 tall)
         roomShape == RoomShape.ROOMSHAPE_IIV then -- 5 (1 wide x 2 tall, narrow)

        grid[y + 1][x] = i -- The square below

      elseif roomShape == RoomShape.ROOMSHAPE_2x1 or -- 6 (2 wide x 1 tall)
             roomShape == RoomShape.ROOMSHAPE_IIH then -- 7 (2 wide x 1 tall, narrow)

        grid[y][x + 1] = i -- The square to the right

      elseif roomShape == RoomShape.ROOMSHAPE_2x2 then -- 8 (2 wide x 2 tall)
        grid[y][x + 1] = i -- The square to the right
        grid[y + 1][x] = i -- The square below
        grid[y + 1][x + 1] = i -- The square to the bottom-right

      elseif roomShape == RoomShape.ROOMSHAPE_LTL then -- 9 (L room, top-left is missing)
        grid[y + 1][x] = i -- The square below
        grid[y + 1][x - 1] = i -- The square to the bottom-left

      elseif roomShape == RoomShape.ROOMSHAPE_LTR then -- 10 (L room, top-right is missing)
        grid[y + 1][x] = i -- The square below
        grid[y + 1][x + 1] = i -- The square to the bottom-right

      elseif roomShape == RoomShape.ROOMSHAPE_LBL then -- 11 (L room, bottom-left is missing)
        grid[y][x + 1] = i -- The square to the right
        grid[y + 1][x + 1] = i -- The square to the bottom-right

      elseif roomShape == RoomShape.ROOMSHAPE_LBR then -- 12 (L room, bottom-right is missing)
        grid[y][x + 1] = i -- The square to the right
        grid[y + 1][x] = i -- The square below
      end

      -- Also, fill in the roomsData with values corresponding to this room index
      roomsData[i] = {
        x = x,
        y = y,
        roomShape = roomShape,
      }

      -- Keep track of the starting room for later
      if roomIndex == startingRoomIndex then
        startingRoomNum = i
      end

      --[[
      Isaac.DebugString("Plotted room " .. tostring(i) .. ":")
      Isaac.DebugString("  ID: " .. tostring(roomData.Variant))
      Isaac.DebugString("  Index: " .. tostring(roomIndex))
      Isaac.DebugString("  Coordinates: (" .. tostring(x) .. ", " .. tostring(y) .. ")")
      Isaac.DebugString("  Shape: " .. tostring(roomShape))
      --]]
    end
  end

  -- Print out a graphic representing the grid
  --[[
  Isaac.DebugString("Grid:")
  for i = 1, #grid do
    local rowString = "  " .. tostring(i) .. ": "
    if i < 10 then
      rowString = rowString .. " "
    end
    for j = 1, #grid[i] do
      if grid[i][j] == -1 then
        -- No room is here
        rowString = rowString .. "  "
      else
        -- A room is here
        rowString = rowString .. grid[i][j]
        if i == roomsData[startingRoomNum].y and
           j == roomsData[startingRoomNum].x then

          rowString = rowString .. "!"

        elseif grid[i][j] < 10 then
          rowString = rowString .. " "
        end
      end
      rowString = rowString .. " "
    end
    Isaac.DebugString(rowString)
  end
  --]]

  -- We have created a grid, so now we need to create a node connection table to feed to the cycle checker algorithm
  Isaac.DebugString("Creating connection table...")
  local RPCheckLoop.nodes = {}
  for i, roomData in pairs(roomsData) do
    local connectedRooms = {}
    local adjacentSquares = RPCheckLoop:GetAdjacentSquares(roomData.roomShape)
    for j = 1, #adjacentSquares do
      local mod = adjacentSquares[j]
      local adjacentRoomID = grid[roomData.y + mod.y][roomData.x + mod.x]
      local alreadyConnected = false
      for k = 1, #connectedRooms do
        if connectedRooms[k] == adjacentRoomID then
          alreadyConnected = true
          break
        end
      end
      if alreadyConnected == false and
         adjacentRoomID ~= -1 then -- We initialized every square to -1 when we created the grid

        connectedRooms[#connectedRooms + 1] = adjacentRoomID
      end
    end

    -- Keep track of the connected rooms for every room
    RPCheckLoop.nodes[i] = connectedRooms
  end

  --[[
  -- Print out the connection list
  Isaac.DebugString("Room connection list:")
  for i, node in pairs(RPCheckLoop.nodes) do
    local debugString = "  " .. tostring(i) .. " - (" .. table.concat(node) .. ")"
    Isaac.DebugString(debugString)
  end
  --]]

  -- Do a Depth First Search (DFS) to find a loop
  RPCheckLoop.visited = {}
  return RPCheckLoop:HasCycle(startingRoomNum, RPCheckLoop.nodes)
end

-- Get the grid coordinates on a 13x13 grid
function RPCheckLoop:GetXYFromGridIndex(idx)
  -- 0 --> (0, 0)
  -- 1 --> (1, 0)
  -- 13 --> (0, 1)
  -- 14 --> (1, 1)
  -- etc.
  local y = math.floor(idx / 13)
  local x = idx - (y * 13)

  -- Now, we add 1 to each x and y because the game uses a 0-indexed grid and Lua's tables are 1-indexed
  return x + 1, y + 1
end

function RPCheckLoop:GetAdjacentSquares(roomShape)
  -- Adjacent tiles for each room shape are listed clockwise, starting at the top
  -- The starting square is always the top-left square
  if roomShape == RoomShape.ROOMSHAPE_1x1 then -- 1
    return {
      {x = 0, y = -1}, -- Up
      {x = 1, y = 0}, -- Right
      {x = 0, y = 1}, -- Down
      {x = -1, y = 0}, -- Left
    }

  elseif roomShape == RoomShape.ROOMSHAPE_IH then -- 2
    return {
      {x = 1, y = 0}, -- Right
      {x = -1, y = 0}, -- Left
    }

  elseif roomShape == RoomShape.ROOMSHAPE_IV then -- 3
    return {
      {x = 0, y = -1}, -- Up
      {x = 0, y = 1}, -- Down
    }

  elseif roomShape == RoomShape.ROOMSHAPE_1x2 then -- 4 (1 wide x 2 tall)
    return {
      {x = 0, y = -1}, -- Up
      {x = 1, y = 0}, -- Right-top
      {x = 1, y = 1}, -- Right-bottom
      {x = 0, y = 2}, -- Down
      {x = -1, y = 1}, -- Left-bottom
      {x = -1, y = 0}, -- Left-top
    }

  elseif roomShape == RoomShape.ROOMSHAPE_IIV then -- 5 (1 wide x 2 tall, narrow)
    return {
      {x = 0, y = -1}, -- Up
      {x = 0, y = 2}, -- Down
    }

  elseif roomShape == RoomShape.ROOMSHAPE_2x1 then -- 6 (2 wide x 1 tall)
    return {
      {x = 0, y = -1}, -- Up-left
      {x = 1, y = -1}, -- Up-right
      {x = 2, y = 0}, -- Right
      {x = 1, y = 1}, -- Down-right
      {x = 0, y = 1}, -- Down-left
      {x = -1, y = 0}, -- Left
    }

  elseif roomShape == RoomShape.ROOMSHAPE_IIH then -- 7 (2 wide x 1 tall, narrow)
    return {
      {x = 2, y = 0}, -- Right
      {x = -1, y = 0}, -- Left
    }

  elseif roomShape == RoomShape.ROOMSHAPE_2x2 then -- 8 (2 wide x 2 tall)
    return {
      {x = 0, y = -1}, -- Up-left
      {x = 1, y = -1}, -- Up-right
      {x = 2, y = 0}, -- Right-top
      {x = 2, y = 1}, -- Right-bottom
      {x = 1, y = 2}, -- Down-right
      {x = 0, y = 2}, -- Down-left
      {x = -1, y = 1}, -- Left-bottom
      {x = -1, y = 0}, -- Left-top
    }

  elseif roomShape == RoomShape.ROOMSHAPE_LTL then -- 9 (L room, top-left is missing)
    return {
      {x = 0, y = -1}, -- Up
      {x = 1, y = 0}, -- Right-top
      {x = 1, y = 1}, -- Right-bottom
      {x = 0, y = 2}, -- Down-right
      {x = -1, y = 2}, -- Down-left
      {x = -2, y = 1}, -- Left-bottom
      {x = -1, y = 0}, -- Left-top
    }

  elseif roomShape == RoomShape.ROOMSHAPE_LTR then -- 10 (L room, top-right is missing)
    return {
      {x = 0, y = -1}, -- Up
      {x = 1, y = 0}, -- Right-top
      {x = 2, y = 1}, -- Right-bottom
      {x = 1, y = 2}, -- Down-right
      {x = 0, y = 2}, -- Down-left
      {x = -1, y = 1}, -- Left-bottom
      {x = -1, y = 0}, -- Left-top
    }

  elseif roomShape == RoomShape.ROOMSHAPE_LBL then -- 11 (L room, bottom-left is missing)
    return {
      {x = 0, y = -1}, -- Up-left
      {x = 1, y = -1}, -- Up-right
      {x = 2, y = 0}, -- Right-top
      {x = 2, y = 1}, -- Right-bottom
      {x = 1, y = 2}, -- Down
      {x = 0, y = 1}, -- Left-bottom
      {x = -1, y = 0}, -- Left-top
    }

  elseif roomShape == RoomShape.ROOMSHAPE_LBR then -- 12 (L room, bottom-right is missing)
    return {
      {x = 0, y = -1}, -- Up-left
      {x = 1, y = -1}, -- Up-right
      {x = 2, y = 0}, -- Right-top
      {x = 1, y = 1}, -- Right-bottom
      {x = 0, y = 2}, -- Down
      {x = -1, y = 1}, -- Left-bottom
      {x = -1, y = 0}, -- Left-top
    }
  end
end

-- A recursive function that does a Depth First Search (DFS) to see if there is a cycle (loop) in the node connection list
function RPCheckLoop:HasCycle(node, cameFrom)
  -- If we found this node already, there is a cycle
  for i = 1, #RPCheckLoop.visited do
    if RPCheckLoop.visited[i] == node then
      return true
    end
  end

  -- Mark that we have visited this node
  RPCheckLoop.visited[#RPCheckLoop.visited + 1] = node

  -- Go through all the nodes that are connected to this node
  for _, n in ipairs(RPCheckLoop.nodes[node]) do
    if n ~= cameFrom then
      if RPCheckLoop:HasCycle(n, node) then
        return true
      end
    end
  end

  return false
end

return RPCheckLoop