1

我正在玩 Dijkstra 的算法，并找到了许多有关它的站点和代码片段，并且认为我能够掌握它，但我没有找到有关如何构建图形本身的信息。也许我不知道谷歌搜索的正确术语，但我只是找不到任何关于如何构建 grpah 它自己绘制图形的信息。

我正在制作一个学习项目，一个小型 c++ 吃豆人游戏，并希望使用这个算法来控制跟随 pac-man 的幽灵。我有一张地图（位图），想在迷宫的每个路口放置一个“节点”。

我该怎么做呢？这是我无法理解的一点。如何构建图表本身？

是否有可视化图形编辑器？任何建议都会很棒。

4

3 回答 3

2

您可以将网格视为图形，并且可以使用图形显示搜索空间表示：

网格如何像图表的图片

块 A、B、C、D 是图的节点，节点之间的权重可以表示节点之间的路径距离。

于 2012-07-29T10:26:50.593 回答
1

图形可以通过编程方式定义，常见的表示形式如下所述。（注意：对于 djiksta 的算法，您还需要存储各种边的权重）。例如，该图的 A 连接到 B（权重 = 5），B 连接到 C（权重 = 1）。

1)邻接表：用于将边表示为列表，更常用于稀疏图。它将有 A->B(5) 和 B->C(1)。（可以promatically表示为链表数组，链表的每个节点都存储传出的顶点标识和权重）

2）邻接矩阵：它将有一个二维矩阵，定义为：

    A B C
A   0 5 0
B   0 0 1
C   0 0 0

编辑：您可以在此关于图形的 topcoder 教程系列中找到更多详细信息：第 1 节讨论图形表示，第 3 节讨论 dijksta 算法。

于 2012-07-29T09:45:34.637 回答
0

都是抽象的。因此，我将描述我如何在我的 android 游戏中制作图表。最终，您可以随心所欲地定义它，但这是我的实现。

一点背景知识，游戏是一个塔防，图表代表了敌人从源头到汇点时所走的路径。为我的模型编写 Dijkstra 算法并不需要太多时间。我有 3 个主要课程：Graph、Node和Connection。

是Graph主要对象。它包含一个节点列表和一个连接列表。此类具有addConnection(Node n1, Node n2, int magnitude)（这是我实际构建图形的方式）、、、getAllSinks()和getAllSources()（getNeighbors(Node n)返回与参数节点共享连接的所有节点）之类的方法。这可能是一种findShortestPath(Node start, Node stop)方法的用武之地。

由于它是一个游戏，因此 aNode在屏幕上具有其位置的 X 和 Y。一个节点也有一个NodeType，它是 Source、Sink 和 Normal（以及其他与游戏相关的用途，如塔）的枚举。Dijkstra 不需要 NodeType。

MyConnection是从一个节点到另一个节点的 1 对 1 链接，它是双向的。如果您区分两个节点端点，您可以使其具有方向性，我只是不需要在我的游戏中这样做。Connection 存储连接的权重。在我的例子中，我将我的图表加权为与源的距离，以便敌人总是可以尝试并采取“最重”的路径来尝试使其到达水槽，例如塔防路径的尽头。重量可以是距离或任何你想要的。此类具有getOtherEndpoint(Node n)、getBothEndpoints()和等方法getWeight()。

所有这些课程都是我自己构建的。他们不继承任何东西。您可以完全按照您想要的方式构建它们，并将您需要的任何信息与图表的任何部分联系起来。这只是我在 Java 中的实现。如果您愿意，或者如果您受到启发编写自己的代码，您可以在 C++ 中做同样的事情，那么我不会接受它。

于 2013-11-27T16:57:22.693 回答