Maze generation: Difference between revisions

{{task|Games}}{{wikipedia|Maze generation algorithm}}

 

<br>

* [[Maze solving]].

<br><br>

 

=={{header|Ada}}==

{{works with|GNAT}}

mazes.ads:

Height : Positive;

Width : Positive;

type Maze_Grid is array (Height_Type, Width_Type) of Cells;

 

mazes.adb:

with Ada.Text_IO;

package body Mazes is

package RNG is new Ada.Numerics.Discrete_Random (Positive);

package Random_Direction is new Ada.Numerics.Discrete_Random (Directions);

Generator : RNG.Generator;

Dir_Generator : Random_Direction.Generator;

function "-" (Dir : Directions) return Directions is

begin

end case;

end "-";

procedure Depth_First_Algorithm

(Maze : in out Maze_Grid;

Next_Direction : Directions;

Valid_Direction : Boolean;

begin

-- mark as visited

Maze (Row, Column).Visited := True;

-- use random direction

Next_Row := Row;

Next_Column := Column;

Move (Next_Row, Next_Column, Next_Direction, Valid_Direction);

if Valid_Direction then

if not Maze (Next_Row, Next_Column).Visited then

Maze (Row, Column).Walls (Next_Direction) :=

False;

end if;

end if;

end loop;

end Depth_First_Algorithm;

procedure Initialize (Maze : in out Maze_Grid) is

Row, Column : Positive;

Depth_First_Algorithm (Maze, Row, Column);

end Initialize;

procedure Put (Item : Maze_Grid) is

begin

for Row in Item'Range (1) loop

if Row = Item'First (1) then

for Col in Item'Range (2) loop

if Item (Row, Col).Walls (North) then

else

end if;

end loop;

Ada.Text_IO.New_Line;

else

Ada.Text_IO.Put ("???");

end if;

end loop;

for Col in Item'Range (2) loop

if Item (Row, Col).Walls (South) then

else

end if;

end loop;

Ada.Text_IO.New_Line;

end loop;

end Put;

Example main.adb:

procedure Main is

package Small_Mazes is new Mazes (Height => 8, Width => 11);

Small_Mazes.Initialize (My_Maze);

Small_Mazes.Put (My_Maze);

{{out}}

<pre>Starting generation at 3 x 7

 

=={{header|Aime}}==

{

data d;

 

0;

{{out}}

<pre>+---+---+---+---+---+---+---+---+---+---+

| | | |

+---+---+---+---+---+---+---+---+---+---+

</pre>

 

=={{header|AutoHotkey}}==

For a challenge, this maze generation is entirely string based. That is to say, all operations including the wall removal and retrieval of cell states are done on the output string.

Width := 11

Height := 8

If (A_Index = Y)

return SubStr(A_LoopField, x, 1)

{{out|Sample output}}

<pre>+-+-+-+-+-+-+-+-+-+-+-+

=={{header|AWK}}==

 

 

# Remember: AWK is 1-based, for better or worse.

srand(t);

}

 

Example output:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

</pre>

 

=={{header|Batch File}}==

{{works with|Windows NT}}

 

:: A stack-less, iterative, depth-first maze generator in native WinNT batch.

:: Rows and Cols must each be >1 and Rows*Cols cannot exceed 2096.

ENDLOCAL

EXIT /B 0

 

Example output:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

</pre>

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

MazeHeight% = 9

MazeCell% = 50

ENDIF

NEXT

'''Sample output:'''

<br>

Also note that this requires an interpreter with working read-write memory support, which is suprisingly rare in online implementations. Padding the code page with extra blank lines or spaces can sometimes help. Using smaller dimensions might also be preferable, especially on slower implementations.

0_ 1!%4+1\-\0!::\-\2%2:p<pv0<< v0p+6/"P"\%"P":\+4%4<^<v-<$>+2%\1-*20g+\1+4%::v^

#| +2%\1-*30g+\1\40g1-:v0+v2?1#<v>+:00g%!55+*>:#0>#,_^>:!|>\#%"P"v#:*+*g00g0<>1

0#$g#<1#<-#<`#<\#<0#<^#_^/>#1+#4<>"P"%\"P"/6+g:2%^!>,1-:#v_$55+^|$$ "JH" $$>#<0

::"P"%\"P"/6+g40p\40g+\:#^"P"%#\<^ ::$_,#!0#:<*"|"<^," _"<:g000 <> /6+g4/2%+#^_

 

{{out}}

=={{header|C}}==

Generation/solver in one. Requires UTF8 locale and unicode capable console. If your console font line-drawing chars are single width, define DOUBLE_SPACE to 0.

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out|Sample output}}

<pre>┌───┬─────┬─────────┬───────┬───┐

│　　　　　│　　╰┄┄┄╯│　　╰┄┄┄┄┄┄┄╯│　　╰┄┄│

└─────┴───────┴───────────┴─────┘</pre>

=={{header|C++}}==

[[File:maze_cpp.png|300px]]

#include <windows.h>

#include <iostream>

}

//--------------------------------------------------------------------------------------------------

 

 

 

 

 

 

 

 

 

 

 

<pre>

</pre>

 

=={{header|Clojure}}==

(:require [clojure.set :refer [intersection

select]]

 

;;Task

 

{{out}}

Written in Commodore BASIC V2 and tested on Commodore 64 and Commodore 128 hardware. (It will also run on the unexpanded Commodore VIC-20 if you reduce the maze size to 8x8.) Due to stack size limitations in the operating systems, this solution eschews recursive subroutine calls. Recursion is accomplished by conditional branching within the maze build routine and the use of an array-based stack for data elements.

 

110 DIM S(MS+1,MS+1):REM SOUTH WALLS

120 DIM W(MS+1,MS+1):REM WEST WALLS

670 NEXT R

680 REM PRINT#4:CLOSE 4:REM CLOSE PRINTER DEVICE

{{out|Output example (for 10x10 maze)}}

<pre>+--+--+--+--+--+--+--+--+--+--+

 

The remove-wall function has been written so as to be as close as possible to the specification. The walls are made from a single unicode character, specified by the block keyword, e. g. (maze 20 6 :block #\X). The BOX_DRAWINGS_LIGHT_DIAGONAL_CROSS character is used by default.

(sort list '> :key (lambda(x) (random 1.0))))

 

do (princ (aref maze i j))))))

 

{{out}}

<pre>

 

Another solution using unicode line drawing chars. Assumes they are single width on console. Code pretty horribly unreadable.

 

(defun 2d-array (w h)

(show))))

 

{{out}}

<pre>┼───┴───┼───┴───┴───┼───┴───┴───┼

 

=={{header|D}}==

import std.stdio, std.algorithm, std.range, std.random;

 

foreach (const a, const b; hor.zip(ver ~ []))

join(a ~ "+\n" ~ b).writeln;

{{out}}

<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

| | | |

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>

=={{header|EasyLang}}==

 

 

.

.

.

 

=={{header|EGL}}==

 

// First and last columns/rows are "dead" cells. Makes generating

end

 

{{out|Output example (for 10x10 maze)}}

<pre>

=={{header|Elixir}}==

{{trans|D}}

def generate(w, h) do

maze = (for i <- 1..w, j <- 1..h, into: Map.new, do: {{:vis, i, j}, true})

end

 

 

{{out}}

 

=={{header|Elm}}==

import Result as R

import Matrix

, update = update

, subscriptions = subscriptions

 

Link to live demo: http://dc25.github.io/mazeGenerationElm/

 

=={{header|Erlang}}==

 

===Using multiple processes===

-module( maze ).

 

[Pid ! {Key, My_pid} || {_Position, Pid} <- Position_pids],

[{Position, read_receive(Pid, Key)} || {Position, Pid} <- Position_pids].

{{out}}

<pre>

 

Usage: start with generate_default/0. Use generate_MxN() to test other maze sizes.

-module(maze).

-record(maze, {g, m, n}).

generate_default() ->

generate_MxN(9, 9).

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

Using mutable state in the form of 2D arrays:

let gen = new System.Random()

fun max -> gen.Next(max)

 

let m = new Maze(10,10)

{{out|Output example}}

<pre>+-+-+-+-+-+-+-+-+-+-+

| | |

+-+-+-+-+-+-+-+-+-+-+</pre>

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' when generating a big maze it's possible to run out of stack space

Loop

 

 

=={{header|Go}}==

 

import (

m.gen()

fmt.Print(m)

{{out}}

<pre>

 

=={{header|Haskell}}==

{-# LANGUAGE TypeFamilies #-}

 

import Data.Array.ST

 

rand range gen = do

 

 

maze :: Int -> Int -> StdGen -> ST s Maze

maze width height gen = do

 

printMaze :: Maze -> IO ()

printMaze (Maze rWalls bWalls) = do

 

{{out|Sample output}}

+---+---+---+---+---+---+---+---+---+---+---+

 

=={{header|Huginn}}==

import Mathematics as math;

import Terminal as term;

maze = Maze( rows, cols );

print( "{}".format( maze ) );

 

=={{header|Icon}} and {{header|Unicon}}==

[[File:Mazegen-unicon-20x30-1321112170.gif|thumb|right|20x30 with two random openings]]

[[File:Mazegen-unicon-20x30-1321060467.gif|thumb|right|20x30 with opposite openings]]

 

procedure main(A) # generate rows x col maze

 

return mazeinfo(&window,maze,sprintf("maze-%dx%d-%d.gif",r,c,&now))

Note: The underlying maze structure (matrix) is uni-directional from the start

{{libheader|Icon Programming Library}}

{{trans|PicoLisp}}

But without any relevant grid library:

assert.0<:n=.<:x*y

horiz=. 0$~x,y-1

'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y

' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text

The result of <code>maze</code> is a pair of arrays: one for open "doors" in the horizontal direction and the other for open "doors" in the vertical direction. The entry and exit doors are not represented by <code>maze</code> -- they are implicitly defined and are implemented in <code>display</code>. (The sequences of coordinates in <code>display</code> are the relative coordinates for the doors. For example, <code>2 1;2 2;2 3</code> are where we put spaces for each vertical door. The variable <code>text</code> is an ascii representation of the maze grid before the doors are placed.)

 

{{out|Example use (with ascii box drawing enabled)}}

+ +---+---+---+---+---+---+---+---+---+---+

| | | | |

+ + + + + + + + +---+ + +

| | | | |

 

=={{header|Java}}==

{{works with|Java|1.5+}}

 

import java.util.Collections;

}

 

{{out}}

<pre>+---+---+---+---+---+---+---+---+---+---+

=={{header|JavaScript}}==

{{trans|J}}

var n=x*y-1;

if (n<0) {alert("illegal maze dimensions");return;}

}

return text.join('');

Variable meanings in function <code>maze</code>:

# <code>x</code>,<code>y</code> — dimensions of maze

 

{{out|Example use}}

<script type="text/javascript">

/* ABOVE CODE GOES HERE */

document.getElementById('out').innerHTML= display(maze(8,11));

produced output:

<pre>+ +---+---+---+---+---+---+---+---+---+---+

 

For example, change replace the line <code>while (0<n) {</code> with:

And replace the closing brace for this while loop with:

setTimeout(step, 100);

}

}

To better see the progress, you might want a marker in place, showing the position being considered. To do that, replace the line which reads <code>if (0 == k%4) {</code> with

line[k]= '#'

Note however that this leaves the final '#' in place on maze completion, and that the function <code>maze</code> no longer returns a result which represents a generated maze.

 

Note also that this display suggests an optimization. You can replace the line reading <code>path.push(here= next);</code> with:

if (1 < neighbors.length)

And this does indeed save a negligible bit of processing, but the maze algorithm will still be forced to backtrack through a number of locations which have no unvisited neighbors.

===HTML Table===

Using HTML, CSS and table cells for maze.

<style type="text/css">

table { border-collapse: collapse }

<a href="javascript:make_maze()">Generate</a>

<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a>

 

 

 

 

 

 

 

 

 

 

 

 

<pre>

</pre>

 

 

'''Generating functions'''

neighbors(cell::Vector, bound::Vector, step::Int=2) =

filter(check(bound), map(dir -> cell + step * dir, [[0, 1], [-1, 0], [0, -1], [1, 0]]))

function walk(maze::Matrix, nxtcell::Vector, visited::Vector=[])

push!(visited, nxtcell)

if neigh ∉ visited

maze[round.(Int, (nxtcell + neigh) / 2)...] = 0

firstcell = 2 * [rand(1:w), rand(1:h)]

return walk(maze, firstcell)

 

'''Printing functions'''

function printmaze(maze)

walls = split("╹ ╸ ┛ ╺ ┗ ━ ┻ ╻ ┃ ┓ ┫ ┏ ┣ ┳ ╋")

 

printmaze(maze(10, 10))

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

class MazeGenerator(val x: Int, val y: Int) {

display()

}

 

=={{header|Lua}}==

{{Works with|Lua|5.1}}

math.randomseed( os.time() )

 

 

print(make_maze())

{{Out}}

<pre>#################################

# # # # # #

#################################</pre>

 

=={{header|M2000 Interpreter}}==

INT((currentx% + oldx%) / 2) return a double, because has 2 as double so we get (integer+integer)/double or integer/double or double. Int(0.5) return.

 

Module Maze {

width% = 40

}

Maze

 

===Depth-first search===

 

 

Module Maze2 {

\\ depth-first search

status--

forchoose=forchoose#val(random(0,status))

OpenDoor(!Entry, !forchoose)

Rem : ShowMaze()

}

Maze2

 

Block[{$RecursionLimit = Infinity,

unvisited = Tuples[Range /@ {m, n}], maze},

RandomSample@{# + {0, 1}, # - {0, 1}, # + {1, 0}, # - {1,

0}}}]} &@RandomChoice@unvisited; maze];

{{Out}}

[[File:MathematicaMazeGraphics.png]]

{{Works with|Mathematica|9.0}}

Here I generate a maze as a graph. Vertices of the graph are cells and edges of the graph are removed walls. This version is mush faster and is convenient to solve.

Block[{$RecursionLimit = Infinity, grid = GridGraph[{m, n}],

unvisitedQ}, unvisitedQ[_] := True;

RandomChoice@VertexList@grid][[2, 1]],

GraphLayout -> {"GridEmbedding", "Dimension" -> {m, n}}]];

{{Out}}

[[File:MathematicaMazeGraph.png]]

 

=={{header|MATLAB}} / {{header|Octave}}==

showProgress = false;

 

 

image(M-VISITED);

 

=={{header|Nim}}==

{{trans|D}}

randomize()

 

iterator randomCover[T](xs: openarray[T]): T =

var js = toSeq 0..xs.high

for i in countdown(js.high, 0):

swap(js[i], js[j])

for j in js:

ver = newSeqWith(h, newSeqWith(w, "| ") & "|")

 

vis[y][x] = true

for p in [[x-1,y], [x,y+1], [x+1,y], [x,y-1]].randomCover:

if p[0] == x: hor[max(y, p[1])][x] = "+ "

if p[1] == y: ver[y][max(x, p[0])] = " "

walk p[0], p[1]

 

for a,b in zip(hor, ver & @[""]).items:

Example output:

<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

| | | | | |

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>

 

=={{header|OCaml}}==

let mark t = Hashtbl.add seen t true

let marked t = Hashtbl.mem seen t

Random.self_init();

visit (Random.int nx, Random.int ny);

Output from 'ocaml gen_maze.ml 10 10':<pre>+---+---+---+---+---+---+---+---+---+---+

| | | |

 

=={{header|Ol}}==

; maze generation

(import (otus random!))

(loop nx ny)))

(try))))))

; maze printing:

(display "+")

maze)

(print)

{{out|Sample 30 x 8 output}}

<pre>+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

 

=={{header|Perl}}==

 

my ($w, $h) = @ARGV;

print @{$hor[$_]}, "+\n";

print @{$ver[$_]}, "|\n" if $_ < $h;

Run as <code>maze.pl [width] [height]</code> or use default dimensions.

{{out|Sample 4 x 1 output}}

| |

+--+--+--+--+</pre>