我的程序是:
var maze = MazeFactory.FromPattern(Patterns.Maze3, Patterns.WallSymbol);
var a = maze.GetElementAt(0, 1);
var b = maze.GetElementAt(12, 0);
var printer = new PathPrinter(ConsoleColor.Yellow, ConsoleColor.Gray, ConsoleColor.Black);
Console.WriteLine("Maze");
printer.Print(maze, Path.Empty, Console.CursorLeft, Console.CursorTop);
var ab = new PathFinder(maze, a, b).GetPaths();
var abPath = ab.OrderBy(p => p.Elements.Count()).First();
Console.WriteLine("A -> B");
printer.Print(maze, abPath, Console.CursorLeft, Console.CursorTop);
var ba = new PathFinder(maze, b, a).GetPaths();
var baPath = ba.OrderBy(p => p.Elements.Count()).First();
Console.WriteLine("B -> A");
printer.Print(maze, baPath, Console.CursorLeft, Console.CursorTop);
输出为:
我希望PathFinder.GetPaths()
返回一个Path
s的集合,以便我可以选择最短的一个,但是该集合仅包含一个元素。
欢迎回答任何问题。
注意:我不是在寻找一种新的解决方案,只是为了解决这个问题。
详细资料:
我有一堂课MazeElement
:
class MazeElement
{
public bool IsPass { get; }
public int X { get; }
public int Y { get; }
public MazeElement(int x, int y, bool isPass) => (X, Y, IsPass) = (x, y, isPass);
}
MazeElement
实例可以形成Maze
:
class Maze
{
public IReadOnlyList<IReadOnlyList<MazeElement>> Elements { get; }
public int MaxY { get; }
public int MaxX { get; }
public Maze(MazeElement[][] elements) =>
(Elements, MaxY, MaxX) =
(elements, elements.Length - 1, elements[0].Length - 1);
public MazeElement GetElementAt(int x, int y) =>
0 <= x && x <= MaxX && 0 <= y && y <= MaxY ?
Elements[y][x] :
null;
}
和一个Path
:
class Path
{
public IEnumerable<MazeElement> Elements { get; }
public bool ReachedDestination { get; }
public static Path Empty => new Path(new MazeElement[0], false);
private Path(IEnumerable<MazeElement> elements, bool reachedDestination) => (Elements, ReachedDestination) = (elements, reachedDestination);
public Path Continued(MazeElement next, bool reachedDestination) => new Path(new List<MazeElement>(Elements) { next }, reachedDestination);
public static Path FromStart(MazeElement start) => new Path(new[] { start }, false);
}
我有一个MazeFactory
可以Maze
从一组string
s创建一个:
static class MazeFactory
{
public static Maze FromPattern(IEnumerable<string> pattern, char wallSymbol) =>
new Maze(pattern.Select((line, y) => line.Select((c, x) => new MazeElement(x, y, c != wallSymbol)).ToArray()).ToArray());
}
和一些这样的集合:
static class Patterns
{
public static readonly char WallSymbol = '#';
public static readonly IReadOnlyList<string> Maze1 = new[]
{
"#########################",
" ###",
"##################### # #",
"# # #",
"# ##################### #",
"# # #",
"# ##################### #",
"# #",
"####################### #"
};
public static readonly IReadOnlyList<string> Maze2 = new[]
{
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" "
};
public static readonly IReadOnlyList<string> Maze3 = new[]
{
"############ ############",
" ###",
"######## ############ # #",
"# # #",
"# ########## ######## # #",
"# # #",
"# ###### ############ # #",
"# #",
"####################### #"
};
}
为了显示结果,我有一个PathPrinter
:
class PathPrinter
{
private static readonly string mazeSymbol = "█";
private static readonly string pathSymbol = "*";
private readonly ConsoleColor wallColor;
private readonly ConsoleColor passColor;
private readonly ConsoleColor pathColor;
public PathPrinter(ConsoleColor wallColor, ConsoleColor passColor, ConsoleColor pathColor) =>
(this.wallColor, this.passColor, this.pathColor) = (wallColor, passColor, pathColor);
public void Print(Maze maze, Path path, int x = -1, int y = -1)
{
x = x == -1 ? Console.CursorLeft : x;
y = y == -1 ? Console.CursorTop : y;
foreach (var line in maze.Elements)
foreach (var e in line)
{
Console.SetCursorPosition(e.X + x, e.Y + y);
Console.ForegroundColor = e.IsPass ? passColor : wallColor;
Console.Write(mazeSymbol);
}
Console.ForegroundColor = pathColor;
foreach (var e in path.Elements)
{
Console.SetCursorPosition(e.X + x, e.Y + y);
Console.BackgroundColor = e.IsPass ? passColor : wallColor;
Console.Write(pathSymbol);
}
Console.SetCursorPosition(0, maze.MaxY + y + 1);
Console.ResetColor();
}
}
最后,我要在PathFinder
中找到路径Maze
:
class PathFinder
{
private readonly Maze maze;
private readonly MazeElement start;
private readonly MazeElement end;
private readonly Dictionary<MazeElement, bool> elementIsChecked;
public PathFinder(Maze maze, MazeElement start, MazeElement end) =>
(this.maze, this.start, this.end, elementIsChecked) =
(maze, start, end, maze.Elements.SelectMany(i => i).ToDictionary(i => i, i => false));
public Path[] GetPaths() => FindPath(Path.FromStart(start)).ToArray();
private IEnumerable<Path> FindPath(Path path) =>
GetContinuations(path).Where(next => next != null)
.SelectMany(next => next.ReachedDestination ? new[] { next } : FindPath(next));
private IEnumerable<Path> GetContinuations(Path path)
{
var e = path.Elements.LastOrDefault();
if (e == null)
return new Path[] { null };
return new[]
{
maze.GetElementAt(e.X, e.Y - 1),
maze.GetElementAt(e.X, e.Y + 1),
maze.GetElementAt(e.X - 1, e.Y),
maze.GetElementAt(e.X + 1, e.Y)
}
.Where(i => i != null)
.Select(i => GetContinuedPath(path, i));
}
private Path GetContinuedPath(Path path, MazeElement e)
{
if (e == null || elementIsChecked[e])
return null;
elementIsChecked[e] = true;
if (e.IsPass)
return path.Continued(e, e == end);
return null;
}
}
您正在函数FindPath中使用“深度优先”搜索,还将您遇到的所有点都标记为elementIsChecked,这是您第一次遇到它们时。标记后,您将不再关注这些点。
但是,由于您使用的是“深度优先”搜索,因此在完成长路径时,最终可能会遇到一个问题。然后,将其标记为elementIsChecked之后,其他路径将不再使用该点。长路径最终会阻塞随后的短路径。
之所以从A-> B开始走很长的路,是因为您在PathFinder.GetContinuations函数中将这些方向放在了优先位置:上,下,左,右。在(8,1),它选择向下,因为right的优先级较低。(使用条件断点可以节省很多麻烦)
因此,您实际上无法再次访问的唯一点就是路径上已经存在的点。一个简单的解决方法是摆脱PathFinder.elementIsChecked并在PathFinder.GetContinuedPath中替换:
if (e == null || elementIsChecked[e])
与
if (e == null || path.Elements.Contains(e))
然后,每条路径一直持续到阻塞自身为止。它效率不高,但是我想这很容易解决。
您可能应该使用“广度优先搜索”,并以相同的速率向所有可能的方向扩展,例如池塘中的涟漪,并在到达目的地后停止扩展
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句