MMO中随机生成地下城的一点随想

qinglan

Blog: http://blog.csdn.net/lfhfut
MSN: beyondlimit2001@hotmail.com


　　找了下，网上关于这方面的资料大多是讲随机迷宫生成算法的，但是MMO中的地下城不仅仅是迷宫这么简单，不是只要生成一条或多条通路就算完成，还包括怪物的摆放，一些事件触发器类物件的摆放，地表景观类物件的摆放，还有地表Tile块的指定等。就生成的通路来说，也不可能只有一种简单的石头地形，或者全是沙地路，而在遇到拐弯或小坡小坎的地形时，地形块的指定会更加的复杂。

　　当然，这些问题都可以通过技术手段一个个来解决，但还有一个问题，如何保证随机生成出来的地图具有可玩性。这要求生成的道路即不能太直，也不能绕的太厉害，会有一些比较巧妙的区域来给玩家采用一些攻防的战略，怪物的颁布也比较合理。这些属于有些类似于艺术创作的东西，全部让计算机来处理还过于复杂。

　　这两天想到了一个方案，以类似于拼图的方式来组装出随机地图。并且可以再简单些，所有的拼图块都是固定大小的正方块，块中间的道路以及地表装饰物等是事先制作好的，这样在拼图时只需要按这些块定义出的接口来确定是否可拼接即可。

　　为了让问题再进一步简单，我们可以要求所有块的连接处的通路宽度必须相同，位置也必须固定在每条边的正中间，限制多了当然会让制作时的自由发挥度降低，但复杂度也会降低不少，这个可以适当做些取舍。

　　服务器在生成随机地图时需要知道两个块是否能拼接，我们可以对每个块及其连接属性做一些定义，这些定义至少要包括：

　　1。该块用到的TileSet编号，只有使用相同TileSet的块才能拼合到一幅地图中。

　　2。该块四条边的连通情况，要为每条边都定义是否可连通，通路的Tile块编号属性。

　　　　只能让两边都可连通或都不可连通的块拼命，否则一条路突然中断，那将会是很尴尬的场景。

　　　　另外，拼接块两边通路的Tile编号也必须相同，否则一条沙地路可能会连到另一条石板路上去。

　　在为地图摆放怪物及触发器类物件时也有一点点不同，指定位置必须采用相对于当前块的相对坐标，在服务器生成完随机地图后再根据每个块的偏移来修改这些坐标为绝对坐标。

　　在生成地图时也有一些细节需要处理，比如某幅地图中一定要出现某个或某几个块，用来放入口出口等。还有一些必须拼合在一起的块，用来实现单独一个块无法容纳下的超大自然景观或是城堡等。可能还需要限制一下某个块只能出现的位置，用来定义地下城的离的比较远的前门和后门等。

　　我们可以为每幅要生成的地图定义一个模板，其中就包含这些限制条件，还有其他策划们可能会想到的一些限制条件，要生成指定的随机地图时，从该模板开始，选择合适的块来进行拼接。

　　最后是随机地图的使用。因为地图是服务器临时生成的，客户端之前并没有该地图的数据，所以在传统的进入地图命令发送之前，需要多加一步处理：如果要进入的地图是随机生成的，则先将该地图数据发送给客户端，待客户端在内存中创建好该地图后，剩下的过程就与传统过程没有区别了。

　　至于服务器如何把生成的地图发给客户端。如果是完全随机生成的地图，要将整幅地图发送给客户端那将是一件很消耗带宽的事，而采用块来拼装的方式后，实际需要发送的数据只有块编号。每个块的定义数据都保存在客户端。

　　服务器也需要保留有每个块的格子阻挡信息，在生成完随机地图后，服务器和客户端都要按此块列表来生成完整的格子阻挡信息，用于寻路及客户端行走的合法性检测等。

　　以上只是这两天的一点随想，不知道暗黑中的随机地下城是如何生成的，google了下没有结果，有相关资料的麻烦共享一下，或者对此主题提供一些相关思路，不胜感激。

instemast

暗黑的不是随机的。是从几个预备的地图中挑选的

qinglan

原来如此，我还以为他是完全随机生成的，正考虑他是怎么做到呢，谢谢

另外还有个韩国游戏，洛奇，他的随机副本，也是暗黑这样，随机选择一个原来制作好的？

Dreamkiller

有个桌面游戏不断生成版图的思路就是这样

龙啸天

可以考?]下常?的拼?D?。

也?全部通用的地?D?K并不存在，但是可以考?]下?似?鼍爸心骋徊糠?D?K通用，然後??C。

曾?也考?]??方面的???，lz，有?趣可以交流下

p.s.这输入法怎么成繁体了。。。。。

JohnnyLZJU

也想过
以传送门做随机拓扑结构的方法可能好些
虽然体验上面差了一些，但是能够减少很多风险和实现难度

qinglan

To 龙啸天:

好像还没有见到已经实现出来的完全随机地图的MMO，可能大都也只是考虑过，不知道你们是因为什么原因没有实现出来？技术上有什么问题吗？


To JohnnyLZJU:

传送门？你的意思是做出很多的地图来，每次传送时随机送到一幅地图去？
如果是这样的话，地图得做的很小，通过传送门跳来跳去的，体验上确实不怎么好，而且也并不是随机地图

sjinny

暗黑的地图是否是完全随即的不知道，但是我感觉至少不是完全预制的。
理论上，这种东西应该是发给客户端一个seed，然后各个客户端使用伪随机数来生成地图。
简单的使用tile随机拼接可能很难作出合乎逻辑的地图，也就是说出来的可能是无厘头的地图…… = =
所以应该首先对地图的概念进行细分：
1.地理位置：它决定了各个子区域的地形地貌、天气和自然环境，自然也会影响到里面的怪物的设置。
2.风格：用这个词是因为一时找不到合适的词。比如同样是丘陵地带，可能是原始丛林里的文明遗迹，也可能是相对荒凉的土匪山寨，这些会决定里面的人造景观、道路等方面，同时在很大程度上影响怪物、特别是人形怪的设置。
3.游戏性：包括游戏难度、玩家团队规模等。
4.根据以上方面的随机选择结果，预先根据游戏性计算地图里要有哪几个游戏热点，比如埋伏、城堡、营地，计算有多少的NPC及相关任务，计算有哪些大型事件（比如山崩、地震之类）。根据这些计算应该把这些东西分布在多大的空间范围内，各个热点之间的空间关联程度。
5.根据策划设计的规则，为不同的游戏热点选择不同的具体地形地貌，比如城堡一般放在山上，营地一般在平地的水边，然后根据之前算出的各个热点的空间关联度来为不同的热点选择空间位置，并放置具体地形，之后在这些热点内部或周围放置与热点相关的NPC或怪物。
6.根据已经放置的热点和怪物，在各个热点之间生成随机的道路，对于热点之间的区域，根据这些区域周围的热点来放置相应的地表装饰和怪物比如对于两个互相敌对的城堡，它们之间可能会有路障和战场，而友好的热点之间可能有商人或信使。
7.放置玩家入口和出口。

所以关键的还是游戏内容的生成，只要游戏内容是合乎逻辑的，那么剩下的问题就是如何把游戏内容融合在一起，这就相当于游戏地图编辑器里自动在tile之间生成过渡地带一样。

只要所有的随机选择都使用伪随机数，那么只要各个客户端使用相同的随机数种子进行相同的计算，就能得到相同的地图。

qinglan

楼上的这方法就是生成完全随机地图了

我考虑的就是这样太过复杂，生成出来的地图也不容易在游戏性上达到要求，当然如果能实现这样的随机地图，那是最好的。

所以我上面考虑的是使用模板的方式，相当于就是要定义出你说的地理信息，风格，热点这些东西，服务器在随机生成时要首先满足模板中定义的这些限制条件，然后再摆放随机块生成其他一些景观和道路。

举个例子，有个10级的地下城，策划设计的是岩洞风格的，那可以定义一个模板，规定只能使用指定ID的一些地图块。这个地下城中必须有个包含入口的块，和一个BOSS所在的寨子块，并且要求玩家必须走完整个洞穴才能打BOSS，所以可以再限制这两个块之间的距离为多少，或者直接限制入口块必须在左下角，寨子块必须在右上角。

生成地图的时候先摆好了这两个块，然后从所有可用的块中随机选择块来生成通路及景观。这里也需要定义一些数据结构来描述这些块，还要一些算法来保证生成的通路仍然不会太复杂，并且至少存在一条从入口到寨子的通路。

生成完之后，将这些块的ID列表以一个固定顺序发给客户端，客户端就能生成同样的地图了。

楼上提到的用一个seed来让服务器和客户端自己生成出同样的地图，这倒可以解决服务器生成的地图发给客户端时数据量过大的问题，理论上来说也确实可以生成完全相同的地图，但实现上怕会有些问题，因为从上面列出来的看，变数也是挺多。

sjinny

你的意思是人工指定地理信息，风格，热点这些东西？

其实可以让策划大致上设计一下整个星球或大陆的整体气候，然后以此为基础使用一个随机位置来选择～