Posted on Apr 7, 2011

Pathfinding 103

Last night, while testing different scenarios with my pathfinding, I found a case that was dead-wrong and would produce a robot-like movement for my AI. So I’m back to optimizing the path.

Navigation mesh

Fail

Blue lines: actual path; Red lines: desired path

I could simply run a line-line test to check if the origin sees the target but that would be too easy. In a more complex path where the path goes along a corner, the simple test will fail and the path will remains centered. So in a wild quest to find an algorithm that would produce desirable path with better cornering, I found a thesis on Efficient Triangulation-Based Pathfinding. I don’t pretend that I understood everything, but it gave me the pieces I needed to develop my own code.

Connections between triangles can be seen as door-frame, if you can see both edge of the frame from where you currently are, remember it and continue to the next one; if you cannot see one of the edges of the frame, say the left one, plot a corner to the last left edge seen and this corner is now your current position. In the screen above, the red path found itself into every door-frame leading to the target: a direct path. So this is basically a good solution to achieve not-so-stupid-path.

Navigation mesh

Optimized-ish path

This is working beautifully with a complex path… with some minors hiccups when both edges of the door-frame aren’t seen from the last position. I’m going off the map for the weekends so I’ll tie everything up when I come back.

I almost forgot that I managed to adapt my code to be asynchronous with Coroutine in Unity. So you can set a maximum allowed time step for the search so it will knows when to pause to the next frame. It’s a mess for now so I’ll clean up (much more a fan of re-code) my code when everything is working so I can publish it on my Google Code.

Latest Tweets