Single Agent Search Video 40: Jump Point Search and Other Algorithms Using Canonical Orderings

This is video 40 in a course on Single Agent Search.
This video discusses the algorithms that uses a canonical ordering as a basis for search, including Canonical A*, Bounded Jump Point Search, Jump Point Search, and Canonical Dijkstra's algorithm.
A demo that allows you to run the algorithms on a small map can be found here:
www.movingai.c...

[@konsbruh]

Thanks a lot, very insightful, its very hard to find resources on this topic, especially on jump point search

[@rectomgris]

is there a place where you have pseudo code for canonical ordering? do you have an example for 3D grid map w/o diagonals using for example z as the preferred dimension?

[@movingailab]

We published an article at ICAPS 2021 on canonical orderings for a 2D map with time as the third dimension. There we called the ordering vhw - vertical, horizontal, wait. You can find that paper here: www.cs.ualberta.ca/~nathanst/papers/hu2021jpst.pdf You can currently find a JPS implementation here: github.com/nathansttt/hog2/blob/PDB-refactor/grids/JPS.cpp#L185

[@arumugam39]

Hey! Great lecture! Is there a way to implement something similar to JPS on a map that does not have diagonal moves?

[@movingailab]

Sure - the canonical ordering would just go horizontally and then vertically, resetting similar to JPS when it passes an obstacle.