An attempt at maze solution with Cellular Automata

Circa 1992-93, an instructor for a data structures class I had at the time gave the class a reference to an article in Dr. Dobb's Journal for a program that attempted to solve a maze by using cellular automata.

For those of you unfamiliar with the term, cellular automata are generally an array of cells with a finite number of 'states', where the step may change based on the state of the cell and its neighbors. The most generally known use of cellular automata is probably Conway's Game of Life.

In this application, the program is given a filename on the command line containing the size, width, and wall characters in addition to an array of cells, each cell either a 'wall' character or not. During each iteration, each non-wall cell is examined, and if three or more of its neighbors (up and down, and to left and right) are wall cells, the cell becomes a wall cell itself. The program requires there be only one successful path thru the maze, and if loops exist, it may not be filled in, so a solution might not be found, but the possibilities will definitely be reduced down.

I did not originate the idea, but a short time back the idea was brought back to mind, and I began playing with it again. The result is below. Because it wasn't my idea, I can't take credit for the idea, only the bugs.

If someone knows the reference to the article so I may give proper credit, please let me know. Otherwise, please enjoy. Your comments are welcome.

UPDATE: A search on the website for Dr. Dobb's Journal showed that the article, CELLULAR AUTOMATA FOR SOLVING MAZES, by Basem A. Nayfeh, appeared in the February 1993 publication.

UPDATE: Many thanks to the A.M. (wherever you are) who pointed out where the idea originated. The article mentioned above was my first encounter.

UPDATE: Added READMORE tag (see Writeup Formatting Tips) to make easier to handle when found in a section listing.

#!/usr/local/bin/perl --
# use strict;

if ($#ARGV < 0) {
    &display_usage;
    exit(0);
}

my $datafile = $ARGV[0] || $0 . '.txt';
my ($height, $width, $bcharlist, @board) = &read_data($datafile);
my @borderchars = split('', $bcharlist);

&display_board($width, $height, 0, @board);

my $changes = $height * $width;
my $passes = 0;
while ($changes > 0) {
    $changes = 0;
    $passes++;
    for (my $y = 0; $y < $height; $y++) {
        for (my $x = 0; $x <= $#{$board[$y]}; $x++) {
            next    if (&is_border($board[$y][$x]));
            my $sum = &count_neighbors($x, $y, 
                        $width, $height, \@board);
            if ($sum >= 3) {
                $changes++;
                $board[$y][$x] = $borderchars[0];
            }
        }
    }
}

&display_board($width, $height, $passes, @board);

sub read_data {
    my ($filename) = @_;
    my $h = 0, $w = 0, $charlist = '#';
    my (@board);
    open(DATAFILE, $filename) or die("Can't open $filename : $!\n");
        while (my $line = <DATAFILE>) {
            chomp($line);
            next        unless (length($line));
            next        if ($line =~ m/^#/); 

            my @parts = split(/\s*[:=]\s*/, $line, 2);
            $w = $parts[1]    if ($parts[0] =~ m/width|x/i);
            $h = $parts[1]    if ($parts[0] =~ m/height|y/i);
            $charlist = $parts[1]
                if ($parts[0] =~ m/border|wall|char/i);
            if ($parts[0] =~ m/board|screen/i) {
                for (my $i = 0; $i < $w; $i++) {
                    $line = <DATAFILE>;
                    chomp($line);
                    @{$board[$i]} = split('', $line);
                }
            }
        }
    close(DATAFILE);
    return($h, $w, $charlist, @board);
}
sub display_board {
    my ($i, $j, $pass, @screen) = @_;
    printf("Pass : %d\nHeight : %d, Width : %d\nBoard : \n",
        $pass, $j, $i);
    for (my $y = 0; $y < $j; $y++) 
        { print(join('', @{$screen[$y]}, "\n")); }
    print("\n");
}
sub is_border {
    my ($character) = @_;
    return(scalar(grep(/$character/, @borderchars)));
}
sub count_neighbors {
    local ($i, $j, $w, $h, *screen) = @_;
    my $ncount = 0;
    if ($j > 0)
        { $ncount++    if (&is_border($screen[$j - 1][$i])); }
    if ($j < ($h - 1))
        { $ncount++    if (&is_border($screen[$j + 1][$i])); }
    if ($i > 0)
        { $ncount++    if (&is_border($screen[$j][$i - 1])); }
    if ($i < $w)
        { $ncount++    if (&is_border($screen[$j][$i + 1])); }
    return($ncount);
}
sub display_usage {
    while (<DATA>) {
        s/\$0/$0/;
        print $_    unless (m/^__DATA__$/);
    }
}
__END__
__DATA__
Program execution:
    $0 filename

where filename is the name of the data file to use.

Datafile format:
<line> : <parameter1><seperator><parameter1_value>
<line> : <parameter2<seperator>parameter2_value>
<line> : <parameter2><seperator>
<line> : <dataline>

<seperator> : <space>*['='|':']<space>*
<parameter1> : ['height'|'width'|'x'|'y']
<parameter1_value> : <number>
<parameter2> : ['border'|'wall'|'char']
<parameter2_value> : <string1>
<dataline> : <string2>

<number> : <digit>+
<string1> : <non_whitespace>+
<string2> : <character>

<digit> : (equivalent to perl regex /\d/)
<space> : (equivalent to perl regex /\s/)
<non_whitespace> : (equivalent to perl regex /\S/)
<character> : (matched by perl regex /./)

Sample file:
x:4
y= 3
wall=#
screen=
## #
#  #
# ##
[download]

Back to Cool Uses for Perl