Maze solving: Difference between revisions
Content deleted Content added
→{{header|Uiua}}: Made the code standalone. |
|||
(10 intermediate revisions by 4 users not shown) | |||
Line 676:
=={{header|C}}==
See [[Maze_generation#C|Maze generation]] for combined gen/solve code.
=={{header|C#}}==
{{trans|Go}}
<syntaxhighlight lang="C#">
using System;
using System.Text;
public class Maze
{
private char[,] cells;
private char[,] hWalls; // Horizontal walls
private char[,] vWalls; // Vertical walls
private Random rand = new Random();
public Maze(int rows, int cols)
{
cells = new char[rows, cols];
hWalls = new char[rows + 1, cols]; // Include walls for the bottom
vWalls = new char[rows, cols + 1]; // Include walls for the right side
// Initialize walls
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
hWalls[i, j] = '-';
vWalls[i, j] = '|';
}
}
// Set the outer walls for the bottom and right
for (int i = 0; i < cols; i++)
{
hWalls[rows, i] = '-';
}
for (int i = 0; i < rows; i++)
{
vWalls[i, cols] = '|';
}
}
public override string ToString()
{
var builder = new StringBuilder();
for (int i = 0; i < cells.GetLength(0); i++)
{
// Top walls
for (int j = 0; j < cells.GetLength(1); j++)
{
builder.Append("+");
builder.Append(hWalls[i, j] == '-' ? "---" : " ");
}
builder.AppendLine("+");
// Side walls and cells
for (int j = 0; j < cells.GetLength(1); j++)
{
builder.Append(vWalls[i, j] == '|' ? "| " : " ");
char cell = cells[i, j] == '\0' ? ' ' : cells[i, j];
builder.Append(cell + " ");
}
builder.AppendLine("|");
}
// Bottom walls
for (int j = 0; j < cells.GetLength(1); j++)
{
builder.Append("+---");
}
builder.AppendLine("+");
return builder.ToString();
}
public void Generate()
{
Generate(rand.Next(cells.GetLength(0)), rand.Next(cells.GetLength(1)));
}
private void Generate(int r, int c)
{
cells[r, c] = ' ';
int[] dirs = { 0, 1, 2, 3 };
Shuffle(dirs);
foreach (int dir in dirs)
{
switch (dir)
{
case 0: // Up
if (r > 0 && cells[r - 1, c] == '\0')
{
hWalls[r, c] = ' ';
Generate(r - 1, c);
}
break;
case 1: // Down
if (r < cells.GetLength(0) - 1 && cells[r + 1, c] == '\0')
{
hWalls[r + 1, c] = ' ';
Generate(r + 1, c);
}
break;
case 2: // Right
if (c < cells.GetLength(1) - 1 && cells[r, c + 1] == '\0')
{
vWalls[r, c + 1] = ' ';
Generate(r, c + 1);
}
break;
case 3: // Left
if (c > 0 && cells[r, c - 1] == '\0')
{
vWalls[r, c] = ' ';
Generate(r, c - 1);
}
break;
}
}
}
private void Shuffle(int[] array)
{
for (int i = array.Length - 1; i > 0; i--)
{
int j = rand.Next(i + 1);
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
public void Solve(int startRow, int startCol, int endRow, int endCol)
{
if (Solve(startRow, startCol, endRow, endCol, -1))
{
cells[startRow, startCol] = 'S';
cells[endRow, endCol] = 'F';
}
}
private bool Solve(int r, int c, int endRow, int endCol, int dir)
{
if (r == endRow && c == endCol) return true;
// Up
if (dir != 1 && r > 0 && hWalls[r, c] == ' ' && Solve(r - 1, c, endRow, endCol, 0))
{
cells[r, c] = '^';
return true;
}
// Down
if (dir != 0 && r < cells.GetLength(0) - 1 && hWalls[r + 1, c] == ' ' && Solve(r + 1, c, endRow, endCol, 1))
{
cells[r, c] = 'v';
return true;
}
// Right
if (dir != 3 && c < cells.GetLength(1) - 1 && vWalls[r, c + 1] == ' ' && Solve(r, c + 1, endRow, endCol, 2))
{
cells[r, c] = '>';
return true;
}
// Left
if (dir != 2 && c > 0 && vWalls[r, c] == ' ' && Solve(r, c - 1, endRow, endCol, 3))
{
cells[r, c] = '<';
return true;
}
return false;
}
}
class Program
{
static void Main(string[] args)
{
var maze = new Maze(4, 7);
maze.Generate();
Random rand = new Random();
maze.Solve(rand.Next(4), rand.Next(7), rand.Next(4), rand.Next(7));
Console.WriteLine(maze);
}
}
</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+
| | | v S |
+ +---+ +---+ + +---+
| | | | > v |
+---+---+ + +---+---+ +
| | | | F |
+ +---+---+ + + + +
| | |
+---+---+---+---+---+---+---+
</pre>
=={{header|C++}}==
Line 1,434 ⟶ 1,636:
=={{header|EasyLang}}==
[https://easylang.dev/show/#cod=hZTbbqMwFEXf/RVb6ksuwjUpSIk0zI8gNKJgGitgRyZNm379yBeM3RnNvCT4XIy9zt7M4oujQl4SiQoH7DCbyB45GUycMTxjI5GB0XJLRi4x1Q0kdpDkCeS17S5vWr3LHowxctWqw3xWH7+m9ouDghIA3chbbR4GpSHMtrgp+L1MHIAYMNWiQQXmIwA+UWEjkCHfYlI95Jp6RKle3ONUp0alcTqd1tCk7hyf2GFAhgHPOOARr9ZKzbsbBuyQ03L591l7F/szj5xfwSjLCSVqGObaHLxGDoksxyaTWzQOxuRIXNW80Jjqq5rDRQMss+jDPge8oEATQyvQqw95U8j9eXpU0K3shbxBLDGhUcEeqa/7ZqFrnlGhr0XC25xqb3oaO5RW9iFopLAkIo5pSzSq6J6hOeVGCZe9yVdOPmZ2nlF74Ylg/qETL5I8zCKplWnVISzNG/8WQgZp1P5nSvrU2mVfd/Y2WcDnpa8zPWmCrFjObvAOgCNHSbg2WUXwhAWJvliYnRoXKtYNJpb64ZGEgxecCzo1klT/e6v4wuvfr2yD0N3I7fqFloSSt1G9tiMG627qva3GOzezZbGkxeCrVrFofnvXMmAL9zkxljio9P1OGA6Q3+I/W6oh0n9h1eTlcF7kUCSu2Jyxhxosujzkrmo2nz4nXGccoSOXmN4fP92Vg0HkN/U7LBtTu1+GU5hHu/1aF4GKuiM+EsfjMckEUlGYfneWK8qJOwezgjyQ3w== Run it]
<syntaxhighlight
size =
n = 2 * size + 1
f = 100 / (n - 0.5)
len m[] n * n
#
background 000
proc show_maze . .
Line 1,452 ⟶ 1,651:
x = (i - 1) mod n
y = (i - 1) div n
color
move x * f - f / 2 y * f - f / 2
rect f * 1.5 f * 1.5
.
.
sleep 0.
.
offs[] = [ 1 n -1 (-n) ]
proc m_maze pos . .
m[pos] = 0
d[] = [ 1 2 3 4 ]
for i = 4 downto 1
d =
dir = offs[d[d]]
d[d] = d[i]
.
.
.
endpos = n * n - 1
proc make_maze . .
for i = 1 to len m[]
m[i] = 1
.
m[i] = 2
m[n * i] = 2
m[n * i - n + 1] = 2
m[n * n - n + i] = 2
.
h = 2 * randint 15 - n + n * 2 * randint 15
m_maze h
m[endpos] = 0
.
#
proc mark pos col . .
x = (pos - 1) mod n
Line 1,496 ⟶ 1,696:
color col
move x * f + f / 4 y * f + f / 4
circle f /
.
proc solve dir0 pos . .
if found = 1
return
.
mark pos 900
sleep 0.05
if pos = endpos
found = 1
.
of = randint 4 - 1
for h = 1 to 4
dir
posn = pos +
if dir <> dir0 and m[posn] =
solve (dir + 1) mod 4
if found =
mark posn 888
sleep 0.08
.
.
.
.
sleep
</syntaxhighlight>
Line 5,597 ⟶ 5,803:
| > > > ^ | | >
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Uiua}}==
Just add the following lines to the end of [https://rosettacode.org/wiki/Maze_generation#Uiua the generator]. It shows you the maze that has been solved with the path highlighted, the list of moves, and the total path length.
<syntaxhighlight lang="uiua">
# You can delete from here to SOLVE THE MAZE
# if you're appending this to the maze generator code.
# Experimental!
["+-+-+-+-+-+-+"
"|. . .|. . .|"
"+-+-+ + + + +"
"|.|. .|.|.|.|"
"+ + +-+-+ + +"
"|.|. . . .|.|"
"+ +-+-+-+-+ +"
"|. . . . . .|"
"+-+-+-+-+-+-+"]
H ← 4
W ← 6
Nfour ← +⊙¤[¯2_0 2_0 0_2 0_¯2] # Gives N4
InBounds ← ▽⊸≡(↧⊃(/↧≥1_1|/↧< +1 × 2 H_W))
GetWall ← -:⊡1:÷2/-.
# S O L V E T H E M A Z E #
.
Start ← 1_1
End ← -Start ×2 H_W
Heur ← /+⌵-End # Manhattan distance.
# (pos grid) -> 1-4 next steps, in bounds, without walls in the way.
Ns ← ≡⊡1▽:⟜(≡(=@ ⊡)⊙¤≡GetWall)≡⊟¤:InBounds Nfour.
astar(Ns|Heur|≍End) Start # Solve (costs = 1 => djikstra)
$"_ moves" ⊙⟜(⍜(⊡|+33)):°□⊢
</syntaxhighlight>
{{out}}
<pre>
╭─
╷ "+-+-+-+-+-+-+"
"|O O O|. O O|"
"+-+-+ + + + +"
"|.|O O|.|O|O|"
"+ + +-+-+ + +"
"|.|O O O O|O|"
"+ +-+-+-+-+ +"
"|. . . . . O|"
"+-+-+-+-+-+-+"
╯
╭─
╷ 1 1
1 3
1 5
3 5
3 3
5 3
5 5
5 7
5 9
3 9
1 9
1 11
3 11
5 11
7 11
╯
"14 moves"
</pre>
Line 5,602 ⟶ 5,873:
{{trans|Kotlin}}
{{libheader|Wren-ioutil}}
<syntaxhighlight lang="
import "./ioutil" for File, FileUtil
/*
|