Struktur Data untuk Mewakili Koneksi Antar Negara di Peta

9

Dalam sebuah game yang saya kembangkan untuk klien, konsep permainan kunci melibatkan pergerakan di peta. Dalam hal ini ukuran dan bentuk serta dari berbagai negara tidak relevan: pindah dari satu negara ke negara yang berdekatan dihitung sebagai satu langkah.

Saya mencoba mencari tahu struktur data terbaik untuk secara internal mewakili koneksi antar negara. Untuk negara tertentu, permainan perlu mengetahui negara mana yang berbatasan, baik untuk mengetahui cara pemain dapat bergerak serta untuk memungkinkan AI permainan merencanakan rute, menentukan jalur yang mungkin dari satu negara ke negara lain. AI juga perlu mengevaluasi seberapa baik suatu negara terhubung, bukan hanya dengan tetangga yang berdekatan tetapi juga dengan tetangga di negara tersebut, dll.

Saya sudah menemukan beberapa kemungkinan tetapi tampaknya tidak cocok dan tidak efisien. Karena AI perlu menghitung banyak rute yang mungkin untuk membuat keputusan yang baik tentang pergerakannya, "tidak efisien" sangat bermasalah.

Saya menduga bahwa ini adalah teka-teki CS yang agak umum dan bahwa ada solusi umum, tetapi saya belum dapat menemukan banyak dengan mencari. Setiap saran dipersilahkan.

maps efficiency Matthew Frederick
sumber
Jika saya harus menanyakan ini di GameDev.StackExchange, beri tahu saya. Saya bertanya di sini karena saya yakin hal semacam ini diperlukan untuk semua jenis masalah pembangunan dan saya tidak perlu bantuan dengan sisi "permainan" itu, per se, hanya bagian perencanaan rute.
Matthew Frederick
Anda memerlukan grafik atau matriks konektivitas (yang berguna, karena penutupan mudah untuk dihitung). Mungkin Anda membutuhkan keduanya. Lihatlah mereka.
2
Lihatlah struktur data grafik dan algoritma: en.wikipedia.org/wiki/Graph_%28data_structure%29
1
Ini tidak sesuai dengan topik saya. Itu harus di GameDev atau Stack Overflow, karena itu topik yang terlalu objektif untuk di sini.

Jawaban:

6

Jelas sebuah Grafik. Lihat di sini Grafik Theory , pada dasarnya Anda mendapatkan node dan edge. Sebuah node dapat berisi 0 atau lebih ujung ke node lain.

Ada banyak algoritma untuk menghitung jalur terpendek (hop atau jarak), periksa cicle (lebih dari satu cara untuk mencapai satu diri), dll.

Sekarang, untuk dapat mengimplementasikan solusi yang efisien, itu sedikit lebih kompleks, tetapi seperti biasa, ada cara.


sumber
Luar biasa terima kasih. Apakah Anda punya saran untuk menemukan algoritma seperti itu? Saya tidak membutuhkan jalur terpendek begitu banyak, tetapi hal-hal seperti memeriksa lingkaran, dll akan sangat berguna.
Matthew Frederick
2

Seperti yang telah disebutkan, Anda akan membutuhkan grafik yang mewakili semua kemungkinan koneksi antar negara. Setiap koneksi juga akan menahan jarak antara dua negara.

Kemudian algoritma pencarian jalur seperti A * dapat digunakan untuk menentukan jalur terpendek antara dua negara.

Ada juga beberapa buku bagus tentang gim ai: Gim AI dengan contoh oleh Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

atau seri AI Game Programming Wisdom. http://www.aiwisdom.com/ Buku pertama memiliki beberapa bab tentang merintis jalan.

Stephen
sumber
Luar biasa, terima kasih atas buku petunjuknya. Tampaknya ada banyak buku AI dan rekomendasi pribadi jauh lebih baik daripada hasil luas yang saya dapatkan dari pencarian.
Matthew Frederick