Some Notes for Myself
I’m in the planning/prototyping phase for an exploration app. These are some links and notes mainly for myself:
http://petitjeanmichel.free.fr/itoweb.petitjean.spheres.html#REF1
http://mathworld.wolfram.com/Sphere-SphereIntersection.html
http://mathworld.wolfram.com/ReuleauxTetrahedron.html
Anyway, the intention of the app (if I’m ever able to make it), is to determine the coverage given a particular placement of probes as well as possibly finding the best possible coverage. It turns out that computational chemistry of all places has the most information on the strategies I’m considering using. Although it might be closer to plain ol’ topology or advanced 3-d math - sadly, I’m currently lacking knowledge in these areas. So there is much research and learnin’ to be done.
If you know much about spherical intersections and volume calculations with N spheres, drop me a line. Hacking through all this myself is pretty tough so far.
April 4th, 2008 at 6:43 pm
> determine the coverage given a particular placement of probes as well as possibly finding the best possible coverage
Interesting challenge (though how practically useful, I’m not sure). For the first goal, you COULD try to calculate out a precise answer, by solving lots of equations. Or… you could just cheat and approximate the answer, to whatever degree of precision you want, by a sort-of Monte Carlo type calculation.
Basically, define your planet and probe positions, in an x-y-z coordinate system. Then loop and randomly choose n positions in space. If a given random position is NOT within 4au of a planet, go to the next position. If it IS within 4 au of a planet, determine whether it is within range of any of the probes. The fraction of random points that is within probe range divided by the total number of random points that was within 4 au of a planet becomes the empirically estimated coverage percentage. The bigger n is, the more accurate your estimate. It’s important that your random point choice is truly random; any given spot in space should have an equal likelihood of being picked. You could write a program to do this in about half an hour, I’m sure.
As for your 2nd goal — “best possible coverage” — that’s a harder problem… You’d have to define your constraints too. With an unlimited # of probes, inefficiently placed, you’d probably be able to get 100% coverage. But since, there’s no way to precisely place bookmarks in EVE — practically, I’m not sure how useful it would be.
April 4th, 2008 at 8:35 pm
I was actually thinking about the exact same Monte Carlo solution you were talking about. My 3d geometry skills are lacking at best and the Monte Carlo approach just replaces that with brute force, a method I always enjoy using
At this point it’s almost all academic. I’ve gotten a little more exploration experience under my belt and am realizing just how nearly useless this all is in actual situation. Best guess probe placement and/or switching up planets that are covered for really persnickety sites seems to work just fine. There’s always just that little part of me that wants to know *exactly* what the solution is
The solution I started drawing up in my mind for best possible coverage had 2 phases to it - determine the best placement using planets only, and then trying to add in the possibility of bookmarked locations (or some approximation thereof). I think you can assume that the best possible non-planet locations would be right at the intersection of 2 other probes (in most cases). So that can give you an idea of where to put another probe, within some constraint as to the maximum number you want placed. I believe you can also determine if a spot is at least possible as long as the location lies within the set of all the outermost celestial bodies - theoretically, all locations inside those objects are bookmarkable by some number of intermediate bookmarks.
Again, all academic. My problem solving brain just got carried away with this whole idea.
Thanks for the comments though. It’s fun to brainstorm about silly stuff like this.
May 28th, 2008 at 8:31 am
Agreed with the “nearly useless” aspect of coming up with a perfect theoretical solution, that can’t be used in-game.
But if you ever play with this again, here’s a “somewhat useful imperfect but practical solution”: try to come up with best possible coverage, using the maximum # of probes that are already directly on planets (i.e., no work to obtain) PLUS the minimum # probes that are DIRECTLY in-line between two celestials (i.e., bookmarks that can be placed with a few tries, just warping between two celestials and the in-line temporary bookmarks.)
For example, for a given system, the tool might report to you: “For 97% coverage, place probes at planets V, IV, III, and a fourth probe at a location in-line between planets I and II at a distance of 2.2 au from planet I.” That would be a useful tool, and potentially not TOO difficult to code, basically automating what I’ve done by eye and guesswork, in my little bit of exploration experience.