随机世界的数据结构

所以，我在考虑制作一个简单的随机世界生成器。这个发生器会创建一个起始“单元”，它有一到四个随机出口（在基本方向上，像迷宫）。在决定完成这些退出之后，我会在每个出口处生成一个新的随机“单元格”，并在玩家接近世界尚未生成的部分时重复。这个概念将允许一个“无限”的世界各种随机生成的世界。然而，我不确定如何在内部最好地表达这一点。随机世界的数据结构

我使用C++（这并不重要，我可以实现任何必要的数据结构）。起初，我想过使用一种有向图，其中每个节点都将边定向到周围的每个单元，但如果用户在世界中找到一个点，回溯到这个点，那么这可能不会奏效从另一个方向点。世界可能会做一些奇怪的事情，比如在一个地方生成两个单元格。

对于这种情况，哪种数据结构可能最有效？还是我在随机的世代中做一些真正愚蠢的事情？

任何帮助将不胜感激。谢谢， Chris

来源

2010-10-22 Chris Covert

A map< pair<int,int>, cell>可能会工作得很好;该对将代表x，y坐标。如果在这些坐标的地图中没有单元格，请创建一个新的单元格。如果你想使它真正无限，你可以用你必须提供的任意长度的整数类来替换整数（例如bigint）

来源

2010-10-22 16:59:25 user470379

我不能相信我没有想到这一点，它的这样一个简单的解决方案和快速。 – 2010-10-22 17:02:52

正如@Nathon提到的一个新单元格一样，一定要检查相邻单元格是否存在，并根据需要创建/防止进入这些相邻单元格的门。 – jholl 2010-10-22 17:09:51

难道你没有存储的散列（或STL集）吗？包含占用单元格的所有网格坐标的集合？

然后，当您在创建一个新的单元格时，可以快速检查候选单元格位置是否已被占用。（如果你有有限的空间，你可以使用一个二维数组 - 我想我在一篇Byte杂志的文章中看到了〜1980年 - 但是如果我理解正确，你想要一个可以无限延伸的世界）

来源

2010-10-22 17:00:19 winwaed

如果世界的细胞排列成一个网格，你可以很容易地给他们笛卡尔坐标。如果您保留现有单元格的大列表，那么在确定从给定单元格退出之前，可以检查该列表以查看它的任何邻居是否已经存在。如果他们这样做，并且你不想拥有单向门（有向图？），那么你就必须考虑他们的退出。如果您不介意在游戏中安装滑槽，您仍然可以随意选择退出，只要确保已连接到现有单元即可。

优化说明：检查散列表以查看它是否包含特定键是O（1）。

来源

2010-10-22 17:00:30 nmichaels

唯一的问题是，一旦世界变大，查找时间会开始变糟，对吗？ – 2010-10-22 17:03:16

如果他使用散列表，则不需要。 – nmichaels 2010-10-22 17:05:27

关于单向门的好处以及对有向图的需求。 – 2010-10-22 17:51:29

我建议你阅读关于图。这正是随机图生成的应用。不是'cell'和'exit'，而是描述'node'和'edge'。

再加上，你可以做最短路径分析，循环检测和各种其他有用的图论应用。

This将帮助您了解有关节点和边：

和here是这些概念完成的应用程序。我以OOP的方式实现了这一点 - 每个节点都知道它是其他节点的边缘。一个流行的选择是使用adjacency list来实现这一点。我认为邻接表概念基本上是user470379用他的答案描述的。但是，他的地图解决方案允许使用无限图，而传统的邻接列表则没有。我喜欢图论，这是它的完美应用。

祝你好运！

布赖恩J. Stianr-

来源

2010-10-22 17:11:28

我真的很想使用图表，也许我会的，我不得不四处看看。我只是觉得HashMap可能更有效率。 – 2010-10-22 17:18:20

这只取决于你想要做什么，以及你想如何解决问题。如果你正在谈论一个人类玩家会与之互动的东西，我认为把这个想法看作一个图形的清晰度将超过你通过使用HashMap获得的任何效率收益。你真的关心你的程序是否需要一秒来生成一个容易推理的随机图，而生成一个难以调试或应用任何现有算法的HashMap的1/10秒？ – 2010-10-22 17:23:09

随机世界的数据结构

回答

相关问题