寻找一个好的世界地图生成algorithm

我正在研究类似文明的游戏,我正在寻找一个用于生成类地球世界地图的好algorithm。 我已经尝试了几个select,但还没有打到真正的赢家。

一种select是使用柏林噪音生成高度图,并在一个水平上添加水,使世界上大约30%的土地是土地。 Perlin噪声(或类似的基于分形的技术)经常被用于地形,而且是相当现实的,但是对于我想要的大陆的数量,大小和位置的控制却没有太多的办法从游戏angular度来看。

柏林噪音

第二个select是从一个随机定位的一个瓷砖种子开始(我在瓷砖网格上工作),确定大陆所需的尺寸,每一个转动添加一个与现有大陆水平或垂直相邻的瓷砖,直到你已经达到了理想的尺寸。 重复其他大陆。 这个技术是文明4中使用的algorithm的一部分。问题是,在放置前几个大陆之后,有可能select被其他大陆包围的起始位置,因此不适合新大陆。 此外,还有一种倾向,就是将大陆彼此靠得太近,导致看起来更像河stream而不是大陆。

随机扩展

有没有人碰巧知道在基于网格的地图上生成逼真的大陆的好algorithm,同时保持对其数量和相对大小的控制?

你可以从大自然中得到启示,修改你的第二个想法。 一旦你生成你的大陆(大小相同),让他们随机移动和旋转,相互碰撞和变形,彼此漂移。 (注意:这可能不是有史以来最容易实现的)。

编辑:这是另一种方式,完成一个实现 – 游戏的多边形地图生成 。

我build议你备份和

  1. 想一想什么是“好”的大陆。
  2. 写一个algorithm,可以告诉一个坏的一个好的大陆布局。
  3. 细化algorithm,以便您可以量化好布局的效果。

一旦你有了这个,你可以开始实现一个algorithm,这应该是这样的形状:

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

为了改进,你可以尝试各种各样的标准优化技巧,无论是模拟退火,遗传编程,还是完全特殊的东西,比如将随机select的边缘正方形从大陆的任何一个边缘移动到与大陆质心相对的边缘。 但关键是要能够编写一个可以从坏的世界告诉好的大陆的程序 。 从手绘大陆和你的testing大陆开始,直到你find你喜欢的东西。

我写了类似于文明1的自动屏保风格克隆的东西。为了logging,我在VB.net中编写了这个logging,但是因为在你的问题中你没有提到关于语言或平台的任何事情,我会保留它抽象。

“地图”指明了大陆的数量,大陆尺寸的差异(例如,1.0将保持所有大陆具有相同的近似陆地面积,低至0.1将允许大陆以最大陆地质量的十分之一存在),最大陆地面积(作为百分比)产生,而中央的土地偏见。 一个“种子”随机分布在每个大陆的地图上,按照中心偏差向地图中心加权(例如,低偏差产生更类似于地球的分布大陆,其中高中心偏差将类似于更多的盘古)。 然后,对于每次增长的迭代,“种子”根据分配algorithm(稍后更多)分配地块,直到达到最大陆地面积。

陆地分配algorithm可以精确到你想要的,但我发现更多有趣的结果应用各种遗传algorithm和掷骰子。 康威的“生命游戏”是一个非常容易的开始。 你需要添加一些全球意识的逻辑,以避免像大陆成长对方,但在大多数情况下,照顾自己。 我发现更多的基于分形的方法(这是我的第一个倾向)的问题是结果要么看起来太模式,要么导致太多的情况下需要hacky感觉变通规则得到一个仍然不够dynamic的结果。 根据您使用的algorithm,您可能需要对结果进行“模糊”处理,以消除大量的单方海洋瓷砖和方格的海岸线。 如果一个像大陆正在产卵的东西被其他几个人包围着,而且没有地方成长,就把种子搬迁到地图上的一个新点,继续发展。 是的,这可能意味着你有时会比计划中的大陆更多,但是如果真的有些事情你不想要的话,那么另外一个办法就是避免这种增长algorithm,种子。 在最坏的情况下(无论如何,我认为),当一个种子没有任何增长并产生一个新的地图时,你可以将一个系列标记为无效。 只要确定你设置了最大的尝试次数,那么如果指定了任何不切实际的事情(比如在10×10电路板上安装50个偶数加权的大陆),它不会永远花费在寻找有效的解决scheme上。

我不能担保如何文明等这样做,当然不包括气候,土地年龄等东西,但通过玩弄种子增长algorithm,你可以得到非常有趣的结果,类似大洲,群岛等你可以使用相同的方法来产生“有机”的河stream,山脉等。

多边形地图生成文章描述了一步一步的地图生成Voronoi多边形。

这家伙也给所有的源代码。 它是Flash(ActionScript 3 / ECMAScript),但可转换为任何其他面向对象的语言

或者尝试使用像TerraJ这样的分形环境软件中实现的algorithm

我已经创build了类似于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> 

只是想在这里袖口:

select一些起点,并分配每个随机抽取(希望)的大小。 如果需要,您可以为计划的大陆和计划中的岛屿维护一个单独的大小绘图。

环绕地面的元素,他们还没有在规划的大小增加一平方米。 但有趣的部分是衡量每个相邻元素将成为一个的机会。 一些build议的事情可能包括:

  1. 距离最近的“其他”土地。 更好的是产生广阔的海洋空间。 越近越好,使狭窄的渠道。 你必须决定是否要让位合并。
  2. 与种子的距离。 越近越好意味着紧凑的地块,越远越好意味着长时间的排挤
  3. 相邻的现有地块的数量。 有利于许多相邻的广场的权重让你顺利的海岸,宁愿less数给你很多的入口和半岛。
  4. 附近有“资源”广场? 取决于游戏规则,当你生成资源广场,如果你想让它变得容易。
  5. 你会允许位接近或join两极吗?
  6. ??? 不知道还有什么

继续下去,直到所有的土地达到规划的规模或由于某种原因不能再长大为止。

请注意,将参数用于这些加权因子可以让您调整生成的世界的种类,这是我喜欢的一些文明特征。

这样你就需要分别在每个位上做地形生成。

我有一个地图创作的想法类似于板块的答案。 它是这样的:

  1. 如果rnd <= 0.292(地球上干地的实际百分比),则通过网格广场扫描,给每个广场“土地”平方。
  2. 将每块土地块向最近的大邻居移动一个方块。 如果邻居是等距离的,那么走向更大的块。 如果块大小相同,则随机select一个块。
  3. 如果两个地块触碰,将它们组合成一个块,从现在开始将所有的方块移动成一个块。
  4. 从第2步重复。当所有的块连接时停止。

这与重力如何在3D空间中工作相似。 这很复杂。 一个更简单的algorithm可以满足您的需求,如下所示:

  1. 在随机的x,y位置和彼此可接受的距离下降n个起始地块。 这些是你的大陆的种子。 (使用毕达哥拉斯定理确保种子与其他种子之间的距离最小。)
  2. 如果这个方向是一个海洋广场的话,从一个现有的地方广场上随机地产生一个广场。
  3. 重复第2步。当地块填满地图总大小的30%时停止。
  4. 如果大陆彼此足够接近的话,可以根据需要放下陆桥,模拟巴拿马式的效应。
  5. 放在更小,随机的岛屿,为更自然的外观所需。
  6. 对于每一个额外的“岛屿”广场,你可以使用相同的algorithm从大陆上切割出内陆的海洋和湖泊广场。 这将使土地百分比保持在所需的数量。

让我知道这是如何工作的。 我从来没有尝试过。

PS。 我看到这与你所尝试的类似。 除了在开始之前立即build立所有的种子,这样大陆就足够分开,并且在地图充足时停止。

你可以尝试一个钻石平方algorithm或perlin噪声来产生类似高度图的东西。 然后,将范围值分配给地图上显示的值。 如果你的“身高”从0到100,那么做0-20水,20-30海滩,30-80草,80-100山。 我认为档次在这个迷你游戏中做了类似的事情,但是我不是专家,我只是在钻石广场的心态中,最终得到它的工作。

我想你可以在这里使用“dynamic编程”风格的方法。

首先解决小问题,巧妙地结合解决scheme来解决更大的问题。

 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" ;) 

看看一些“graphics布局algorithm”将是非常好的,

  • 基于力的algorithm
  • 遗传algorithm的graphics布局

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

这是我在想什么,因为我即将实施这样的事情,我有一个游戏开发。 :

世界分为地区。 取决于世界的大小,它将决定有多less地区。 对于这个例子,我们假设一个中等规模的世界,有6个地区。 每个网格区域分成9个网格区域。 那些网格区域分成9个网格。 (这不是为了angular色的移动,而仅仅是为了地图的创build)网格用于生物群落,网格区域用于过度的地形特征(大陆vs大洋),而地区则用于整体气候。 网格分解成瓦片。

随机生成的区域得到了分配的逻辑气候集。 网格区域被随机分配给,例如; 海洋或土地。 网格根据网格区域和气候随机地分配生物群系,这些网格是森林,沙漠,平原,冰川,沼泽或火山。 一旦所有这些基础都被分配了,就可以把它们混合在一起,使用填充瓦片组的随机百分比函数。 例如; 如果你有一个森林生物群系,在沙漠生物群旁边,你有一个algorithm,可以减less一块瓷砖会变得“forest”“的可能性,并增加它将是”沙漠“的。 所以,在它们之间大约一半的时候,你会看到一种混合的影响,把两个生物群落结合起来,在它们之间有一个平滑的过渡。 从一个网格区域到另一个网格区域的过渡可能需要更多的工作来确保逻辑陆块形成。例如,来自一个网格区域的生物群落接触来自另一个网格的生物群落,而不是基于邻近区域具有简单的开关百分比。 例如,从生物群落的中心到生物群系的边缘有50块瓷砖,这意味着从它接触的边缘到下一个生物群落的中心有50块瓷砖。 从逻辑上讲,从一个生物群落到另一个生物群落将会发生100%的变化。 所以,当瓷砖接近两个生物群落的边界时,百分比缩小到60%左右。 我认为,把太多的生物群落越过边界的可能性太大是不明智的,但是你会希望边界有些混合。 对于网格区域,百分比变化将更加明显。 只下降到60%左右,而不是下降到80%左右。 然后必须进行第二次检查,以确保没有任何逻辑的海洋旁边的陆地生物群落中间没有随机的水瓦。 因此,无论是将水瓦连接到海洋上,还是build立一个通道来解释水瓦,或者把它完全拆除。 在水基生物群落中的土地更容易用岩石露头等来解释。

哦,有点笨,对不起。

我会根据一些你知道“有效”的布局来放置分形地形(例如2×2网格,菱形等,有一些抖动),但是高斯分布阻止峰值向着大陆中心的边缘。 把水位降低一点,直到靠近边缘。

我其实并没有尝试过这个,但是大卫·约翰斯通(David Johnstone)关于构造板块的回答是受到启发的。 我试着在我的老文明项目中自己实现它,当处理碰撞时,我有另外一个想法。 每个大陆不是直接生成图块,而是由节点组成。 将质量分配给每个节点,然后使用2D元球方法生成一系列“斑点”大陆。 构造和大陆漂移简单地通过移动节点就可以很容易地“伪造”。 根据你想要走多么复杂,你甚至可以应用像电stream这样的东西来处理节点运动,并生成对应于板块边界重叠的山脉。 可能不会增加太多东西的游戏玩法,但它可以从一个纯学术的angular度来看一个有趣的地图生成:)

如果你之前没有和他们合作过的话,可以很好的解释这个metaballs:

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