Znajdź najkrótszą drogę przez przeszkody, gdy wszystkie normalne ścieżki są zablokowane

Robię Tower Defense i mam podstawowe wyszukiwanie ścieżek, ale mam problem.

Chcę zablokować ścieżkę, a gdy nastąpi blok, biegacze zaatakują wieże blokujące.

Potrzebuję więc sposobu na znalezienie najkrótszej ścieżki, która - co ważniejsze - ma najmniejszą liczbę wież na drodze.

Jak mogę to zrobić?

algorithm path-finding tower-defense

— Dani
źródło

czy nie byłoby to wykrywanie kolizji na twojej ścieżce, po której można chodzić?

— Prix

Ponieważ wieże blokujące są zniszczalne, w rzeczywistości istnieje ścieżka. Sam koszt przejścia przez nie jest znacznie wyższy niż poruszanie się po niezakłóconej ścieżce. (Zobacz odpowiedź z coderanger poniżej)

— bummzack

Punktacja na twojej ścieżce sprawia, że przejście przez wieżę kosztuje tyle samo, co przejście przez dużą liczbę płytek. Zasadniczo będzie próbował je ominąć, ale jeśli nie będzie takiej ścieżki, wyjście nadal będzie przebiegać przez najmniejszą liczbę przeszkód. Możesz dostroić karę, aby czasem tak po prostu przeszła, zamiast obchodzić mapę, jeśli chcesz.

— koderanger
źródło

chciałbym zobaczyć kodowy przykład tej implementacji, brzmi prosto i solidnie

— DFectuoso

Algorytm A * ( en.wikipedia.org/wiki/A * _search_alameterm) działa z kosztami ścieżki. Po prostu zwiększ koszt segmentów przebiegających przez wieżę. Twoi agenci będą wtedy próbowali ominąć wieże lub jeśli „taniej” będzie zaatakować wieżę, zaatakują ją. Algorytm A * ma na celu zminimalizowanie kosztów, więc powinieneś być w stanie osiągnąć to, co chcesz, po prostu dostosowując koszty ścieżki ...

— bummzack

To świetne rozwiązanie, o którym bym nie pomyślał, dzięki!

— jhocking 27.04.11

Tylko uwaga: nadanie węzłom wieży ogromnych kosztów ruchu bez zwiększania szacunku zastosowanego dla algorytmu A *, gdy ścieżka jest oczywiście zablokowana, oznacza, że twoi agenci sprawdzą każdy węzeł po swojej stronie przeszkody przed podjęciem decyzji o zerwaniu przez punkt. W zależności od liczby węzłów i agentów algorytm może być zbyt wolny.

— Martin Sojka