Win a copy of Penetration Testing Basics this week in the Security forum!

Star Map program

Mark Fletcher
Ranch Hand
Posts: 897
Hello,

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?

Mark

fred rosenberger
lowercase baba
Bartender
Posts: 12227
36
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.

Mark Fletcher
Ranch Hand
Posts: 897
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.

Hi Fred,

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!

Mark

Stefan Wagner
Ranch Hand
Posts: 1923
You could let the database make the work:

(Using 7 instead of 7.7 for lazyness )

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 ]

Mark Fletcher
Ranch Hand
Posts: 897
Yup doing it in SQL would be ideal. Unfortunately Im confined to storing my data in MS Access

I'll try putting those queries into MS Access and see if it doesnt choke on it.

Thanks!

Mark

Stefan Wagner
Ranch Hand
Posts: 1923
Uhhh! access!
But I would expect an ABS and SQRT on access.

The sql-window will of couse damage my nice indentation!

fred rosenberger
lowercase baba
Bartender
Posts: 12227
36
my math is a little rusty (as is my limited SQL), but that distance formula doesn't look right to me...

don't you want to sum the square of all 3 distances, then take the square root of that???

in other words...

given P(x1, y1, z1) and P(x2, y2, z2), the distance is

sqrt( (x1-x2)^2 + (y1-y2)^2 + (z1 - z2)^2 )

you don't need to worry about the abs, since squaring them will make it positive anyway, no matter the order.

assuming i have my math right, i don't know how to write this in SQL.
[ June 11, 2004: Message edited by: fred rosenberger ]

Stefan Wagner
Ranch Hand
Posts: 1923
Yes - you're absolutely right!