1

我将尝试编写游戏。我的游戏需要在传统游戏网格上运行A*寻路算法。

例如：（S=Start，G=Goal，X=Wall）

-------------------------------
|  |  |  |  |  |  |  |  | G|  |
-------------------------------
|  |  |  |  |  |  |  |  |  |  |
-------------------------------
|  | X| X| X| X|  |  |  |  |  |
-------------------------------
|  |  |  |  | X|  |  |  |  |  |
-------------------------------
| S|  |  |  |  |  |  |  |  |  |
-------------------------------

要实现 A*，我需要能够获取任何节点的“邻居”。（例如，Start 有 3 个邻居（Above、Diagonal 和 Right）。）

想到在数据层映射它的方法是二维数组或链表。

该阵列似乎是性能最高且易于实现的。所以如果S是[0][4]，那么它的邻居将是[0 + 1][4]（右），[0][4 - 1]（上），[0 + 1][4 - 1]（对角线）

但是在进行了几年的 .NET 应用程序开发之后，基本数组对我来说似乎有点过时了。

所以在我走这条路之前，我想我会问是否有一个很好的 .NET 集合类型可以用来绘制一个网格（在数据层，而不是 UI）。

4

2 回答 2

3

您不需要绘制整个网格。按需为给定节点生成邻居要容易得多。即节点（x，y）的邻居将是{x-1, x, x+1} x {y-1, y, y+1} - (x, y)。如果这些点中的任何一个位于网格尺寸之外，则不考虑它们。如果这些位置中的任何一个有墙，您也可以忽略它们。所以现在你只需要考虑如何有效地检查一个位置的墙壁。因为可以在这个特定问题中使用上述方法找到节点的邻居，所以我认为您在这里不需要邻接列表或邻接矩阵。

编辑：在检查某个位置的墙壁时，我曾经使用从坐标到整数的映射来做到这一点。即(x, y) => x + y*MaxWidth。您会为每个坐标获得一个唯一的整数。现在，您只需使用该整数将墙壁位置存储在哈希表或类似的东西中即可进行有效查找。如果网格的尺寸相当大，则此方法胜过二维数组表示。

于 2012-12-03T23:48:34.750 回答
3

在这种情况下，数组听起来是正确的选择。请记住，提供的大多数数据结构都试图提供不同的功能。

鉴于您需要的唯一抽象方法（邻居）是快速实现，因此没有理由使用任何更复杂的方法作为基础。

于 2012-12-03T23:49:30.657 回答