Hello :) I’m trying to work out how to code this routine (using the no-stack approach): https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker
does this look like I’m on the right track? I’d like to at least have something semi-decent before working on the printing code, as that itself could be a challenge for me. Makes testing mighty difficult, but hopefully someone more experienced can know if it’s close just by following the logic (the way I’ve been coding it):
(define (maze height width)
(define grid (make-grid #:h height #:w width))
(define (forge-path grid point)
(define (get-neighbors)
(define y (point-y point))
(define x (point-x point))
(define (valid-neighbor? p)
(and (> y -1) (< y height)
(> x -1) (< x width)))
(filter (conjoin (curry unvisited? grid) valid-neighbor?)
(list (inc-y point) (dec-y point)
(inc-x point) (dec-x point))))
(define (try-neighbors grid neighbors)
(cond
[(null? neighbors) (mark-visited grid point)]
[else
(try-neighbors (forge-path (mark-visited grid point)
(random-neighbor neighbors))
(cdr neighbors))]))
(try-neighbors grid (get-neighbors)))
(forge-path grid (make-point #:y 0 #:x 0)))
thank you, hope my code was readable enough.
The Grid is a struct containing: the grid itself, a vector of h*w, which contains: * Square structs, which have n s e w fields to denote which walls (paths) have been knocked down (forged) * a set containing coordinates of the squares which have been visited, stored as (y,x) Point structs.
I noticed that you only time you ever check the grid, is to see if a square has been visited or not. So, I figured it was better to just have a set of visited nodes and never actually index into the grid as such - just update it.
I think you should make a printer for the grid - and use in, say, try-neighbors to see what is going on.
Make it print the visited fields too.
I couldn’t think of a way to do it in ascii, with each square being 1 tile (to save the upscaling in my head). Maybe I’ll just have to have it print the letter of the wall that was knocked down or something. Thanks :)
Maybe use a terminal that supports colors?
I’m using ncurses, but (not being an artist in the slightest) couldn’t think of a set of 4 tiles (indiscriminate of position on the grid) that could represent a square with either wall N,E,S,W knocked down, if that makes sense.
I think you can draw each box as four characters. It’s a bit tricky to pick the right characters though.
Yeah, seems like using a single char per tile isn’t going to work. Just worried about all the moving parts involved that don’t involve the algorithm itself, but I’ll get there :)
Hmm. I might be easier to draw the grid using pict.
after struggling to come up with a set using only unicode characters combined with ncurses reverse attribute (and giving up at a square with only the side walls removed) I think you’re right ;)
even the eight (unicode-supported!) trigrams of the i-ching seem to have been designed in a way so as to make this impossible. Just to spite me, naturally.
for posterity, I found this ruby code online which takes a very nice approach:
puts " " + "_" * (width * 2 - 1)
height.times do \|y\|
print "\|"
width.times do \|x\|
print((grid[y][x] & S != 0) ? " " : "_")
if grid[y][x] & E != 0
print(((grid[y][x] \| grid[y][x+1]) & S != 0) ? " " : "_")
else
print "\|"
end
end
puts
end The bit-twiddling eludes me at the moment, but it appears that rather than thinking of each square as a… square, with potential missing lines, each square is thought of as either the left/right edge of another, or as the ceiling/floor of another:
___________________
\|___ \| \| ___ \| \|
\| \| _\|___ \| \| \| \| \|
\| \| \| \|___\|___\| \|
\| _\|_\| \| \| ___ \| \|
\|_______\| \|___ \|___\|
\| _______\| \| \| \|
\| \| _ \| _\| \|___\| \|
\| \| \| _\| \| \|_ \| \|
\|___\|_____\| \|___\| \|
\|___________\|_______\|
Nice idea
It really is. I’ll save the “thinking outside the box” related puns for the Christmas crackers ;)
I used pict for rendering
IIRC that is the “Growing Tree” algorithm it can be configured a bit http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
For drawing the maze I cheated and just draw the empty space not the walls.
@samdphillips That’s great! I just finished translating that same version (https://gist.github.com/dys-bigwig/ee7e08ffff14416f280f121c130c238b), and was about to ask how I could make it more idiomatic and less of a naive procedural->functional conversion, but you beat me to it! Thank you :)
There is a bit of imperative-ness in tracking visited cells, but it’s hidden inside of the generation function.
It’ll probably take a while to wrap my head around your code, but I notice the use of streams. IIRC there’s a section in SICP (about the queens problem?) that uses streams as an alternative to backtracking.
I don’t think it needs streams. I probably expecting a larger dataset for some reason.
So I was probably trying to save some cons’ing by using a stream. But I think a stream is just about equivalent in that case (a short 4 element list/stream)
It probably should be a sequence which might be better.
Unless you’re generating very large mazes it probably doesn’t make a big difference.
Just a very modest roguelike, so I shouldn’t think so.
The backtracking that occurs is mostly a function of keeping a list of cells that need to be visited.
That was what stumped me for some time. The link between in-place updating of the grid, and having the result of the recursive call on the neighbour be “available” to the initial call (ala a fold) in order to know which cells have been visited wasn’t something immediately obvious to me at all. Sorry, bit hard to put in words, hope it makes some sense.
Despite usually finding mutation more confusing, I feel like in this sort of situation the imperative way matches how you imagine it “working” in your head. At least, for a non-mathematically-minded person such as myself ;)
“Okay, cross this one off, move on to that one; I’ll keep a list of the ones I should come back to in the event I hit a dead-end” is a bit more natural in some ways than “right, before I finish this one, I’ll do the entire process first on this neighbor. But first, I’ll keep a list of remaining neighbors, remembering however to remember which of those I’ve crossed off when I come back after having done that neighbor I chose to finish first.” or…something like that.
Yeah it’s a little easier if you’ve written a few different graph traversals over the years
@samdphillips If you don’t mind me asking, any particular projects that spring to mind that you’ve used similar graph traversals for in the past?
Garbage collectors generally use graph traversal
Doing filesystem scans are technically a kind of graph traversal
I suppose if you squint, the paths between grid squares could be seen as references to objects held by other objects? Or I’m completely off haha. Thanks either way, good to know that learning this could help with creating languages one day in the distant future :)
Yes that’s it. Except you generally don’t pick a random path between nodes.