C# 随机二维瓦片地图生成算法

Random 2D Tile-Map Generating Algorithm

提问by Ace

Can anyone tell me a way to generate island structures or hill structures like in minecraft?

谁能告诉我一种在我的世界中生成岛屿结构或山丘结构的方法吗？

I'm just searching for a proper THEORY for that random-shape generating, but it should keep a defined base pattern..

我只是在为随机形状生成寻找合适的理论，但它应该保持一个定义的基本模式..

like: islands schould be rounded but variate in shape and scale ( min/max width & height ).

像：岛屿应该是圆形的，但形状和比例（最小/最大宽度和高度）各不相同。

or: rivers schould not be straight lines, they should have curves and a random width.

或者：河流不应是直线，它们应该有曲线和随机宽度。

or even: generating some sort of forest, where trees are placed in a way that the user can still walk through the forest (that's a simple one I think, just say that some blocks around a tree should remain blank, if code tries to put more trees around the last one )

甚至：生成某种森林，其中树木以用户仍然可以穿过森林的方式放置（我认为这是一个简单的方法，只是说树周围的一些块应该保持空白，如果代码试图放置最后一棵树周围的树更多）

What kind of math can I use to do such things?

我可以用什么样的数学来做这样的事情？

I would be glad for some links for tutorials or references. I've searches all around the web for hours, but all I could find was some books to buy like "game mathematics" or something, but my budget is set to zero.

我很高兴提供一些教程或参考资料的链接。我在网上搜索了几个小时，但我只能找到一些书，比如“游戏数学”之类的东西，但我的预算设置为零。

EDIT:

编辑：

First of all, I'm sorry for my bad englisch.

首先，我很抱歉我的英语不好。

Secondary I want to thank all of you for your answers. These are great references and I'll spend much time to go deeper in that.

中学 我要感谢你们所有人的回答。这些都是很好的参考资料，我会花很多时间深入研究。

采纳答案by Ray Hayes

I strongly recommend looking at Amit's Game Programming Informationand other blog posts by him. He had a whole series on creating realistic looking maps with rivers, coastlines, etc.

我强烈建议您查看Amit 的游戏编程信息和他的其他博客文章。他有一整套关于用河流、海岸线等创建逼真的地图。

Building Worlds

Although procedural map generation can be applied to non-grid worlds, it's most often used with grids. Viewed at a single point in time, generated game maps are rarely as nice as hand-crafted worlds. However, they have three advantages: (1) lower cost per world if there are many worlds to be made, (2) more replay value because the next time through the world is different, and (3) potential for the world evolving while the game progresses.

• Amit's World Map Generator
• Procedural Content Generation: generating terrain, cities, buildings
• Dungeon generation in Unangband
• Generating game worlds with a lock-and-key structure so that certain rooms require objects from other rooms
• Algorithm for building rivers
• Adding rivers to randomly generated terrain
• The original Rogue algorithm for generating dungeons
• 11 Maze Generating Algorithms with demos and code
• Using noise functions to generate caverns such as those in Terraria and Minecraft
• Irregular shaped rooms, simple algorithm
• Resizable interior room regions
• Tunneler algorithm for digging dungeons in DungeonMaker
• Guide to random Terrain Generation techniques
• Wiki guide to procedural content generation
• Simulating Large Virtual Worlds

建造世界

尽管程序地图生成可以应用于非网格世界，但它最常用于网格。在单个时间点查看，生成的游戏地图很少像手工制作的世界一样好。但是，它们具有三个优势：(1) 如果要制作多个世界，则每个世界的成本较低；(2) 由于下一次世界不同，因此重玩价值更高，以及 (3) 世界在不断发展的同时发展的潜力游戏进展。

• Amit 的世界地图生成器
• 程序内容生成：生成地形、城市、建筑物
• Unangband的地牢生成
• 生成具有锁钥结构的游戏世界，以便某些房间需要其他房间的物品
• 构建河流的算法
• 将河流添加到随机生成的地形
• 生成地牢的原始Rogue算法
• 11 个带演示和代码的迷宫生成算法
• 使用噪声函数生成洞穴，例如 Terraria 和 Minecraft 中的洞穴
• 不规则形状的房间，简单的算法
• 可调整大小的室内区域
• 在 DungeonMaker 中挖掘地牢的 Tunneler 算法
• 随机地形生成技术指南
• 程序内容生成的 Wiki 指南
• 模拟大型虚拟世界

Amit's Polygonal Map Generation for Games(first item in list) is a hugely impressive article that talks about the logic of generating sensible shaped coastlines, islands, rivers, mountains, etc. Hugely impressive bit of work!

Amit 的游戏多边形地图生成（列表中的第一项）是一篇令人印象深刻的文章，它讨论了生成合理形状的海岸线、岛屿、河流、山脉等的逻辑。令人印象深刻的工作！

A Method For 'Growing' Rivers In A Randomly Generated World[included in above list] fairly simple algorithm for generating a river's path based upon the other 'tiles' in the map, e.g. their type and elevation.

一种在随机生成的世界中“生长”河流的方法[包括在上面的列表中] 一种相当简单的算法，用于根据地图中的其他“图块”（例如它们的类型和海拔）生成一条河流的路径。

回答by Mizipzor

I once found a great site for the theory when I made a rougelike. Have a look.

我曾经在制作 rougelike 时找到了一个很好的理论网站。看看。

回答by quetzalcoatl

Quite often the maps are being logically split into layers/overlays like "base terrain height", "water level", "highlands", "trees", "housing" etc.

通常，地图在逻辑上被划分为图层/叠加层，例如“基础地形高度”、“水位”、“高地”、“树木”、“房屋”等。

Then for each layer a different kind of generator is run. Very often fractals are used because they tend to generate interesting and hard to predict shapes. But only a part of the fractal is used. Using whole one would instantly expose the structure (on the top-level fractals are very repetitive) and viewers would notice it. So, the generated fractal is then distorted/modified/filtered/cut so that will not be obvious. For example, you may generate the base terrain level with some simple X-Y trigonometric oscillator, and then sum it up with a part your fractal image, limited to some min-max values, and you'd get an uneven terrain with noticeable hills and drops..

然后对于每一层运行不同类型的生成器。分形经常被使用，因为它们往往会产生有趣且难以预测的形状。但是只使用了分形的一部分。使用整个结构会立即暴露结构（顶层分形非常重复）并且观众会注意到它。因此，生成的分形然后被扭曲/修改/过滤/切割，因此不会很明显。例如，您可以使用一些简单的 XY 三角振荡器生成基础地形级别，然后将其与分形图像的一部分相加，限制为某些最小值-最大值，并且您会得到带有明显山丘和水滴的不平坦地形..

For all other layers, you usually cannot "sum up", because the layers other than terrain are not about "height" or "density" but rather they are 0/1 - place the tree here or not to place the tree here? But again, you perform it similarly: you generate some image (maybe a fractal again), then inspect the numbers and set a threshold value: everywhere when the number is higher/lower than X, you place/notplace the thing. You may additionally filter or branch it: for example if a tree would hit an under-water position, place a fish there or not place the tree at all.

对于所有其他图层，您通常无法“总结”，因为地形以外的图层与“高度”或“密度”无关，而是关于 0/1 - 将树放在这里还是不将树放在这里？但同样，您执行类似的操作：您生成一些图像（可能又是一个分形），然后检查数字并设置阈值：当数字高于/低于 X 时，您放置/不放置该东西。您还可以对其进行过滤或分支：例如，如果一棵树会碰到水下位置，则在那里放置一条鱼或根本不放置树。

I am surprosed you couldnt find resources on it. Few years ago googling for "terrain generation algorithms" would return many hits!

我很惊讶你找不到资源。几年前，谷歌搜索“地形生成算法”会返回很多点击！