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 个主要课程:GraphNodeConnection

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 回答