Hacker News new | comments | show | ask | jobs | submit login
Thesis about the pathfinding AI of my action RPG game written in clojure(lisp) (resatori.com)
33 points by resatori 1823 days ago | hide | past | web | 7 comments | favorite

The wavefront-expansion pathing algorithm described in the paper is very similar to the approach in the roguelike game Brogue [1], whose author refers to as using "Dijkstra maps". The game uses it for many purposes, such as seeking the player, fleeing, finding food and treasure, and even auto-exploring [2]. It was also one of the discussion topics when the game featured on the Roguelike Radio podcast [3].

[1]: https://sites.google.com/site/broguegame/home

[2]: http://roguebasin.roguelikedevelopment.org/index.php?title=T...

[3]: http://roguelikeradio.blogspot.com/2011/10/interview-brian-w...

The mob motion reminds me of Liquid War. Details about their algorithm at http://www.ufoot.org/liquidwar/v5/techinfo/algorithm

Seems pretty straightforward. The 'wavefront-expansion' algorithm does a breadth-first expansion from the goal node, to every other node. As this is done, the distance from each node examined, to the goal, is stored. Afterwards, in order to move towards the goal, an entity at a particular node, moves to its neighboring node that has the shortest distance to the goal.

Have you seen this paper: http://grail.cs.washington.edu/projects/crowd-flows/ ? It touches on many of the same issues.

I wonder how this compares to using flocking algorithms? It seems less efficient from what I gather.

I wrote about this in the thesis. I did not use flocking algorithms because they are much more complex.

I wonder how many people saw the video and wanted to make a WoW/Aggro/Leeroooy related comment but held back afraid of being downvoted.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact