Autor Wątek: Przechodzenie z jednego punktu na mapie do drugiego - algorytm  (Przeczytany 3457 razy)

Offline kaban

  • Użytkownik

# Luty 10, 2010, 13:26:14
witam

piszę strategię i zastanawiam się jak napisać operację przechodzenia z jednego punktu na mapie do innego biorąc pod uwagę przeszkody. Pierwszy pomysł jaki miałem to podzielić całą mapę na kwadraciki i użyć algorytmu kruskala albo prima (wtedy od razu miałbym drogę jaką musi przebyć dana jednostka).

Czy są inne może bardziej optymalne algorytmy, żeby to wykonać czy któryś z tych jest wystarczający? Dodam, że mapa nie będzie miała wymiary góra powiedzmy 100x100 kwadracików.

Offline Mr. Spam

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

Offline ShadowDancer

  • Redaktor

# Luty 10, 2010, 13:32:37
Podzielić mapę na sektory i w nich kolejne sektory/per pixel ;)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Luty 10, 2010, 13:52:37
Cytuj
Pierwszy pomysł jaki miałem to podzielić całą mapę na kwadraciki i użyć algorytmu kruskala albo prima (wtedy od razu miałbym drogę jaką musi przebyć dana jednostka).
Niestety, algorytmy Kruskala i Prima są do zupełnie czego innego i sensownej drogi nimi nie wyznaczysz. :) Zainteresuj się Breadth First Search albo algorytmem Dijkstry.

Offline Liosan

  • Moderator

# Luty 10, 2010, 13:53:27
Chcesz użyć algorytmu do szukania minimalnego drzewa rozpinającego do znalezienia drogi na mapie? Przecież one nie znajdą Ci najlepszej ścieżki...

Czemu nie użyjesz A*? To taki zmodyfikowany algorytm Dijkstry, ulepszony o wykorzystanie heurystyki "jak daleko jeszcze" (która w ogólnych grafach jest trudna, ale na płaskiej mapie łatwa do wytworzenia :) )

Nie rozumiem ostatniej uwagi... chodzi Ci o to, że masz nieograniczoną planszę? No to niestety będziesz ją musiał ograniczać na potrzeby wyszukiwania drogi...

Liosan

Offline kaban

  • Użytkownik

# Luty 10, 2010, 14:00:45
chodziło mi w tej uwadze o to, żeby dać wyobrażenie z jaką skalą mamy do czynienia
algorytm Dijkstry już kiedyś implementowałem więc powinienem dać sobie z tym radę. A dla jakiej mapy to nie będzie zamulać gdy dla powiedzmy góra 100 jednostek?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Luty 10, 2010, 14:06:08
Cytuj
Czemu nie użyjesz A*? To taki zmodyfikowany algorytm Dijkstry, ulepszony o wykorzystanie heurystyki "jak daleko jeszcze" (która w ogólnych grafach jest trudna, ale na płaskiej mapie łatwa do wytworzenia :) )
W tym przypadku A* nie sprawdzi się raczej zbyt dobrze - nie dość, że w przypadku labiryntów może się nieco pogubić, to algorytm Dijkstry wymaga kolejki priorytetowej. Przy BFS wystarczy zwykłe FIFO. :)

Offline Liosan

  • Moderator

# Luty 10, 2010, 14:16:59
W tym przypadku A* nie sprawdzi się raczej zbyt dobrze - nie dość, że w przypadku labiryntów może się nieco pogubić...
A kolega pytał o labirynty? Bo ja zrozumiałem, że to płaszczyzna z przeszkodami... Jeśli to labirynt to faktycznie A* jest do kitu.

Liosan

Offline htmlowiecii

  • Użytkownik

# Luty 10, 2010, 18:04:51
możesz wyznaczyć punkty które będą miały różne koszty przejścia (bo jeśli będzie to strategia to raczej wszędzie będzie dało się wejść, ale pewne rzeczy omijać) Punktowi docelowemu wyznaczyć wartość równą odległości od jednostki która tam zmierza (właściwie to będzie trzeba zrobić wektory) i od wektora który przypiszemy do celu odejmujemy wektory przeszkód (ale ta metoda zakłada, że przez każde pole przejdziesz, tylko czasem jest to drogie, ale też umożliwia wcześnmie ominąć ruchomy obiekt)

edit dorzucenie obrazka, bo chyba namieszałem
« Ostatnia zmiana: Luty 10, 2010, 18:22:55 wysłana przez htmlowiecii »

Offline kaban

  • Użytkownik

# Luty 10, 2010, 19:26:00
A kolega pytał o labirynty? Bo ja zrozumiałem, że to płaszczyzna z przeszkodami... Jeśli to labirynt to faktycznie A* jest do kitu.

tak, to ma być płaszczyzna 2d z przeszkodami. Poszukałem trochę o algorytmie A* i chyba na niego się skuszę.

Offline kaban

  • Użytkownik

# Luty 13, 2010, 10:41:34
mam jeszcze jedno pytanie, jak algorytm A* się zachowa, gdy nie znajdzie żadnej drogi z punktu wyjściowego do docelowego? Bo przecież tak też może się przytrafić

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Luty 16, 2010, 15:06:14
mam jeszcze jedno pytanie, jak algorytm A* się zachowa, gdy nie znajdzie żadnej drogi z punktu wyjściowego do docelowego? Bo przecież tak też może się przytrafić
Przemierzy wszystkie miejsca na mapie, szukając "tego jedynego" przejścia. :) Jeśli masz nieograniczoną mapę, to masz problem, ale sam się o niego prosisz, bo na nieograniczonej mapie nigdy nie wiadomo, czy nie ma jakiegoś przejścia do jakiegoś punktu. Tak jak ktoś powiedział, trzeba wtedy "udać" że mapa jest ograniczona, szukając ścieżki na wystarczająco dużym obszarze.
Na takich dużych mapach możesz pokusić się o A* hierarchiczny, żeby było szybciej, tzn dzielisz mapę nie tylko na mniejsze kwadraty ( takie, że masz ich powiedzmy 1000000), ale też robisz siatkę waypointów (powiedzmy 100) pomiędzy którymi na pewno da się przejść. Żeby ją wyznaczyć, musisz zgadnąć, gdzie na mapie mogą być (powinny to być środki wolnych przestrzeni) i de facto uruchomić A* pomiędzy każdym waypointem i jego najbliższymi sąsiadami, żeby zobaczyć, czy jest wystarczająco krótka ścieżka. Jeśli jest, to takie połączenie między waypointami będzie należeć do siatki.
Potem, żeby sprawdzić, czy jest ścieżka pomiędzy startem a metą, szukasz kolejno:
- ścieżki na tych małych kwadracikach, od startu do najbliższego waypointa
- ścieżki na siatce, od tego waypointa do waypointa najbliżej mety
- ścieżki na kwadracikach, od waypointa najbliżej mety do mety
Każdy z powyższych kroków może być zaimplementowany algorytmem A*. Jeżeli wszystkie 3 się dobrze wykonają, to znaczy że ścieżka istnieje, każdy z tych podpunktów będzie natomiast o kilka rzędów wielkości szybszy niż szukanie ścieżki na 1000000 małych kwardacików.

Pozdrawiam.