@fuso: I really appreciate your notes! I'm currently revising the implementation with what you mentioned in mind. About the priority queue, wouldn't it be implemented on top of a binary heap anyway? Or are you talking about another implementation? And yeah, I'm adding support for tile tags as soon as possible.
Plainly, it is merely a list.
Yeah, that's possible Gubid, although I'm not sure if it'd guarantee the best path (just because it found a good path in x number of iterations doesn't mean it's the best path overall). I was thinking of making the path lookup take place as part of a frame update instead of the big loop I have now (or maybe a choice between the two), so I'll try to implement something like that and see how good it works in practice. Thanks!
I think that for regular rpgmaker maps, you do not need entirely different algorithms seeing how maps of sizes 100x100 or the like are in fact small. There are however a number of algorithms that ensures approximate paths in much less than O
time (or O(sqrt
) in practice for open maps) (O(g) roughly means that it is no worse than proportional to g), at least assuming the entire path does not need to be reported (which is co-o
, i.e. "at least" n time). One approach is to abstract the path-finding process whch gives high-level guides of the optimal paths. This worked great even for maps with a width of a million! However, that assumes the map is fairly static, i.e. does not change too much/often. Rare changes can still be handled fairly efficiently. Interestingly, you there also merely compute a rough idea of how the farther parts of the path looks while the first tiles of the path are completely identified.
See e.g.
http://aigamedev.com/theory/near-optima ... athfinding
and Near-Optimal Hierarchical Path-Finding by Botea, Müller, and Schaffer, available at
http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf .
Yeah, that's possible Gubid, although I'm not sure if it'd guarantee the best path (just because it found a good path in x number of iterations doesn't mean it's the best path overall). I was thinking of making the path lookup take place as part of a frame update instead of the big loop I have now (or maybe a choice between the two), so I'll try to implement something like that and see how good it works in practice. Thanks!
I think some [commericial] games do what Gubid suggests but yes, it is approximate of course.
Rpgmaker maps are definitely small enough for you to be able to preprocess and store a rough estimate of all-pairs shortest paths but not exactly for larger maps with a naïve algorithm. You only need 2 bits per tile to store direction so about (wh)^2 / 4 bytes which is merely 40kB for 20x20 maps but 6MB for 100x100 maps. This obviously also has problems with maps that change too much. However, there are algorithms that can trade error, space, and query time and you may adjust your parameters accordingly. We have the special case here where our graphs are almost planar (moves do not cross each other), have a constant degree (only few number of possible moves from each tile), possibly undirected (if you can go in one direction, you can go in the other), and 1/inf-weights (all legal moves cost 1). For this case, you can find an approximate shortest path that is arbitrarily close to the optimal one in roughly constant time using only roughly linear space, i.e. O(wh) instead of O(wh^2)! These algorithms are usually called "shortest-path oracles". See for instance
Approximate Distance Oracles by M. Thorup,
Compact oracles for reachability and approximate distances in planar digraphs by M. Thorup,
or Fast and Exact Shortest Path Queries Using Highway Hierarchies by D. Schultes.
Good luck.
