Thursday, July 16, 2009

Cost and Heuristics Take 2


I had a little time today to take another look at the travel costs and heuristics inspired by the discussion with Steve in the previous post.

Now Detour is using the polygon edge midpoints instead of polygon centroids to calculate the cost and heuristics. The start and end points are also taken into account, so there is slight API change.

The above screenshot shows the comparison between the old and new. In the process I also found out that Detour was not handling the A* open list properly (the nodes never got closed flag, argh!), now it is fixed too. Over estimating the heuristics helps quite a bit to find more straigth path, but making it too great will "wall hug" when finding around obstacles.

The stuff is in SVN now, I will optimize it a bit and make a new release soonish.

No comments:

Post a Comment