Image:Maze.png

From Wikipedia, the free encyclopedia

• Image
• File history
• File links

No higher resolution available.
Maze.png‎ (200 × 200 pixels, file size: 443 B, MIME type: image/png)

Maze, generated by my algorithm; Source edited for clarity by quin/10-24-06

import java.awt.*;
import java.applet.*;
  
/*
 * For the benefit of novice programmers, I've listed
 * the various bitmasks used to the best of my ability
 * (I don't use Java, I'm assuming it uses standard coordinates where 0,0 is the top left)
 * I've commented on the drawing code as well
 *
 *  1: Wall above
 *  2: Wall below
 *  4: Wall left
 *  8: Wall right
 * 16: queued to be added
 * 32: "in" the maze
 *
 *  - quin/10-24-06
 */

public class Maze extends Applet {
   int maze[][];
   
   public void init () {
       int x, y, n, d;
       int dx[] = { 0, 0, -1, 1 };
       int dy[] = { -1, 1, 0, 0 };
       int todo[] = new int[400], todonum = 0;
  
       /* We want to create a maze on a grid. */
       maze = new int[20][20];
  
       /* We start with a grid full of walls. */
       for (x = 0; x < 20; ++x)
           for (y = 0; y < 20; ++y)
               if (x == 0 || x == 19 || y == 0 || y == 19) {
                   maze[x][y] = 32;
               } else {
                   maze[x][y] = 63;
               }
  
       /* Select any square of the grid, to start with. */
       x = (int) (1 + Math.random () * 18);
       y = (int) (1 + Math.random () * 18);
  
       /* Mark this square as connected to the maze. */
       maze[x][y] &= ~48;
  
       /* Remember the surrounding squares, as we will */
       for (d = 0; d < 4; ++d)
           if ((maze[x + dx[d]][y + dy[d]] & 16) != 0) {
               /* want to connect them to the maze. */

               /* alternately, you could use a struct to store the two integers
                * this would result in easier to read code, though not as speedy
                * of course, if you were worried about speed, you wouldn't be using Java
                * you could also use a single integer which represents (x + y * width)
                * this would actually be faster than the current approach
                * - quin/10-24-06
                *    Actually, the former wouldn't work in Java- there's no such thing as a
                *    struct. It's a class or nothing, I'm afraid.
                *    - Jae Armstrong/23-03-07
                */
                
               todo[todonum++] = ((x + dx[d]) << 16) | (y + dy[d]);
               maze[x + dx[d]][y + dy[d]] &= ~16;
           }
  
       /* We won't be finished until all is connected. */
       while (todonum > 0) {
           /* We select one of the squares next to the maze. */
           n = (int) (Math.random () * todonum);
           x = todo[n] >> 16; /* the top 2 bytes of the data */
           y = todo[n] & 65535; /* the bottom 2 bytes of the data */
  
           /* We will connect it, so remove it from the queue. */
           todo[n] = todo[--todonum];
  
           /* Select a direction, which leads to the maze. */
           do
               d = (int) (Math.random () * 4);
           while ((maze[x + dx[d]][y + dy[d]] & 32) != 0);
  
           /* Connect this square to the maze. */
           maze[x][y] &= ~((1 << d) | 32);
           maze[x + dx[d]][y + dy[d]] &= ~(1 << (d ^ 1));
  
           /* Remember the surrounding squares, which aren't */
           for (d = 0; d < 4; ++d)
               if ((maze[x + dx[d]][y + dy[d]] & 16) != 0) {
                   
                   /* connected to the maze, and aren't yet queued to be. */
                   todo[todonum++] = ((x + dx[d]) << 16) | (y + dy[d]);
                   maze[x + dx[d]][y + dy[d]] &= ~16;
               }
           /* Repeat until finished. */
       }
       
       /* One may want to add an entrance and exit. */
       maze[1][1] &= ~1; 
       maze[18][18] &= ~2;
   }
  
   public void paint (Graphics g) {
       int x, y;
  
       for (x = 1; x < 19; ++x)
           for (y = 1; y < 19; ++y) {
               if ((maze[x][y] & 1) != 0) /* This cell has a top wall */
                   g.drawLine (x * 10, y * 10, x * 10 + 10, y * 10);
               if ((maze[x][y] & 2) != 0) /* This cell has a bottom wall */
                   g.drawLine (x * 10, y * 10 + 10, x * 10 + 10, y * 10 + 10);
               if ((maze[x][y] & 4) != 0) /* This cell has a left wall */
                   g.drawLine (x * 10, y * 10, x * 10, y * 10 + 10);
               if ((maze[x][y] & 8) != 0) /* This cell has a right wall */
                   g.drawLine (x * 10 + 10, y * 10, x * 10 + 10, y * 10 + 10);
           }
   }
}

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. Subject to disclaimers.

File history

Click on a date/time to view the file as it appeared at that time.

• Search for duplicate files
• Edit this file using an external application

  See the setup instructions for more information.

File links