Comment by payasr | Hacker News Reader

Comment by payasr | Hacker News Reader

There's a _lot_ of work on hierarchical route planning in games. I don't mean to put down the developers or anything, and I'm so glad all of this works, but there are plenty of ideas in the academic-world that I think developers should know more about.

Botea, Adi, Martin Müller, and Jonathan Schaeffer. 2004. “Near Optimal Hierarchical Path-Finding.” In Journal of Game Development. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.....

Rahmani, Vahid, and Nuria Pelechano. 2017. “Improvements to Hierarchical Pathfinding for Navigation Meshes.” In Proceedings of the Tenth International Conference on Motion in Games, 8:1–8:6. MIG ’17. New York, NY, USA: ACM.

Toll, Wouter van, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, and Roland Geraerts. 2016. “A Comparative Study of Navigation Meshes.” In Proceedings of the 9th International Conference on Motion in Games, 91–100. ACM.

And route planning in graphs (with static edge weights) has been studied to death.

https://arxiv.org/pdf/1504.05140.pdf

Note that they meant that they have a new algorithm for their game and not a new algorithm for the world, so don't shit on them for no reason. For all we know they could have already read the papers you mentioned. They even mentioned that this was an old technique in the blog:

> Pathfinding is an old problem, and so there are many techniques for improving pathfinding. Some of these techniques fall into the category of hierarchical pathfinding

It took me till my late 30's to realize this is the power of a graduate degree. There are lots of people out there who understand programming, and there's a tier of programmers who understand research as a fundamental part of it.

You don't need a graduate degree to understand it, but conveying that you understand it on your resume is hard to do in any universally meaningful way without that degree. The words that would grab the attention of the tech lead, the PM, and the HR are all different.

The freedom to think abstractly and not in terms of everything-is-on-fire-all-the-time is absolutely the best thing about being a graduate student :)

The problem with many phd's is that they don't understand how useless research papers are in most cases. You have very tight constraints and the algorithms written by researchers are almost never optimal, you have to do significant tweaks or reinvent it entirely to fit it into your constraints.

In this case you just linked a bunch of irrelevant papers that didn't solve the problem (pathfinding on an infinite and mutable map) and calling the developers ignorant for not looking at them. It is you who are ignorant thinking that you being a grad student means that you must know better than professionals, and also you lack reading comprehension since they didn't even claim their approach is new. This blog was not meant to contribute as a research paper, it was meant to show the community what improvements for the game they were working on.

I've been thinking about writing a blog series on route planning algorithms if there is enough interest.. let me know if anyone wants it lol?

Yes, please!

Long shot, but if by any chance you could explain Highway Dimension [1] like I'm 5, and how it leads to faster routing algorithms, I would definitely be interested! I've watched some of Goldberg's videos (e.g. [2]), so I have some vague intuition, but not nearly as much as I feel I could/should. (Though it's entirely possible it's just something that can't be meaningfully ELI5'd in a usable manner... I don't know.)

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...

[2] https://www.youtube.com/watch?v=ArO1ZviOMhI

Sure! That is a classic paper, I didn't know there was a video too. Let me try:

Highway Dimension- Say we are given a bidirectional graph G and a radius r. Now take a vertex v, and find the set of all shortest paths from v of length > r and <= 4r. Let us call this set P(v, r). Iterate for all vertices in the graph and real radii, and obtain similar sets. Then, highway dimension is the size of the smallest set (H) of vertices such that all sets collected in the previous step have at least one vertex in H.

Why is this useful- Empirically, we know that road networks have small highway dimensions. This is interesting because it implies that there are only a handful of vertices from which you can take the shortest paths to all the vertices in the network. Intuitively, it makes sense too. If you want to travel long distances, it's best to take the highway as early as possible, and travel along it for as long as you can, then descend to the local roads as you reach closer to the destination.

Highway dimension basically gives us a theoretical way of capturing the inherent 'hierarchy' of the road network edges and explains why Contraction Hierarchies works so well on road networks (as opposed to random graphs, where CH can be easily beaten). HTH!

Oh wow! To confirm I understand this, is the following correct? "The radius-r highway dimension of a graph G is the(/a?) minimal set of vertices that must be visited when traveling a distance ∈ (r, 4r]." I'm actually a little unclear on r—I assumed HD is a function of r, but you said you iterate over all real radii to obtain HD, which would mean HD is independent of r?

Yes this is helpful, thank you so much! :)

HD is independent of r. And it's not the minimal set of vertices that must be visited.. it is the smallest set of which at least one must be visited. Another good explanation of HD is in section 1.3 of the skeleton dimension paper (https://arxiv.org/pdf/1609.00512.pdf).

Oh, sorry, I was vague about the visiting—I meant the set must be visited, i.e. something in it must be visited. I'll take a look at that one too, thanks!

Also, there's some recent work on similar metrics, if you are interested. Do check out (https://arxiv.org/abs/1609.00512) and Sabine Storandt's work on how route planning algorithms behave as graphs scale (https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/1774...)

Wow, the abstract on skeleton dimension looks quite amazing. I only happened to come across HD after working on a tangentially related algorithm, but I didn't keep up with the progress on that front... it didn't even hit me they might've already progressed beyond that to a stronger measure. That's pretty awesome, thanks for sharing!

There are often comments of the form " I've been thinking of doing x, is there any interest?"

The answer is always yes! Partly because no matter how niche a topic is there are people interested in it, and partly because creating such things will help your own understanding.

Go for it!

Thanks Steve!

I wanted to make a tiny routing program, read a few papers but they're too advanced. I'd like some basics :)

There are some excellent ready-to-use libraries too, if you don't want to code everything yourself. Please see the following gist for a list: https://gist.github.com/PayasR/bc46af938195a827e42006c3f5544...

Oh wow, you're actually compiling a list! I'm not sure this is relevant (it's for a different stochastic routing problem), but here's something I have, if you feel it's relevant enough to be added: https://git.io/SOTA-Py

I know of SOTA and SPOTAR.. thanks! :)

Cool! Yup :)

thanks to you too

thanks a lot man

I actually learned something today about pathfinding by (re) reading that post for 15 mins. The papers linked make no sense to me. Maybe the paper authors need make abstracts and summaries more approachable.

The authors are optimising for communicating with their peers: scientists and academic researchers.

If you find this communication hard to digest, then chances are you are not part of the intended audience. It is then mostly pointless to try to change their wording.

There is enough other material (books, Web articles) from other people who deliberately target developers.

Will using those make a measurable difference to the game?

No, they either assume immutable maps or graph based maps like road networks.

Reply on news.ycombinator.com