+- High Frontier Forums (http://highfrontier.com/forum)
+-- Forum: General (http://highfrontier.com/forum/forumdisplay.php?fid=1)
+--- Forum: Dev Log (http://highfrontier.com/forum/forumdisplay.php?fid=15)
+--- Thread: Pathfinding in a wrap-around world (/showthread.php?tid=141)
Pathfinding in a wrap-around world - JoeStrout - 03-12-2016
We've knocked out a lot of new features and fixes for 0.22, and a few days ago, all that was left was this little issue, where sometimes we see a resident walking off across the lake (or otherwise going where nobody should be).
And wow, that turns out to be one deep rabbit hole!
The problem is that path-finding and navigation in a cylindrical coordinate system (which applies to torus and sphere habs in High Frontier, as well as cylinders of course) is a whole lot more complicated than normal path-finding. Every point has an infinite number of equivalent coordinates. For example, if your cylinder is 100 units around, then a point at X=10 is the same as X=110, X=-90, X=210, and so on.
We were normalizing all coordinates (basically using modular arithmetic) to get all the coordinates into a standard range, but that doesn't work correctly in some cases. A little path from X=90 to X=110 ends up looking like a big path from X=90 to X=10, and then we find a ton of intersections with that and other paths which are halfway around the cylinder. Bad mojo.
We've just about got our heads wrapped around it now; it's all solvable, but tricky. There's been surprisingly little written about this situation, so we will be doing at least a blog post, if not a tech report, once we have it all sorted out!
- Joe
RE: Pathfinding in a wrap-around world - JoeStrout - 03-17-2016
Whew! That was a lot harder than it seemed even a week ago. But I think we have all the edge cases working now.
This was the last item on our to-do list for v0.22, so that blog post is going to have to wait... we need to get the next build out the door!