都是抽象的。因此,我将描述我如何在我的 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++ 中做同样的事情,那么我不会接受它。