Quote:Original post by irreversible
Define "improved upon". If you can improve A* you'll probably become famous and get lots of women. A* can be tweaked and refined or combined with derivatives of itself to improve efficiency, but "improving upon it" seems a bit audacious.

You can "improve upon" A* in many ways. In this particular case I refer to gaining a speedup without trading away completeness or optimality. For example, A* improves upon Dijkstra's Algorithm (although by your definition above, A* is nothing but a "tweak" of that algorithm).

Anyway, I dislike the incredulous attitude and sarcastic tone of your post (and the other poster). I'm not claiming anything very shocking: there are many examples where people have improved on the performance of A* without trading away optimality or using extra memory. Fringe Search for example (Bjornsson 2005) is an iterative deepening technique which is shown to be faster than A* on general graphs. On grid maps other approaches like the dead-end heuristic (Bjornsson06) speed up A* by identifying and pruning areas that A* would necessarily explore but which cannot lead to the goal. A more recent result along these lines (Pochter09) does even better.

My approach is similar to these. It's implemented, tested and I have a draft paper on my desk.
Sheesh.

Quote:Original post by pithlit

Quote:Original post by irreversible
Define "improved upon". If you can improve A* you'll probably become famous and get lots of women. A* can be tweaked and refined or combined with derivatives of itself to improve efficiency, but "improving upon it" seems a bit audacious.

You can "improve upon" A* in many ways. In this particular case I refer to gaining a speedup without trading away completeness or optimality. For example, A* improves upon Dijkstra's Algorithm (although by your definition above, A* is nothing but a "tweak" of that algorithm).

Anyway, I dislike the incredulous attitude and sarcastic tone of your post (and the other poster). I'm not claiming anything very shocking: there are many examples where people have improved on the performance of A* without trading away optimality or using extra memory. Fringe Search for example (Bjornsson 2005) is an iterative deepening technique which is shown to be faster than A* on general graphs. On grid maps other approaches like the dead-end heuristic (Bjornsson06) speed up A* by identifying and pruning areas that A* would necessarily explore but which cannot lead to the goal. A more recent result along these lines (Pochter09) does even better.

My approach is similar to these. It's implemented, tested and I have a draft paper on my desk.
Sheesh.

Didn't mean to step on your toe there, dude. It seems semantics are getting in the way in here - to me an improvement is more than a refinement or optimization (eg multi-tiering your map for pathfinding). I'd say it's debatable whether A* is an improvement or a refinement with regards to Dijikstra's algorithm because the two aren't really comparable in most cases. By improvement I mean a considerable speed-up, not just a tweak or optimization to make an existing algorithm faster. Consider the FFT with regards to DFT. FFT does the same thing, yet it made DFT pretty much obsolete. Then again, FFT hasn't been improved upon since the 70s even though people have opted to precalculated sine/cosine look-up tables and such, providing a measurable, yet ultimately marginal increase in speed. In the end it's still the same old FFT. I personally wouldn't consider A* the same as Dijikstra's algorithm. Then again, this is - as I said - semantics.

Quote:Original post by irreversible
Didn't mean to step on your toe there, dude.

That's OK. I was just taken aback by such incredulous responses. FWIW, my approach involves pruning the graph before running standard A* over it. The net result is a new pathfinding system which is significantly faster.

Quote:Original post by irreversible
It seems semantics are getting in the way in here - to me an improvement is more than a refinement or optimization (eg multi-tiering your map for pathfinding).

I don't think pathfinding algorithms that use multi-level abstractions are a refinement of A*; I'd argue they build on it but are entirely different. For instance, they trade speed for optimality. There's also extra preprocessing that has to happen and sometimes on the fly modification of the graph itself. Further, the applicability of hierarchical pathfinders is usually more limited than A* (i.e. you can't directly apply most hierarchical pathfinders to general graphs).
Yet nevertheless, for certain classes of problems (pathfinding on large graphs in 2 and 3 dimensional Euclidean spaces) such methods improve running times by an order of magnitude or more.

By comparison, a refinement or optimisation of A* would be a faster priority queue or a better heuristic.

Quote:I'd say it's debatable whether A* is an improvement or a refinement with regards to Dijikstra's algorithm because the two aren't really comparable in most cases.

Of course they're comparable. They solve the same problem, have the same guarantees (complete, optimal)
and, when h=0, A* reduces to Dijkstra's.

Quote:Original post by pithlit
... are there any games that use 4 direction movement?

Oh, the horrible memories. Ultima 3. You could only move and attack in 4 directions, but the enemies could attack (and probably move, but I'd don't truly remember) in 8. I felt no guilt when I discovered I could herd the enemies into single file, as they refused to step on treasure chests.