Mencari algoritme pembuatan peta dunia yang bagus [tutup]

Saya sedang mengerjakan game mirip Peradaban dan saya sedang mencari algoritme yang bagus untuk menghasilkan peta dunia mirip Bumi. Saya telah bereksperimen dengan beberapa alternatif, tetapi belum menemukan pemenang yang sebenarnya.

Salah satu opsinya adalah membuat peta ketinggian menggunakan kebisingan Perlin dan menambahkan air pada tingkat tertentu sehingga sekitar 30% dunia adalah daratan. Sementara kebisingan Perlin (atau teknik berbasis fraktal serupa) sering digunakan untuk medan dan cukup realistis, itu tidak menawarkan banyak cara untuk mengontrol jumlah, ukuran dan posisi benua yang dihasilkan, yang saya ingin miliki dari perspektif gameplay.

Pilihan kedua adalah memulai dengan benih satu ubin yang diposisikan secara acak (saya sedang mengerjakan kisi ubin), tentukan ukuran yang diinginkan untuk benua dan setiap belokan tambahkan ubin yang secara horizontal atau vertikal berdekatan dengan benua yang ada sampai Anda telah mencapai ukuran yang diinginkan. Ulangi untuk benua lain. Teknik ini adalah bagian dari algoritma yang digunakan dalam Civilization 4. Masalahnya adalah bahwa setelah menempatkan beberapa benua pertama, adalah mungkin untuk memilih lokasi awal yang dikelilingi oleh benua lain, dan dengan demikian tidak akan cocok dengan yang baru. Juga, ia memiliki kecenderungan untuk menelurkan benua yang terlalu berdekatan, menghasilkan sesuatu yang lebih mirip sungai daripada benua.

Adakah yang kebetulan mengetahui algoritme yang baik untuk menghasilkan benua yang realistis pada peta berbasis grid sambil tetap mengontrol jumlah dan ukuran relatifnya?

Anda dapat mengambil isyarat dari alam dan memodifikasi ide kedua Anda. Setelah Anda membuat benua Anda (yang semuanya berukuran hampir sama), buatlah benua itu bergerak secara acak dan berputar serta bertabrakan dan mengubah bentuk satu sama lain dan saling menjauh. (Catatan: ini mungkin bukan hal termudah yang pernah diterapkan.)

Sunting: Berikut cara lain untuk melakukannya, lengkap dengan implementasi - Pembuatan Peta Poligonal untuk Game .

Saya sarankan Anda kembali dan

1. Pikirkan tentang apa yang membuat benua "baik".
2. Tulis algoritme yang dapat membedakan tata letak benua yang baik dari yang buruk.
3. Sempurnakan algoritme sehingga Anda dapat mengukur seberapa bagus tata letak yang baik.

Setelah Anda memilikinya, Anda dapat mulai menerapkan algoritme yang seharusnya berbentuk seperti ini:

• Hasilkan benua yang jelek dan kemudian perbaiki.

Untuk peningkatan, Anda dapat mencoba semua jenis trik pengoptimalan standar, apakah itu anil simulasi, pemrograman genetik, atau sesuatu yang benar-benar ad hoc , seperti memindahkan persegi tepi yang dipilih secara acak dari mana pun ia berada di benua ke tepi yang berlawanan dengan pusat massa benua. Tetapi kuncinya adalah mampu menulis program yang dapat membedakan benua yang baik dari yang buruk. Mulailah dengan benua yang digambar tangan serta benua uji Anda, sampai Anda mendapatkan sesuatu yang Anda sukai.

Saya menulis sesuatu yang mirip dengan apa yang Anda cari untuk tiruan gaya screensaver otomatis dari Peradaban 1. Sebagai catatan, saya menulis ini di VB.net tetapi karena Anda tidak menyebutkan apa pun tentang bahasa atau platform dalam pertanyaan Anda, saya akan terus itu abstrak.

"Peta" menentukan jumlah benua, varians ukuran benua (misalnya 1.0 akan membuat semua benua dengan perkiraan luas daratan yang sama, turun ke 0.1 akan memungkinkan benua ada dengan 1/10 massa benua terbesar), luas daratan maksimum (sebagai persentase) untuk menghasilkan, dan bias lahan pusat. Sebuah "benih" didistribusikan secara acak di sekitar peta untuk setiap benua, berbobot ke arah tengah peta sesuai dengan bias pusat (misalnya bias rendah menghasilkan benua terdistribusi yang lebih mirip dengan Bumi, sedangkan bias pusat yang tinggi akan lebih menyerupai Pangea). Kemudian untuk setiap iterasi pertumbuhan, "benih" menetapkan ubin tanah sesuai dengan algoritma distribusi (lebih lanjut nanti) sampai luas lahan maksimum tercapai.

Algoritme distribusi tanah bisa setepat yang Anda inginkan, tetapi saya menemukan hasil yang lebih menarik dengan menerapkan berbagai algoritme genetika dan melempar dadu. "Game of Life" dari Conway benar-benar mudah untuk dimulai. Anda perlu menambahkan BEBERAPA logika yang sadar secara global untuk menghindari hal-hal seperti benua tumbuh satu sama lain, tetapi sebagian besar hal akan berjalan dengan sendirinya. Masalah yang saya temukan dengan pendekatan yang lebih berbasis fraktal (yang merupakan kecenderungan pertama saya) adalah hasilnya terlihat terlalu berpola, atau menyebabkan terlalu banyak skenario yang membutuhkan aturan pemecahan masalah yang bersifat hacky untuk mendapatkan hasil yang masih belum terasa cukup dinamis. Bergantung pada algoritme yang Anda gunakan, Anda mungkin ingin menerapkan "pengaburan" pada hasil untuk menghilangkan hal-hal seperti ubin samudra persegi tunggal yang berlimpah dan garis pantai berpetak-petak. Jika sesuatu seperti benua yang sedang berkembang biak dikelilingi oleh beberapa lainnya dan tidak memiliki tempat tersisa untuk tumbuh, pindahkan benih ke titik baru di peta dan lanjutkan pertumbuhannya. Ya, itu bisa berarti Anda kadang-kadang berakhir dengan lebih banyak benua daripada yang direncanakan, tetapi jika itu benar-benar sesuatu yang sangat tidak Anda inginkan maka cara lain untuk membantu menghindarinya adalah bias algoritma pertumbuhan sehingga mereka mendukung pertumbuhan ke arah yang paling tidak dekat dengan yang lain. biji. Paling buruk (menurut saya), Anda dapat menandai seri sebagai tidak valid ketika benih tidak memiliki tempat lagi untuk tumbuh dan menghasilkan peta baru. Pastikan Anda menetapkan jumlah percobaan maksimum sehingga jika ada sesuatu yang tidak realistis (seperti menyesuaikan 50 benua dengan bobot genap di papan 10x10), tidak akan menghabiskan waktu selamanya untuk mencoba menemukan solusi yang valid.

Saya tidak bisa menjamin bagaimana Civ dll melakukannya, dan tentu saja tidak mencakup hal-hal seperti iklim, umur tanah, dll. Tetapi dengan bermain-main dengan algoritma pertumbuhan benih Anda bisa mendapatkan hasil yang cukup menarik yang menyerupai benua, kepulauan dll. Anda bisa menggunakan pendekatan yang sama untuk menghasilkan sungai yang tampak 'organik', pegunungan, dll.

Saya telah membuat sesuatu yang mirip dengan gambar pertama Anda di JavaScript. Ini tidak super canggih tetapi berhasil:

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>

Artikel pembuatan peta poligonal menjelaskan langkah demi langkah pembuatan peta unsing poligon Voronoi.

Orang ini juga memberikan semua kode sumber. Ini Flash (ActionScript 3 / ECMAScript) tetapi dapat ditransposisi ke bahasa berorientasi objek lainnya

Atau coba gunakan algoritma yang diimplementasikan di beberapa perangkat lunak lingkungan fraktal seperti TerraJ

Hanya memikirkan manset di sini:

Pilih beberapa titik awal, dan tetapkan masing-masing ukuran yang digambar secara acak (diharapkan). Anda dapat mempertahankan gambar ukuran terpisah untuk benua yang direncanakan dan pulau yang direncanakan jika Anda mau.

Lingkarkan elemen-elemen tanah, dan jika mereka belum mencapai ukuran yang direncanakan, tambahkan satu persegi. Tetapi bagian yang menyenangkan adalah menimbang peluang bahwa setiap elemen yang bertetangga akan menjadi satu. Beberapa hal yang disarankan yang mungkin menjadi faktor:

1. Jarak ke tanah "lain" terdekat. Lebih jauh lebih baik menghasilkan ruang samudra yang luas. Lebih dekat lebih baik membuat saluran sempit. Anda harus memutuskan apakah Anda akan membiarkan bit bergabung juga.
2. Jarak dari biji. Lebih dekat lebih baik berarti massa tanah padat, lebih jauh lebih baik berarti bit-bit yang dirangkai panjang
3. Banyaknya petak-petak tanah yang berdekatan. Pembobotan yang mendukung banyak kotak yang berdekatan memberi Anda pantai yang mulus, lebih memilih sedikit yang memberi Anda banyak jalan masuk dan semenanjung.
4. Adanya kotak "sumber daya" di sekitar? Tergantung pada aturan permainan, kapan Anda menghasilkan kuadrat sumber daya, dan apakah Anda ingin membuatnya mudah.
5. Apakah Anda mengizinkan bit untuk mendekati atau bergabung dengan kutub?
6. ??? tidak tahu apa lagi

Lanjutkan sampai semua daratan mencapai ukuran yang direncanakan atau tidak dapat tumbuh lagi karena suatu alasan.

Perhatikan bahwa melakukan parameter pada faktor pembobotan ini memungkinkan Anda menyesuaikan jenis dunia yang dihasilkan, yang merupakan fitur yang saya sukai dari beberapa Civ.

Dengan cara ini Anda perlu melakukan pembuatan medan pada setiap bit secara terpisah.

Anda dapat mencoba algoritma persegi berlian atau kebisingan perlin untuk menghasilkan sesuatu seperti peta ketinggian. Kemudian, tetapkan nilai rentang ke apa yang muncul di peta. Jika "ketinggian" Anda dari 0 hingga 100, buatlah 0 - 20 air, 20 - 30 pantai, 30 - 80 rumput, 80 - 100 gunung. Saya pikir notch melakukan sesuatu yang mirip dengan ini di minicraft, tapi saya bukan ahli, saya hanya dalam pola pikir berlian persegi setelah akhirnya membuatnya bekerja.

Saya pikir Anda dapat menggunakan pendekatan gaya "pemrograman dinamis" di sini.

Selesaikan masalah kecil terlebih dahulu dan gabungkan solusi dengan cerdas untuk menyelesaikan masalah yang lebih besar.

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

Akan sangat baik untuk melihat beberapa "Algoritma Tata Letak Grafik"

• Algoritma Berbasis Paksa
• Algoritma Genetika untuk Tata Letak Grafik

Anda dapat memodifikasinya agar sesuai dengan tujuan Anda.

Saya punya ide untuk pembuatan peta yang mirip dengan jawaban lempeng tektonik. Itu terjadi seperti ini:

1. menyapu melalui kotak-kotak grid yang memberikan setiap kotak sebuah kotak "tanah" jika rnd <= 0,292 (persentase sebenarnya dari tanah kering di planet bumi).
2. Migrasikan setiap bagian tanah satu persegi menuju tetangga terdekatnya yang lebih besar. Jika tetangga memiliki jarak yang sama, pergi ke bagian yang lebih besar. Jika potongan berukuran sama, pilih satu secara acak.
3. jika dua bidang tanah bersentuhan, kelompokkan menjadi satu bagian, mulai sekarang pindahkan semua kotak menjadi satu.
4. ulangi dari langkah 2. Hentikan jika semua potongan telah terhubung.

Ini mirip dengan cara kerja gravitasi dalam ruang 3D. Ini cukup rumit. Algoritme yang lebih sederhana untuk kebutuhan Anda akan berfungsi sebagai berikut:

1. Masukkan n kotak awal lahan secara acak pada posisi x, y, dan jarak yang dapat diterima satu sama lain. Ini adalah benih untuk benua Anda. (Gunakan teorema Pythagoras untuk memastikan benih memiliki jarak minimum antara mereka sendiri dan yang lainnya.)
2. menelurkan kotak tanah dari kotak tanah yang ada ke arah acak, jika arah itu adalah kotak samudra.
3. ulangi langkah 2. Berhenti saat kotak tanah mengisi 30% dari total ukuran peta.
4. jika benua cukup dekat satu sama lain, jatuhkan jembatan darat sesuai keinginan untuk mensimulasikan efek jenis Panama.
5. Kunjungi pulau kecil dan acak sesuai keinginan untuk tampilan yang lebih alami.
6. untuk setiap bujur sangkar "pulau" tambahan yang Anda tambahkan, potong bujur sangkar laut dan danau dari benua dengan menggunakan algoritma yang sama secara terbalik. Ini akan mempertahankan persentase tanah pada jumlah yang diinginkan.

Beri tahu saya cara kerjanya. Saya sendiri belum pernah mencobanya.

PS. Saya melihat ini mirip dengan apa yang Anda coba. Kecuali itu mengatur semua benih sekaligus, sebelum memulai, sehingga benua akan terpisah cukup jauh dan akan berhenti ketika peta cukup terisi.

Sebenarnya saya belum pernah mencobanya tapi terinspirasi oleh jawaban David Johnstone tentang lempeng tektonik. Saya mencoba menerapkannya sendiri dalam proyek Civ saya yang lama dan ketika harus menangani tabrakan, saya punya ide lain. Alih-alih menghasilkan ubin secara langsung, setiap benua terdiri dari node. Distribusikan massa ke setiap node kemudian buat serangkaian benua "blob" menggunakan pendekatan metaball 2D. Tektonik dan pergeseran benua akan sangat mudah untuk "dipalsukan" hanya dengan memindahkan node di sekitarnya. Bergantung pada seberapa kompleks Anda ingin pergi, Anda bahkan dapat menerapkan hal-hal seperti arus untuk menangani pergerakan node dan menghasilkan pegunungan yang sesuai dengan batas lempeng yang tumpang tindih. Mungkin tidak akan menambahkan banyak hal ke sisi gameplay,

Penjelasan yang bagus tentang metaballs jika Anda belum pernah bekerja dengannya sebelumnya:

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

Inilah yang saya pikirkan, karena saya akan menerapkan sesuatu seperti ini yang saya miliki untuk game dalam pengembangan. :

Dunia terbagi menjadi beberapa wilayah. Tergantung pada ukuran dunia, itu akan menentukan berapa banyak wilayah. Untuk contoh ini, kami akan mengasumsikan dunia berukuran sedang, dengan 6 wilayah. Setiap zona grid dibagi menjadi 9 zona grid. zona grid tersebut masing-masing dibagi menjadi 9 grid. (ini bukan untuk pergerakan karakter, tetapi hanya untuk pembuatan peta) Grid untuk bioma, zona grid untuk fitur daratan yang melengkung, (benua vs laut) dan wilayah untuk iklim keseluruhan. Kisi-kisi terurai menjadi ubin.

Dibuat secara acak, daerah-daerah tersebut mendapatkan set iklim logis. Zona kisi ditetapkan secara acak, misalnya; laut atau darat. Grid mendapatkan bioma secara acak dengan pengubah berdasarkan zona grid dan iklimnya, seperti hutan, gurun, dataran, glasial, rawa atau vulkanik. Setelah semua dasar-dasar tersebut ditetapkan, saatnya untuk memadukannya, menggunakan fungsi berbasis persentase acak yang mengisi set petak. Sebagai contoh; jika Anda memiliki bioma hutan, di samping bioma gurun, Anda memiliki algoritme yang mengurangi kemungkinan petak menjadi "hutan" dan meningkatkannya menjadi "deserty". Jadi, sekitar setengah jalan di antara keduanya, Anda akan melihat semacam pengaruh campuran yang menggabungkan dua bioma untuk menghasilkan transisi yang agak mulus di antara keduanya. Transisi dari satu zona grid ke zona berikutnya mungkin akan membutuhkan sedikit lebih banyak pekerjaan untuk memastikan formasi logika landmass. Seperti, misalnya, bioma dari satu zona grid yang menyentuh bioma dari yang lain, alih-alih memiliki persentase peralihan sederhana berdasarkan kedekatan. Misalnya ada 50 ubin dari pusat bioma ke tepi bioma, artinya ada 50 ubin dari tepi yang disentuhnya ke tengah bioma berikutnya. Itu secara logis akan meninggalkan perubahan 100% dari satu bioma ke bioma berikutnya. Jadi, saat ubin semakin dekat dengan batas kedua bioma, persentasenya menyempit menjadi sekitar 60% atau lebih. Menurut saya, tidak bijaksana memberikan terlalu banyak kemungkinan melintasi bioma jauh dari perbatasan, tetapi Anda ingin perbatasannya agak tercampur. Untuk zona grid, perubahan persentase akan jauh lebih jelas. Alih-alih% turun menjadi sekitar 60%, itu hanya akan turun menjadi sekitar 80%. Dan pemeriksaan sekunder kemudian harus dilakukan untuk memastikan bahwa tidak ada ubin air acak di tengah bioma darat di sebelah laut tanpa logika tertentu. Jadi, sambungkan ubin air itu ke massa samudra untuk membuat saluran yang menjelaskan ubin air, atau singkirkan semuanya. Tanah di bioma berbasis air lebih mudah dijelaskan menggunakan singkapan batuan dan semacamnya.

Oh, agak bodoh, maaf.

Saya akan menempatkan medan fraktal menurut beberapa tata letak yang Anda tahu "berfungsi" (misalnya kisi 2x2, berlian, dll, dengan beberapa jitter) tetapi dengan redaman distribusi Gaussian memuncak ke arah tepi pusat benua. Letakkan permukaan air lebih rendah sehingga sebagian besar tanah sampai Anda mendekati tepinya.