随机世界的数据结构

Question

所以,我正在考虑制作一个简单的随机世界发生器.这个发生器将创建一个起始"细胞",它将具有一到四个随机出口(在基本方向,类似于迷宫).那些决定退出后,我会在每一位的出口的一个新的随机"细胞",并重复每当玩家将获得近尚未生成的世界的一部分.这个概念将允许一个"无限"的世界,所有这些都是随机生成的; 但是,我不确定如何在内部最好地代表这一点.

我正在使用C++(这并不重要,我可以实现任何必要的数据结构).起初我以为使用排序向图,其中每个节点会围绕着它向边各小区,但这个如果用户发现在世界上的斑点,回溯,回来到可能会无法正常工作从另一个方向发现.世界可能会做一些奇怪的事情,例如在一个位置生成两个单元格.

关于什么样的数据结构可能对这种情况最有效的任何想法？或者我是否在为随机的世界一代做一些非常愚蠢的事情？

任何帮助将不胜感激.谢谢,克里斯

Answer 1

我建议你阅读有关图表的内容.这正是随机图生成的应用.而不是'单元'和'退出',你描述'节'和'边'.

此外,您还可以执行最短路径分析,循环检测和各种其他有用的图论应用.

这有助于您了解节点和边缘:

而这里是这些概念完成的应用程序.我以OOP方式实现了这一点 - 每个节点都知道它与其他节点的边缘.一种流行的替代方案是使用邻接列表来实现它.我认为邻接列表概念基本上是user470379用他的答案描述的.但是,他的地图解决方案允许无限图,而传统的邻接列表则不允许.我喜欢图论,这是它的完美应用.

祝好运!

-Brian J. Stianr-

Answer 2

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