Maze Thread

[davisdude]

Shame on you. Not for adding the end manually, but for using ms (paint)!

Yeah. I actually have Gimp, but Paint is just so much easier to use...

I would NOT want to have to find the end in that last maze... that's crazy

I actually did a race with a friend. It took a while.

The first maze was easy, you should've chosen a better end

I think that actually was where it stopped, now that I think about it...

[Op Winter Storm]

I would like to see one that starts at each of the 4 corners, and works simultaneously. That'd be pretty cool. I'm not going to pretend that I knew how to do it, though...

[davisdude]

New, more optimized maze. Removed some bugs and made it automatically choose an end! If the end it too easy, you can press any key (but escape) to place it somewhere else. Also fixed an issue regarding the images (if you look closely at the images missing the bottom and right wall, you'll notice they're off some).

I would like to see one that starts at each of the 4 corners, and works simultaneously. That'd be pretty cool. I'm not going to pretend that I knew how to do it, though...

That's a neat idea. One similar to that has already been done here. I may try to do something like that, though.

[davisdude]

Alright, I did your idea. It starts in separate corners and once it finishes it chooses a random start and finish.
You can press escape to close it.
You can press space to save the image to C:/Users/YOUR NAME/App Data/Roaming/LOVE/Maze.
You can press any other key to:
- Pause while it's working.
- Switch the start and end once it's finished.

[Germanunkol]

Don't you generate four seperate mazes now, though? So start and finish might be in different mazes and the end doesn't have to be reachable from the start...?

[davisdude]

Sometimes the mazes may connect. However, there is a chance that there will be unconnected grids. I will have to make sure that I solve that problem...

[pgimeno]

Infinite Maze (no, it's not the same image again and again, it's Eller's algorithm).

Works with LÖVE 0.9.1+.

[davisdude]

Coincidentally, I just revisited this project and remade the maze generator. Now it even connects all the mazes! without using ms paint

Use mousewheel-up/down to increase/decrease the size of the cells. r to restart

[darkfrei]

Mazer thread

2023-03-24T09_47_50-mazer - lib for Love2D.png (21.56 KiB) Viewed 4036 times

2023-03-24T09_47_55-mazer - lib for Love2D.png (21.06 KiB) Viewed 4036 times

2023-03-24T09_47_59-mazer - lib for Love2D.png (21.01 KiB) Viewed 4036 times

[pgimeno]

I recently implemented Kruskal's algorhtm. Conceptually It's one of the simplest I found; however, the mazes it generates have many short blind alleys, as it happens with any other algorithm which generates a uniformly distributed spanning tree (such as Aldous-Broder or Wilson's algorithms).

Kruskal Maze.png (4.29 KiB) Viewed 2842 times

This time I went with the thin walls representation instead of the more common "walls are the same size as passages" representation.

Code: Select all

math.randomseed(require('socket').gettime())
local maze = {}
local W = 39
local H = 29
local tilesize = 20
local MW = W*2+1
local MH = H*2+1

for i = 1, MW*MH do
  maze[i] = 1
end

-- Kruskal's algorithm: assign different IDs to each vertex; pick up a random
-- edge and if the IDs on both sides are different, remove the edge and join
-- both sets. We use a flood fill algorithm for simplicity, but there are
-- faster variants.

do
  local function floodfill(x, y, target, new)
    if maze[y*MW + x + 1] ~= target then return end
    maze[y*MW + x + 1] = new
    if maze[y * MW + x] == 0 then
      floodfill(x-2, y, target, new)
    end
    if maze[y * MW + x + 2] == 0 then
      floodfill(x+2, y, target, new)
    end
    if maze[(y - 1) * MW + x + 1] == 0 then
      floodfill(x, y-2, target, new)
    end
    if maze[(y + 1) * MW + x + 1] == 0 then
      floodfill(x, y+2, target, new)
    end
  end

  -- Build a list of edges
  local edges = {}
  local nedges = 0
  -- Vertical edges
  for y = 1, MH - 2, 2 do
    for x = 2, MW - 3, 2 do
      nedges = nedges + 1
      edges[nedges] = y*MW + x + 1
    end
  end
  -- Horizontal edges
  for y = 2, MH - 3, 2 do
    for x = 1, MW - 2, 2 do
      nedges = nedges + 1
      edges[nedges] = y*MW + x + 1
    end
  end

  -- Step 1: Assign a different ID to each cell
  for y = 1, MH - 2, 2 do
    for x = 1, MW - 2, 2 do
      maze[y*MW + x + 1] = y*MW + x + 1
    end
  end

  while nedges ~= 0 do
    local samegroup = false
    local x1, y1, x2, y2 = 0, 0, 0, 0

    -- Step 2: Pick an edge at random
    local i = math.random(1, nedges)

    if edges[i] % MW % 2 == 0 then
      -- Vertical edge - check group of upper and lower vertices
      x1 = (edges[i] - 1) % MW
      y1 = (edges[i] - 1 - x1) / MW - 1
      x2 = x1
      y2 = y1 + 2
      if maze[edges[i] - MW] == maze[edges[i] + MW] then
        samegroup = true
      end
    else
      -- Horizontal edge - check left and right vertices
      x1 = (edges[i] - 1) % MW - 1
      y1 = (edges[i] - 2 - x1) / MW
      x2 = x1 + 2
      y2 = y1
      if maze[edges[i] - 1] == maze[edges[i] + 1] then
        samegroup = true
      end
    end

    -- Step 3: If they are not in the same group, add an edge and
    --         mark all connected cells with the same group.
    if not samegroup then
      -- Remove wall
      maze[edges[i]] = 0
      -- Flood fill one of the sides with the group number of the other
      floodfill(x1, y1, maze[y1 * MW + x1 + 1], maze[y2 * MW + x2 + 1])
    end

    -- Remove the edge from the list
    edges[i] = edges[nedges]
    edges[nedges] = nil
    nedges = nedges - 1

    -- Go to step 2 until there are no more edges
  end
end

local canvas = love.graphics.newCanvas()

-- Draw the maze on the canvas
love.graphics.setCanvas(canvas)
love.graphics.rectangle("fill", 0, 0, tilesize*W, 1)
love.graphics.rectangle("fill", 0, 0, 1, tilesize*H)
for y = 1, MH - 2, 2 do
  local yy = (y-1) * 0.5
  for x = 1, MW - 2, 2 do
    local xx = (x-1) * 0.5
    if maze[y*MW + (x+1) + 1] ~= 0 then
      love.graphics.rectangle("fill", (xx+1)*tilesize, yy*tilesize, 1, tilesize)
    end
    if maze[(y+1)*MW + x + 1] ~= 0 then
      love.graphics.rectangle("fill", xx*tilesize, (yy+1)*tilesize, tilesize+1, 1)
    end
  end
end
love.graphics.setCanvas()

function love.draw()
  love.graphics.setBlendMode("alpha", "premultiplied")
  love.graphics.draw(canvas, math.floor(tilesize*0.5), math.floor(tilesize*0.5))
  love.graphics.setBlendMode("alpha", "alphamultiply")
end