A New Algorithm Makes It Faster to Find the Shortest Paths

wired.com

24 points·quapster··9 comments

Open articleView on HN

Discussed here a couple of months ago:

https://news.ycombinator.com/item?id=44812695

Sorry, didn't see that post when searching!

Why not post the original story instead.

https://www.quantamagazine.org/new-method-is-the-fastest-way...

Thank you. The op was so full of ads i couldn't even read it.

Here is the paper https://arxiv.org/abs/2504.17033

Only within undirected graphs. Sadly, this won't revolutionize video games, where we still have to use the A* algorithm from 1968 that is the literal computing bottleneck limiting us to mere hundreds of intelligent characters at once in a barely dynamic environment.

I got way too excited.

In the article it does talk about how they arrived at a partial solution that only worked on undirected graphs, but then they started taking a hybrid approach to get it to work on directed graphs.

The paper also indicates it works on directed graphs: https://arxiv.org/abs/2504.17033

That said, it might only be faster for large, sparse graphs.

Jump point search is obscenely fast. It's technically an optimization of A* but the behavior and runtime looks nothing like it.

It only worked on undirected graphs in 2023. This article is about the newest breakthrough that works on directed graphs as well.

Reply on news.ycombinator.com