Autor Wątek: [SOLVED] A* w generowaniu ulic, jaką dobrać heurystykę ?  (Przeczytany 2169 razy)

Offline Nargil

  • Użytkownik
    • projekty

# Marzec 26, 2011, 22:15:22
Generuję proceduralnie siatkę ulic. Wygląda to tak, że dobieram parę punktów na kafli terenu i staram się je połączyć ze sobą. Zaimplementowałem A* w oparciu o pseudokod z wikipedii.

Chciałbym, żeby algorytm generował możliwie jak najmniej zakrętów (kosztem dłuższej drogi wokół przeszkody) i możliwie wykorzystywał istniejące już trasy. Toteż jako wagi przejścia dałem:
//Istnieje droga na kafli nb(sąsiedniej do x)
if(mStreetLayer.RoadTiles[nb].Road_ids.size()) cost = 1;
// droga jest przedłużeniem
else if(nb - x == x-tiles[x].came_from) cost = 2;
// nastąpił skręt
else cost = 3;

Problem polega na tym, że jeśli nie stosuję heurystyki h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y)) to algorytm ma tendencje do wyszukiwania drogi bardzo okrężnej, lub nie znalezienia trasy w ogóle. Ilustruje to następujący obrazek,

Gdzie mając sieć ulic A dorzucam punkt B. Widzimy, że niebieska ulica łącząca A i B biegnie bardzo okrężną drogą. Kolor czerwony to przeszkody. Pomarańczowym zaznaczyłem jakbym tę trasę widział.

Zastosowanie w/w heurysytki ignoruje natomiast moje preferencje co do prostych dróg "wielokrotnego użytku" i tworzy trasę na obwodzie przeszkody.

Jakieś rady ?
« Ostatnia zmiana: Kwiecień 06, 2011, 00:05:17 wysłana przez Nargil »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Slovian

  • Użytkownik

# Marzec 26, 2011, 23:09:55
Tak na pierwszy rzut oka - według mnie najprościej by było przynajmniej spróbowac załatwic sprawę "małej ilości zakrętów" post processem ścieżki. Nie wiem czy efekt zadowoli Cię, ale warto przynajmniej spróbowac. Generalnie wygląda to na łatwy strzał. Wyliczasz ścieżkę bez kombinowania z zakrętami - otrzymujesz najkrótszą ścieżkę, potencjalnie pokręconą . Następnie zapuszczasz post-process gotowej ścieżki, w którym starasz się "prostowac ścieżkę" nie gubiąc jej optymalności.

Offline kamykadze

  • Użytkownik

# Kwiecień 03, 2011, 15:42:35
Jesteś pewien, że dobrze A* zaimplementowałeś???
Musisz pamiętać, że w A* heurystyka powinna być niedoszacowana (tj. mniejsza niż rzeczywista odległość). W przeciwnym wypadku może zostać zwrócona nieoptymalna ścieżka. Może to jest problem, choć trudno mi przesądzać, bo nie do końca rozumiem oznaczenia w Twoim wzorze na h(n).

Ja bym zaryzykował jeszcze jedno podejście - odległość między dwoma "kwadratami" jest nieznacznie większa, gdy zmienia "kierunek" dotychczasowej ścieżki. Jeśli nic z tego nie wyjdzie, sugerowałbym podejście Sloviana.
« Ostatnia zmiana: Kwiecień 03, 2011, 15:46:35 wysłana przez kamykadze »

Offline Slovian

  • Użytkownik

# Kwiecień 04, 2011, 14:42:31
To jeszcze odnośnie zaproponowanej na starcie heurystyki. Niestety nie może być ona poprawna z jednego podstawowego powodu - wartość "kosztu" wierzchołka zależy od tego kto był jego poprzednikiem - a to rozwala zupełnie warunki kroku algorytmu wyszukiwania. Musiał by czasem ponownie przeszukiwać wierzchołek mimo, że bazowy koszt dojścia do niego jest większy niż poprzednio, ale za to jest możliwość wygenerowania tańszych połączeń do jego sąsiadów. Gdy zaczniesz wchodzić w to jakie będzie to miało implikacje dla bazowego A* - to zobaczysz ze zupełnie rozwali Ci to algorytm. Nawet jeśli napiszesz jakieś rozwiązanie, które będzie wyglądało że działa (bo heurystyka będzie ZWYKLE wybierać wierzchołki w dobrej kolejności) - nie będziesz mógł zapewnić że znalazło najkrótszą ścieżkę. Brzmi to skomplikowanie i gdybyś próbował jako szyć w obecnym rozwiązaniu jakieś modyfikacje A* by to obsłużyć wyszła by jakaś masakra.

Jeśli chcesz "ładnie" rozwiązać problem musisz wirtualnie rozszerzyć przestrzeń wyszukiwania - by każde pole było nie jednym wierzchołkiem grafu wyszukiwania, ale dwoma (jednym przechodzonym "pionowo" i jednym przechodzonym "poziomo").

Offline Liosan

  • Moderator

# Kwiecień 04, 2011, 14:49:36
Moim zdaniem waga jest za duża - ja przy wyszukiwaniu tras dodawałem jedną tysięczną (albo mniej) odległości między dwoma kaflami jako bonus za przedłużenie trasy - to wystarczało, by je prostować, a nie miało szans zaważyć na optymalności wyniku.

Liosan

Offline Nargil

  • Użytkownik
    • projekty

# Kwiecień 05, 2011, 23:08:37
Dziękuję za rady. Jest dużo lepiej. W zasadzie to akceptowalnie.

Najpierw tworzona droga z zachodu na wschód (s1 -> e1), potem z północy na południe (s2 -> e2).

O ile w pełni rozumiem wybór ścieżki w punkcie P1 (optymalna ulica poszła by w prawo o 1 pixel i wtedy w dół do końca), spowodowany heurystyką - nastąpiłoby oddalenie się od celu, podczas gdy możliwe jest przybliżenie się, a algorytm jeszcze nie wie, że później i tak będzie musiał się oddalić.

To jednak nie rozumiem wyboru ścieżki pierwszej. Czemu w P2 nastąpił zakręt, po to by stworzyć kolejny w P3 ? Dorysowana zielona ścieżka byłaby bardziej optymalna.

Szczerze to wątpię, by komuś się chciało analizować ten kod, ale wkleję mimo wszystko ;-)
http://pastebin.com/K1qVyY8S
pseudokod z wikipedii: http://tiny.pl/hd4vc
Nazwy zmiennych są spójne.


edit: o kurde jaka skucha w #55 ;-) Założono, że openset jest posortowane. Poprawiono. Szkoda, że mam te kawałki losowo generowane i nie zapisałem ziarna z poprzedniego przykładu, by porównać ;/

edit2: wydaje się wporządku. Oznaczam jako SOLVED.
« Ostatnia zmiana: Kwiecień 06, 2011, 00:14:01 wysłana przez Nargil »

Offline koirat

  • Użytkownik

# Grudzień 06, 2011, 00:14:01
Swoją drogą napisałeś w pierwszym poście iż czasem ścieżki nieznajduje, jeśli tak to ewidentnie masz błąd w implementacji bo A* gwarantuje dojście do celu jeśli jest to możliwe.

Offline yarpen

  • Użytkownik

# Grudzień 06, 2011, 00:22:30
LOL, szkoda, ze jeszcze dluzej nie poczekales z ta odpowiedzia...

Offline koirat

  • Użytkownik

# Grudzień 06, 2011, 00:38:13
LOL,
Niewiem dlaczego ale jak klikam "Pokaż wiadomości od ostatniej wizyty."
To dostaje takie kwiatki z cmętarza.

Offline Nargil

  • Użytkownik
    • projekty

# Grudzień 06, 2011, 00:39:42
Z przykrością informuję Cię koirat, że problem już dawno był oznaczony jako solved. Nawet napisałem co nie tak. Nice gravediggin though.

Efekty:
http://www.youtube.com/watch?v=4x9AMeZsFqU
http://warsztat.gd/screens.php?x=view&id=9066