如何在自顶向下的透视游戏中用低algorithm复杂度表示地图?

这是我第一次开发电子游戏,而且我迷失了方向。

我想知道在自上而下的透视游戏中表示2D地图的方法。

(像这样:vengadoravg.github.io/1/game.html btw,这是我开发的第一场比赛)

到目前为止,我已经find了一种在自顶向下的透视游戏中表示2D地图的方法:

使用matrix。 如果一个正常的地板位置是由某个数字(或字符)表示的,那么这个障碍就用一个不同的数字表示,而敌人则用另一个不同的数字表示。 这个matrix将允许我运行图论algorithm和疯狂的事情,但是我认为这将是algorithm上非常复杂的,因为这个图将是真正的人口稠密的。 因此,所有的精灵应该是相同的大小,否则,matrix将是真的,真的很大。

还有其他更好的方法吗?

在algorithm复杂性方面,哪个最适合运行图论algorithm呢?

我道歉,如果这个问题听起来是主观的…但我认为一种方法的优越性可以由其algorithm的复杂性决定:)

为了说明的目的,我将地图节点称为瓦片,但原理是相同的。 如果一个区域中有多个节点,那么“瓦片”将包含一个数组或节点列表。 对于所有这些,可以应用图论的应用程序,尽管应用程序的方法或多或less取决于您正在使用的特定algorithm。

现在,如果matrix表示一个二维数组,那么除了tile [x + y * width] = tile [x,y]的一维数组之外,这可能是algorithm最不复杂的方法。 这样的结构,你总是知道一个瓷砖到另一个瓷砖的距离,并可以随时访问其邻居,而不需要逐步遍历内存。

接下来是一个稀疏matrix ,其中的信息结构如下(作为伪结构):

Row : { PreviousRow, NextRow, ArrayOfTiles : { ColumnIndex, TileImage } } 

或者,作为一个关联数组 ,如.NET 字典中的键位编码XY位置,值是包含瓷砖信息的对象。

最后,您可以使用诸如Quadtrees之类的树来创建任意图块大小和/或密度。 如果你的地图是完全无序的,那么一个简单的图表,其中每个瓦片都有其邻居的引用就足够了。

大多数情况下,这取决于你的API提供了什么。 如果你期望有很多的空白空间,那么关联数组将是最直接的使用,因为它可以像一个常规的二维matrix,没有为未使用的元素分配空间,以及插入,删除和删除O(1)的复杂性。 否则,一个普通的二维数组很好。

一般来说, 总是select最不复杂的数据结构来满足您的需求 。