Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

Comment on

( #3333=superdoc: 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= ## # # # # ##

In reply to An attempt at maze solution with Cellular Automata by atcroft

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others scrutinizing the Monastery: (3)
    As of 2017-02-26 17:40 GMT
    Find Nodes?
      Voting Booth?
      Before electricity was invented, what was the Electric Eel called?

      Results (376 votes). Check out past polls.