Menemukan jalur terpendek pada kisi heksagonal

Saya sedang menulis permainan berbasis giliran yang memiliki beberapa elemen simulasi. Satu tugas yang saya tutup saat ini adalah dengan menemukan jalan. Yang ingin saya lakukan adalah memindahkan setiap belokan seorang petualang AI satu ubin lebih dekat ke targetnya menggunakan x saat ini, dan targetnya x, y.

Dalam mencoba mencari tahu sendiri, saya dapat menentukan 4 arah tanpa masalah dengan menggunakan

dx = currentX - targetY
dy = currentY - targetY

tapi saya tidak yakin bagaimana menentukan 6 arah mana yang sebenarnya merupakan rute "terbaik" atau "terpendek".

Sebagai contoh, cara setup saat ini, saya menggunakan Timur, Barat, NE, NW, SE, SW tetapi untuk sampai ke ubin NE saya pindah ke Timur kemudian NW daripada hanya memindahkan NW.

Saya harap ini tidak semua bertele-tele. Bahkan hanya satu atau dua tautan untuk memulai saya akan menyenangkan. Sebagian besar info yang saya temukan adalah pada menggambar grid dan menggosok sistem koordinat aneh yang dibutuhkan.

Beberapa jawaban!

Sistem koordinat yang paling sering saya lihat untuk traversal berbasis hex adalah sistem di mana pemain dapat bergerak ke setiap arah NSEW normal, serta NW dan SE. Maka Anda hanya membuat setiap baris offset setengah-persegi. Sebagai contoh, lokasi (2,7) dianggap berdekatan dengan (1,7), (3,7), (2,6), (2,8), dan yang aneh: (1,6) dan (3,8). Sementara itu, jika kita mengasumsikan (2,7) ditampilkan di tengah layar, (2,6) akan ditampilkan atas-dan-ke-kanan, (2,8) akan ditampilkan turun-dan-ke -the-left, (1,7) dan (3,7) akan mengurungnya masing-masing ke kiri dan kanan, dan (1,6) dan (3,8) masing-masing akan menempatkan diri mereka atas kiri dan kanan bawah.

Diagram dari apa yang saya maksud:

Jika Anda melakukannya dengan cara ini, menemukan jalur langsung terpendek tidak sulit - menempuh jarak NW / SE maksimum yang Anda bisa tanpa melampaui target Anda sepanjang sumbu kardinal, kemudian berjalan langsung di sepanjang sumbu itu ke target.

Tapi tentu saja itu akan dengan senang hati membawa Anda langsung melewati pegunungan atau medan yang tidak bisa dilewati. Untuk menjawab pertanyaan yang belum Anda tanyakan: Algoritma Pencarian A * adalah pendekatan umum dan cukup baik untuk merintis jalan. Ini tidak hanya akan menangani tata letak non-grid yang aneh, tetapi juga akan dengan senang hati mengatasi rintangan dan bahkan terhambat / lambat.

Saya baru saja memposting perpustakaan utilisasi hex-grid di CodePlex.com di sini: https://hexgridutilities.codeplex.com/ Perpustakaan mencakup path-finding (menggunakan A- * a la Eric Lippert) dan menyertakan utiliti untuk konversi otomatis antara koordinat jagged (disebut Pengguna) dan koordinat non-jagged (disebut Canonical). Algoritma path-findingn memungkinkan biaya langkah untuk setiap node bervariasi baik dengan entri hex dan te dilalui hex-side (meskipun contoh yang diberikan lebih sederhana). Juga, bidang pandang yang ditingkatkan menggunakan pengecoran bayangan disediakan, [edit: kata-kata dihapus].

Berikut adalah contoh kode yang dapat dikonversi dengan mudah antara tiga sistem koordinat hex-grid:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D dan IntVector2D adalah [sunting: homogen] implementasi integer dari affine2D Graphics Vector and Matrix. Pembagian akhir oleh 2 pada aplikasi vektor adalah untuk menormalkan kembali vektor; ini bisa dikubur dalam implementasi IntMatrix2D, tetapi kemudian alasan argumen ke-7 ke konstruktor IntMatrix2D kurang jelas. Perhatikan caching gabungan dan evaluasi malas dari formulasi tidak terkini.

Matriks ini untuk kasus ini:

• Hex butir vertikal;
• Asal di kiri atas untuk koordinat Canonical & User, kiri bawah untuk Koordinat kustom;
• Sumbu Y vertikal ke bawah;
• Sumbu X persegi panjang melintang secara horizontal; dan
• Sumbu X Canonical ke Utara-Timur (yaitu ke atas dan ke kanan, pada 120 derajat CCW dari sumbu Y).

Pustaka kode yang disebutkan di atas menyediakan mekanisme elegan yang sama untuk pengambilan hex (yaitu mengidentifikasi hex yang dipilih dengan klik mouse).

Dalam koordinat Canonical, 6 vektor arah-kardinal adalah (1,0), (0,1), (1,1) dan terbalik mereka untuk semua segi enam, tanpa asimetri dari coordintes bergerigi.

Ini adalah masalah yang terpecahkan, dengan banyak literatur untuk mendukungnya. Sumber daya terbaik yang saya tahu ada di Red Blob Games: https://www.redblobgames.com/grids/hexagons/ .

Singkatnya, alasan yang paling mungkin adalah Anda memulai dengan sistem koordinat yang salah. Menggunakan sistem koordinat Cube yang mengimplementasikan algoritma A * cukup sederhana. Lihat demo langsung di tautan di atas.

Jika Anda benar - benar ingin menggunakan beberapa sistem lain, maka konversikan ke dan dari saat diperlukan.