Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Random maze generator

by ambrus (Abbot)
on May 19, 2009 at 11:05 UTC ( #764894=sourcecode: print w/ replies, xml ) Need Help??

Category: Fun Stuff
Author/Contact Info
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.

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

Comment on Random maze generator
Select or Download Code
Replies are listed 'Best First'.
Re: Random maze generator
by toolic (Bishop) on Jun 03, 2010 at 23:45 UTC
    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.

      If your son gets bored with this type of mazes, you can give him another one: Sample output:

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

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

        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

      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/>

      G. Wade
Re: Random maze generator
by ambrus (Abbot) on Jun 04, 2010 at 17:48 UTC

Back to Code Catacombs

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: sourcecode [id://764894]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (8)
As of 2015-08-02 05:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found
    past polls