Random maze generator

[ambrus]

Category:

Fun Stuff

Description:

This is the rewrite of an old random maze generator I wrote in C. It uses the same method for generating the maze, but the interface is different: the old one let you traverse the maze while seeing only your immediate environment, whereas this one only prints the maze as an ascii art (view in a fixed font).

The @ marks the starting position and > is the goal.

#!perl
# labir.pl -- maze generator
# Copyright (C) Zsban Ambrus 2001--2009
use warnings; use strict; use 5.010;
my $W = 35;
my $H = 19;
my @a = ([(1)x(3+2*$W)], map({ [1, (0)x(1+2*$W), 1] } 1 .. 1+2*$H), [(
+1)x(3+2*$W)]);
for my $u (0 .. $H-1) {
    for my $v (0 .. $W-1) {
        $a[2+2*$u][2+2*$v] = 1;
    }
}
my @y = (-1)x($W*$H);
my $C; $C = sub {
    no warnings "recursion";
    my($v) = @_;
    my $w = $y[$v];
    if ($w < 0) {
        return $v;
    } else {
        my $z = &$C($w);
        $y[$v] = $z;
        return $z;
    }
};
my $U = sub {
    my($u, $v) = @_;
    my($c, $d) = (&$C($u), &$C($v));
    $c != $d and
        $y[$c] = $d;
};
while (&$C(0) != &$C($W*$H-1)) {
    my $a = 1 < rand(2);
    my $x = int(rand($H));
    my $y = int(rand($W));
    $a ? $y < $W - 1 : $x < $H - 1 or next;
    my ($u, $v) = (($x+!$a)*$W+($y+$a), $x*$W+$y);
    &$C($u) != &$C($v) || rand(5) < 1 or next; # here's the magic
    &$U($u, $v);
    $a[2+!$a+2*$x][2+$a+2*$y] = 1;
}
for my $r (1 .. 1+2*$H) {
    for my $c (1 .. 1+2*$W) {
        my $o = $a[$r][$c];
        my $v = $a[$r-1][$c] && $a[$r+1][$c];
        my $h = $a[$r][$c-1] && $a[$r][$c+1];
        print(
            2 == $r && 2 == $c ? "@" :
            2*$H == $r && 1+2*$W == $c ? ">" :
            $o ? " " :
            $v ? ($h ? " " : "-") :
            ($h ? "|" : "+")
        );
    }
    print "\n";
}
__END__

Here's an example output.

+-------+---+---+-----+---+-----+-+-+-----+-------+-+-+---+---------+-
++
|@      |   |   |     |   |     | | |     |       | | |   |         | 
+|
+-- | +-+---+-- | ----+ | | --- | | +-+ +-+-+-+---+ +-+ | | | +---+-+ 
+|
|   | | |             | | |     | |   | | | | |     |   | | | |   |   
+|
+-+ +-+-+ | --+-+-+   +-+ | +-+ +-+-+ | | +-+ | --+ +-- +-+ +-+-+ | --
++
| |       |   | | |   |     | | | | | | |   | |   |           | |     
+|
+-+ | --+-+-+-+-+ | --+ ----+-+-+-+ +-+ +-- +-+---+ +-- +-- --+-+-- | 
+|
|   |   | | |         |       | | | | | |           |   |     | |   | 
+|
+---+ | +-+-+-----+   | | +-+-+-+-+-+ | +-+ +-- | | +-+-+-- +-+ | --+-
++
|   | |   | |     |     | | |   | |   |   | |   | | | |     | |       
+|
| --+ +---+ +-+ +-+ --+ +-+-+-+ +-+ +-+-+-+ | --+-+ | | +---+ | | +-+ 
+|
|             | |     |   | | |     | | |   |   | |   | |     | | | | 
+|
+-+-- +-+ | +-+ +-+-- +-+-+-+ +-+   | +-+-- +-+-+-+-+-+-+ | +-+ +-+ +-
++
| |   | | | |     |     | |     |     | |   | | | | |     | | |   | | 
+|
| +-- +-+ +-+-+-- +-+ | +-+ +-- +-- --+ +---+ | +-+-+ | | +-+ | --+ | 
+|
|       | |   |     | |   | |                   | | | | | |         | 
+|
| +---+-+-+-- +-+ --+ | | +-+-- | | | +-+ | +-+ | | +-+-+ +-+ ----+ +-
++
| |   | |       |     | | |     | | | | | | | |   | |   |   |     | | 
+|
+-+-+ +-+-+-+ | +-- | +-+ | | --+-+-+-+-+ +-+ +-+-+ | +-+ --+ | | | +-
++
| | |     | | | |   |   | | |   |     |   |     |   | |     | | |   | 
+|
+-+ +-+-- +-+-+ +-+-+---+ +-+-- | ----+-+ | +-- +-+ | |   --+ | +---+ 
+|
|   | |   |     | |     | |           | | | |   | |                   
+|
+-+ +-+---+ +-- | +-+-+ | | +-------- +-+ | +-+ +-+ +-+ | +-+---- ----
++
| |   |     |   |   | | |   |             |   |     | | | | |         
+|
| | --+ | --+ | | --+ | +-- +---+ --+ +-- | --+-----+-+-+ | | | | | +-
++
| |   | |     |     |   |       |   | |   |         | | | |   | | | | 
+|
+-+ | +-+-----+---- +-+-+   | --+---+-+-+ | +---+---+ +-+ +-+-+-+ | | 
+|
| | | | |     |     | |     |       | | |   |   |   |   | | | | | | | 
+|
| | +-+-+ +-- +-- --+-+ | | +---+ --+ +-+ | | +-+-+-+ | | | | | +-+ | 
+|
|     | | |         | | | | |   |   | |   | | |   |   | | |   | | | | 
+|
+-+ +-+-+ +---------+ | +-+-+ --+ --+ | +-+-+-+ | +-+-+ | | +-+ | | | 
+|
| | | |   |         | | | |             | |     | | |   |   |   | |   
+|
| | | | | | +-----+-+-+ | | | ----+ +-+-+-+ | +-+-+ | | +-+ +-- | | | 
+|
|   |   | | |     | |     | |     | | |   | | | |   | |   |     |   | 
+|
|   +---+-+-+ | | | +---- +-+ ----+-+ +-+-+-+ | +-- | +-+ +-+-- +-- | 
+|
|   |         | |                 |   | |   | | |       |   |   |   | 
+|
+-+ +-- --+---+-+ +-+-- +-+-- --+-+-- | | | | +-+ +-+-+-+ --+ +-+-+-+ 
+|
| |       |     | | |   | |     | |   |   | |   | | | | |   | | | | | 
+>
+-+-------+-----+-+-+---+-+-----+-+---+---+-+---+-+-+-+-+---+-+-+-+-+-
++

[toolic]

ambrus, you saved my day! My son asked me to draw him a bunch of mazes by hand. That is no job for a human.

For anyone stuck on pre-5.10.0, just comment out use 5.010; and it works just fine.

[choroba]

If your son gets bored with this type of mazes, you can give him another one:
Read more... (5 kB)
Sample output:

╲╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱
╱╲╲╱╱╲╱╱╱╱╱╲╱╲╱╲╱╱╱╱╱╱╱╲╱╲╱╱╱╱╲╱╱╲╱╱╱╲╲╱╱╲╲╱╲╲╱╲╱╲╲╱╱╲╲╲╲╲╱╲╱╱╲╲╱╲╲╲╲╱╲╲╱╱╱╲╱╲╲
╲╲╲╱╱╲╱╱╲╲╲╲╲╲╲╲╱╱╲╱╱╲╱╲╱╱╱╲╲╲╲╲╲╲╱╲╱╲╲╱╱╱╲╱╲╲╲╱╱╲╲╱╱╲╲╱╱╲╱╱╲╱╱╱╲╲╲╱╱╱╲╱╱╱╱╱╱╲╱
╱╱╲╲╲╲╲╱╱╱╱╱╲╱╲╲╱╱╲╱╲╲╲╱╱╱╱╱╱╲╱╱╱╲╲╲╱╲╲╱╱╲╲╱╲╱╱╱╱╲╱╲╱╱╲╲╲╲╱╲╲╱╲╱╲╱╱╲╲╲╲╱╲╲╲╱╱╲╲
╲╱╲╲╱╱╱╱╱╱╲╱╱╲╲╱╱╱╱╲╲╲╲╱╲╱╱╲╱╱╲╲╲╱╱╱╱╱╱╲╱╱╲╲╲╲╱╲╱╲╲╲╱╲╲╲╲╱╱╱╱╱╲╱╲╱╲╱╱╱╱╱╱╲╲╱╱╲╱
╱╱╲╱╱╲╱╱╱╲╱╲╲╱╱╲╱╲╲╲╱╱╱╱╲╱╱╲╲╲╱╲╲╲╱╱╱╲╲╱╱╱╱╲╱╲╱╲╲╱╱╱╱╱╱╲╲╱╱╲╱╲╱╱╲╲╲╱╱╲╲╲╲╲╲╲╱╲╲
╲╱╲╱╱╲╱╱╲╲╲╲╱╱╲╲╲╱╱╲╲╲╲╱╲╱╱╲╱╲╱╱╱╱╱╱╱╲╲╱╱╲╲╲╲╲╱╲╱╱╱╲╲╱╱╱╱╱╲╱╲╲╲╲╲╲╲╱╱╲╱╱╱╱╱╲╱╱╱
╱╱╲╱╲╱╱╲╲╲╲╱╱╱╱╱╲╲╱╲╱╱╲╱╱╱╲╲╲╲╱╱╲╲╲╱╲╲╱╲╲╲╱╱╱╲╲╱╱╲╱╱╱╱╱╱╱╱╲╱╱╱╲╲╱╲╲╱╲╱╱╲╲╲╱╲╱╲╲
╲╱╲╱╲╲╲╱╱╱╱╱╱╲╱╱╲╱╱╲╲╲╱╲╲╱╲╲╲╱╲╱╲╲╱╲╱╲╲╲╱╱╱╲╱╱╱╲╲╲╱╱╲╲╲╱╱╱╱╲╱╲╱╲╲╱╱╲╲╲╲╲╲╱╱╱╲╲╱
╱╲╲╱╲╲╱╲╲╲╲╲╱╱╱╱╲╱╱╱╲╱╱╲╲╲╱╲╱╱╲╱╲╱╲╲╱╱╲╱╱╲╲╱╲╱╱╲╲╱╱╱╱╱╲╲╱╱╲╲╱╱╲╲╱╱╱╲╲╲╱╱╲╱╱╱╲╱╲
╲╲╱╱╲╲╱╲╱╲╲╲╲╲╱╱╲╱╲╱╱╲╱╱╲╲╱╲╲╱╲╲╱╱╲╱╲╱╲╱╲╲╱╱╲╱╱╲╲╲╲╲╱╱╱╲╱╱╲╱╲╲╲╱╲╱╱╲╲╲╲╱╱╱╲╲╱╱╱
╱╲╲╱╱╲╱╱╱╱╱╱╲╱╱╱╱╱╱╱╱╱╱╲╱╲╱╲╱╲╲╲╲╱╱╱╱╱╲╱╱╲╱╱╲╱╱╱╲╲╱╱╱╱╱╱╱╱╲╲╱╱╱╲╲╱╱╱╲╱╱╲╲╱╲╲╱╱╲
╲╲╲╱╲╲╲╲╲╲╱╲╱╱╱╲╱╱╲╱╱╲╱╲╱╱╲╲╲╲╱╲╲╱╱╲╲╲╲╱╲╲╱╱╱╱╲╱╲╲╲╱╱╱╱╲╲╲╱╲╲╲╱╱╲╱╱╲╲╲╲╱╱╱╲╱╲╱╱
╱╱╲╱╲╱╲╱╱╲╱╲╱╱╱╲╱╱╲╱╲╱╲╲╲╱╲╲╲╱╲╲╲╱╱╲╲╲╲╱╱╲╱╲╲╱╲╲╱╱╱╲╱╲╱╱╱╲╲╲╲╱╲╲╲╱╱╱╱╱╲╱╱╲╱╲╲╲╲
╲╱╲╲╱╱╱╱╲╲╱╱╲╲╱╱╲╲╱╲╲╲╲╱╱╲╱╱╲╱╲╱╲╲╲╲╱╲╱╲╱╱╱╲╱╲╲╱╲╲╱╲╲╱╱╱╱╲╲╱╱╱╲╲╲╱╱╱╱╱╲╲╱╱╱╱╱╲╱
╱╱╲╲╱╱╱╱╱╱╲╲╱╲╲╱╲╱╱╲╲╲╲╲╱╲╲╲╱╱╱╱╲╱╱╱╲╲╲╲╱╱╲╲╱╲╱╲╲╱╱╱╲╱╱╲╲╲╲╱╱╲╲╱╱╱╱╲╱╱╲╱╱╲╲╲╱╲╲
╲╱╱╲╱╱╲╲╲╱╱╲╲╲╱╱╲╱╱╲╱╱╱╱╲╲╱╲╲╲╲╲╲╱╲╲╱╱╱╱╲╱╲╱╲╲╱╲╲╱╲╱╱╱╱╱╲╲╲╱╱╲╲╲╱╱╲╲╱╱╲╱╱╱╱╱╱╲╱
╱╱╲╱╲╱╱╲╲╱╲╱╱╱╱╲╲╱╱╲╲╲╱╲╱╱╱╲╲╲╲╱╲╲╲╱╱╲╱╱╲╱╱╱╱╱╱╱╲╱╲╲╲╱╱╲╲╱╱╲╲╱╱╱╲╲╱╲╱╲╱╱╱╱╲╲╱╲╲
╲╱╲╱╱╱╱╲╱╱╲╱╲╲╲╲╱╱╱╲╱╲╲╲╱╱╲╲╱╲╱╲╱╱╲╲╱╲╱╲╲╱╲╲╱╲╲╱╲╲╱╱╱╲╲╲╲╲╲╲╱╱╲╱╲╲╱╱╲╲╱╲╱╱╱╱╲╲╱
╱╲╲╱╱╲╲╲╲╲╲╱╲╱╲╲╲╲╱╲╱╱╱╲╱╱╲╲╲╲╱╱╲╱╱╲╱╱╲╱╱╱╱╱╲╲╱╱╱╲╲╲╱╲╲╱╲╲╱╲╲╱╱╱╱╱╲╲╱╱╱╲╲╲╱╲╱╲╲
╲╲╱╲╱╲╲╱╲╲╱╱╱╲╱╱╲╲╱╱╲╱╲╲╱╱╱╱╱╱╱╱╲╱╲╱╲╱╲╱╱╱╲╱╱╲╱╱╱╱╲╱╱╲╲╱╱╲╱╱╲╲╲╲╱╱╲╱╲╲╱╲╲╲╲╲╱╲╱
╱╱╱╱╱╲╱╲╱╲╱╱╲╲╱╲╱╱╱╱╱╲╱╱╲╲╱╲╱╲╱╲╲╱╲╲╲╲╲╲╲╱╲╱╱╲╲╱╱╱╲╱╲╱╱╱╲╲╱╲╱╲╲╱╲╲╱╱╱╱╱╲╱╲╱╲╲╱╲
╲╱╲╲╱╲╲╲╱╲╱╱╲╱╲╲╲╱╱╲╱╱╱╱╱╲╱╲╱╱╱╲╱╱╱╱╱╲╲╲╱╱╱╲╲╲╱╲╱╲╲╲╲╱╲╱╲╲╱╲╱╱╲╱╲╲╱╲╱╲╲╲╲╲╱╲╲╱╱
╱╱╲╱╱╱╱╲╱╱╲╱╲╱╲╱╱╲╲╱╲╲╲╲╱╲╱╱╱╲╱╱╲╲╲╲╲╲╱╲╱╱╱╲╱╲╲╲╱╲╱╱╲╱╱╱╱╲╱╲╱╱╱╲╲╱╱╱╲╱╱╲╲╱╱╲╲╲╲
╲╱╲╱╲╱╲╲╱╱╲╱╲╲╲╱╲╱╱╱╲╲╱╱╲╲╱╲╲╲╲╲╲╱╲╱╱╲╱╲╱╱╱╱╱╲╲╲╱╱╲╱╲╱╱╲╲╱╲╲╲╲╱╲╲╱╲╱╱╲╱╱╲╲╱╱╲╱╱
╱╲╲╲╲╱╲╱╱╱╱╱╲╱╲╲╲╲╱╲╲╱╲╱╱╲╱╲╲╱╲╱╱╱╲╱╱╱╱╱╱╲╲╱╲╲╱╲╱╱╱╱╲╱╲╲╲╱╲╱╱╱╱╱╲╲╲╱╱╲╱╲╲╲╲╲╱╱╲
╲╲╱╲╱╱╱╲╲╲╱╱╲╱╱╲╱╲╱╱╲╱╲╲╱╲╱╱╲╱╱╲╲╱╲╱╲╱╱╲╱╱╲╱╲╲╱╱╱╲╲╱╱╱╱╱╲╲╲╱╲╲╲╱╲╲╱╱╱╲╲╱╲╲╱╲╱╱╱
╱╱╲╲╱╲╲╱╱╲╱╱╱╲╲╱╲╲╱╱╲╱╱╲╲╲╱╲╱╱╱╲╲╱╱╲╲╲╱╱╱╲╱╲╲╱╲╲╱╱╱╲╱╲╲╱╱╱╲╱╲╱╱╱╱╲╱╱╲╲╲╱╱╱╲╱╱╲╲
╲╱╲╲╲╲╲╲╱╲╲╲╲╱╱╲╲╱╱╱╲╲╲╱╲╲╱╲╲╲╲╲╱╱╲╲╱╲╱╲╱╱╱╱╲╱╱╲╱╲╱╲╲╱╱╲╲╲╲╲╲╲╱╲╱╲╲╲╱╱╲╱╲╱╱╲╲╲╱
╱╱╲╱╱╲╲╱╲╲╱╱╲╱╲╲╱╱╱╲╲╲╲╱╲╲╲╲╱╲╲╲╱╱╲╲╲╱╲╱╱╱╲╲╱╲╲╱╲╲╲╲╱╲╲╱╱╲╱╲╱╲╱╲╲╱╲╲╲╲╱╱╱╱╲╲╲╲╲
╲╱╲╱╱╲╲╲╱╱╱╱╱╲╲╱╱╱╲╲╱╲╲╲╱╱╲╱╱╲╲╲╲╱╲╲╱╱╱╲╱╱╱╲╱╱╲╲╲╲╲╲╱╲╱╱╱╲╲╲╲╱╱╲╱╱╲╱╱╱╱╲╱╲╱╲╲╱╱
╱╲╱╲╱╱╲╱╱╲╱╲╲╱╱╱╱╱╱╲╲╱╱╲╲╱╲╱╱╲╱╱╱╱╱╱╱╲╱╱╲╲╲╲╱╱╱╲╱╱╱╱╲╲╲╱╲╱╱╱╲╱╱╱╱╱╱╱╱╲╲╱╱╲╱╲╲╲╲
╲╲╱╲╱╱╲╱╲╱╱╲╱╲╱╱╱╲╲╲╱╱╱╲╱╱╲╱╱╲╱╱╲╲╲╲╲╱╱╱╱╱╲╲╲╲╱╱╱╱╲╱╲╲╲╱╲╱╲╱╲╱╱╲╲╲╱╲╱╱╱╲╲╱╲╱╲╱╱
╱╱╱╲╱╱╲╱╲╱╱╱╱╲╲╱╱╲╲╲╲╲╱╲╱╱╱╱╱╱╲╲╲╱╲╲╱╲╱╱╱╱╱╱╲╲╲╱╲╱╲╱╲╲╱╱╲╱╲╲╲╲╲╲╲╲╲╲╱╲╱╲╲╲╲╱╲╱╲
╲╱╱╲╲╱╲╲╲╱╲╱╲╲╱╱╲╲╲╱╱╲╲╲╱╱╱╱╲╲╲╱╲╲╱╲╱╲╲╲╲╲╱╱╱╲╱╱╲╱╲╲╲╱╲╱╲╲╱╲╱╱╲╱╲╲╱╱╱╱╲╱╲╱╲╱╱╱╱
╱╱╱╱╲╲╲╱╱╲╱╱╲╱╱╱╱╱╲╲╱╱╱╲╲╲╱╱╱╱╱╲╱╱╱╲╱╲╱╱╱╲╱╱╱╲╱╱╲╲╲╱╲╱╲╲╲╱╲╲╲╲╲╱╲╱╱╲╲╱╲╲╲╲╲╱╱╲╲
╲╱╱╱╱╱╱╲╱╱╲╱╲╱╲╲╲╱╲╲╱╱╲╲╱╲╱╲╱╲╱╲╱╲╱╲╱╱╱╱╲╱╱╱╱╲╱╱╲╱╲╱╲╱╲╲╲╱╲╲╲╲╲╲╱╲╱╲╱╱╱╲╱╲╲╲╲╱╱
╱╱╱╲╲╱╲╱╲╲╲╲╲╲╱╱╲╲╱╱╲╲╲╲╲╲╱╲╲╱╱╱╲╱╲╲╲╱╲╱╲╲╲╲╲╲╲╲╱╱╱╱╲╲╱╱╲╱╱╱╱╲╲╲╱╲╱╱╲╲╲╲╲╲╱╲╱╲╲
╲╲╱╱╲╱╲╱╱╲╱╲╱╲╲╱╱╲╱╱╱╲╱╲╱╲╱╱╱╱╲╲╲╱╲╱╱╱╲╲╱╱╲╲╱╱╲╲╱╲╲╱╱╲╱╲╲╲╲╲╱╲╲╲╱╲╱╲╱╲╲╱╱╱╲╲╱╲╱
╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╱╲╲

Update: Code should be tidy now. Click here for a screencast.

[code-ninja]

This, sir, is by far the loveliest code I've ever seen in Perl. I'm feeling like a 6 yr old who got a new toy to play with! :-D

[gwadej]

Having been in the same position a few years ago, I wrote Games::Maze::SVG. The original implementation generated nicely printable mazes. That version quickly morphed into playable mazes.

Of course, my son lost interest in mazes shortly after I finished writing all of this.<shrug/>

[ambrus]

See also chipmunk's Maze and Snake!.