A note on pathfinding

edited in General
Gleamed from http://www.shiningrocksoftware.com/?p=901

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

  • Unfortunately I don't have a link to the page at this time (I'm hoping somebody else here might know what I'm talking about) but it may be that I find it somewhere in my browser history some time.

    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)
  • Great articles. Nueral pathways for logic is always fascinating
Sign In or Register to comment.