Use A* with suggestions :


Hierarchical ... coarse/fine pathfind shortens lengths...

Use Heap Q to optimize openlist sorts (tree like sort functionality)

Inline functions -- guy I talked to more than a year ago on USENET game AI group
used MSC++6 professional (inlines worked) ran 3X as fast as me recompiling his code
on MSC++6 Standard ($@#$%& no optimization including NO inlining.

Squareroot approx abs_dX abs_dY dist = longest_side + 1/2 of shortest_side

Quote: supposed I am in a large room, and i try to go into a small room, but there is no entrance into that room, it's door is closed and it is unreachable.

If this is a frequent problem, you have several options depending on your access patterns:

1) Cache results of previous searches.

2) Create a separate 'connected components' graph. Associate each of your pathing space nodes with a node in the component graph. Before doing a search for a full path, do a search over your connected components graph to verify that a path actually exists (optionally, you may be able to make this into a table if your world is static and the number of islands is low).

[Edited by - BrianL on April 8, 2005 10:23:33 AM]

Both Extrarius' and BrianL's suggestions equate to finding a maximal clique graph from the natural connectivity graph. Certainly this is a good optimisation that can be performed offline IF your maps are static.

However, if your maps are static, given the trivially small size of your search space, I think you'd find a simple flood fill algorithm, such as the Distance Transform Algorithm, far more efficient for your needs. It also has the aesthetic side effect of being able to easily predict when a destination is unreachable.

Furthermore, suboptimal paths are trivially found by permitting an erroneous transition of states with a small probability (the probability being proportional to the level of supoptimality).

There are also some lovely optimisations one can do when using contiguous memory to represent the map that really speed the algorithm up.

Just my 2 cents worth...

Cheers,

Timkin