Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Pathfinding in a wrap-around world
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

Joe Strout
Lead Developer, High Frontier

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!

Joe Strout
Lead Developer, High Frontier


Forum Jump:

Users browsing this thread: 1 Guest(s)