Not good enough yet, but an improvement.
I did a small update to Detour yesterday. The heuristics of the Detour path finder have been really bad and I though about improving it a bit. The pathfinder should perform now much better especially with meshes generated using the tiled process. I'm pretty sure Mr. Ericson would not approve my changes, though. I have to admit that I do not understand the problem good enough yet.
I settled to something that does not over expand the open list and something that is visually pleasing as well as coherent.
I noticed that the problem is not only they heuristics, but also the cost function. It is main in the ass to create good cost function which would work with many types of polygons. Additionally the tiled processing sometimes generated regular squares, which eve further messes up any cost function that you come up with.
The cost function I ended up doing actually measures the distance from previous polygon to the next polygon instead of current to next. It sort of emulates 8-connected links in 4-connected environment. I think using the midpoints for anything related to polygons and pathfinding is super bad. Especially trying to follow a path by following the midpoints! Edge mid points may be one notch better choice, but they are bad estimate too.
Visually, looking at the results a Dijkstra producses, the problem looks a lot like distance field building problems. I wonder if one of those algorithms could spark some ideas. The CDA algorithms are close to my prev-to-next distance calculation in the sense that they use larger environment to make better guesses.
Image from paper: George J. Grevera, The ‘‘dead reckoning’’ signed distance transform, 2004.
This is great work you're doing! I'm looking forward to further developments.
ReplyDeleteUsing centroids is even worse when you're pathing through a triangle strip! Edge mid-points are much better. I'll have to try combining them with your previous-to-next idea.
(Your link to the Grevera paper is broken: it has "www.blogger.com/" at the start.)
(Link fixed, looks like links without http will get some extra address added.)
ReplyDeleteI certain cases the edge midpoints are indeed better than centroids. Maybe it would be possible to adjust the edge midpoints based on the previous nodes?
I tried out a cost function that fits the point on the edge based on the previous and next edge midpoints, like a local path smoothing. It's somewhat slower (I get about a 15% reduction in speed on the A* part of the path find). I haven't really noticed any path improvements yet. I should run it through a test suite.
ReplyDeleteHave you tried on almost regular grid type of scenario? I don't get much improvement on the meshes which come out of my non-tiled process, but the when there are more regular tiles, my regular cost function starts to behave almost random on diagonal paths like in the above picture. That is, an L-shaped path is as short is more pleasant diagonal path.
ReplyDeleteUsing edge midpoints eliminates L-shaped paths, without giving regions a lower than realistic cost, which previous to next can sometimes do (since the straight line from previous to next might not touch current).
ReplyDeleteHmm... I think I'm starting to get this :) I will need to try out the edge midpoint version at some point.
ReplyDeleteI assume that when you use the edge midpoints, you place extra A* node at the start and end location and then all the rest nodes are at edge midpoints? Versus my current version where all the nodes are at the polygon centers and start and end do not receive any special attention.
Now that I think about, it the above scenario should also find better first edge in the start and end polys.
Steve, is any of your work available somewhere online? I would be interested to see how other people have solved their pathfinder data structures.
Start and end are special cased to return the path start and end, rather than edges or centroids.
ReplyDeleteMy code is proprietary - unfortunately I can't share it. But there's not much more to it than this.
On a grid, I love how your previous to next calculations automatically produce Bresenham style lines. That's something typically lacking in tiled pathfinding - usually the path goes on a 45 degree diagonal until it gets to the same row as the destination.