Dungeon Generator

This was a one-week project where I created a Dungeon level generator inspired by the likes of roguelikes such as Angbad. This was done using Lua in the IDE Zerobrane. Both of which I have 0 previous experience with.

While working on this project the first day just consisted of me hammering down Lua and Zero brane basics.


print("Hello, World!")

The Gridsystem

The next couple days I created a grid that contained nothing but walls. From there a room was generated, then a bunch of rooms at random positions, then the rooms hade spacing for the corridors to move between them, then a start and end room was made, and finally the rooms got doors. The biggest challenge in this part was the fact that tables, which is the Lua equitant of the all so common array, start at 1 by default.


function GenerateRoomsOnGrid()
  currentAmountOfRooms = 0;
  failedRoommTries = 0;

  while(currentAmountOfRooms < roomAmount and failedRoommTries < roomRetry) do
    
    newRoomY = math.random(1 , #grid )
    newRoomX = math.random(1 , #grid )
    thisRoomWidth = math.random(roomMin,roomMax)
    thisRoomHeigth = math.random(roomMin,roomMax)
    
    canMakeRoom = true;
    if grid[newRoomY][newRoomX] ~= floor then
      
      for y = newRoomY - roomSpaceing, newRoomY + thisRoomHeigth + roomSpaceing do
        for x = newRoomX - roomSpaceing, newRoomX + thisRoomWidth + roomSpaceing do
          if y < 1 or y > #grid or x < 1 or x > #grid or grid[y][x] == floor then
            canMakeRoom = false
            failedRoommTries = failedRoommTries + 1
            break
          end
        end
        
        if canMakeRoom == false then
          break
        end
      end
      
      if canMakeRoom then
        failedRoommTries = 0
        
        for y = newRoomY, newRoomY + thisRoomHeigth do
          for x = newRoomX, newRoomX + thisRoomWidth do
              grid[y][x] = floor
          end
        end
        
        randomizer = math.random(0,1)
        if randomizer > 0.5  then
          doorPointVerticalWall = math.random(newRoomY, newRoomY + thisRoomHeigth)
          grid[doorPointVerticalWall][newRoomX-1] = door
        else
          doorPointVerticalWall = math.random(newRoomY, newRoomY + thisRoomHeigth)
          grid[doorPointVerticalWall][newRoomX+thisRoomWidth+1] = door
        end
        
        randomizer = math.random(0,1)
        if randomizer > 0.5  then
          doorPointHorizontalWall = math.random(newRoomX, newRoomX + thisRoomWidth)
          grid[newRoomY-1][doorPointHorizontalWall] = door
        else
          doorPointHorizontalWall = math.random(newRoomX, newRoomX + thisRoomWidth)
          grid[newRoomY+thisRoomHeigth+1][doorPointHorizontalWall] = door
        end
        currentAmountOfRooms = currentAmountOfRooms+1;
        
      end
    end
  end
end

Corridors

The last 4 days got spent on figuring out the corridors as well as cleaning up the code. When it came to make the corridors work, I ended up with a solution that uses dijkstra's algorithm from the start room to find every other door. This creates a kind of snaking effect where the corridors move between all the rooms becoming one big corridor leading to all the rooms. Looking like this:

One of the especially hard things for me to figure out was how to use the Lua tables that function as hash maps, lists and arrays at the same time to make the, frontier, and came from lists of the dijkstra's algorithm work properly


function GenerateCorridorsFromStart()
  
  frontier[1] = AddToList(doorList[1].Y , doorList[1].X, nil)
  table.insert(cameFrom, frontier[1])
  while frontier[1] ~= nil do
    currentIndex = 0
    for i = 1, #cameFrom do
      if cameFrom[i].X == frontier[1].X and cameFrom[i].Y == frontier[1].Y then
        currentIndex = i
        break
      end
    end
    table.remove(frontier,1)
    current = cameFrom[currentIndex]
    CheckGridPositionOntoTables(current.Y-1,current.X, currentIndex)
    CheckGridPositionOntoTables(current.Y+1,current.X, currentIndex)
    CheckGridPositionOntoTables(current.Y,current.X-1, currentIndex)
    CheckGridPositionOntoTables(current.Y,current.X+1, currentIndex)
  end
  
  for i = 2, #doorList do
    aDoorPos = nil
    for j = 1, #cameFrom do
      if doorList[i].X == cameFrom[j].X and doorList[i].Y == cameFrom[j].Y then
        aDoorPos = cameFrom[j]
        break
      end
    end
    
    local l = cameFrom[aDoorPos.Previous]
    while l.Previous do
      grid[l.Y][l.X] = floor
      l = cameFrom[l.Previous]
    end
  end
end


function CheckGridPositionOnTables(y, x, index)
  
  if IsAPossiblePositon(x, y) then
    table.insert(frontier, AddToList(y, x, index))
    table.insert(cameFrom, AddToList(y, x, index))
    if grid[y][x] == door then
      table.insert(doorList, AddToList(y,x,index)) 
    end
  end
end


function IsAPossiblePositon(x,y)

  for i = 1, #cameFrom do
    
    if cameFrom[i].X == x and cameFrom[i].Y == y then
      return false
    end
  end
  
  if grid[y][x] == door then return true end

  for Y = -1, 1 do
    for X = -1, 1 do
      if x +X > #grid or x+X < 1 or y+Y > #grid or y+Y < 1 then 
        return false 
      elseif grid[y + Y][x + X] == floor then 
        return false 
      end
    end
  end
  return true
end

The Aftermath

In the end I would like to improve how the corridors are generated by doing them in one batch instead of one by one as it is the slowest process of the script. I would also improve the code cleanliness by adding a bit more spacing and removing redundant comments to dampen the moments where you hit a brick wall of code. But as a pretty novice programmer this project was a ton of fun. Mainly because I didn’t follow any online tutorials or guides about anything and I got to use a couple of things that I hadn't ever really used before but always known how to operate like, 2d arrays, and linked lists. But I also got to work with completely new algorithms which I had to make proper research for like Dijkstra’s.