It would be cool if there was a tool to visualise or otherwise measure how badly a design will make A* crap the bed to compare.
I can help with that! I am not a math student by any means, but I have an amateur ability to interprete things. So I went to look at the wiki entry, and Wiki has this very useful animation:
Wiki link:
http://en.wikipedia.org/wiki/A*_search_algorithmNotice that having the interruption slowed down the search process significantly, and the slow down was affected by the size of the obstacle. Once past the obstacle, the rest of the distance was resolved very quickly.
Another gif, showing the effect that multiple paths have:
All of this implies that:
- Any bend in a pathway increases computational time
- More than one pathway drastically increases computational time
From my understanding, the best pathway would be straight lines leading out of stairways, leading directly into relevant rooms.
This seems to imply that small corridors and large rooms with high/low traffic designations should result in best FPS.
EDIT: What I wonder about is how is this computed on a three dimensional level. Is the initial straight line drawn through Z levels, or individually to Z-level transitions?
If through Z levels, this would mean that idling areas should be right on main staircases to minimize path to/from stairs.
Frequently, the journey is Start in resting area -> Go to point A -> Go to point B to finish task -> Go back to resting area