Jump point search
Optymalizacja A* na jednorodnych siatkach, która przeskakuje nieciekawe komórki i zatrzymuje się tylko tam, gdzie ścieżka naprawdę może skręcić.
Na otwartej siatce A* marnuje ogromną ilość czasu na ocenianie tysięcy równoważnych komórek — między dwoma punktami jest wiele ścieżek tej samej długości. Jump point search przycina tę symetrię: z komórki „skacze” w danym kierunku, aż trafi na cel, krawędź albo tzw. punkt skoku, w którym przeszkoda wymusza wybór. Do kolejki trafiają tylko punkty skoku, a nie każdy krok pośredni.
Metodę opublikowali w 2011 roku Daniel Harabor i Alban Grastien. Nie wymaga przetwarzania wstępnego, zwraca dokładnie tę samą optymalną ścieżkę co A* i na otwartym terenie bywa szybsza o rząd wielkości. Ograniczenie jest wyraźne: zakłada siatkę o jednakowym koszcie i nie przenosi się wprost na navmesh ani graf ważony.