CODEWITHSUNDEEP
rubyalgorithmrecursionbacktrackingmaze
perrywinkle
perrywinkle

Reputation: 383

Understanding a Ruby implementation of the recursive-backtracking algorithm

I am trying to understand a particular Ruby implementation of the recursive-backtracking algorithm which generates mazes: https://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking

I have read up and (to some level at least) understood the steps in the algorithm. However, due to my inexperience in Ruby and particularly dealing with bitwise operations, the recursive method Jamis Buck has provided in this blog of his is really confusing me. Particularly, line 40 and 41:

grid[cy][cx] |= direction
grid[ny][nx] |= OPPOSITE[direction]

I understand that the OR operations done here are to make it so that it fulfills the requirement of the cell being "already traversed" as seen in the conditionals:

... && grid[ny][nx] == 0

However, that's as far as I understand it. Why couldn't these just be booleans instead? What is the point of performing an OR operation on the grid[ny][nx] with the opposite direction originally stored?

Sorry if this is something trivial I'm just not seeing. Still rather new to algorithms and Ruby in general.

Upvotes: 3

Views: 234

Answers (1)

Pavel Mikhailyuk
Pavel Mikhailyuk

Reputation: 2877

Imagine a maze as a grid of rooms, where each room has its own independent walls.

Why couldn't these just be booleans instead?

The author points that

I generally implement the field as a grid of bitfields (where the bits in each cell describe which direction passages have been carved)

He implemented the state of each room in 4 bits, where 0 is a wall, and 1 is a "passageway".

If you implement it with 4 booleans, you will spend more code and memory.

What is the point of performing an OR operation on the grid[ny][nx] with the opposite direction originally stored?

To carve a passageway between two rooms with independent walls you need to remove two walls. Example: when you want to make the North passageway, you have to remove North wall of the current room and South wall of the adjacent room.

What is the meaning behind performing an OR operation on the "current" cell and the neighbor to its right?

(grid[y][x] | grid[y][x+1]) & S != 0 literally means "if current room OR right one has South passageway". Lets translate this part to pseudo code:

IF (current room has no Bottom wall) print " " ELSE print "_"
IF (current room has no Right wall)
  IF (either(current room OR Right one) has no Bottom wall) print " " ELSE print "_"
ELSE
  print "|"
END

With space changed for ., the bottom of two horizontally adjacent rooms(with passageway) could look like ___ or ... or .._ or _..

And Line 59 controls the logic of the second character in this pattern.

You can fix the seed (line 14) and than change bitwise OR for bitwise AND in line 59 ( (grid[y][x] & grid[y][x+1]) & S != 0 ) to see the change in display.

Upvotes: 3

Related Questions