I was just curious to know what the following method of pathfinding is called: [hugely non-optimised psuedo] Put a zero in the destination node Put a 1 in each node adjacent to the destination node For each node with a 1 in, put a 2 in each adjacent node that does not already have a number in For each node with a 2 in, put a 3 in... etc Until: the origin node has a number in (route found) Or: no numbers are placed (no route possible) Then, when the route is found, follow from the origin to the destination by moving to the adjacent node with the lowest number. I first came across it in that Isometric Games In DirectX book (or whatever it was called) but don't seem to come across any other references to it. Also, what is the advantage of A* over the above? Pure curiosity really. Ta. Paul

Sounds like a sub-part of A*, using the given cost only minus the heuristic. Using just what you've outlined would not give optimal paths. It would depend heavily on the order you traverse nodes. Sounds as though it's closer to best first, though it's been a while so I could be confusing my algorithms.

That seems like a variation of A* to me, except with no heuristic and just assuming each node (tile) has a weight of 1.

Edit: Bah, too slow [smile]

I thought A* started at the origin and worked towards the destination. Is that not correct then? Don't know much about it to be honest.

I've used the one above a lot and it certainly LOOKS like it is giving an optimal path. Obviously there are ways to speed up on the above algorithm in terms of how fast it computes the path but over any 2D grid or location to location in text adventures it always produces the shortest possible route.

Thanks for the responses though.

Paul

Yes the working toward the destination is the heuristic cost, but A* also uses the 'given cost' which represents 'distance travelled so far' which is basically what you are talking about. Minus the heuristic you basically have Dijkstra.

ive seen this used a few times, and from my experiences, it hasnt been all that useful

i basically agree with EasilyConfused

I'm way rusty on search algorithms, but that looks like a simple breadth-first graph search. I can't remember if it has a more specific name then that, sorry.

I remember using something like this in a robot simulation, where the map was represented as a series of nodes from landmarks in the environment. It's useful if you don't have a proper heuristic for calculating the A* distance, or if you want to calculate the path for entire map (for example, if your robot gets lost).

I'm a bit unsure of this (due to the rustiness), but I'm fairly sure that while both A* and breadth-based searching will provide optimal results, A* will be a lot faster with a good heuristic.

I think Trapper Zoid is right and this is just a breath-first search, and I think it might be useful in several cases. For example, if you need to go to the goal from many different places this might be a good option.

You can also use this algorithm to make your map smart and store several values, like "distance to food", "distance to water", "distance to enemy camp", etc. A unit can then come up with a utility function to maximize, which is a combination of those values, and then it can decide how to move just looking at the squares immediately around its current location. I read somewhere that The Sims used a similar idea.

Just curious, how are you supposed to pronounce A*? Is it 'a-star'?

I've always heard a star, in French people even call it "a étoile", which is the exact translation of a star.

According to wikipedia, its a star.