Maze generation: Difference between revisions

Content added Content deleted
(add Ada)
Line 10: Line 10:


See also [[Maze solving]].
See also [[Maze solving]].

=={{header|Ada}}==
{{works with|Ada 2010}}
{{works with|GNAT}}

mazes.ads:
<lang Ada>generic
Height : Positive;
Width : Positive;
package Mazes is

type Maze_Grid is private;

procedure Initialize (Maze : in out Maze_Grid);

procedure Put (Item : Maze_Grid);

private

type Directions is (North, South, West, East);

type Cell_Walls is array (Directions) of Boolean;
type Cells is record
Walls : Cell_Walls := (others => True);
Visited : Boolean := False;
end record;

subtype Height_Type is Positive range 1 .. Height;
subtype Width_Type is Positive range 1 .. Width;

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

end Mazes;</lang>

mazes.adb:
<lang Ada>with Ada.Numerics.Discrete_Random;
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;

procedure Depth_First_Algorithm
(Maze : in out Maze_Grid;
Row : Height_Type;
Column : Width_Type);

function Has_Unvisited_Neighbours
(Maze : Maze_Grid;
Row : Height_Type;
Column : Width_Type)
return Boolean;

procedure Move
(Row : in out Height_Type;
Column : in out Width_Type;
Direction : Directions;
Valid_Move : out Boolean);

function "-" (Dir : Directions) return Directions is
begin
case Dir is
when North =>
return South;
when South =>
return North;
when East =>
return West;
when West =>
return East;
end case;
end "-";

procedure Depth_First_Algorithm
(Maze : in out Maze_Grid;
Row : Height_Type;
Column : Width_Type)
is
Next_Row : Height_Type;
Next_Column : Width_Type;
Next_Direction : Directions;
Valid_Direction : Boolean;
begin
-- mark as visited
Maze (Row, Column).Visited := True;
-- continue as long as there are unvisited neighbours left
while Has_Unvisited_Neighbours (Maze, Row, Column) loop
-- use random direction
Next_Direction := Random_Direction.Random (Dir_Generator);
Next_Row := Row;
Next_Column := Column;
Move (Next_Row, Next_Column, Next_Direction, Valid_Direction);
if Valid_Direction then
-- connect the two cells
if not Maze (Next_Row, Next_Column).Visited then
Maze (Row, Column).Walls (Next_Direction) :=
False;
Maze (Next_Row, Next_Column).Walls (-Next_Direction) :=
False;
Depth_First_Algorithm (Maze, Next_Row, Next_Column);
end if;
end if;
end loop;
end Depth_First_Algorithm;

function Has_Unvisited_Neighbours
(Maze : Maze_Grid;
Row : Height_Type;
Column : Width_Type)
return Boolean
is
Neighbour_Row : Height_Type;
Neighbour_Column : Width_Type;
Is_Valid : Boolean;
begin
for Dir in Directions loop
Neighbour_Row := Row;
Neighbour_Column := Column;
Move
(Row => Neighbour_Row,
Column => Neighbour_Column,
Direction => Dir,
Valid_Move => Is_Valid);
if Is_Valid
and then not Maze (Neighbour_Row, Neighbour_Column).Visited
then
return True;
end if;
end loop;
return False;
end Has_Unvisited_Neighbours;

procedure Initialize (Maze : in out Maze_Grid) is
Row, Column : Positive;
begin
-- initialize random generators
RNG.Reset (Generator);
Random_Direction.Reset (Dir_Generator);
-- choose starting cell
Row := RNG.Random (Generator) mod Height + 1;
Column := RNG.Random (Generator) mod Width + 1;
Ada.Text_IO.Put_Line
("Starting generation at " &
Positive'Image (Row) &
" x" &
Positive'Image (Column));
Depth_First_Algorithm (Maze, Row, Column);
end Initialize;

procedure Move
(Row : in out Height_Type;
Column : in out Width_Type;
Direction : Directions;
Valid_Move : out Boolean)
is
begin
Valid_Move := False;
case Direction is
when North =>
if Row > Height_Type'First then
Valid_Move := True;
Row := Row - 1;
end if;
when East =>
if Column < Width_Type'Last then
Valid_Move := True;
Column := Column + 1;
end if;
when West =>
if Column > Width_Type'First then
Valid_Move := True;
Column := Column - 1;
end if;
when South =>
if Row < Height_Type'Last then
Valid_Move := True;
Row := Row + 1;
end if;
end case;
end Move;

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 Col = Item'First (2) then
Ada.Text_IO.Put ('+');
end if;
if Item (Row, Col).Walls (North) then
Ada.Text_IO.Put ("---");
else
Ada.Text_IO.Put (" ");
end if;
Ada.Text_IO.Put ('+');
end loop;
Ada.Text_IO.New_Line;
end if;
for Col in Item'Range (2) loop
if Col = Item'First (2) then
if Item (Row, Col).Walls (West) then
Ada.Text_IO.Put ('|');
else
Ada.Text_IO.Put (' ');
end if;
elsif Item (Row, Col).Walls (West)
and then Item (Row, Col - 1).Walls (East)
then
Ada.Text_IO.Put ('|');
elsif Item (Row, Col).Walls (West)
or else Item (Row, Col - 1).Walls (East)
then
Ada.Text_IO.Put ('>');
else
Ada.Text_IO.Put (' ');
end if;
if Item (Row, Col).Visited then
Ada.Text_IO.Put (" ");
else
Ada.Text_IO.Put ("???");
end if;
if Col = Item'Last (2) then
if Item (Row, Col).Walls (East) then
Ada.Text_IO.Put ('|');
else
Ada.Text_IO.Put (' ');
end if;
end if;
end loop;
Ada.Text_IO.New_Line;
for Col in Item'Range (2) loop
--for Col in Item'Range (2) loop
if Col = Item'First (2) then
Ada.Text_IO.Put ('+');
end if;
if Item (Row, Col).Walls (South) then
Ada.Text_IO.Put ("---");
else
Ada.Text_IO.Put (" ");
end if;
Ada.Text_IO.Put ('+');
--end loop;
end loop;
Ada.Text_IO.New_Line;
end loop;
end Put;
end Mazes;</lang>

Example main.adb:
<lang Ada>with Mazes;
procedure Main is
package Small_Mazes is new Mazes (Height => 8, Width => 11);
My_Maze : Small_Mazes.Maze_Grid;
begin
Small_Mazes.Initialize (My_Maze);
Small_Mazes.Put (My_Maze);
end Main;</lang>

Output:
<pre>Starting generation at 3 x 7
+---+---+---+---+---+---+---+---+---+---+---+
| | | | |
+ + + +---+ + + +---+---+---+ +
| | | | | | |
+ +---+---+ +---+---+ + + + +---+
| | | | | | | |
+ +---+---+---+---+ +---+ + + + +
| | | | | | |
+ + +---+ + + + +---+---+---+ +
| | | | | | |
+ + +---+---+---+---+---+ +---+ + +
| | | | | |
+---+ + +---+---+---+ +---+---+---+ +
| | | | |
+ +---+ +---+---+ +---+---+---+---+---+
| |
+---+---+---+---+---+---+---+---+---+---+---+</pre>


=={{header|D}}==
=={{header|D}}==
Retrieved from "https://rosettacode.org/wiki/Maze_generation"