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 |
||
-- use random direction |
|||
loop |
|||
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; |
end Mazes; |
||
</lang> |
|||
Example main.adb: |
Example main.adb: |
||
<lang Ada>with Mazes; |
<lang Ada>with Mazes; |