Pokazuje zasięg na siatce sześciokątnej


10

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.


1
Zgadzam się z Byte56, że szeroki algorytm pierwszego wyszukiwania jest dobrym rozwiązaniem. Nie oznacza to, że nie powinieneś próbować być kreatywnym, ale jeśli chodzi o dobrze znane algorytmy, jest to dobry, który dobrze się stosuje.
theJollySin

Odpowiedzi:


11

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:

wprowadź opis zdjęcia tutaj

(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ść.


czy potrafisz znaleźć odległość między dwoma węzłami za pomocą BFS i biorąc pod uwagę przeszkody / różne ciężary?
Łukasz B.

Koszt przenoszenia między węzłami powinien być w większości wstępnie obliczony. Koszt nie jest obliczany przy użyciu BFS, BFS jest algorytmem przemierzającym węzły. Sposób określania kosztu podróży z jednego węzła do drugiego jest niezależny od sposobu przechodzenia przez węzły.
MichaelHouse

Dzięki, teraz rozumiem, dlaczego moje myślenie było błędne, kluczem do tego było stwierdzenie „Ponieważ nie używasz pozycji końcowej (ponieważ twoja pozycja końcowa jest po prostu„ tak daleko, jak możesz ”). W moim rozwiązaniu Miałem pozycję końcową, to była jednostka. Właśnie rozwiązałem problem ze złego kierunku. Najpierw wyznaczyłem granicę, a potem stamtąd wróciłem do mojej jednostki, w ten sposób prawdopodobnie wiele razy przeszedłem przez te same węzły. kiedy moja prędkość rośnie, liczba obliczeń również rośnie. Jak mi pokazałeś, zawsze odwiedzę węzeł raz. Po prostu miałem zły punkt widzenia, naprawdę dzięki, to bardzo upraszcza.
user23673,

4

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 = xy
        results.append(H.add(Cubex, Δy, Δz)))

Spowoduje to utworzenie granic wyrównanych do siatki heksadecymalnej:

wprowadź opis zdjęcia tutaj

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.


1

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;
    }
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.