Witam, szukam algorytmu, który najlepiej rozwiąże mój problem. Potrzebuje znaleźć najkrótszą drogę na mapie od punktu A do punktu B. Mapa jest dość obszerna, więc na rękę byłoby mi rozwiązanie najbardziej optymalne. Zastanawiałem się nad algorytmem Dijkstry, ale proszę o waszą opinię/propozycje.
- Rejestracja:ponad 14 lat
- Ostatnio:ponad 11 lat
0
Jeszcze może Cię zainteresować http://pl.wikipedia.org/wiki/Algorytm_A*
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
0
Najprostsza wersja to faktycznie sprowadzenie mapy do grafu i zapuszczenie Dijkstry/A*.
Można by coś powiedzieć z większą pewnością gdybyśmy wiedzieli co to za mapa i jak ją przechowujesz, a ściśle jaka jest dokładnie struktura ścieżek/przeszkód (jak 'wygląda' mapa).
W szczególności mapa może być w formie geometrycznej zabroń wstępu na niektóre obszary (typu ściany i inne przeszkody), przez resztę można przejść albo grafowej mamy ileś punktów i łączymy je przejściami (jak np. mapa samochodowa).
Dijkstry na dużej mapie nie będzie zamulał skryptu? O ile pamiętam to sprawdzał on każde połączenie z celem, czyli w moim przypadku za każdym razem wałkowałby każdy korytarz.
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
0
Dijkstry na dużej mapie nie będzie zamulał skryptu? O ile pamiętam to sprawdzał on każde połączenie z celem, czyli w moim przypadku za każdym razem wałkowałby każdy korytarz.
Dokładnie, Dijkstra sprawdza każde pole, a ściślej sprawdza aż znajdzie ścieżkę ale nie podejmuje żadnych prób żeby ilość testowanych pól zmniejszyć.
Różnica między A* a Dijkstrą jest taka że ten pierwszy próbuje właśnie poprawić wydajność stosując heurystykę, w grafach gdzie to możliwe (w Twoim przypadku typową heurystyką jest odległość punktu docelowego i kratki - przykładowo chcąc trafić do sklepu mamy większą szansę trafić jeśli idziemy w jego kierunku zamiast w przeciwnym (ale jeśli się okaże że droga jest zablokowana to trzeba będzie później spróbować innych dróg)).
Będzie to działać, zarówno Dijkstra i A* powinny być bardzo szybkie o ile nie będziesz używał naprawdę dużych map (typu 10000x10000). No i tak będzie pewnie najprościej, chociaż może nie najładniej (bo droga w kratkowanym gridzie to jednak nie dokładnie to samo do droga w budynku).
Jeśli chodzi o bardziej ogólny motion planning to jest trochę bardziej rozbudowany temat i ludzie nawet piszą na jego temat książki i biblioteki. Pierwsze co mi przychodzi do głowy to drzewo które kiedyś implementowałem, ale ogólnie nie jestem ekspertem w tym temacie ;]
edytowany 1x, ostatnio: msm
Kratek oczywiście nie pokażę :) Mapkę dostosuję tak, aby się pokrywało z girdami, ponieważ mapka nie będzie dokładnym odwzorowaniem budynku a jedynie pomocą w dotarciu od pokoju A do pokoju Z. Bardzo dziękuję Ci za pomoc. Uważam, że A* będzie tutaj lepszym rozwiązaniem, ponieważ ile razy szukaliśmy pokoju w urzędzie a okazywało się, że był on tuż za rogiem? ^^
graficznejtzn. jak powiedzmy w grach strategicznych (jednostka może przejść przez wszystko oprócz przeszkód) to raczej da się lepiej.