Menampilkan rentang pada kisi heksagonal

Inilah situasinya.

Saya memiliki papan heksagonal, dan sebuah unit di atasnya, dengan kecepatan atau nilai bergerak 4. Medan yang lebih berat memiliki biaya yang berbeda. Ketika saya mengklik unit tersebut, permainan akan menunjukkan kisaran bergerak.

Solusi saya adalah memeriksa setiap hex dalam kisaran 4, dengan pathfinding A *, dan jika biaya path kurang dari 4 maka hex ini berada dalam range. Akhirnya permainan dengan baik menunjukkan kisaran unit itu.

Pertanyaan saya adalah: Apakah ada solusi lain untuk mencari jangkauan pada hex grid atau kotak persegi, karena walaupun saya benar-benar bangga dengan apa yang saya lakukan dalam solusi saya, saya pikir, ini sedikit berlebihan? :))

Apa yang membuat saya mengajukan pertanyaan ini? Saya perhatikan bahwa ketika kecepatan unit adalah 4 atau 6 atau bahkan 8, waktu untuk rentang komputasi untuk komputer saya benar-benar baik, tetapi ketika kecepatannya 10 dan lebih saya perhatikan bahwa saya perlu menunggu beberapa detik untuk menghitung . Nah di game nyata saya agak tidak melihat sesuatu seperti ini dan pathfinding A * saya agak dioptimalkan dengan baik, jadi saya berpikir bahwa solusi saya salah.

Terima kasih atas balasannya.

Anda benar bahwa A * sedikit berlebihan, tetapi tidak banyak. Anda seharusnya tidak melihat penundaan seperti Anda. A * sebenarnya hanya algoritma Dijikstra yang dimodifikasi . Karena Anda tidak menggunakan posisi ujung (karena posisi ujung Anda hanya "sejauh yang Anda bisa"), menggunakan A * dengan itu menambahkan heuristik tidak diperlukan. Cukup menggunakan Dijikstra atau pencarian pertama yang sederhana akan cukup.

Misalnya, Dikikstra akan tersebar merata di semua arah:

(Pencarian pertama yang sederhana akan terlihat mirip dengan ini)

Pantau biaya perjalanan ke setiap node. Setelah sebuah node berada pada biaya perjalanan maksimum, jangan memproses node yang terhubung lebih jauh. (Mirip dengan tempat node berjalan ke dinding di bawah).

Jika Anda mengalami masalah kinerja hanya 10 node keluar, Anda akan ingin melihat bagaimana Anda mengakses node. Pencarian pertama yang luas harus dapat menavigasi ratusan node tanpa penundaan yang nyata (tentu saja tidak beberapa detik). Pertimbangkan menyimpan versi dunia Anda yang sederhana dalam format grafik, untuk traversal cepat.

Amit Patel telah menyediakan sumber yang bagus untuk mendapatkan rentang di situsnya . Dalam artikel tersebut, ia menggunakan algoritme berikut untuk mengumpulkan ubin hex dalam rentang:

for each -N ≤ Δx ≤ N:
    for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N):
        Δz = -Δx-Δy
        results.append(H.add(Cube(Δx, Δy, Δz)))

Ini membuat batas selaras dengan kisi hex:

Ini akan menemukan semua heks dalam jarak tertentu dari heks tengah, jika Anda ingin mempertimbangkan hambatan, gunakan pencarian pertama yang luas dari jawaban saya yang lain.

Jika ada yang membutuhkannya, inilah implementasi C # dari algoritma Patel:

IEnumerable<Hex> GetRange(Hex center, int range)
    {
        var inRange = new List<Hex>();
        for (int q = -range; q <= range; q++)
        {
            int r1 = Math.Max(-range, -q - range);
            int r2 = Math.Min(range, -q + range);
            for (int r = r1; r <= r2; r++)
            {
                inRange.Add(center.Add(new Hex(q, r, -q - r)));
            }
        }

        return inRange;
    }