Maze Generator 1

1 collaborator

WHAT IS IT?

A demonstration of the BAM maze generating algorithm. This model will randomly generate a maze with 1 unique solution to get from one red patch to the other (without crossing the white walls). The maze can be saved as a .png image file.

_The goal is to get from one red patch to the other by only stepping on the black space_

HOW IT WORKS

This model uses the slides to create 2 red patches (right and left). It then sets 2 distinct white lines (above and below). Finally, the model generates random white lines connected either to the "above" white line or the "below" one - but never to both of them! This algorithm guarentees that there will remain black space between the white lines, which is the uniqe solution to the maze.

HOW TO USE IT

Press "Setup" to start. Press "Go Forever" to generate the maze. Press again once you think the maze is done to your liking. Press "Clean" to remove all the remaining turtles.

If you like it, press "Export Maze" to save it as a .png file.

You can use the sliders to change the vertical position of the red patches (Start and Finish). You can also change the difficulty level (Easy, Medium, or Hard).

Try to solve the maze!

DIFFICULTY LEVELS

The difficulty levels are only an estimate. The difference between them is in the amount of turtles used to create the maze. The more turtles, the more homogenous the random pattern becomes, and thus the maze is easir to solve on average.

However, it takes a significantly shorter time to create easy mazes.

THINGS TO NOTICE

Use the sliders and change the world dimensions. When is the maze most difficult?

This is a really inefficient implementation of the algorithm as every tick many turtles die and are reborn.

EXTENDING THE MODEL

You may change the size of the world at any time. I recommend using 65*40. (please do not change the world wrapping - it will cause a bug).

There are many things which I would like to extend:

improve efficiency
control the random downhill movement a bit more
generate patterns
make the space between white lines be more than a single patch size
improve the code (it is way too complex)
make larger steps and different angles of movement

CREDITS AND REFERENCES

Benjamin Menashe, Instagram @benjamaze.original

bmenashe94@gmail.com

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

patches-own [ xxx ]

to setup
  clear-all

  ;; set sides with starting turtles
  ask patches with [count neighbors != 8]
    [ set xxx 1 ]
  ask patches with [pxcor = min-pxcor + 1] [set pcolor white]
  ask patches with [pxcor = max-pxcor - 1] [set pcolor white]

  ;; set top and bottom white
  ask patches with [pycor = max-pycor or pycor = min-pycor] [ set pcolor white ]
  clean-corners

  setup-start-finish ;set start and finish

  ;; sprout turtles
  ask n-of edges (patches with [pcolor = white]) [
    sprout 1
      [ set color blue
        facexy -1 * pxcor pycor
        fd 1 ]
  ]
  reset-ticks
end 

to setup-start-finish
  ask patches with [pxcor = max-pxcor and pycor = Right-Height] [
    set pcolor red
    ask neighbors [ set pcolor black ]
    ask patch-at 0 2 [ set pcolor white ]
    ask patch-at 0 -2 [ set pcolor white ]
  ]
  ask patches with [pxcor = min-pxcor and pycor = Left-Height] [
    set pcolor red
    ask neighbors [ set pcolor black ]
    ask patch-at 0 2 [ set pcolor white ]
    ask patch-at 0 -2 [ set pcolor white ]
  ]
end 

to clean-corners
  ask patches with [pycor = max-pycor and pxcor = max-pxcor ] [ set pcolor black ]
  ask patches with [pycor = max-pycor and pxcor = min-pxcor ] [ set pcolor black ]
  ask patches with [pycor = min-pycor and pxcor = max-pxcor ] [ set pcolor black ]
  ask patches with [pycor = min-pycor and pxcor = min-pxcor ] [ set pcolor black ]
end 

to go
  ;; die if neighbors
  ask turtles [
    if count turtles-on neighbors > 0
    [ die ]
  ]

  ;; turn if facing edge
  ask turtles [
    if patch-ahead 1 = nobody
    or
    patch-left-and-ahead 45 1 = nobody
    or
    patch-right-and-ahead 45 1 = nobody
    [ rt 180 ]
  ]

  ;; die if facing white
  ask turtles [
    if [pcolor] of patch-ahead 1 = white
    or
    [pcolor] of patch-left-and-ahead 45 1 = white
    or
    [pcolor] of patch-right-and-ahead 45 1 = white
    or
    [pcolor] of patch-left-and-ahead 90 1 = white
    or
    [pcolor] of patch-right-and-ahead 90 1 = white
    [ die ]
  ]


  ;; move
  ask turtles [
    set pcolor white
    set xxx 1
    downhill4 xxx
    ask patch-left-and-ahead 135 1 [ set xxx 1 ]
    ask patch-right-and-ahead 135 1 [ set xxx 1 ]
  ]

  ;; sprout turtles
  ask n-of edges (patches with [pcolor = white])
  [
    sprout 1
      [ set color blue
        let yyy random 4
        if yyy > 2.5
        [ set heading 0 ]
        if yyy > 1.5 and yyy < 2.5
        [ set heading 90 ]
        if yyy > 0.5 and yyy < 1.5
        [ set heading 180 ]
        if yyy > -0.5 and yyy < 0.5
        [ set heading 270 ]

        ifelse patch-ahead 1 = nobody
        [ rt 180 fd 1]
        [ fd 1]
    ]
  ]
  tick
end 

to kill
  ask turtles [ die ]
  ask patches with [ pcolor = red ]
  [ask neighbors4 [ set pcolor black ]
  ]
end 

to-report edges
    if Difficulty = "Easy" [ report count patches with [count neighbors != 8] - 6 ]
    if Difficulty = "Medium" [ report max-pycor / 3 ]
    if Difficulty = "Hard" [ report 1 ]
end

There are 3 versions of this model.

Uploaded by	When	Description	Download
Benjamin Menashe	almost 6 years ago	cosmetic cleanup	Download this version
Benjamin Menashe	almost 6 years ago	Start and Finish position can be changed. Exporting mazes now works.	Download this version
Benjamin Menashe	almost 6 years ago	Initial upload	Download this version

Attached files

File	Type	Description	Last updated
Maze Generator 1.png	preview	Preview for 'Maze Generator 1'	almost 6 years ago, by Benjamin Menashe	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo