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.
0
0
Jeszcze może Cię zainteresować http://pl.wikipedia.org/wiki/Algorytm_A*
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).
0
Pracuję nad mapą budynku. Sądzę, że dobrym rozwiązaniem będzie podzielenie jej na kwadraty i użycie A*. Ściany będą polami zabronionymi. Korytarze skrypt będzie pokonywał po ukosie owych kwadratów. Co myślicie?
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 ;]