c# - 如何计算 X 内的所有节点？

Question

我正在尝试实现寻路算法，但我认为我遇到了术语问题，因为我不太确定如何解释我需要该算法做什么。

我有一个规则的节点网格，我试图找到某个“曼哈顿距离”内的所有节点。

在此处输入图像描述

找到例如 5 内的节点非常简单。

在此处输入图像描述

但我对“加权曼哈顿距离”感兴趣，其中某些方格“花费”两倍（或更多）进入。例如，如果橙色方块花费 2，紫色方块花费 10，我感兴趣的图表如下所示：

在此处输入图像描述

首先，这个有术语吗？当您一开始并不完全确定事物的名称时，很难查找有关事物的信息。

其次，我如何计算哪些节点属于我的参数？我不是在寻找一个完整的解决方案，只是一些开始的提示；当我意识到我的实现需要三个Dictionarys 时，我开始认为可能有一种更简单的处理方式。

score 2 · Accepted Answer

对于术语，您基本上是在任意（正）加权图上要求一定距离内的所有点。使用不同的权重意味着它不再对应于特定的度量标准，例如曼哈顿距离。

至于算法，Dijkstra 的算法可能就是你想要的。基本思想是保持迄今为止您发现的每个方格的最低成本，以及接下来要探索的最佳方格的优先级队列。

与传统的 Dijkstra 不同，在找到每个方格的最小路径之前，您会一直前进，如果与节点的距离太长，您将希望停止将节点添加到队列中。完成后，您将获得所有从起始正方形的最短路径最多为的正方形的列表x，这听起来像是您想要的。

score 1 · Accepted Answer

您可能最好使用带加权图的 Dijkstra 算法，如下所述： http ://www.csl.mtu.edu/cs2321/www/newLectures/29_Weighted_Graphs_and_Dijkstra's_Algorithm.html （在中间有算法描述页。）

在您的情况下，曼哈顿距离可能只是意味着您不想要图中的对角线路径。

score 1 · Accepted Answer

Eric Lippert 提供了一个关于在 C# 中编写 A-* 路径查找算法的优秀博客系列：

3 回答 3