Friday, September 20, 2013

In Which I Attempt to Construct a Position and Give Up

We popped our static wormhole last night.  We did it mostly to roll the wormhole, but since our system was zipped up, we figured we might as well take the opportunity to run the one anomaly that has spawned in our system in the last few days.  (We try to keep our system clean.)  So, we got out the expensive sleeper-killers, and blew away the site.

I warped off the site to get a probing ship ready to resolve the new wormhole.  Jayne brought in an Osprey to boost up everyone's shields for storage, and then fleetwarped everyone back home.  Oops.  Um, did anyone happen to bookmark the site?

No.  Well, we didn't want that ISK anyway.

Since the last time when I really wanted to get to a site which I had no way to get to, I have been stashing away personal bookmarks that are relatively distant from their nearby celestial and not in the direction of any other celestial.  The idea here is to get a set of points that would allow me to construct all game-accessible locations in my system.  I don't have total coverage even yet, but my coverage is very good.  So, I figured that now, with 100m ISK or so of loot and salvage on the line, I might try it.

The idea here is to get a set of bookmarks that, when viewed as vertices, define a convex polyhedron with the desired point on the interior.  You can then warp between any two vertices on an edge, making a new bookmark along that edge.  Consider the two new polyhedra which include the new vertex while removing one of the two vertices that it is on the line between.  The two combined contain the same volume as the original, and so one of them must necessarily include the desired grid.  So, determine which of the two it is, discard the superfluous point, and iterate.  Each time you do this, you cut down on the search volume.  If you do this long enough, you'll get on grid.
2D Analog to Search Geometry

Long story short, it's slow and very tedious.  I started out with my surrounding points on average maybe 5 AU from the site.  I got it down to about 1/10 AU or so, but that took about an hour.  So 50x reduction in search space per hour.  At that rate, to get the error down to grid size -- call it 200km -- it would take roughly another three hours.  And since wrecks only last two hours, it was pretty clear that the whole project was going to fail.  I gave up.

So, right now the process of constructing an arbitrary grid seems pretty hard.  I cannot do it in the timeframe of a wreck.

On the other hand, it does seem like I am not that far off.  If I could double the rate at which I refine the volume, I'd be fast enough.  Having written this up, I've been forced to think about the mathematics of what I was trying to do.  I've already gotten a better idea of what I should have been doing.  I was using perhaps 6 points; I now think a tetrahedron is superior.  And I was taking small slices off each iteration, whereas I now think that shooting for the midpoint would be faster even though it would often make it impossible to simply eyeball which polyhedron contains the target.  So, until next time a juicy site is lost in plain sight... I am going to keep adding to my corpus of points.

1 comment:

  1. What you were trying is really difficult to achieve in practice, despite the relatively simple theory behind it and the simplification that is inherent with EVE Online's 'grid' implementation of space.

    I once chased down a wreck in space that was between two known points, and that took me a bit too long, and ended in full burn in an interceptor. The acceleration and deceleration of warp, plus the one-second in-game tick, makes the fine-tuning part almost impossible to get right.

    I dunno, maybe you could get relatively close given enough time, but there is always the possibility that the object is above or below your deepest z-axis bookmark, and having even 1/10th of an AU to cover without warp drive would render the endeavour unfeasible.