To answer the OP's questions:

(1) that algorithm is known as the Distance Transform algorithm.

(2) A* has the advantage that it is optimally efficient. That is, it guarantees to expand fewer nodes in a search tree to find the optimal solution (if it exists) than any other algorithm. However, the cost of implementing A* can actually make it less efficient than simple algorithms like the DTA. It really depends on your particular problem.

Cheers,

Timkin

That is 'breadth-first'. It is a brute force method that sometimes can be useful for small maps -- when more complex methods have more overhead versus the simple processing of scanning neighbors in a expanding box. Often the low data requirement allows the method to be executed right on the game/simulations map (versus requiring the Open/Closed node sets used by other methods).

Quote: Original post by Anonymous Poster
That is 'breadth-first'.

Yes, it is an example of breadth-first search, but as I said above, that particular algorithm is known as the Distance Transform.

Quote: It is a brute force method that sometimes can be useful for small maps -- when more complex methods have more overhead versus the simple processing of scanning neighbors in a expanding box.

I think I'm hearing an echo...

A distance transform computes the optimal path between one location and any other location in the map in time proportional to the number of map nodes, which is obviously optimal; A* (like simpler depth-first, breadth-first, etc. searches) computes paths between two locations, which is a different problem.
Obviously the effort to compute a distance transform and spend memory to store it is justified if the path information is reused: unchanging obstacles, fixed origins and destinations, large numbers of agents dispersing from the same place or (more commonly) going to the same destination.
As a practical example, in Liquid War an approximate distance transform (dynamically updated every frame) is used to move each player's hundreds of units (which conveniently converge towards a single cursor).

Quote: Original post by LorenzoGatti
A distance transform computes the optimal path between one location and any other location in the map in time proportional to the number of map nodes, which is obviously optimal

That would depend on your termination condition. ;) Most implementations I have seen that weren't obvious flood-fills of the whole map would only search as deep as the cost horizon of a particular node... but yes, you are most definitely correct in what you say... and certainly the DTA is a very good method for handling multiple units pathing to a singular point. 8)

This sounds like a version of Dijkstra's algorithm to me. Is Distance Transform a special case of Dijkstra's?

Quote: Original post by Froztwolf
Is Distance Transform a special case of Dijkstra's?

The short answer: no.

I'd call that "flood fill" (from raster graphics). I agree it's a basic breadth-first search.