Maze Generation: Recursive Backtracking


I’ve pronounced prior to which generating mazes is a fantastic default plot when experimenting with a latest programming language. I’ve nonetheless to find a improved a single (but I’d adore to listen to recommendations). But, prior to we can dive in to generating a obstruction (especially in a syntax we have been unknown with), we had improved have a plain learn of how a routine works.

With mazes, we can take your collect of a plain double-handful of algorithms: recursive backtracking, Prim’s, Kruskal’s, Eller’s, Aldous-Broder or Wilson’s algorithms, recursive division, hunt-and-kill, as well as more.

My favorite, as well as a a single we use by default, is recursive backtracking. It is quick, simple to know, as well as candid to implement. You’ll need enough mental recall to store a complete obstruction in memory, though, as well as it requires smoke-stack space again proportionate to a distance of a maze, so for unusually vast mazes it can be sincerely inefficient. But for many mazes, it functions a charm.

Here’s a mile-high perspective of recursive backtracking:

  1. Choose a starting indicate in a field.
  2. Randomly select a wall during which indicate as well as carve a thoroughfare by to a diagonally opposite cell, nonetheless customarily if a diagonally opposite dungeon has not been visited yet. This becomes a latest stream cell.
  3. If all diagonally opposite cells have been visited, behind up to a final dungeon which has uncarved walls as well as repeat.
  4. The algorithm ends when a routine has corroborated all a approach up to a starting point.

I in all use a margin as a grid of bitfields (where a pieces in any dungeon report which citation passages have been carved). That’s substantially usually a C programmer in me reporting dominance, though; feel giveaway to examination with alternative representations.

In Ruby, we customarily initialize a grid similar to so:

1

grid = Array.new(height) { Array.new(width, 0) }

Next, a algorithm itself is kicked off by job a workman function:

1
2
3
4
5

def carve_passages_from(cx, cy, grid)
  # work, work, work
end

carve_passages_from(0, 0, grid)

This starts figure passages in a grid, starting during a upper-left corner, (0,0). And as we competence have guessed from a algorithm’s name, this functions recursively, as we’ll see next.

The carve_passages_from process initial makes a list of directions which ought to be attempted from a stream cell:

1

directions = [N, S, E, W].sort_by{rand}

We arrange a list in pointless order, so which a trail will meander, rsther than than carrying a disposition in any sold direction.

Then, a duty iterates over any of those directions, last a coordinates of a dungeon in which citation as well as determining if a dungeon is stream or not. Note which a dungeon is stream customarily if it lies inside of a end of a maze, AND it has not formerly been visited: we customarily wish to carve passages in to inexperienced cells, to equivocate formulating round loops in a maze.

1
2
3
4
5
6
7
8

directions.each do |direction|
  nx, ny = cx + DX[direction], cy + DY[direction]

  if ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0
    # dungeon is valid!
    # ...
  end
end

Finally, if a dungeon is valid, we carve a thoroughfare out of a stream dungeon as well as in to a subsequent cell. Then, we recursively call carve_passages_from upon a latest cell:

1
2
3

grid[cy][cx] |= direction
grid[ny][nx] |= OPPOSITE[direction]
carve_passages_from(nx, ny, grid)

And that’s unequivocally all there is to it! The full implementation, together with a small lines to outlay a obstruction as ASCII, is here:

<noscript>[recursive-backtracker2.rb during gist.github.com]</noscript>

Start by essay your own doing in a denunciation you’re gentle in, usually to hang your thoughts around a algorithm. Try replacing a recursion with iteration (always a fun exercise). Consider fluctuating it to embody weave mazes (where passages pierce over or underneath alternative passages), or braided mazes (mazes where deadends have been private to emanate loops in a maze), or symmetrical mazes, or wrapped mazes. Or even different cell tesselations. If you’re during all similar to me, we might find which your “toy” plot has taken upon a hold up of a own, as well as you’re unexpected researching latest as well as sparkling ways to set up mazes!

Once we assimilate a algorithm, though, a genuine fun is perplexing it in a denunciation you’re unknown with. It’ll uncover we conditionals, bit strategy (if we operate a bitfield storage similar to we showed above), iteration, recursion, as well as console outlay (if we confirm to describe your maze, too). When you’ve finished, you’ll have a fantastic thought of how a denunciation looks as well as functions in practice, as well as not usually for pardonable “hello world” apps.

Give it a try! Please share your implementations in a comments (links to gist.github.com have been preferred).


the { buckblogs :here } – Home

Incoming search terms: