Maze generation: Difference between revisions

Content added Content deleted
(→‎{{header|Ada}}: Simplified way of detecting unvisited neighbours.)
(→‎{{header|Ada}}: Neighbouring cells are tested only once.)
Line 51: Line 51:
<lang Ada>with Ada.Numerics.Discrete_Random;
<lang Ada>with Ada.Numerics.Discrete_Random;
with Ada.Text_IO;
with Ada.Text_IO;

package body Mazes is
package body Mazes is
package RNG is new Ada.Numerics.Discrete_Random (Positive);
package RNG is new Ada.Numerics.Discrete_Random (Positive);
package Random_Direction is new Ada.Numerics.Discrete_Random (Directions);
package Random_Direction is new Ada.Numerics.Discrete_Random (Directions);

Generator : RNG.Generator;
Generator : RNG.Generator;
Dir_Generator : Random_Direction.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);

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

function "-" (Dir : Directions) return Directions is
function "-" (Dir : Directions) return Directions is
begin
begin
Line 85: Line 72:
end case;
end case;
end "-";
end "-";

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 Depth_First_Algorithm
procedure Depth_First_Algorithm
(Maze : in out Maze_Grid;
(Maze : in out Maze_Grid;
Line 100: Line 119:
-- mark as visited
-- mark as visited
Maze (Row, Column).Visited := True;
Maze (Row, Column).Visited := True;
-- continue as long as there are unvisited neighbours left
loop
loop
All_Tested := True;
-- use random direction
for D in Directions loop
loop
All_Tested := All_Tested and Tested_Wall (D);
Next_Direction := Random_Direction.Random (Dir_Generator);
exit when not Tested_Wall (Next_Direction);
end loop;
end loop;
-- all directions are either visited from here,
-- or previously visited, or invalid.
exit when All_Tested;
-- use random direction
Next_Direction := Random_Direction.Random (Dir_Generator);
Next_Row := Row;
Next_Row := Row;
Next_Column := Column;
Next_Column := Column;
Move (Next_Row, Next_Column, Next_Direction, Valid_Direction);
Move (Next_Row, Next_Column, Next_Direction, Valid_Direction);
if Valid_Direction then
if Valid_Direction then
-- connect the two cells
if not Maze (Next_Row, Next_Column).Visited then
if not Maze (Next_Row, Next_Column).Visited then
-- connect the two cells
Maze (Row, Column).Walls (Next_Direction) :=
Maze (Row, Column).Walls (Next_Direction) :=
False;
False;
Line 125: Line 139:
end if;
end if;
Tested_Wall (Next_Direction) := True;
Tested_Wall (Next_Direction) := True;
-- continue as long as there are unvisited neighbours left
All_Tested := True;
for D in Directions loop
All_Tested := All_Tested and Tested_Wall (D);
end loop;
-- all directions are either visited (from here,
-- or previously visited), or invalid.
exit when All_Tested;
end loop;
end loop;
end Depth_First_Algorithm;
end Depth_First_Algorithm;

procedure Initialize (Maze : in out Maze_Grid) is
procedure Initialize (Maze : in out Maze_Grid) is
Row, Column : Positive;
Row, Column : Positive;
Line 144: Line 166:
Depth_First_Algorithm (Maze, Row, Column);
Depth_First_Algorithm (Maze, Row, Column);
end Initialize;
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
procedure Put (Item : Maze_Grid) is
begin
begin
for Row in Item'Range (1) loop
for Row in Item'Range (1) loop
if Row = Item'First (1) then
if Row = Item'First (1) then
Ada.Text_IO.Put ('+');
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 (North) then
if Item (Row, Col).Walls (North) then
Ada.Text_IO.Put ("---");
Ada.Text_IO.Put ("---+");
else
else
Ada.Text_IO.Put (" ");
Ada.Text_IO.Put (" +");
end if;
end if;
Ada.Text_IO.Put ('+');
end loop;
end loop;
Ada.Text_IO.New_Line;
Ada.Text_IO.New_Line;
Line 216: Line 203:
else
else
Ada.Text_IO.Put ("???");
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 if;
end loop;
end loop;
if Item (Row, Item'Last (2)).Walls (East) then
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("|");
else
Ada.Text_IO.Put_Line (" ");
end if;
Ada.Text_IO.Put ('+');
for Col in Item'Range (2) loop
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
if Item (Row, Col).Walls (South) then
Ada.Text_IO.Put ("---");
Ada.Text_IO.Put ("---+");
else
else
Ada.Text_IO.Put (" ");
Ada.Text_IO.Put (" +");
end if;
end if;
Ada.Text_IO.Put ('+');
--end loop;
end loop;
end loop;
Ada.Text_IO.New_Line;
Ada.Text_IO.New_Line;
end loop;
end loop;
end Put;
end Put;
end Mazes;</lang>
end Mazes;
</lang>
Example main.adb:
Example main.adb:
<lang Ada>with Mazes;
<lang Ada>with Mazes;
Retrieved from "https://rosettacode.org/wiki/Maze_generation"