tag:blogger.com,1999:blog-1272803659321539598.post1747801088659271943..comments2024-03-28T23:38:41.403-07:00Comments on Digesting Duck: Costs and HeuristicsMikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-1272803659321539598.post-70931795371485245872009-07-15T07:27:11.687-07:002009-07-15T07:27:11.687-07:00Start and end are special cased to return the path...Start and end are special cased to return the path start and end, rather than edges or centroids.<br /><br />My code is proprietary - unfortunately I can't share it. But there's not much more to it than this.<br /><br />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.Kweepahttps://www.blogger.com/profile/08971942083796430669noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-60157851780643811972009-07-13T23:26:47.003-07:002009-07-13T23:26:47.003-07:00Hmm... I think I'm starting to get this :) I w...Hmm... I think I'm starting to get this :) I will need to try out the edge midpoint version at some point.<br /><br />I 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.<br /><br />Now that I think about, it the above scenario should also find better first edge in the start and end polys.<br /><br />Steve, is any of your work available somewhere online? I would be interested to see how other people have solved their pathfinder data structures.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-41047016846855480692009-07-13T15:58:03.420-07:002009-07-13T15:58:03.420-07:00Using edge midpoints eliminates L-shaped paths, wi...Using 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).Kweepahttps://www.blogger.com/profile/08971942083796430669noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-2557393569401358612009-07-13T10:26:42.815-07:002009-07-13T10:26:42.815-07:00Have you tried on almost regular grid type of scen...Have 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.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-9218170109453182892009-07-13T09:12:56.447-07:002009-07-13T09:12:56.447-07:00I tried out a cost function that fits the point on...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.Kweepahttps://www.blogger.com/profile/08971942083796430669noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-64279703294951667782009-07-12T01:47:55.385-07:002009-07-12T01:47:55.385-07:00(Link fixed, looks like links without http will ge...(Link fixed, looks like links without http will get some extra address added.)<br /><br />I 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?Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-86573344022858509402009-07-10T09:50:45.753-07:002009-07-10T09:50:45.753-07:00This is great work you're doing! I'm looki...This is great work you're doing! I'm looking forward to further developments.<br /><br />Using 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.<br /><br />(Your link to the Grevera paper is broken: it has "www.blogger.com/" at the start.)Kweepahttps://www.blogger.com/profile/08971942083796430669noreply@blogger.com