Roguelikes

[duaner]

I know at least Gunroar is interested in roguelikes, so I thought it would be fun to have a thread on techniques with a special emphasis on love.

I got side-tracked from updating my old roguelike into developing caves. I'm using a simple bombardment function on areas created by recursively splitting a rectangle into smaller rectangles.

Code: Select all

-- pseudo-lua
r = big_rectangle
curr = btree()
splitter(curr, 1)

function splitter(curr, i)
  if i < max_iterations then
    l, r = split_rectangle_at_a_random_length()
    curr:add(l, r)
    splitter(l, i+1)
    splitter(r, i+1)
  end
  return curr
end

Code: Select all

function _M:bomb(bound, r, tile, reps, only)
  r = math.round(r)

  local cs = {}
  local rcx, rcy = bound:center()
  local sqsz = math.max(bound.size_x, bound.size_y) / 2

  for i = 1, reps or 10 do
    local cx, cy, trec

    for j = 1, 100 do
      local a = math.random() * math.pi * 2
      local r2 = math.random(sqsz - r)
      cx = math.round(math.cos(a) * r2 + rcx)
      cy = math.round(math.sin(a) * r2 + rcy)
      trec = rectangle:new(cx, cy, cx, cy):grow(r)

      if bound:encloses(trec) then
        break
      end
    end
    table.insert(cs, { x=cx,  y=cy})

    local rect = bound:clip(trec)
    if not rect then
      log.error('rectangle error %s, (%d, %d), r%d, x%f', tostring(bound), cx, cy, r, bound.size_x)
    end
    assert(rect)
    assert(bound:encloses(rect), 'out of bound')
    if only then
      for x, y in rect:iter() do
        if self:get(x, y) ~= only then
          rect = nil
        end
      end
    end

    if rect then
      for x, y in rect:iter() do
        local d = math.sqrt((cx - x)^2 + (cy - y)^2)
        local r3 = r - math.random() + 0.5
        if d <= r3 and self.bounds:has_point(x, y) then
          self:set(x, y, tile)
        end
      end
    end
  end

  return cs
end

This is giving me good results. Of course, the trick is to keep everything connected. Lava blobs are still blocking paths, occasionally. On the other hand, the whole point to a map is to partition off the space, since large, open areas usually result in the player getting surrounded and killed. (Water is impassible in my game.)

[glitchapp]

generative creation is something I've always be interested on and never managed to master. I guess that by adding some blocks to the equations you can even create less random levels, I think a good balance within randomness and blocks could be useful for other genres...
Thanks for sharing.

[milon]

Those cave systems are pretty nice!

... Lava blobs are still blocking paths, occasionally... (Water is impassible in my game.)

I did some proc gen stuff to create maps a long time ago. Life changed, and I rarely have time for anything anymore, but here's how I made sure all (relevant) map regions were accessible:

About bridges - if they're only 1 or 2 tiles long, it'll just draw the road overtop rather than placing boats...

And definitely - borrow any code you want to! That's one of my reasons for putting the code online.
My current road-building implementation is as follows:
1. Calculate the Manhattan distance between all nodes
2. Sort by distance, shortest first
3. Add the shortest route to the to-build list
4. Work through the rest of the list, adding to the to-build list any route that connects an already-connected with an unconnected node, until nothing new gets added
5. Pathfind the route (A*) for each of the to-build routes, applying special rules for pathing over mountains (create a tunnel) and over water (bridge/boat), then laying down actual roads where appropriate (don't pathfind to a dungeon from a city)

I think this guarantees that all nodes are connected, and therefore all nodes are accessible regardless of terrain.

You can click the link in the quote header for the fuller post, and to see the project as it was. Not sure how well it will work in recent version of love though.

[duaner]

I guess that by adding some blocks to the equations you can even create less random levels

I keep thinking about doing that, but I never seem to get around to it.

I think this guarantees that all nodes are connected, and therefore all nodes are accessible regardless of terrain.

I managed to fix the blockage by simply checking a border around the blobs. It's nice to have a fast language like lua after constantly having to optimize gdscript.

Connections are relatively easy with the room generation system I'm using. Every pair of rooms on the btree are the children of the larger rectangle that encloses them, so when making dungeon rooms, I just connect every pair with a corridor, then connect their parents, and so on. You can see the result below. (Note that the bridges follow the corridor paths.) For the caves, I just read off the outer leaves into an array and connect them in array order.

I love working on the terrain generation, but I really should get back to updating the game.

[duaner]

This is a really simple maze algorithm that I've made way too complicated. I'm going to have to clean it up a bit. It works, though.

Code: Select all

function _M:maze(bound, mult)
  for x, y in bound:perim() do
    if self:get(x, y) == 'rock' then
      self:random_wall_tile(x, y)
    end
  end

  for x, y in bound:grow(-1):iter() do
    self:random_wall_tile(x, y)
  end

  local plan = { }

  local planb = (bound / mult):floor()
  local half_planb = (planb / 2):floor()

  for x, y in planb:iter() do
    plan[planb:index(x, y)] = 1
  end

  local st = { }
  local visited = { }
  local x, y = half_planb:random()
  x = planb.x1 + (x - half_planb.x1) * 2
  y = planb.y1 + (y - half_planb.y1) * 2
  local start = planb:index(x, y)

  plan[start] = 0
  visited[start] = true
  table.insert(st, start)

  local card = {
    { x = -1, y = 0 },
    { x = 1, y = 0 },
    { x = 0, y = -1 },
    { x = 0, y = 1 },
  }

  while #st > 0 do
    local curr = table.remove(st)
    local x, y = planb:coord(curr)
    local unv = { }

    for _, cc in ipairs(card) do
      local dx, dy = cc.x, cc.y
      local nx, ny = x + dx * 2, y + dy * 2
      if planb:has_point(nx, ny) then
        local i = planb:index(x + dx, y + dy)
        local j = planb:index(nx, ny)

        if not visited[j] then
          table.insert(unv, {i, j})
        end
      end
    end

    if #unv > 0 then
      table.insert(st, curr)
      assert(visited[curr])

      local nex = unv[math.random(#unv)]

      if plan[nex[1]] == 1 then
        plan[nex[1]] = 0
      end

      if plan[nex[2]] == 1 then
        plan[nex[2]] = 0
      end

      visited[nex[2]] = true
      table.insert(st, nex[2])
    end

    if ct == 100000 then error('excess') end
  end

  local ly
  for x, y in planb:iter() do
    local i = planb:index(x, y)

    local tar = rectangle:new((x - 1) * mult + 1, (y - 1) * mult + 1, x * mult, y * mult)
    if plan[i] == 0 then
      self:fill(tar, 'floor')
    end
  end
end

[Azzla]

I love working on the terrain generation, but I really should get back to updating the game.

Reminds me of when I made zero progress on my game for an entire month because I fell into a rabbit hole of trying to make beautiful particle systems and shaders. It's always something with gamedev

[LonelyOwl]

Hope I'm not too late to catch this train. I've been fascinated with dungeon generation since I watched the talk the creator of brogue gave at roguelike-dev. Seems like no matter what, I always find myself for some reason making a dungeon generator. This is my latest iteration of that. I wanted to post and encourage anyone working on generation: Visualize your outputs. I have spent a ridiculous amount of hours comparing values in a print() log. It's awful, and can lead to some pain staking bugs. Especially if you don't have any custom error handling methods.

Also, try offloading your generation onto love threads. It's a great way to not have Big O Notation ruin your plan of generating beautiful maps. I have found that if I want to avoid the Big O demon, it's almost mandatory to use hash maps or some kind of linked list versus iteration. Especially when it comes to algorithms like flood fill, bfs, or anything that relies on recursion for that matter. Below is a visualization, and a good example of why it's helpful. Hope you guys enjoy.

https://jmp.sh/Z9CZ1Vq6 <- Jumpshare (Gyazo alternative) video of current generation.

I'm using a "room accretion" method, which I think maybe brogue popularized. It's a little more botched though. I could not get hallways to work without some awful O^n / efficiency issues. The method I'm using is as simple as follows:

• Generate a "room" of random size.

• "Throw" this room at the dungeon to see if it sticks.

• If the room sticks, add it to the dungeons table of valid rooms.

• Do this until certain parameters like room ratio % or # of rooms is met.

• Since rooms overlap, we process those overlapping wall tiles to determine door locations

• Pick a random "best" door, and resolve the other overlapping conflicts (Just make them walls instead)

• Analyze the map by instantiating a dijkstra source at the starting room, and building out.

I paraphrased the "generate a random room" because that alone is quite a lot to explain. But essentially I just create a shape (square, rectangle, circle, Cellular Automata blob, etc) then maybe combine it with another (Merge tile data together at center, and sometimes use offsets for something like "T rooms").

The reason I believe visualization, or step-visualization is important later on in generation is because your codebase is inevitably going to grow exponentially, and something as small as a nil reference error can cause some nasty bugs. Especially.. especially if you're using hash maps (or multiple in my case.) Here is an example:



In this photo, the visualization of my dijkstra pathing ends abruptly on the X-axis (visually y axis). The error was a nil reference to the distance property of a node... one of 3000+ nodes. I could have looked at a lot of things for that, and probably have to step through the recursion to fix it. But because of the visualization, it was quite obvious that the hash map I was referencing did not carry values past a certain amount. This was due to a small math mistake I made when changing generation size. I have a lot more examples of this.

Another reason visualization is nice, is in my video, you can visualize a lot of elements of generation that would be impossible otherwise. As mentioned previously, I offloaded generation onto a thread so that I could keep the main thread from hanging when I run into recursion issues, or other errors that don't seem to crash the main thread. (This has it's perks, and disadvantages). As a result, (if you've seen the video) You can see in the room generation that my larger rooms "favor" the right side of the screen. This could just be how random works, or there could be an underlying issue (which there is). Likewise, I can also visualize how the player would traverse the map naturally using the dijkstra visualization. Also, I can see how rooms are being attached to other rooms in case I want to tweak parameters for how often certain rooms appear. The list goes on. But some of these things would be impossible if the generation happens immediately.

This does come at the price of maybe implementing threads, but definitely implementing some method of reading changes to the map incrementally. Using spritebatches, it is actually super easy to read changes from a map -> apply only those changes to the spritebatch -> and then further reference those changes for visualization. Here is one function I have that handles most of it:

Code: Select all

-- Iterate over list of previous changes, and change tile color one at a time.
    if #self.previousChanges > 0 then
        for i = 1, #self.previousChanges / 10 + 2 do
            local change = self.previousChanges[i]
            table.remove(self.previousChanges, i)

            if change then 
                self.spriteBatch:setColor(1,1,1,1)
                if change.tile.distance then
                    local distance = change.tile.distance
                    local r,g,b,a = _HSV((distance*2)/255, 1, 1)
                    self.spriteBatch:setColor(r,g,b,a)
                end
                self.spriteBatch:set(change.id, change.quad, change.tile.wx*64, change.tile.wy*64)
            end
        end
    end

I wouldn't recommend using this by any means, but it serves as just an example. I actually haven't put much effort into systems that handle map changes, right now it's just hard coded into the map class. But in this code (inside a love.update() call). I simply observe a stack (self.previousChanges) for any newly added changes. Newly added changes are added to the stack when I :pop() data from my generation thread. Once changes are found, I "pop" them and then set the corresponding spriteBatch quad to it's new information. In my case, I :add quads to the spritebatch at a lower alpha than 0. Then I store the `identifier` :add gives me as `change.id` as well as the `quad` and `tile` information. This is pushed into the self.previousChanges stack. That's really all there is to say about that right now because although this is a method, it's probably not the best.

Anyways, hopefully my post gets approved and you all can see this and maybe it will help in your own project! I am more than excited to answer any questions anyone has about this as I plug away. Next on my list is lakes, chasms, and then what I call "flavormachines".

[Gunroar:Cannon()]

I got side-tracked from updating my old roguelike into developing caves. I'm using a simple bombardment function on areas created by recursively splitting a rectangle into smaller rectangles.

You guys are geniuses!


I just use an aggressively modified rotLove.