Maze generation: Difference between revisions

{{trans|Python}}

V vis = [[0] * w [+] [1]] * h [+] [[1] * (w + 1)]

V ver = [[‘| ’] * w [+] [String(‘|’)]] * h [+] [[String]()]

R s

{{out}}

=={{header|Action!}}==

Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.

DEFINE RIGHT="1"

DEFINE BOTTOM="2"

DO UNTIL CH#$FF OD

CH=$FF

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Maze_generation.png Screenshot from Atari 8-bit computer]

{{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;

end Put;

end Mazes;

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>+---+---+---+---+---+---+---+---+---+---+

=={{header|APL}}==

This example shows how to use GNU APL scripting.

doMaze 9 9

)OFF

{{out}}

<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:

==={{header|QB64}}===

This implementation was written using QB64. It should also be compatible with Qbasic, as it uses no QB64-exclusive features.

RANDOMIZE TIMER

REM wait

{{out}}

==={{header|BASIC256}}===

size_x = 25

size_y = 15

print

next i

{{out}}

{{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:

=={{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>┌───┬─────┬─────────┬───────┬───┐

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Diagnostics;

}

}

Sample output:

<pre>

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

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

#include <windows.h>

#include <iostream>

}

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

=={{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|Delphi}}==

{$APPTYPE CONSOLE}

Main;

{{out}}

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

[https://easylang.online/apps/_r_maze0.html Run it]

n = 2 * size + 1

endpos = n * n - 2

.

call make_maze

=={{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/

{{libheader|cl-lib}}

(cl-defstruct maze rows cols data)

(print-maze maze solution)))

{{out}}

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

The solution uses the following library <tt>bits.fs</tt>, which implements bit-arrays:

<br>

: to-bits ( c -- f f f f f f f f )

else

drop

<br>

The solution uses three bit-arrays: one to track whether a cell has been visited, one for "East"-walls (walls to the right of a cell) and one for "South"-walls (walls to the bottom of a cell).

<br>

\ Maze Generation

: maze ( width height -- ) build-maze maze. ;

{{out}}<pre>

=={{header|FreeBASIC}}==

' compile with: fbc -s console

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

Loop

=={{header|Fōrmulæ}}==

=={{header|Go}}==

import (

m.gen()

fmt.Print(m)

{{out}}

<pre>

=={{header|Haskell}}==

{-# LANGUAGE TypeFamilies #-}

main :: IO ()

{{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>

=={{header|Julia}}==

'''Generating functions'''

check(bound::Vector) = cell -> all([1, 1] .≤ cell .≤ bound)

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

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

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

}

Maze2

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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()

walk rand(0..<w), rand(0..<h)

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

{{out}}

This difers of the basic Javascript in that in NodeJS we take advantage of the asynchronous behaviour. This code was modified from the plain Javascript section to make it '''Asynchronous''' and able to run under ''strict mode''.

'use strict';

/*

display: display

}

{{out|Example use}}

Here is a basic example of what your main file should contain:

'use strict';

}, (err) => console.error(err));

Sample Output:

=={{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}}

Adapted a couple of techniques from the excellent D submission<br>

(however this holds the grid as an array of complete lines)

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #000080;font-style:italic;">--

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

=={{header|PHP}}==

Code inspired by the D and Python solutions (with the implementation of backtracking, or sometimes it wouldn't work). Could have been done procedurally or fully OO (with cells as class too). A debug flag has been provided to allow following the inner workings. Works on PHP > 5.6.

class Maze

{

$maze = new Maze(10,10);

{{out}}

<pre>

=={{header|Picat}}==

gen_maze(8,8).

end,

println("+").

{{out}}

<pre>

=={{header|PicoLisp}}==

This solution uses 'grid' from "lib/simul.l" to generate the two-dimensional structure.

(de maze (DX DY)

(de display (Maze)

{{out}}

<pre>: (display (maze 11 8))

=={{header|PL/I}}==

{{trans|REXX}}

mgg: Proc Options(main);

/* REXX ***************************************************************

End;

Output:

<pre>

=={{header|Processing}}==

color background_color = color (80, 80, 220);

color runner = color (255, 50, 50);

if(wall[3]) line((j+1)*c_size, i*c_size, j*c_size, i*c_size);

}

'''It can be played on line''' :<BR> [https://www.openprocessing.org/sketch/880778/ here.]

==={{header|Processing Python mode}}===

g_size = 10

background_color = color(80, 80, 220)

if wall[2]: line((j + 1) * c_size, (i + 1) * c_size, (j + 1) * c_size, i * c_size)

if wall[3]: line((j + 1) * c_size, i * c_size, j * c_size, i * c_size)

=={{header|Prolog}}==

Works with SWI-Prolog and XPCE.

maze(Lig,Col) :-

\+cell(L, C1).

{{out}}

[[File:Prolog-Maze.jpg]]

=={{header|PureBasic}}==

;indexes for types of offsets from maze coordinates (x,y)

#visited ;used to index visited(x,y) in a given direction from current maze cell

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

The maze is represented by an array of cells where each cell indicates the walls present above (#dir_N) and to its left (#dir_W). Maze generation is done with a additional array marking the visited cells. Neither an entry nor an exit are created, these were not part of the task. A simple means of doing so is included but has been commented out.

=={{header|Python}}==

def make_maze(w = 16, h = 8):

if __name__ == '__main__':

{{out}}

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

Maze generator

#lang racket

; return the result

(maze N M tbl))

Printing out the maze

;; Shows a maze

(define (show-maze m)

(displayln "+"))

(newline))

Example:

{{works with|rakudo|2015-09-22}}

Supply a width and height and optionally the x,y grid coords for the starting cell. If no starting cell is supplied, a random one will be selected automatically. 0,0 is the top left corner.

:N< ╵ >,

:E< ╶ >,

}

{{out}}

<small><pre style="font-family: consolas, inconsolata, monospace; line-height: normal;">┌ ╵ ────────────────────────────┬───────────────────────────────────────────┬───────────┬───────────────────────────┐

=={{header|Rascal}}==

{{trans|Python}}

import util::Math;

import List;

println(("" | it + "<z>" | z <- b));

}

<pre>rascal>make_maze(10,10)

=={{header|Red}}==

size: as-pair to-integer ask "Maze width: " to-integer ask "Maze height: "

]

print ""

{{out}}

<pre>Maze width: 15

In order to preserve the aspect ratio (for most display terminals), several &nbsp; '''changestr''' &nbsp; invocations and

<br>some other instructions were added to increase the horizontal dimension (cell size).

parse arg rows cols seed . /*allow user to specify the maze size. */

if rows='' | rows==',' then rows= 19 /*No rows given? Then use the default.*/

otherwise nop

end /*select*/

Some older REXXes don't have a &nbsp; '''changestr''' &nbsp; BIF, so one is included here &nbsp; ──► &nbsp; [[CHANGESTR.REX]].

The above REXX version had a quite of bit of code to "dress up" the maze presentation, &nbsp; so a slimmed-down version

<br>was included here for easier reading and understanding of the program's logic.

parse arg rows cols seed . /*allow user to specify the maze size. */

if rows='' | rows=="," then rows= 19 /*No rows given? Then use the default.*/

if hood(rr,cc)==1 then do; r!= rr; c!= cc; @.r!.c!= 0; return 1; end

end /*c*/ /* [↑] r! and c! are used by invoker.*/

{{out|output|text=&nbsp; when using input: &nbsp; &nbsp; <tt> 10 &nbsp;10 </tt>}}

===version 3===

* 04.09.2013 Walter Pachl

**********************************************************************/

End

End

Output:

<pre>

=={{header|Ruby}}==

DIRECTIONS = [ [1, 0], [-1, 0], [0, 1], [0, -1] ]

# Demonstration:

maze = Maze.new 20, 10

{{out}}

=={{header|Rust}}==

Uses the [https://crates.io/crates/rand rand] library

const WIDTH: usize = 16;

maze.open_doors();

maze.paint();

{{out}}

=={{header|Scala}}==

object MazeTypes {

private def openInDirection(loc: Loc, dir: Direction): Boolean =

doors.contains(Door(loc, loc + dir)) || doors.contains(Door(loc + dir, loc))

{{out}}

<pre>

=={{header|Sidef}}==

{{trans|Perl}}

var avail = (w * h)

say (ver[i].join('') + '|')

}

{{out}}

<pre>

=={{header|SuperCollider}}==

// some useful functions

(

w.front.refresh;

)

=={{header|Swift}}==

{{works with|Swift|3}}

extension Array {

let y = 10

let maze = MazeGenerator(x, y)

{{out}}

<pre>

=={{header|Tcl}}==

{{trans|Javascript}}

# Helper to pick a random number

# Demonstration

maze create m 11 8

{{out}}

<pre>

Legend: cu = current location; vi = boolean hash of visited locations; pa = hash giving a list neighboring cells to which there is a path from a given cell.

@(do

(defvar *r* (make-random-state nil))

@;;

@(bind m @(make-maze width height))

{{out}}

At the user interface level, the straightness parameter is represented as a percentage. This percentage is converted to a number of cells based on the width and height of the maze. For instance if the straightness parameter is 15, and the maze size is 20x20, it means that 15% out of 400 cells, or 60 cells will be traversed before the queue is scrambled. Then another 60 will be traversed and the queue will be scrambled, and so forth.

(defvar pa) ;; path connectivity hash

(defvar sc) ;; count, derived from straightness fator

(set h (max 1 h))

(print-maze (make-maze w h s) w h))

{{out}}

=={{header|XPL0}}==

def Cols=20, Rows=6; \dimensions of maze (cells)

int Cell(Cols+1, Rows+1, 3); \cells (plus right and bottom borders)

Text(0, if Y#Rows & Cell(X, Y, LeftWall) then "| " else " ");

];

Output:

=={{header|Wren}}==

{{trans|Kotlin}}

import "os" for Process

var mg = MazeGenerator.new(x, y)

mg.generate(0, 0)

{{out}}

Generate a maze without marked entry or exit points.

{{trans|Python}}

fcn make_maze(w = 16, h = 8){

// make arrays with lists of lists (all mutable)

return(ver,hor);

}

{{out}}

<pre>