Jump Point Search
En optimering av A* på enhetliga rutnät som hoppar rakt över ointressanta celler och bara stannar vid de punkter där vägen verkligen kan böja av.
På ett öppet rutnät slösar A* enorm tid på att utvärdera tusentals likvärdiga celler — det finns många vägar av samma längd mellan två punkter. Jump point search beskär den symmetrin: från en cell "hoppar" den i en riktning tills den träffar målet, en kant eller en så kallad hoppunkt där ett hinder tvingar fram ett vägval. Bara hoppunkterna läggs i kön, inte varje mellansteg.
Daniel Harabor och Alban Grastien publicerade metoden 2011. Den kräver ingen förberäkning, ger exakt samma optimala väg som A* och är ofta en storleksordning snabbare på öppna ytor. Begränsningen är tydlig: den förutsätter ett rutnät med enhetliga kostnader och fungerar inte rakt av på ett navmesh eller en viktad graf.