Poprawianie AStar, aby znaleźć najbliższą lokalizację do nieosiągalnego celu

12

Zaimplementowałem AStar w Javie i działa dobrze dla obszaru z przeszkodami, do którego można dotrzeć do wybranego miejsca docelowego.

Jednak gdy miejsce docelowe jest nieosiągalne, obliczona „ścieżka” nie jest w żaden sposób zbliżona do najbliższej lokalizacji (do lokalizacji nieosiągalnej), ale jest raczej losową ścieżką.

Czy istnieje realny sposób na ulepszenie AStar w poszukiwaniu ścieżki do najbliższej lokalizacji do nieosiągalnego celu?

path-finding Shivan Dragon
źródło

Odpowiedzi:

21

Śledź węzeł o najniższym EstimatedDistanceToEnd(tj. Najniższym h(x)), a jeśli żaden węzeł końcowy nie jest dostępny do cofnięcia z, zamiast tego cofnij z tego węzła.

BlueRaja - Danny Pflughoeft
źródło
Prosty. Kocham to!
John McDonald
Właśnie uderzyłem się w głowę i powiedziałem „doh”, kiedy przeczytałem twoją odpowiedź. Dzięki!
Shivan Dragon,
1

To nie jest tak naprawdę pytanie *. A * polega na znalezieniu ścieżki z punktu A do punktu B. Mimo że można ją rozszerzyć, wyniki mogą być z łatwością bałaganu i nieprzewidywalne. Zamiast tego potrzebujesz algorytmu, który wybiera najbliższe osiągalne miejsce docelowe.

Oto jeden ze sposobów, aby to zrobić: Jeśli A * zwraca prawidłową ścieżkę (węzły początkowe / końcowe w ścieżce pasują do węzłów wejściowych), zwróć ścieżkę. Inaczej...

  • Rozpocznij wyszukiwanie od początkowego węzła
  • Przejdź przez wszystkie połączone węzły (pamiętaj o oflagowaniu odwiedzonych, aby uniknąć nieskończonej rekurencji)
  • Porównaj odległości do miejsca docelowego, aby znaleźć najbliższy węzeł
snake5
źródło
Coś takiego jak Flood Fill wydaje się właściwe pl.wikipedia.org/wiki/Flood_fill zauważ, że nadal musisz A * od węzła początkowego do węzła o najniższej odległości. Należy również pamiętać, że zawsze wiąże się to ze sprawdzaniem wszystkich połączonych węzłów, a zatem może być bardzo wolne.
Roy T.,
Tak, może być powolny. Ale powolność najprawdopodobniej wynikałaby z rozproszenia węzłów w pamięci; które można łatwo naprawić. Można go także przyspieszyć, poświęcając trochę dokładności - po prostu pomiń linki, które są za daleko lub wskazują niewłaściwy kierunek.
snake5
1
@Roy: A *, BFS, a wszystkie podobne algorytmy wyszukiwania ścieżek będzie dokładnie tak wolno, jak powodzi nadzienia, bo wszystko trzeba sprawdzić każdy węzeł podłączony do upewnij się, że jest nie do końca ścieżki. Istnieją jednak sposoby na złagodzenie tego problemu; patrz tutaj .
BlueRaja - Danny Pflughoeft