03-12-2016, 07:24 AM

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

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