Szybsza alternatywa dla algorytmu Dijkstry dla systemu GPS

Question

Jestem prawdziwym maniakiem prędkości, jeśli chodzi o algorytmy i wtyczki, które stworzyłem dla gry.

Prędkość jest ... trochę ... niezadowalająca. Zwłaszcza podczas jazdy samochodem i nie podążania ścieżką, ścieżka musi zostać ponownie obliczona ... i zajmuje to trochę czasu, więc GPS w grze gromadzi wiele sygnałów "niewłaściwej drogi" (i układa sygnały w górę oznacza więcej kalkulacji po każdym niewłaściwym ruchu), ponieważ chcę mieć szybki system live-gps, który stale aktualizuje się.

Zmieniłem stary algorytm (niektóre prosta implementacja Dijkstra) zwiększanie :: Dijkstry obliczyć drogę od węzła A do węzła B

(całkowita lista węzeł jest około ~ węzły 15k z ~ połączenia 40K, dla ciekawy ludzie tutaj to mapa: http://gz.pxf24.pl/downloads/prv2.jpg (12 MB), krawędzie w czerwonych liniach są węzłami),

, ale tak naprawdę nie zwiększyło to prędkości. (Przynajmniej nie zauważalnie, może 50 ms).

Informacje, które są przechowywane w tablicy węzeł jest:

The ID of the Node, 
The position of the node, 
All the connections to the node (and which way it is connected to the other nodes, TO, FROM, or BOTH) 
Distance to the connected nodes. 

Jestem ciekawy, czy ktoś zna jakieś szybsze alternatyw w C/C++? Wszelkie sugestie (+ przykłady kodu?) Są mile widziane!

---

Jeśli ktoś jest zainteresowany projektem, to jest tutaj (źródło + binarne):

https://gpb.googlecode.com/files/RouteConnector_177.zip

W tym filmie można zobaczyć, co GPS-System jest tak:

http://www.youtu.be/xsIhArstyU8

jak widać czerwona trasa aktualizuje się powoli (no, dla nas - graczy - jest powolna).

(ByTheWay: luki między czerwonymi liniami zostały ustalone dawno temu: P)

Answer 1

Ponieważ jest to GPS, musi mieć stałe miejsce przeznaczenia. Zamiast obliczać ścieżkę z bieżącego węzła do miejsca docelowego za każdym razem, gdy zmieniasz bieżący węzeł, możesz zamiast tego znaleźć najkrótsze ścieżki od miejsca docelowego do wszystkich węzłów: wystarczy uruchomić Dijkstę raz, zaczynając od miejsca docelowego. Zajmie to tyle czasu, ile trwa aktualizacja.

Następnie w każdym węźle zachowaj prev = the node previous to this on the shortest path to this node (od miejsca docelowego). Aktualizujesz to, obliczając najkrótsze ścieżki. Lub możesz użyć tablicy prev[] poza węzłami - w zasadzie każda metoda, której używasz do rekonstrukcji ścieżki, powinna teraz działać.

Podczas przenoszenia samochodu Twoja ścieżka jest podana przez currentNode.prev -> currentNode.prev.prev -> ....

Rozwiązuje to opóźnienie aktualizacji i zapewnia optymalną ścieżkę, ale przy wprowadzaniu miejsca docelowego nadal występuje niewielkie opóźnienie.

Powinieneś rozważyć takie podejście, nawet jeśli planujesz używać A * lub innych heurystyk, które nie zawsze dają optymalną odpowiedź, przynajmniej jeśli nadal będziesz opóźniony w stosowaniu tych metod.

Na przykład, jeśli masz ten wykres:

1 - 2 cost 3 
1 - 3 cost 4 
2 - 4 cost 1 
3 - 4 cost 2 
3 - 5 cost 5 

Tablica prev wyglądałby następująco (obliczone podczas obliczania odległości d[]):

 1 2 3 4 5 
prev = 1 1 1 2 3 

Znaczenie:

shortest path FROM TO 
       1 2 = prev[2], 2 = 1, 3 
       1 3 = prev[3], 3 = 1, 3 
       1 4 = prev[ prev[4] ], prev[4], 4 = 1, 2, 4 (fill in right to left) 
       1 5 = prev[ prev[5] ], prev[5], 5 = 1, 3, 5 
       etc. 

Answer 2

Aby zacząć od razu, możesz oszukać w następujący sposób: ay.

Masz dość mały zestaw "głównych węzłów komunikacyjnych". Dla każdego węzła określ jego "sąsiedztwo" (wszystkie węzły w pewnej odległości). Przechowuj najkrótsze trasy z każdego głównego węzła komunikacyjnego do każdego innego. Przechowuj najkrótsze trasy do/z każdego węzła do głównych tras.

Jeśli oba węzły znajdują się w tej samej okolicy, można obliczyć najlepszą odpowiedź w locie. W innym przypadku rozważmy tylko drogi formy, "tutaj do głównego węzła komunikacyjnego blisko mnie do głównej arterii blisko niego". Ponieważ już je przeliczyłeś i masz ograniczoną liczbę kombinacji, bardzo szybko możesz obliczyć trasę w locie.

Następnie wyzwaniem staje się wybranie zestawu głównych węzłów komunikacyjnych. Powinien to być dość mały zestaw węzłów, przez który powinny przejść najdogodniejsze trasy - więc wybieraj węzeł co jakiś czas wzdłuż głównych ulic. Lista kilkuset powinna być więcej niż wystarczająco dobra dla twojej mapy.