algorithm - 優れた世界地図生成アルゴリズムを探しています

Question

私は Civilization のようなゲームに取り組んでおり、地球のような世界地図を生成するための優れたアルゴリズムを探しています。私はいくつかの代替案を試しましたが、まだ真の勝者を見つけていません.

1 つのオプションは、パーリンノイズを使用して高さマップを生成し、世界の約 30% が陸地になるレベルで水を追加することです。パーリンノイズ (または同様のフラクタルベースの手法) は地形に頻繁に使用され、かなり現実的ですが、結果として生じる大陸の数、サイズ、および位置を制御する方法はあまり提供されません。ゲームプレイの観点から持っています。

パーリンノイズ

2 番目のオプションは、ランダムに配置された 1 タイルのシード (私はタイルのグリッドに取り組んでいます) から始めて、大陸に必要なサイズを決定し、各ターンが既存の大陸に水平または垂直に隣接するタイルを追加することです。希望のサイズに達しました。他の大陸についても繰り返します。この手法は、Civilization 4 で使用されるアルゴリズムの一部です。問題は、最初のいくつかの大陸を配置した後、他の大陸に囲まれた開始位置を選択できるため、新しい大陸に適合しないことです。また、大陸同士が近づきすぎて、大陸というより川のように見える結果になる傾向があります。

ランダム展開

大陸の数と相対的なサイズを制御しながら、グリッドベースの地図上に現実的な大陸を生成するための優れたアルゴリズムを知っている人はいますか?

score 38 · Accepted Answer

自然からヒントを得て、2 番目のアイデアを修正することができます。大陸 (すべてほぼ同じサイズ) を生成したら、それらをランダムに移動させ、回転させ、互いに衝突させ、変形させ、互いに離れて漂流させます。(注: これは、これまでで最も簡単に実装できるものではない可能性があります。)

編集：これは、実装を完了した別の方法です —ゲーム用のポリゴンマップ生成。

score 12 · Accepted Answer

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>

score 11 · Accepted Answer

私はCivilization1の自動スクリーンセーバースタイルのクローンのためにあなたが求めているものに似たものを書きました。記録のために私はこれをVB.netで書きましたが、あなたの質問では言語やプラットフォームについて何も言及していないので、それは抽象的です。

「マップ」は、大陸の数、大陸のサイズの変動（たとえば、1.0はすべての大陸を同じおおよその土地面積に保ち、0.1まで下げると、大陸は最大の大陸の1/10の質量で存在できるようになります）、最大土地面積を指定します。（パーセンテージとして）生成する、および中央の土地バイアス。「シード」は、各大陸のマップの周囲にランダムに分散され、中央のバイアスに従ってマップの中心に向かって重み付けされます（たとえば、バイアスが低いと、地球に似た分散した大陸が生成されますが、中央のバイアスが高いと、パンゲア）。次に、成長の反復ごとに、「シード」は、最大土地面積に達するまで、分散アルゴリズム（詳細は後で説明します）に従って土地タイルを割り当てます。

土地分布アルゴリズムは必要に応じて正確にすることができますが、さまざまな遺伝的アルゴリズムを適用してサイコロを振ると、より興味深い結果が得られました。コンウェイの「ライフゲーム」は、始めるのが本当に簡単なものです。大陸が互いに成長するようなことを避けるために、いくつかのグローバルに認識されたロジックを追加する必要がありますが、ほとんどの場合、物事は自分で処理します。よりフラクタルベースのアプローチ（これが私の最初の傾向でした）で私が見つけた問題は、結果がパターン化されすぎているか、またはまだ十分に動的でないと感じられる結果を得るためにハッキーな感じの回避策ルールを必要とするシナリオが多すぎることでした。使用するアルゴリズムによっては、結果に「ぼかし」パスを適用して、豊富な単一の正方形の海のタイルや市松模様の海岸線などを排除することができます。大陸が他のいくつかに囲まれてスポーンされ、成長する場所がなくなった場合は、シードをマップ上の新しいポイントに移動して、成長パスを続行します。はい、それはあなたが計画よりも多くの大陸になってしまうことを意味する可能性がありますが、それが本当にあなたが強く望んでいないものである場合、それを回避するのに役立つ別の方法は、成長アルゴリズムにバイアスをかけて、他の最も近い方向への成長を優先することです種子。最悪の場合（とにかく私の意見では）、シードが成長して新しいマップを生成する場所が残っていない場合、シリーズに無効のフラグを立てることができます。最大試行回数を設定して、非現実的なものが指定されている場合（10x10ボードに50の均等な重みの大陸を合わせるなど）、有効な解決策を見つけるために永遠に費やすことはありません。

Civなどがどのようにそれを行うかを保証することはできません。もちろん、気候や土地の年齢などはカバーしていませんが、シード成長アルゴリズムを試してみると、大陸や諸島などに似た非常に興味深い結果を得ることができます。同じアプローチを使用して、「有機的」に見える川、山脈なども作成します。

score 11 · Accepted Answer

バックアップすることをお勧めします

「良い」大陸とは何かを考えてみてください。
良い大陸配置と悪い配置を見分けるアルゴリズムを書いてください。
アルゴリズムを改良して、適切なレイアウトがどの程度優れているかを定量化できるようにします。

それが整ったら、次のような形のアルゴリズムの実装を開始できます。

くだらない大陸を生成し、それらを改善します。

改善のために、シミュレートされたアニーリング、遺伝的プログラミング、または完全にアドホックなものであるかどうかにかかわらず、あらゆる種類の標準的な最適化トリックを試すことができます。たとえば、ランダムに選択されたエッジスクエアを大陸上のどこからでも大陸の質量中心の反対側のエッジに移動します。しかし、重要なのは、良い大陸と悪い大陸を見分けることができるプログラムを書けるようになることです。気に入ったものが得られるまで、手描きの大陸とテスト大陸から始めます。

score 10 · Accepted Answer

ポリゴンマップ生成の記事では、ボロノイポリゴンを使用しない段階的なマップ生成について説明しています。

この男は、すべてのソースコードも提供します。Flash (ActionScript 3 / ECMAScript) ですが、他のオブジェクト指向言語に置き換え可能です。

または、 TerraJなどのフラクタル環境ソフトウェアに実装されているアルゴリズムを使用してみてください。

score 5 · Accepted Answer

ここで袖口を考えてみてください：

いくつかの開始点を選び、それぞれにランダムに描かれた (期待される) サイズを割り当てます。必要に応じて、計画された大陸と計画された島々に対して個別のサイズドローを維持できます。

土地要素をループし、まだ計画されたサイズになっていない場所に 1 つの正方形を追加します。しかし、面白いのは、隣接する各要素が 1 つになる可能性を比較検討することです。考慮に入れる可能性のある提案されたもの：

最も近い「他の」土地までの距離。さらに広い海洋空間を生成します。近いほど、チャンネルは狭くなります。ビットもマージするかどうかを決定する必要があります。
種子からの距離。近いほど良いのはコンパクトな陸塊を意味し、遠いほど良いのは長く伸びた小片を意味します
隣接する既存の土地の正方形の数。多くの隣接する正方形を優先して重み付けすると滑らかな海岸が得られ、少数を優先すると多くの入り江と半島が得られます。
近くに「資源」の広場はありますか？ゲームのルール、リソーススクエアをいつ生成するか、簡単にするかどうかによって異なります。
ビットが極に近づいたり、合体したりすることを許可しますか?
??? 他に何を知らない

すべての陸塊が計画されたサイズに達するか、何らかの理由でそれ以上成長できなくなるまで続けます。

パラメータをこれらの重み係数に合わせることで、生成される世界の種類を調整できることに注意してください。これは、いくつかの Civ で気に入った機能です。

この方法では、各ビットで個別に地形生成を行う必要があります。

score 4 · Accepted Answer

高さマップのようなものを生成するために、ダイヤモンドスクエアアルゴリズムまたはパーリンノイズを試すことができます。次に、範囲の値をマップに表示されるものに割り当てます。「高さ」が 0 から 100 の場合、0 ～ 20 の水、20 ～ 30 のビーチ、30 ～ 80 の草、80 ～ 100 の山を作成します。notch は minicraft でこれと似たようなことをしたと思いますが、私は専門家ではありません。

score 3 · Accepted Answer

ここで「動的プログラミング」スタイルのアプローチを使用できると思います。

最初に小さな問題を解決し、ソリューションを賢く組み合わせてより大きな問題を解決します。

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

いくつかの「グラフレイアウトアルゴリズム」を参照することは非常に良いことです。

目的に合わせてこれらを変更できます。

score 3 · Accepted Answer

構造プレートの回答に似たマップ作成のアイデアがありました。次のようになりました。

rnd <= 0.292 (惑星地球上の乾燥した土地の実際のパーセンテージ) の場合、各正方形に「土地」の正方形を与えるグリッドの正方形を掃引します。
各土地チャンクを、最も近い大きな隣に向かって 1 マス移動します。隣人が等距離にある場合は、より大きなチャンクに向かいます。チャンクが同じサイズの場合、ランダムに 1 つを選択します。
2 つの土地の正方形が接触している場合は、それらをチャンクにグループ化し、すべての正方形を 1 つとして移動します。
ステップ 2 から繰り返します。すべてのチャンクが接続されたら停止します。

これは、3D 空間で重力がどのように機能するかに似ています。かなり複雑です。ニーズに合ったより単純なアルゴリズムは次のように機能します。

n 個のスターターランドスクエアを、ランダムな x、y 位置で、互いに許容可能な距離にドロップします。これらはあなたの大陸の種です。(ピタゴラスの定理を使用して、シードと他のすべてのシードとの間の距離が最小になるようにします。)
その方向が海の正方形である場合、ランダムな方向に既存の土地の正方形から土地の正方形を生成します。
手順 2 を繰り返します。土地の正方形がマップサイズ全体の 30% を占めたら停止します。
大陸が互いに十分に近い場合は、パナマ型の効果をシミュレートするために、必要に応じて陸橋にドロップします。
より自然な外観にするために、必要に応じて小さな島をランダムにドロップします。
追加する余分な「島」の正方形ごとに、同じアルゴリズムを逆に使用して、大陸から内海と湖の正方形を切り取ります。これにより、土地のパーセンテージが目的の量に維持されます。

これがどのように機能するか教えてください。私はそれを自分で試したことはありません。

PS。これはあなたが試したものと似ています。ただし、開始前にすべてのシードを一度に設定するため、大陸は十分に離れており、マップが十分にいっぱいになると停止します。

score 2 · Accepted Answer

私は実際にこれを試したことはありませんが、構造プレートに関する David Johnstone の回答に触発されました。古い Civ プロジェクトで自分で実装しようとしましたが、衝突の処理に関しては別のアイデアがありました。タイルを直接生成する代わりに、各大陸はノードで構成されます。各ノードに質量を分配し、2D メタボールアプローチを使用して一連の「ブロブ」大陸を生成します。テクトニクスと大陸移動は、ノードを移動するだけで、ばかばかしいほど簡単に「偽装」できます。進みたい複雑さに応じて、電流などを適用して節点の動きを処理し、重なっているプレート境界に対応する山脈を生成することもできます。おそらく、ゲームプレイの面ではそれほど多くは追加されませんが、

以前にメタボールを使用したことがない場合のメタボールの適切な説明:

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

score 2 · Accepted Answer

開発中のゲームにこのようなものを実装しようとしているので、これが私が考えていることです。:

地域に分かれた世界。世界の規模に応じて、リージョンの数が決まります。この例では、6 つの地域を持つ中規模の世界を想定しています。各グリッドゾーンは 9 つのグリッドゾーンに分割されます。これらのグリッドゾーンは、それぞれ 9 つのグリッドに分割されます。(これはキャラクターの移動用ではなく、単にマップの作成用です) グリッドは生物群系用であり、グリッドゾーンはアーチ状の地形 (大陸と海) 用であり、地域は全体的な気候用です。グリッドはタイルに分割されます。

ランダムに生成された地域には、論理的な気候セットが割り当てられます。たとえば、グリッドゾーンはランダムに割り当てられます。海か陸か。グリッドには、グリッドゾーンと気候 (森林、砂漠、平原、氷河、沼地、火山) に基づいた修飾子を使用してランダムにバイオームが割り当てられます。これらの基本要素がすべて割り当てられたら、タイルセットを埋めるランダムなパーセンテージベースの関数を使用して、それらをブレンドします。例えば; 砂漠バイオームの隣に森林バイオームがある場合、タイルが「森林」になる可能性を減らし、「砂漠」になる可能性を高めるアルゴリズムがあります。そのため、それらのほぼ中間で、2 つのバイオームを組み合わせて、それらの間のややスムーズな移行をオフにする一種の混合効果が表示されます。1 つのグリッドゾーンから次のグリッドゾーンへの移行は、ロジックランドマスフォーメーションを確保するためにおそらくもう少し作業が必要になるでしょう。たとえば、バイオームの中心からバイオームの端まで 50 個のタイルがあります。つまり、接する端から次のバイオームの中心まで 50 個のタイルがあります。それは論理的に、あるバイオームから次のバイオームへと 100% の変化を残すことになります。そのため、タイルが 2 つのバイオームの境界に近づくにつれて、パーセンテージは約 60% にまで狭まります。境界から遠く離れたバイオームを横断する可能性を高くしすぎるのは賢明ではないと思いますが、境界をある程度ブレンドする必要があります。グリッドゾーンでは、パーセンテージの変化がより顕著になります。% が約 60% に低下する代わりに、約 80% にしか低下しません。そして、二次的なチェックを実行して、海の隣の土地バイオームの真ん中に、ロジックなしでランダムな水タイルがないことを確認する必要があります. したがって、その水タイルを海塊に接続して、水タイルを説明するチャネルを作成するか、それを完全に削除します。水ベースのバイオームの土地は、岩の露頭などを使用して説明する方が簡単です。

あ、バカです、ごめんなさい。

score 1 · Accepted Answer

「機能する」ことがわかっているレイアウト (例: 2x2 グリッド、ダイアモンドなど、多少のジッターあり) に従ってフラクタル地形を配置しますが、大陸の中心の端に向かってピークを減衰させるガウス分布を使用します。端に近づくまで水位を低くして、ほとんどが陸地になるようにします。

algorithm - 優れた世界地図生成アルゴリズムを探しています

12 に答える 12

Related

Reference