シミュレーションゲームのマップをプロシージャル生成してみる

初めに

シドマイヤーズ シヴィライゼーション VIのようなシミュレーションゲームを作りたいと考えている。そこで自動生成のシステムを採用したい。
そのためにプロシージャルについて調べて、現実世界の地図に似たような物を作る。

目標 ↓

この二つみたいな感じで世界地図的なやつをランダム自動生成したい

やってみた

実際に調べてみると

• パーリンノイズ
  　　滑らかな乱数を生成するノイズ
  こんな感じの情報が出てきた

この記事を参考にとりあえずパーリンノイズを使って作ってみた。

いい感じにできたので、海とか川も作ってよりリアルにしてみる。

とりあえずこんな感じの事を考えた。

• 高度マップ生成

  Perlinノイズを使って地形の基盤を作る

• 地形分類

  高度に基づいて海、草原、山などを割り当て

• 川の生成

  高い位置から低い位置に向かうようにランダムに川を作る

• 陸地の生成

  ランダムに位置を選んで陸地を作る

• マップの描画

  各地形に対応するPrefabを配置してマップを作る

こうやればうまくいくかもと思ったので改良版を作った。

改良版

結構うまくいった。

しかし陸地の中になぜか湖のようなが大量発生してしまったが今回は別に要らないので、
フラッドフィル（塗りつぶし）アルゴリズムを使用して、外部の海域を検出。内側（内陸）の小さな水域を削除または陸地に変換。

高度マップ: 陸地の詳細を生成（山、草原、森など）。
湿度マップ: バイオームの分類（砂漠、森、湿地など）。
といった複数のマップを組み合わせることによってよりリアルに。

ここにオクターブなるものを追加するとより細かい地形を作れるのでと書いてあるので
それも追加。

シード値：乱数生成の初期値するやつで、これも使う

再改良版

ここで力尽きた。
川とかが海にたどり着く前に止まってしまうのを直したかったがうまくいかなかった。

結論

プロシージャルを調べて、ノイズであったりマスクであったり、ものすごく複雑な要素が組み合わさって実現できていること、かなりの労力を必要とすることがよく分かった。
実際に作ってみると想像以上に大変。
シヴィライゼーションとかを作っている人たちがいかに凄いかよく分かった気がする。

サンプルプログラム

めちゃくちゃ長いし、読みずらいと思いますし、何か間違っていると思います。すみません。

MapGenerator.cs

using System;
using System.Collections.Generic;
using UnityEngine;

public class MapGenerator : MonoBehaviour
{
    public GameObject oceanPrefab;
    public GameObject shallowWaterPrefab;
    public GameObject grassPrefab;
    public GameObject forestPrefab;
    public GameObject mountainPrefab;
    public GameObject desertPrefab;
    public GameObject lakePrefab;
    public GameObject riverPrefab;
    public GameObject swampPrefab;
    public GameObject hillPrefab;
    public GameObject glacierPrefab;
    public GameObject cirqueWallPrefab;
    public int mapWidth = 100;
    public int mapHeight = 100;
    public float noiseScale = 20f;
    public int octaves = 4;
    public float persistence = 0.5f;
    public float lacunarity = 2f;
    public int riverCount = 5;
    public int continentCount = 3;
    public float swampRatio = 0.1f;

    private TileType[,] map;
    private float[,] heightMap;
    private float[,] moistureMap;
    private float[,] continentMask;
    private float[,] biomeNoiseMap;

    private enum TileType
    {
        Ocean,
        ShallowWater,
        Grass,
        Forest,
        Mountain,
        Desert,
        Lake,
        River,
        Swamp,
        Hill,
        Glacier,
        CirqueWall,
    }

    void Start()
    {
        GenerateMap();
        RenderMap();
    }

    public void GenerateMap()
    {
        int seed = UnityEngine.Random.Range(1, 10000);

        // Generate maps
        continentMask = GenerateMaskMap(mapWidth, mapHeight, continentCount, seed);
        heightMap = GenerateCombinedNoiseMap(mapWidth, mapHeight, noiseScale, octaves, persistence, lacunarity, seed);
        moistureMap = GenerateCombinedNoiseMap(mapWidth, mapHeight, noiseScale / 2, octaves, persistence, lacunarity, seed + 1);
        biomeNoiseMap = GenerateCombinedNoiseMap(mapWidth, mapHeight, noiseScale / 4, octaves, persistence, lacunarity, seed + 2);

        ApplyMaskToHeightMap();
        map = new TileType[mapWidth, mapHeight];

        ClassifyBiome();
        GenerateRivers();
        SuppressInlandWater();
        RenderMap();
    }

    float[,] GenerateCombinedNoiseMap(int width, int height, float scale, int octaves, float persistence, float lacunarity, int seed)
    {
        float[,] noiseMap = new float[width, height];
        System.Random rng = new System.Random(seed);

        float offsetX = rng.Next(-100000, 100000);
        float offsetY = rng.Next(-100000, 100000);

        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                float amplitude = 1;
                float frequency = 1;
                float noiseHeight = 0;

                for (int i = 0; i < octaves; i++)
                {
                    float sampleX = (x / scale * frequency) + offsetX;
                    float sampleY = (y / scale * frequency) + offsetY;

                    float perlinValue = Mathf.PerlinNoise(sampleX, sampleY) * 2 - 1;
                    noiseHeight += perlinValue * amplitude;

                    amplitude *= persistence;
                    frequency *= lacunarity;
                }

                noiseMap[x, y] = Mathf.InverseLerp(-1, 1, noiseHeight);
            }
        }

        return noiseMap;
    }

    float[,] GenerateMaskMap(int width, int height, int numContinents, int seed)
    {
        float[,] maskMap = new float[width, height];
        System.Random rng = new System.Random(seed);

        for (int i = 0; i < numContinents; i++)
        {
            int centerX = rng.Next(width);
            int centerY = rng.Next(height);
            float radius = rng.Next(30, 60);

            for (int x = 0; x < width; x++)
            {
                for (int y = 0; y < height; y++)
                {
                    float distance = Vector2.Distance(new Vector2(x, y), new Vector2(centerX, centerY));
                    maskMap[x, y] += Mathf.Max(0, 1 - (distance / radius));
                }
            }
        }

        return maskMap;
    }

    float[,] GenerateFalloffMap(int width, int height)
    {
        float[,] falloffMap = new float[width, height];
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                float fx = x / (float)width * 2 - 1;  // -1 to 1
                float fy = y / (float)height * 2 - 1; // -1 to 1
                float value = Mathf.Max(Mathf.Abs(fx), Mathf.Abs(fy)); // 距離ベースの減衰
                falloffMap[x, y] = Mathf.Pow(value, 2); // 減衰の強さを調整（2乗で滑らかに）
            }
        }
        return falloffMap;
    }

    void ApplyMaskToHeightMap()
    {
        float[,] falloffMap = GenerateFalloffMap(mapWidth, mapHeight);

        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                // 地形の高さを元のマスクと減衰マスクの両方で調整
                heightMap[x, y] *= continentMask[x, y] * (1 - falloffMap[x, y]);

                // 高さが一定以下なら海に設定
                if (heightMap[x, y] < 0.1f)
                {
                    heightMap[x, y] = 0f; // 海
                }
            }
        }
    }

    void ClassifyBiome()
    {
        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                float height = heightMap[x, y];
                float moisture = moistureMap[x, y];
                float biomeNoise = biomeNoiseMap[x, y];

                // 緯度による気候帯の影響を考慮
                float latitude = (float)y / mapHeight;
                TileType biome = DetermineBiomeByLatitudeAndHeight(latitude, height, moisture, biomeNoise);

                map[x, y] = biome;
            }
        }
    }

    TileType DetermineBiomeByLatitudeAndHeight(float latitude, float height, float moisture, float biomeNoise)
    {
        if (height < 0.3f)
        {
            return TileType.Ocean;
        }
        else if (height >= 0.3f && height < 0.35f)
        {
            return TileType.ShallowWater;
        }
        else if (height > 0.8f)
        {
            if (latitude < 0.3f || latitude > 0.7f)
            {
                return biomeNoise < 0.5f ? TileType.CirqueWall : TileType.Glacier;
            }
            return TileType.Mountain;
        }
        else if (height > 0.6f)
        {
            return TileType.Hill;
        }
        else
        {
            if (biomeNoise < 0.4f)
            {
                return TileType.Forest;
            }
            else if (biomeNoise < 0.8f)
            {
                return TileType.Grass;
            }
            else
            {
                return TileType.Desert;
            }
        }
    }

    void GenerateRivers()
    {
        for (int i = 0; i < riverCount; i++)
        {
            Vector2Int startPoint = FindRiverStartPoint();
            if (startPoint != Vector2Int.zero)
            {
                List<Vector2Int> path = FindPathToOcean(startPoint);
                if (path.Count > 0)
                {
                    foreach (var position in path)
                    {
                        map[position.x, position.y] = TileType.River;
                    }
                }
                else
                {
                    // 経路が見つからなかった場合、別の開始地点を探す
                    i--;
                }
            }
        }
    }

    Vector2Int FindRiverStartPoint()
    {
        for (int attempts = 0; attempts < 300; attempts++)
        {
            int x = UnityEngine.Random.Range(0, mapWidth);
            int y = UnityEngine.Random.Range(0, mapHeight);
            if (map[x, y] == TileType.Mountain)
            {
                return new Vector2Int(x, y);
            }
        }
        return Vector2Int.zero;
    }

    List<Vector2Int> FindPathToOcean(Vector2Int start)
    {
        PriorityQueue<Vector2Int, float> openSet = new PriorityQueue<Vector2Int, float>();
        Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();
        Dictionary<Vector2Int, float> gScore = new Dictionary<Vector2Int, float>();
        Dictionary<Vector2Int, float> fScore = new Dictionary<Vector2Int, float>();

        openSet.Enqueue(start, 0);
        gScore[start] = 0;
        fScore[start] = Heuristic(start);

        while (openSet.Count > 0)
        {
            Vector2Int current = openSet.Dequeue();

            if (map[current.x, current.y] == TileType.Ocean || map[current.x, current.y] == TileType.ShallowWater)
            {
                return ReconstructPath(cameFrom, current);
            }

            foreach (Vector2Int neighbor in GetNeighbors(current))
            {
                float tentativeGScore = gScore[current] + Cost(current, neighbor);
                if (!gScore.ContainsKey(neighbor) || tentativeGScore < gScore[neighbor])
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeGScore;
                    fScore[neighbor] = gScore[neighbor] + Heuristic(neighbor);

                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Enqueue(neighbor, fScore[neighbor]);
                    }
                }
            }
        }

        return new List<Vector2Int>(); 
    }

    float Heuristic(Vector2Int point)
    {
        return heightMap[point.x, point.y];
    }

    float Cost(Vector2Int from, Vector2Int to)
    {
        return Mathf.Abs(heightMap[from.x, from.y] - heightMap[to.x, to.y]);
    }

    List<Vector2Int> ReconstructPath(Dictionary<Vector2Int, Vector2Int> cameFrom, Vector2Int current)
    {
        List<Vector2Int> totalPath = new List<Vector2Int> { current };
        while (cameFrom.ContainsKey(current))
        {
            current = cameFrom[current];
            totalPath.Add(current);
        }
        totalPath.Reverse();
        return totalPath;
    }

    List<Vector2Int> GetNeighbors(Vector2Int position)
    {
        List<Vector2Int> neighbors = new List<Vector2Int>
        {
            new Vector2Int(position.x + 1, position.y),
            new Vector2Int(position.x - 1, position.y),
            new Vector2Int(position.x, position.y + 1),
            new Vector2Int(position.x, position.y - 1)
        };

        neighbors.RemoveAll(pos => !IsInBounds(pos));
        return neighbors;
    }

    void SuppressInlandWater()
    {
        bool[,] visited = new bool[mapWidth, mapHeight];
        Queue<Vector2Int> queue = new Queue<Vector2Int>();

        // マップの端からフラッドフィルを開始
        for (int x = 0; x < mapWidth; x++)
        {
            if (map[x, 0] == TileType.Ocean) queue.Enqueue(new Vector2Int(x, 0));
            if (map[x, mapHeight - 1] == TileType.Ocean) queue.Enqueue(new Vector2Int(x, mapHeight - 1));
        }
        for (int y = 0; y < mapHeight; y++)
        {
            if (map[0, y] == TileType.Ocean) queue.Enqueue(new Vector2Int(0, y));
            if (map[mapWidth - 1, y] == TileType.Ocean) queue.Enqueue(new Vector2Int(mapWidth - 1, y));
        }

        // 外部海域をマーキング
        while (queue.Count > 0)
        {
            Vector2Int pos = queue.Dequeue();
            if (!IsInBounds(pos) || visited[pos.x, pos.y]) continue;

            visited[pos.x, pos.y] = true;

            if (map[pos.x, pos.y] == TileType.Ocean || map[pos.x, pos.y] == TileType.ShallowWater)
            {
                foreach (var neighbor in GetNeighbors(pos))
                {
                    if (!visited[neighbor.x, neighbor.y])
                    {
                        queue.Enqueue(neighbor);
                    }
                }
            }
        }

        // マーキングされていない水域を内海とみなし陸地に変換
        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                if (!visited[x, y] && (map[x, y] == TileType.Ocean || map[x, y] == TileType.ShallowWater))
                {
                    map[x, y] = TileType.Grass; // 内海を陸地に変換
                }
            }
        }

    }

    void RenderMap()
    {
        foreach (Transform child in transform)
        {
            Destroy(child.gameObject);
        }

        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                GameObject prefabToInstantiate = null;
                switch (map[x, y])
                {
                    case TileType.Ocean: prefabToInstantiate = oceanPrefab; break;
                    case TileType.ShallowWater: prefabToInstantiate = shallowWaterPrefab; break;
                    case TileType.Grass: prefabToInstantiate = grassPrefab; break;
                    case TileType.Forest: prefabToInstantiate = forestPrefab; break;
                    case TileType.Mountain: prefabToInstantiate = mountainPrefab; break;
                    case TileType.Desert: prefabToInstantiate = desertPrefab; break;
                    case TileType.Lake: prefabToInstantiate = lakePrefab; break;
                    case TileType.River: prefabToInstantiate = riverPrefab; break;
                    case TileType.Swamp: prefabToInstantiate = swampPrefab; break;
                    case TileType.Hill: prefabToInstantiate = hillPrefab; break;
                    case TileType.Glacier: prefabToInstantiate = glacierPrefab; break;
                    case TileType.CirqueWall: prefabToInstantiate = cirqueWallPrefab; break;
                }

                if (prefabToInstantiate != null)
                {
                    Instantiate(prefabToInstantiate, new Vector3(x, y), Quaternion.identity, transform);
                }
            }
        }
    }

    bool IsInBounds(Vector2Int position)
    {
        return position.x >= 0 && position.x < mapWidth && position.y >= 0 && position.y < mapHeight;
    }
}

// PriorityQueue クラスの実装
public class PriorityQueue<TElement, TPriority>
{
    private List<(TElement Element, TPriority Priority)> _elements = new List<(TElement Element, TPriority Priority)>();
    private IComparer<TPriority> _comparer;

    public PriorityQueue() : this(Comparer<TPriority>.Default) { }

    public PriorityQueue(IComparer<TPriority> comparer)
    {
        _comparer = comparer ?? throw new ArgumentNullException(nameof(comparer));
    }

    public int Count => _elements.Count;

    public void Enqueue(TElement element, TPriority priority)
    {
        _elements.Add((element, priority));
        _elements.Sort((x, y) => _comparer.Compare(x.Priority, y.Priority));
    }

    public TElement Dequeue()
    {
        if (_elements.Count == 0) throw new InvalidOperationException("The queue is empty.");
        var element = _elements[0];
        _elements.RemoveAt(0);
        return element.Element;
    }

    public bool Contains(TElement element)
    {
        return _elements.Exists(e => EqualityComparer<TElement>.Default.Equals(e.Element, element));
    }
}

参考資料

私がこのコードを作る上で参考にした資料です。
偉大な先人たちに感謝。