# A note on pathfinding

Especially on large maps, it's expensive using A* when there's no route between points A and B (because A* will have to search the WHOLE map to confirm it's not available). A better solution is to have an

*access map*so the pathfinding can

**first**checks if points A and B are connected before then calculating the path.

## Comments

I saw an article somewhere about a technique that you can use to shorten the time taken to find paths which is effective when there are multiple paths of the same length.

Consider a grid of nodes, and consider 2 nodes A and B where B is the node to the top-right of A. Assuming diagonal moves are not possible, one can get from A to B by either going Up->Right, or by going Right->Up, both paths are equally long and equally easy/difficult/favoured so A* will expand both of them at the same time. Clearly this is not the most efficient way to handle things because it's basically finding you 2 different (but equally optimal) paths, when you only need 1.

Thats the general idea if I recall correctly...and *somewhere* I'm sure I saw here is an article that explained a way to handle such situations so that it did less work.

EDIT: Found it. The word I was looking for was "symmetry" :P

You can find the article here (AIGameDev)

Also, google turned up what I think is the same article on his blog here, which is conveniently broken up into 3 parts. Because I certainly don't want to read such a long article in one go...especially not now (at 3AM X_X)