*
The moose likes Programming Diversions and the fly likes Star Map program Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Star Map program" Watch "Star Map program" New topic
Author

Star Map program

Mark Fletcher
Ranch Hand

Joined: Dec 08, 2001
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


Mark Fletcher - http://www.markfletcher.org/blog
I had some Java certs, but they're too old now...
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11255
    
  16

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
Mark Fletcher
Ranch Hand

Joined: Dec 08, 2001
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

Joined: Jun 02, 2003
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 ]

http://home.arcor.de/hirnstrom/bewerbung
Mark Fletcher
Ranch Hand

Joined: Dec 08, 2001
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

Joined: Jun 02, 2003
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

Joined: Oct 02, 2003
Posts: 11255
    
  16

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

Joined: Jun 02, 2003
Posts: 1923

Yes - you're absolutely right!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Star Map program