Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Ampersand]

For thouse interested in path finding, the A* implementation in that Java applet is just Terrible, on open ground A* should go strait towards its target and check hardly any nodes at all, this implementation is queuing hundreds of unnecessary nodes and checking almost as many nodes as Dijkstra.  It's only someone school project so its not surprising the implementation is poor but don't let this confuse you as to how efficient a real A* implementation is, it is in fact orders of magnitude better then Dijikstra and should be used in any instance UNLESS site-to-site teleports are on the map, only Dijikstra can deal with teleporting.

Such as, for example, staircases?

[Sowelu]

For thouse interested in path finding, the A* implementation in that Java applet is just Terrible, on open ground A* should go strait towards its target and check hardly any nodes at all, this implementation is queuing hundreds of unnecessary nodes and checking almost as many nodes as Dijkstra.  It's only someone school project so its not surprising the implementation is poor but don't let this confuse you as to how efficient a real A* implementation is, it is in fact orders of magnitude better then Dijikstra and should be used in any instance UNLESS site-to-site teleports are on the map, only Dijikstra can deal with teleporting.

Hmmm.  It looked to ME like any other A* implementation with variable tile cost, and a heuristic that guesses on the low side (like it's required to for admissability).  A* always has to guess that somewhere out there, there's a road that'll get it there even faster...well, as long as you're in a world where roads exist.

On a map made entirely out of grass and water and the possibility of roads (but none on the map), that A* is going to branch way out...because it is guaranteed to find an optimal path.  And sometimes you get a degenerate case, like a narrow strip of grass from origin to destination, surrounded by a one-tile-wide border of water, surrounded by road.  You gotta expand outward to find those roads if they exist.  If there's some oddball diagonal path that tags just ONE road, then it still has to do it, because that's the optimal path and A* always finds the optimal path.

Impaler, PLEASE don't bash on that implementation; I think you just don't have enough experience with A*.  If you set two nodes on roads, that applet will do exactly what you're describing.  A* acts weird with large areas of high path cost, but as far as I can tell, that java applet is a perfect implementation.

The lesson here:  If you have variable tile costs, A* is not much better then Dijkstra for any case where you are not pathing on the lowest cost path.  Adding tile costs which are lower than the cost of a 'normal' tile can give you a huge performance hit straight out the gate, if you depend on A*.  If your map is mostly grass and tunnel, your lowest path cost should be grass and tunnel if you want a fast algorithm.

(I should know.  My last game project had a tile cost of 10, while my A* heuristic thought the best cost was 5 * manhattan distance.  The algorithm went psycho...but, I have to keep it like that for when I implement roads that really do cost 5 instead of 10!)