Saya membuat game 2d untuk situs web di mana alam semesta dapat tumbuh sangat besar (pada dasarnya sangat besar). Awalnya, alam semesta terdiri dari 6 bintang yang jaraknya sama dari titik asal (0, 0). Tugas saya adalah untuk dapat menghasilkan lebih banyak bintang yang akan memiliki "jalur" (tepi) yang terhubung satu sama lain. Bagaimana saya bisa merancang algoritma yang memenuhi batasan ini:
- Bintang-bintang dihasilkan secara acak. (mis. (x, y) koordinat untuk bintang baru perlahan-lahan akan keluar dari (0, 0) ke segala arah, lebih disukai dalam format spiral)
- Tepi TIDAK akan menyeberang.
- Meskipun harus ada beberapa variasi, bintang baru tidak boleh terlalu jauh atau terlalu dekat dengan bintang lain. (Misalnya harus ada radius minimum)
- Tidak ada bintang / titik harus memiliki multiplisitas lebih dari 3.
- Mengingat bahwa semua ini akan disimpan dalam Database, algoritme tidak dapat terlalu mahal. Dengan kata lain, saya ingin mencapai sesuatu dengan kompleksitas O (n) (Saya tidak tahu apakah ini layak).
Pada dasarnya, apa yang akan saya tuju adalah galaksi berbentuk spiral di mana bintang-bintang adalah titik pada grafik dan perjalanan antar bintang digambarkan oleh tepian antara bintang-bintang itu.
Langkah-langkah khusus yang perlu saya selesaikan adalah:
- Secara acak menghasilkan titik di sekitar tetangga bintang lain yang belum memiliki multiplisitas 3.
- Temukan bintang pertama yang belum memiliki multiplisitas 3 yang tidak akan menghasilkan konflik tepi.
- Jika bintang berjarak jarak minimum x unit maka buatlah tepi antara dua titik.
Saya mencoba mencari solusi, tetapi keterampilan matematika saya (dan pengetahuan tentang Teori Grafik) membutuhkan banyak pekerjaan. Juga, setiap sumber daya / tautan tentang hal ini akan sangat dihargai.
Berikut adalah beberapa pseudo-code yang saya pikirkan, tetapi saya tidak yakin apakah ini akan berhasil dan saya yakin itu tidak akan bekerja dengan sangat baik setelah beberapa 10.000 bintang, dll.
newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
for (star in the known universe):
if(distance between newStar and star > x units):
if(star has < 3 multiplicity):
if(path from newStar to star does not intersect another path):
connect the star to the other star
break;
newStar = new random (x, y) coordinate
Juga, jika ada yang punya saran tentang bagaimana saya harus menyimpan ini di database MySQL, saya juga akan menghargai itu.
Akhirnya, jika tidak ada yang masuk akal di atas, saya telah memasukkan gambar dari apa yang ingin saya capai di bawah ini:
sumber
Jawaban:
Saran: Jaga agar jaringan semesta internal tertata dengan sempurna, algoritmik, dan relatif sederhana. Anda hanya perlu semesta untuk terlihat acak ketika ditampilkan di layar pengguna . Hanya terapkan offset acak ke posisi bintang untuk tampilan pengguna.
Masalah: Pendekatan yang paling jelas menghitung offset acak untuk setiap bintang tidak akan melakukan pekerjaan yang sangat baik untuk menyembunyikan struktur sebenarnya yang mendasarinya. Anda hanya dapat mengacak bintang dengan jumlah kecil sebelum berisiko bertabrakan satu sama lain atau melewati jalur.
Solusi: Anda dapat menerapkan distorsi acak besar dan mendapatkan semesta tampak jauh lebih acak dan menarik jika Anda menerapkan keacakan non-lokal terkoordinasi. Bayangkan menempatkan bintang-bintang di atas lembaran karet, dan bayangkan secara acak merentangkan dan menekan bagian-bagian yang berbeda dari lembaran itu. Itu bisa menggeser seluruh kelompok bintang dengan jarak yang jauh. Mereka tidak akan pernah bertabrakan atau menyeberang karena bintang-bintang di dekatnya meregang dan menipis dalam hubungannya satu sama lain.
Cara melakukannya: Cari generator medan fraktal. Ada banyak kode gratis dan terbuka untuk itu. Anda hanya memerlukan kode dasar yang menghasilkan nilai ketinggian untuk setiap titik di peta. Kami akan menggunakannya dengan cara yang berbeda. Gunakan kode itu untuk menghasilkan DUA peta terrain-height independen. Mulailah dengan X, posisi Y, bintang yang sebenarnya, lihat lokasi di setiap peta, gunakan satu nilai peta untuk mengimbangi posisi tampilan X bintang dan gunakan nilai peta lainnya untuk mengimbangi posisi tampilan Y bintang. Anda harus bermain dengan beberapa faktor penskalaan, tetapi itu dapat memberi Anda efek lembaran karet yang melengkung secara acak. Variasi besar dalam posisi bintang harus sepenuhnya menyembunyikan posisi pesanan yang mendasarinya. Sifat fraktal dari keacakan akan memberikan efek yang terlihat sangat alami,
sumber