Im writing a star map program for the 2300AD roleplaying game. 2300AD was a roleplaying game written back in the 80's by the now defunct Game Designers Workshop.
In the game, adventurers could travel from solar system to solar system, providing that they were no further than 7.7 light years (ly) apart. The 2300AD game came with a Near Star List, a list of nearly 700 stars within 50 ly or our own Solar System (Sol). Each star had an X, Y and Z coordinate, with Sol at the origin.
What I would like to do is iterate through the list of stars and calculate all the links that are within 7.7 LY. Id like to do this in the most efficent manner possible.
Ive thought about an algorithm for doing this, but I thought I would throw it out to you folks to see if you could come up with something more efficient.
All the star information is stored in a database.
My algorithm is something like this For each star a in list 1) Select all stars from <starlist> where x coordinate is + or - 7.7ly, y coordinate is + or - 7.7ly, z coordinate is + or - 7.7ly 2) For each star b returned in <selection> 2a) If entry for a to b OR b to a in <links> then get next b 2b) Work out absolute distance between a and b 2c) If absolute distance between a and b <= 7.7 then store in <links> 2d) Get next b 3) Get next a
<starlist> and <links> would be tables <selection> is a result set from <starlist>
Sorry if my pseudo code sucks! Anyone think of a better way of doing this?
Having done no math at all to verify this, it might be worthwhile to sort the list on, say, the x coord. that should be pretty darn fast. then, for each star, you don't have to check any star earlier on the list (you've already tested it travelling the other way), and as soon as you get to a star > 7.7 on the x-axis, you don't have to test any more.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Joined: Dec 08, 2001
Originally posted by fred rosenberger: Having done no math at all to verify this, it might be worthwhile to sort the list on, say, the x coord. that should be pretty darn fast. then, for each star, you don't have to check any star earlier on the list (you've already tested it travelling the other way), and as soon as you get to a star > 7.7 on the x-axis, you don't have to test any more.
Thats a pretty good idea; in the original list, the list is sorted in alphabetical order rather than by a particular coordinate axis, so as I build up my list of connected stars Id be jumping all over the place. Make more sense to sort by one axis and work along it. Thanks!
A step ahead we can say replace the conditions with: (ABS (s.x - n.x) < 7), while 'ABS' might be vendor-specific.
...and Phythagoras, who is looking over my shoulder says:
Did you knew, Phythagoras speaks SQL?
Btw: PostgreSQL supports 3d-coordinates and might have a function s.distance(n) < 7, if you defined x,y,z as Coordinate. I never used it, only know from flying over the docs. [ June 10, 2004: Message edited by: Stefan Wagner ]