Apakah kotak persegi atau hex lebih baik untuk merintis jalan?

17

Apakah ada perbedaan yang signifikan antara menggunakan kotak persegi atau heksagonal untuk area yang dicari oleh algoritma pencarian jalur. Dengan kata lain, lebih baik persegi atau heksagonal, dan jika demikian mengapa.

ai path-finding Edwin Earl Ross
sumber
4
Methinks Anda harus menggunakan apa pun yang sesuai dengan gameplay Anda;)
Andrew Russell

Jawaban:

19

Pertimbangan utama untuk memutuskan apakah akan menggunakan kuadrat vs kisi hex seharusnya bukan kemudahan implementasi AI - algoritma pencarian luas-pertama dan kedalaman-pertama hampir sama tidak peduli apa pun jenis grafik yang Anda miliki.

Sebaliknya, ini adalah masalah gameplay yang harus dipertimbangkan oleh para desainer game. Kotak persegi lebih mudah diakses oleh pasar massal (papan hex cenderung terlihat "culun"), dan dalam dunia kontrol atas / bawah / kiri / kanan itu jauh lebih intuitif untuk menavigasi di sekitar kotak daripada hex dari sudut pandang UI. Kotak kotak juga cenderung membatasi gerakan sedikit lebih banyak; dengan asumsi gerakan ortogonal (dan bukan diagonal), dibutuhkan 4 gerakan untuk berjalan mengelilingi rintangan satu-persegi, dibandingkan dengan 3 gerakan dalam kotak hex. Dari sudut pandang pemrograman, heks juga sedikit lebih mudah untuk diimplementasikan tetapi ini bukan tentang algoritma pencarian sebanyak bahwa kotak persegi sama dengan array dua dimensi, tetapi kotak hex tidak benar-benar memetakan ke struktur data standar.

Sisi bawah dari kotak persegi adalah bahwa gerakan itu tidak pernah terasa benar. Bergerak secara diagonal harus mengambil titik gerakan sqrt (2), tetapi dalam praktiknya gerakan 1 (yang membuatnya terasa seperti berjalan di diagonal cepat dan jarang ada alasan untuk berjalan secara ortogonal) atau itu adalah 2 gerakan (yang membuat gerakan diagonal terasa terlalu lambat ). Dengan kisi-kisi hex, jarak gerakan jauh lebih intuitif, karena jarak selalu sama dari satu hex ke yang lain tidak peduli jalan mana yang Anda ambil.

Ian Schreiber
sumber
4
+1. Ini adalah keputusan desain, bukan keputusan AI. Jika Anda menginginkan kisi heksagonal, kisi kotak offset seperti www-cs-students.stanford.edu/~amitp/game-programming/grids/… mungkin kurang menakutkan bagi pemain biasa, dan secara matematis setara dengan hexagon. Juga, itu adalah representasi dalam memori yang nyaman juga.
2
+1 untuk kalimat "Kotak persegi lebih mudah diakses oleh pasar massal (papan hex cenderung terlihat" culun ")": D
Kornel Kisielewicz
Edwin tidak menanyakan apa yang lebih baik pada game berbasis grid. Dia bertanya apa yang lebih baik bagi AI untuk menggunakan kuadrat atau segi enam. Dunia dan gameplay itu sendiri tidak harus dibatasi untuk itu, hanya apa node AI mencari.
AttackingHobo
Saya telah mengimplementasikan game strategi berbasis giliran dengan kisi hex dan kuadrat, dan sama sekali tidak ada perbedaan yang diperlukan dalam hal kompleksitas pathfinding. Saya bahkan mengganti satu game dari peta hex ke peta persegi, dan (terlepas dari rendering) satu-satunya perubahan yang saya buat adalah metode MapLocation :: GetDistance () yang menghitung jarak antara dua sektor. Saya hanya perlu menyesuaikan perhitungan agar setiap baris lainnya diimbangi sedikit. Dalam kedua kasus, Anda dapat menggunakan representasi dalam memori yang sama. Jadi, seperti yang dikatakan orang lain, ini benar-benar masalah desain.
Mike Strobel
4
Di samping itu, heks dapat dipetakan ke array 2 dimensi. Bayangkan sebuah kotak persegi, lalu geser setiap kolom genap setengah langkah ke bawah. Anda sudah mendapatkan grid kuadrat offset sekarang, yang isomorfis ke kisi hex
Asmor
3

Saya bukan ahli AI dengan cara apa pun, tetapi perbedaannya harus diabaikan. Kotak persegi sedikit lebih cepat (4 koneksi per node, bukan 6), tapi itu bukan faktor pembatas dalam runtime algoritmik. Bergantung pada algoritma apa yang Anda rencanakan untuk digunakan, kode tersebut mungkin sedikit lebih kompleks untuk hex grid, karena sedikit lebih rumit untuk menghitung koordinat, dan lebih sulit untuk menggunakan semacam pintasan quadtree / octree yang saya percaya adalah sering digunakan dalam pencarian jalan.

Tetapi untuk dunia sederhana seperti tingkat permainan strategi turn-based, perbedaan antara dua tata letak seharusnya tidak terlalu berarti; kotak persegi akan sedikit lebih sederhana dan lebih cepat.

Gregory Avery-Weir
sumber
5
"Kotak persegi sedikit lebih cepat (4 koneksi per node, bukan 6)" - kecuali Anda dapat melakukan perjalanan diagonal, dalam hal ini 8 koneksi vs 6.
Ian Schreiber
Sentuh. Anda sepenuhnya benar; tentu saja koneksi diagonal mungkin.
Gregory Avery-Weir
3

Ada satu perbedaan praktis yang bisa saya pikirkan mengenai perencanaan jalur. Melintasi dari pusat sel heks ke ke tetangganya selalu jarak yang sama sedangkan, jika Anda mengizinkan perjalanan diagonal, ini tidak benar untuk kotak.

Clodéric
sumber
0

Panduan tentang segi enam ini mengagumkan. Bagian tentang pathfinding memiliki contoh interaktif dan beberapa info tentang cara menyesuaikan pathfinding persegi.

Jika Anda menggunakan pathfinding berbasis grafik seperti A * atau algoritma Dijkstra atau Floyd-Warshall, pathfinding pada hex grid tidak berbeda dengan pathfinding pada grid persegi.

  • Tetangga. Contoh kode yang saya berikan di tutorial pathfinding memanggil graph.neighbors untuk mendapatkan tetangga dari suatu lokasi. Gunakan fungsi di bagian tetangga untuk ini. Saring tetangga yang tidak bisa dilewati.
  • Heuristis. Kode sampel untuk A * menggunakan fungsi heuristik yang memberikan jarak antara dua lokasi. Gunakan rumus jarak, diskalakan agar sesuai dengan biaya pergerakan. Misalnya jika biaya pergerakan Anda adalah 5 per hex, maka kalikan jaraknya dengan 5.
Menandai
sumber