Pokazuje zasięg na siatce sześciokątnej

Oto sytuacja.

Mam sześciokątną planszę i jednostkę na niej o wartości prędkości lub ruchu 4. Różny teren ma inne koszty. Kiedy kliknę na jednostkę, gra powinna pokazać mi zakres ruchu.

Moim rozwiązaniem było sprawdzenie każdego heksa w zakresie 4, z wyszukiwaniem ścieżki A *, a jeśli koszt ścieżki był mniejszy niż 4, to ten heks był w zasięgu. Na koniec gra ładnie pokazuje mi zasięg tej jednostki.

Moje pytanie brzmi: czy istnieje inne rozwiązanie do wyszukiwania zasięgu na siatce szesnastkowej lub kwadratowej, ponieważ nawet jeśli jestem naprawdę dumny z tego, co zrobiłem w moim rozwiązaniu, myślę, że to trochę przesadzone? :))

Co sprawia, że ​​zadaję to pytanie? Zauważyłem, że gdy prędkość jednostki wynosi 4, 6 lub nawet 8, czas na zasięg obliczeniowy dla mojego komputera był naprawdę dobry, ale kiedy prędkość wynosiła 10 i więcej, zauważyłem, że muszę poczekać kilka sekund na obliczenie .Cóż w prawdziwych grach raczej nie widzę czegoś takiego, a moje wyszukiwanie A * jest raczej dobrze zoptymalizowane, więc myślę, że moje rozwiązanie jest złe.

Dziękuję za wszelkie odpowiedzi.

Masz rację, że A * to trochę przesada, ale niewiele. Nie powinieneś widzieć opóźnień tak jak ty. A * to tak naprawdę tylko zmodyfikowany algorytm Dijikstry . Ponieważ nie używasz pozycji końcowej (ponieważ twoja pozycja końcowa jest tylko „tak daleko, jak to możliwe”), użycie A * z dodaną heurystyką nie jest konieczne. Wystarczy użyć Dijikstra lub prostego wyszukiwania , wystarczy pierwsze wyszukiwanie .

Na przykład Dikikstra rozłoży się równomiernie we wszystkich kierunkach:

(Proste wyszukiwanie po raz pierwszy będzie wyglądać podobnie do tego)

Śledź koszty podróży do każdego węzła. Gdy węzeł osiągnie maksymalny koszt podróży, nie przetwarzaj dalej połączonych węzłów. (Podobnie do miejsca, w którym węzły biegną do ściany poniżej).

Jeśli masz problemy z wydajnością przy zaledwie 10 węzłach, możesz sprawdzić, w jaki sposób uzyskujesz dostęp do tych węzłów. Pierwsze wyszukiwanie powinno być w stanie poruszać się po setkach węzłów bez zauważalnego opóźnienia (na pewno nie kilka sekund). Zastanów się nad zapisaniem prostej wersji swojego świata w formie wykresu, aby móc szybko przejść.

Amit Patel zapewnił doskonałe źródło informacji o zasięgach na swojej stronie . W artykule używa następującego algorytmu do zbierania kafelków heksów w zakresie:

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)))

Spowoduje to utworzenie granic wyrównanych do siatki heksadecymalnej:

Znajduje to wszystkie heksy w pewnej odległości od centralnego heksa, jeśli chcesz rozważyć przeszkody, skorzystaj z szerokości pierwszego wyszukiwania z mojej drugiej odpowiedzi.

Jeśli ktoś tego potrzebuje, oto implementacja algorytmu Patel w języku C #:

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;
    }