100

我正在开发类似文明的游戏，并且正在寻找一种生成类似地球的世界地图的好算法。我已经尝试了一些替代方案，但还没有找到真正的赢家。

一种选择是使用Perlin 噪声生成高度图，并添加一定水平的水，以使世界上大约 30% 是陆地。虽然 Perlin 噪声（或类似的基于分形的技术）经常用于地形并且相当逼真，但它并没有提供太多控制所产生大陆的数量、大小和位置的方式，我想从游戏的角度来看。

柏林噪声

第二种选择是从随机放置的单瓦种子开始（我正在处理瓦片网格），确定大陆所需的大小，每轮添加一个与现有大陆水平或垂直相邻的瓦片，直到您已达到所需的大小。重复其他大陆。这种技术是文明 4 中使用的算法的一部分。问题是在放置前几个大陆之后，有可能选择一个被其他大陆包围的起始位置，因此不适合新大陆。此外，它倾向于生成过于靠近的大陆，导致看起来更像河流而不是大陆的东西。

随机扩展

有没有人碰巧知道在基于网格的地图上生成逼真的大陆同时控制它们的数量和相对大小的好算法？

4

12 回答 12

38

您可以从大自然中汲取灵感并修改您的第二个想法。一旦你生成了你的大陆（它们的大小都差不多），让它们随机移动和旋转，相互碰撞和变形，并相互漂移。（注意：这可能不是最容易实现的事情。）

编辑：这是另一种实现方式，完成了一个实现 - Polygonal Map Generation for Games。

于 2010-03-25T23:52:49.180 回答
12

我在 JavaScript 中创建了类似于您的第一张图片的内容。它不是超级复杂，但它有效：

http://jsfiddle.net/AyexeM/zMZ9y/

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<style type="text/css">
    #stage{
        font-family: Courier New, monospace;
    }
    span{
        display: none;
    }
    .tile{
        float:left;
        height:10px;
        width:10px;
    }
    .water{
        background-color: #55F;
    }
    .earth{
        background-color: #273;
    }
</style>
</head>

<body>


<div id="stage">

</div>

<script type="text/javascript">

var tileArray = new Array();
var probabilityModifier = 0;
var mapWidth=135;
var mapheight=65;
var tileSize=10;

var landMassAmount=2; // scale of 1 to 5
var landMassSize=3; // scale of 1 to 5


$('#stage').css('width',(mapWidth*tileSize)+'px');


for (var i = 0; i < mapWidth*mapheight; i++) {

    var probability = 0;
    var probabilityModifier = 0;

    if (i<(mapWidth*2)||i%mapWidth<2||i%mapWidth>(mapWidth-3)||i>(mapWidth*mapheight)-((mapWidth*2)+1)){

        // make the edges of the map water
        probability=0;
    }
    else {

        probability = 15 + landMassAmount;

        if (i>(mapWidth*2)+2){

            // Conform the tile upwards and to the left to its surroundings 
            var conformity =
                (tileArray[i-mapWidth-1]==(tileArray[i-(mapWidth*2)-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth-2]));

            if (conformity<2)
            {
                tileArray[i-mapWidth-1]=!tileArray[i-mapWidth-1];
            }
        }

        // get the probability of what type of tile this would be based on its surroundings 
        probabilityModifier = (tileArray[i-1]+tileArray[i-mapWidth]+tileArray[i-mapWidth+1])*(19+(landMassSize*1.4));
    }

    rndm=(Math.random()*101);
    tileArray[i]=(rndm<(probability+probabilityModifier));

}

for (var i = 0; i < tileArray.length; i++) {
    if (tileArray[i]){
        $('#stage').append('<div class="tile earth '+i+'"> </div>');
    }
    else{
        $('#stage').append('<div class="tile water '+i+'"> </div>');
    }
}

</script>

</body>
</html>
于 2013-10-22T23:31:28.497 回答
11

我为文明 1 的自动屏​​幕保护风格克隆写了一些类似于你所追求的东西。为了记录，我在 VB.net 中写了这个但是因为你在你的问题中没有提到任何关于语言或平台的东西我会保留它抽象。

“地图”指定了大陆的数量、大陆的大小差异（例如，1.0 将使所有大陆保持相同的近似陆地面积，降至 0.1 将允许大陆以最大大陆质量的 1/10 存在）、最大陆地面积（以百分比形式）生成，以及中央土地偏差。每个大陆的“种子”随机分布在地图周围，根据中心偏差向地图中心加权（例如，低偏差产生更类似于地球的分布式大陆，而高中心偏差将更像一个盘古）。然后对于每次迭代的增长，“种子”根据分布算法（稍后会详细介绍）分配土地块，直到达到最大土地面积。

土地分配算法可以随心所欲地精确，但我发现应用各种遗传算法和掷骰子的结果更有趣。康威的“生命游戏”非常容易上手。您需要添加一些全局感知逻辑，以避免诸如大陆相互生长之类的事情，但在大多数情况下，事情会自行解决。我发现更多基于分形的方法（这是我的第一个倾向）的问题是结果要么看起来过于模式化，要么导致太多场景需要 hacky-feeling 变通规则来获得仍然感觉不够动态的结果。根据您使用的算法，您可能希望在结果上应用“模糊”传递，以消除诸如丰富的单方形海洋瓷砖和方格海岸线之类的东西。如果某个大陆被其他几个人包围并且无处可生长，请将种子重新定位到地图上的新点并继续生长过程。是的，这可能意味着您有时最终会获得比计划更多的大陆，但如果这确实是您坚决不想要的东西，那么另一种帮助避免它的方法是偏向增长算法，因此它们有利于在与其他大陆最不接近的方向上增长种子。在最坏的情况下（无论如何我认为），当种子无处可生长并生成新地图时，您可以将系列标记为无效。只要确保您设置了最大尝试次数，因此如果指定了任何不切实际的内容（例如在 10x10 板上安装 50 个均匀加权的大陆），它就不会永远花时间去寻找有效的解决方案。

我不能保证 Civ 等是如何做到的，当然也不包括气候、土地年龄等，但通过使用种子生长算法，你可以获得类似于大陆、群岛等的非常有趣的结果。你可以也使用相同的方法来制作看起来“有机”的河流、山脉等。

于 2010-04-16T04:44:13.447 回答
11

我建议你备份并

  1. 想想是什么造就了“好”的大陆。
  2. 编写一个算法，可以区分好的大陆布局和坏的大陆布局。
  3. 改进算法，以便您可以量化一个好的布局有多好。

一旦你有了它，你就可以开始实现一个算法，它的形状应该是这样的：

  • 生成蹩脚的大陆，然后改进它们。

为了改进，您可以尝试各种标准优化技巧，无论是模拟退火、基因编程还是完全临时的东西，例如将随机选择的边缘正方形从大陆上的任何地方移动到大陆质心对面的边缘。但关键是能够编写一个程序来区分好大陆和坏大陆。从手绘大陆和你的测试大陆开始，直到你得到你喜欢的东西。

于 2010-03-26T01:58:33.850 回答
10

多边形地图生成文章描述了不使用 Voronoi 多边形的逐步地图生成。

这家伙还提供了所有源代码。它是 Flash (ActionScript 3 / ECMAScript)，但可以转换为任何其他面向对象的语言

或者尝试使用一些分形环境软件（如TerraJ ）中实现的算法

于 2011-07-24T15:29:42.830 回答
5

只是想在这里袖手旁观：

选择一些起点，并为每个起点分配一个随机绘制的（希望的）尺寸。如果需要，您可以为计划的大陆和计划的岛屿维护单独的尺寸图。

循环遍历土地元素，在它们尚未达到计划大小的地方添加一个正方形。但有趣的部分是权衡每个相邻元素将是一个的机会。一些建议的事情可能会影响：

  1. 到最近的“其他”土地的距离。此外，更好地产生广阔的海洋空间。越近越好使狭窄的通道。您必须决定是否也让位合并。
  2. 与种子的距离。越近越好意味着紧凑的土地块，越远越好意味着长串
  3. 相邻的现有土地广场的数量。有利于许多相邻广场的加权会给你平滑的海岸，更喜欢少数给你很多入口和半岛。
  4. 附近有“资源”广场吗？取决于游戏规则，何时生成资源方块，以及是否想让它变得简单。
  5. 你会允许比特接近或加入两极吗？
  6. ？？？不知道还有什么

继续，直到所有地块都达到计划的大小或由于某种原因不能再增长。

请注意，将参数添加到这些权重因子可以让您调整生成的世界类型，这是我喜欢某些文明的一个特性。

这样，您需要分别对每个位进行地形生成。

于 2010-03-25T23:58:55.280 回答
4

您可以尝试使用菱形平方算法或柏林噪声来生成高度图之类的东西。然后，将范围值分配给地图上显示的内容。如果您的“高度”从 0 变为 100，则制作 0 - 20 水，20 - 30 海滩，30 - 80 草地，80 - 100 山。我认为notch在minicraft中做了类似的事情，但我不是专家，我只是在终于让它工作后处于菱形思维模式。

于 2013-01-23T04:49:22.563 回答
3

我认为您可以在这里使用“动态编程”风格的方法。

先解决小问题，然后巧妙地结合解决方案来解决更大的问题。

A1= [elliptical rectangular random ... ]// list of continents with area A1 approx. 
A2= [elliptical rectangular random ... ]// list of continents with area A2 approx.
A3= [elliptical rectangular random ... ]// list of continents with area A3 approx.
...
An= [elliptical rectangular random ... ]// list of continents with area An approx.

// note that elliptical is approximately elliptical in shape and same for the other shapes.

Choose one/more randomly from each of the lists (An).

Now you have control over number and area of continents.

You can use genetic algorithm for positioning them 
as you see "fit" ;)

看一些“Graph Layout Algorithms”会很好

您可以修改这些以适合您的目的。

于 2010-03-26T05:35:08.340 回答
3

我有一个类似于构造板块答案的地图创建想法。它是这样的：

  1. 如果 rnd <= 0.292（地球上干地的实际百分比），扫过网格方块，给每个方块一个“土地”方块。
  2. 将每个土地块向其最近的较大邻居迁移一格。如果邻居是等距的，则走向更大的块。如果块大小相等，则随机选择一个。
  3. 如果两个陆地方块接触，将它们组合成一个块，从现在开始将所有方块移动为一个。
  4. 从第 2 步开始重复。连接所有块时停止。

这类似于重力在 3D 空间中的工作方式。这很复杂。满足您需求的更简单算法将按如下方式工作：

  1. 在随机的 x,y 位置和彼此之间可接受的距离处放入 n 个起始土地方块。这些是你们大陆的种子。（使用勾股定理确保种子与所有其他种子之间的距离最小。）
  2. 如果该方向是海洋方块，则在随机方向从现有陆地方块生成陆地方块。
  3. 重复步骤 2。当陆地方块填满地图总大小的 30% 时停止。
  4. 如果大陆彼此足够接近，请根据需要放置陆桥以模拟巴拿马型效果。
  5. 根据需要放入更小、随机的岛屿，以获得更自然的外观。
  6. 对于您添加的每一个额外的“岛屿”方块，使用相同的算法从大陆中切出内陆海和湖泊方块。这将使土地百分比保持在所需的数量。

让我知道这是怎么回事。我自己从未尝试过。

PS。我看到这与您尝试的类似。除了它在开始之前立即设置所有种子，因此大陆之间的距离会足够远，并且会在地图填满时停止。

于 2011-10-26T17:44:27.757 回答
2

这就是我的想法，因为我即将为正在开发的游戏实现类似的东西。：

世界分为区域。根据世界的大小，它会决定有多少地区。对于这个例子，我们假设一个中等大小的世界，有 6 个区域。每个网格区域分为 9 个网格区域。这些网格区域分别分成 9 个网格。（这不是用于角色移动，而仅用于创建地图）网格用于生物群落，网格区域用于拱形陆地特征（大陆与海洋），区域用于整体气候。网格分解成瓷砖。

随机生成的区域被分配了逻辑气候集。例如，网格区域被随机分配；海洋或陆地。网格会根据网格区域和气候随机分配生物群落，包括森林、沙漠、平原、冰川、沼泽或火山。一旦分配了所有这些基础知识，就该将它们混合在一起了，使用基于随机百分比的函数填充图块集。例如; 如果你有一个森林生物群系，在一个沙漠生物群系旁边，你有一个算法可以减少瓷砖“森林”的可能性，并增加它“沙漠”的可能性。因此，在它们之间大约一半的地方，您会看到一种混合效果，将两个生物群系结合起来，使它们之间的过渡有点平滑。从一个网格区域到下一个网格区域的转换可能需要更多的工作来确保逻辑陆地形成。例如，一个网格区域的生物群落与另一个网格区域的生物群落接触，而不是基于接近度的简单切换百分比。例如，从生物群系的中心到生物群系的边缘有 50 个图块，这意味着从它接触的边缘到下一个生物群系的中心有 50 个。从逻辑上讲，从一个生物群系到另一个生物群系会发生 100% 的变化。因此，随着瓷砖越来越靠近两个生物群系的边界，百分比缩小到 60% 左右。我认为，给远离边界的生物群落提供太多可能性是不明智的，但你会希望边界有点混合。对于网格区域，百分比变化将更加明显。百分比不会下降到 60% 左右，而是只会下降到 80% 左右。然后必须进行二次检查，以确保在靠近海洋的陆地生物群系中间没有随机的水瓦，没有一些逻辑。因此，要么将该水瓦连接到海洋块以形成一个解释水瓦的通道，或者将其完全移除。使用岩石露头等更容易解释水基生物群落中的土地。

哦，有点笨，对不起。

于 2013-04-30T23:23:59.977 回答
2

我实际上并没有尝试过，但它受到大卫约翰斯通关于构造板块的回答的启发。我尝试在我的旧 Civ 项目中自己实现它，当涉及到处理碰撞时，我有了另一个想法。每个大陆不是直接生成瓦片，而是由节点组成。将质量分配到每个节点，然后使用 2D 元球方法生成一系列“blob”大陆。只需移动节点，构造学和大陆漂移就很容易“伪造”。根据您想要的复杂程度，您甚至可以应用电流之类的东西来处理节点移动并生成与板块边界重叠相对应的山脉。可能不会在游戏性方面增加太多，

如果您以前没有使用过元球，这是一个很好的解释：

http://www.gamedev.net/page/resources/_//feature/fprogramming/exploring-metaballs-and-isosurfaces-in-2d-r2556

于 2010-04-16T06:47:53.030 回答
1

我会根据一些你知道“有效”的布局（例如 2x2 网格、菱形等，有一些抖动）放置分形地形，但高斯分布的阻尼峰值向下朝向大陆中心的边缘。把水位放低，这样大部分都是陆地，直到你靠近边缘。

于 2010-03-26T03:37:02.613 回答