Beefy Boxes and Bandwidth Generously Provided by pair Networks chromatic writing perl on a camel
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

An attempt at maze solution with Cellular Automata

by atcroft (Monsignor)
on Dec 09, 2001 at 06:28 UTC ( #130497=CUFP: print w/ replies, xml ) Need Help??

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= ## # # # # ##

Comment on An attempt at maze solution with Cellular Automata
Download Code
Re: An attempt at maze solution with Cellular Automata
by Anonymous Monk on Mar 13, 2002 at 23:29 UTC
    The attribution to the author of this algorithm is incorrect. This algorithm was actually first outlined in the following reference:

    Preston, Kendall. _Modern Cellular Automata_. Plenum Press, New York: 1984. Pages 175-176.

    Questions?
    taltman at lbl.gov

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (15)
As of 2014-04-24 09:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (565 votes), past polls