Jump point search
Un'ottimizzazione di A* sulle griglie uniformi che salta a pie' pari le celle poco interessanti e si ferma solo nei punti in cui un percorso può davvero svoltare.
Su una griglia aperta, A* spreca moltissimo tempo a valutare migliaia di celle equivalenti: tra due punti esistono molti percorsi di uguale lunghezza. La jump point search elimina questa simmetria: da una cella «salta» in una direzione finché non incontra la meta, un bordo o un cosiddetto jump point, dove un ostacolo impone una scelta. Solo i jump point finiscono nella coda, non ogni passo intermedio.
Daniel Harabor e Alban Grastien pubblicarono il metodo nel 2011. Non richiede preelaborazione, restituisce esattamente lo stesso percorso ottimo di A* ed è spesso un ordine di grandezza più veloce su terreno aperto. Il limite è chiaro: presuppone una griglia a costo uniforme e non si applica direttamente a una navmesh o a un grafo pesato.