Maze Thread

Showcase your libraries, tools and other projects that help your fellow love users.
davisdude
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Maze Thread

Post by davisdude »

Germanunkol wrote:Shame on you. Not for adding the end manually, but for using ms (paint)! :D
Yeah. I actually have Gimp, but Paint is just so much easier to use... :P
Germanunkol wrote: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.
Image
Ranguna259 wrote:The first maze was easy, you should've chosen a better end :P
I think that actually was where it stopped, now that I think about it...
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
User avatar
Op Winter Storm
Prole
Posts: 5
Joined: Fri Sep 06, 2013 7:05 pm

Re: Maze Thread

Post by 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... :o:
After eating an entire bull, a mountain lion felt so good he started roaring. He kept it up until a hunter came along and shot him. The moral: When you're full of bull, keep your mouth shut. - Will Rogers
davisdude
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Maze Thread

Post by 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).
Op Winter Storm wrote: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... :o:
That's a neat idea. One similar to that has already been done here. I may try to do something like that, though. :D
Attachments
Maze.love
(4.2 KiB) Downloaded 158 times
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
davisdude
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Maze Thread

Post by 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.
Attachments
Maze.love
(4.61 KiB) Downloaded 148 times
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
Germanunkol
Party member
Posts: 712
Joined: Fri Jun 22, 2012 4:54 pm
Contact:

Re: Maze Thread

Post by 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...?
trAInsported - Write AI to control your trains
Bandana (Dev blog) - Platformer featuring an awesome little ninja by Micha and me
GridCars - Our jam entry for LD31
Germanunkol.de
davisdude
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Maze Thread

Post by 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...
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Maze Thread

Post by 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+.
Attachments
InfiniteMaze.love
(2.64 KiB) Downloaded 160 times
davisdude
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Maze Thread

Post by davisdude »

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

Use mousewheel-up/down to increase/decrease the size of the cells. r to restart
Attachments
maze-v2.love
(7.69 KiB) Downloaded 144 times
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: Maze Thread

Post by darkfrei »

:halloween:
:awesome: Mazer thread
:x
2023-03-24T09_47_50-mazer - lib for Love2D.png
2023-03-24T09_47_50-mazer - lib for Love2D.png (21.56 KiB) Viewed 1902 times
2023-03-24T09_47_55-mazer - lib for Love2D.png
2023-03-24T09_47_55-mazer - lib for Love2D.png (21.06 KiB) Viewed 1902 times
2023-03-24T09_47_59-mazer - lib for Love2D.png
2023-03-24T09_47_59-mazer - lib for Love2D.png (21.01 KiB) Viewed 1902 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Maze Thread

Post by 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
Kruskal Maze.png (4.29 KiB) Viewed 708 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
Post Reply

Who is online

Users browsing this forum: Ahrefs [Bot] and 45 guests