KaVir
Wizard
Group: Members
Posts: 1,116
Joined: Jun 19, 2006
|
#46 Posted Jul 9, 2009, 3:37 pm
|
David Haley said:Any kind of literal grid mechanism is likely to be rather expensive given the size of your universe.
"Just" a galaxy, but the point is still valid. I was originally thinking the vast majority of it would be generated though, so that only a tiny portion would need to be explicitly mapped out - perhaps either a simple grid (if the hand-built parts are in a small cluster together) or a quadtree (if they're scattered around).
A typical wilderness system could actually be used to handle space travel reasonably well I think, with only a few (mostly cosmetic) modifications. It'd certainly be one of the easier ways to implement it. Not the most elegant though.
|
......................... KaVir at God Wars II: godwars2.org 3000 Roomless world. Manual combat. Endless possibilities.
Last edited Jul 9, 2009, 3:40 pm by KaVir
|
|
Scandum
Wizard
Group: Members
Posts: 1,105
Joined: Aug 8, 2006
|
#47 Posted Jul 9, 2009, 3:43 pm
|
Banner said:Are we talking 2, 3, 10, 20mb here or hundreds? Or less? I dare say more than 10mb would be too much.
Assuming 4 byte pointers you'd have a 4 MB grid. Each index in the grid would point to either NULL or a sub_galaxy pointer which would contain a sorted array of solar systems, and a sorted array of so called dead_space, or use linked lists / whatever you're comfortable with. A solar system and dead space would measure 1x1x1 light years allowing a maximum of 10.000 solar systems/dead spaces per location on the grid.
When a player jumps to a sub_galaxy that points to NULL you'd have to create a sub_galaxy on the fly and populate it with randomly placed solar systems. Next you'd have to see if the player is within a solar system/dead space, and create that on the fly and populate it with astroids/planets/etc. Design wise it'd be easiest to keep things contained within their solar system, so people can't detect anything outside of their solar system, though in theory it should be possible to scan bordering solar systems/dead space, but since 1 cubic light year is pretty big people probably would never notice it. When the last player jumps out of a solar system or dead space you can destroy it, and when the last player jumps out of a sub_galaxy you can destroy that as well. If you want data persistance, for example, player A burries item B on planet C you could keep things in memory and add a bunch of events to destroy the data at a later date.
If you use a shared object system like I suggested you'll save additional memory. Sure it's possible to use something other than a grid, but 4 MB is nothing nowadays, so if you have the memory I'd suggest saving yourself a headache and using it. I'm not a fan of building wobbly data structures on top of wobbly data structures, regardless, the grid can be replaced by a binary tree. I'd advise against a quad tree and instead go for straight forward hashing if you want to go that route.
|
|
|
|
|
Runter
Wizard
Group: Members
Posts: 1,074
Joined: Jun 1, 2006
|
#49 Posted Jul 9, 2009, 4:02 pm
|
David Haley said:What is a "wobbly data structure"?
wobbly data structure == 'unbalanced' tree? :)
|
|
.........................
-Heath
For once you have tasted flight Ruby you will walk the earth with your eyes turned skywards,
for there you have been and there you will long to return. --
Leonardo Da Vinci Yukihiro Matsumoto
|
|
quixadhal
Wizard
Group: Members
Posts: 1,256
Joined: Oct 17, 2007
|
#50 Posted Jul 9, 2009, 6:15 pm
|
Ack! Who dragged the pointer hash grid thingy in here? :)
Anyhoo... my idea was just to store positions as offsets from your galactic center. In a 2D plane, you need an angle and a distance to pin down a point, which is referred to as polar coordinates. You can extend this to a 3D sphere, either by specifying two angles (one for the XY plane and one for the YZ plane), or perhaps more simply by specifying a height vector from the point on the XY plane. That's how the game Homeworld handled navigation, you dragged out a ray at an angle from your ship and once that point was set, you dragged a second ray for the height.
Either way, it makes relative point to point navigation very simple. Finding the relative vector to an object requires one conversion... you already have your absolute position (from GC), you query the absolute position of your destination, and then you do a single conversion (pythagoras?) to get the vector from you to it.
Of course, you can convert back and forth between cartesian (grid) and polar coordinates, so it's not magic. I think it makes more sense to store and use polar coordinates for a game where 90% of your interactions would be relative vectors between objects. One bonus you get from this approach is that you have a built-in way to control granularity.
If you use integers for your relative coordinate sphere (the space around your position), you have a constant point spacing around where you are. If you want to travel farther, you could switch to floating point and lose precision, which would simulate small errors that might result from miscalculating gravitational effects.
So, let's say you want to travel to another star system that's 150ly away. Maybe your 32-bit local coordinates are based on km, and 150ly is 150 * 9.5 trillion km, so you use a float to travel. 1.425x10^15km. When you get there, your actual precise destination might not be spot-on, but it will be within the 2x10^9km sphere of your local coordinate system. So, you turn off the warp drive and kick in the standard drive to cover the remaining distance.
I haven't really tried to provide any sort of working system for this, but that's my idea. I think it's doable, and it feels like a better fit than trying to force box coordinates around the problem.
|
......................... 
|
|
|
|
Kayle
Wizard
Group: Members
Posts: 979
Joined: Nov 27, 2006
|
#52 Posted Jul 9, 2009, 6:48 pm
|
Quix's idea sounds like the perfect way to handle travel, and the imprecision is perfect as well. Hyperspace/Slipspace/Warp travel is inaccurate, It's fairly easy to get to the intended system, but then you might not end up exactly where you intended to be. As an aside, after reading the books based around the Halo games, the Covenant appear to have a much higher accuracy with slipspace jumps due to the fact that they've been working with it longer than humans. So I don't know for sure how you could introduce a controlled variation on the exit vector for a Hyperspace/Slipspace/Warp jump.
I think I like the idea of a quadtree though, I might have to look into those further.
All this talk has me wanting to actually write a space system ... Looks like the first drop-in module for Elysium might be added to the to do list. :P
|
......................... Owner/Coder Coder
Malevolent Whispers Star Wars: The Sith Wars
{Development Phase - Not accepting players} Open Alpha - Players Welcome - Full System Re-writes Imminent.
IMC2 Contact: Kayle@MW
FUSS Project Team Lead
SmaugMuds.Org - The Smaug MUDs Community Center
|
|
David Haley
Wizard
Group: Members
Posts: 5,730
Joined: Jun 30, 2007
|
#53 Posted Jul 9, 2009, 10:07 pm
|
Kayle said:So I don't know for sure how you could introduce a controlled variation on the exit vector for a Hyperspace/Slipspace/Warp jump.
By doing it on purpose and not by accident. Don't rely on imprecise data types: simply do your calculations in units appropriate for your distances. If the basic unit is the light year, express jumps in terms of light years. You can still do things like 0.001 light years if you want smaller distances. (The floating point error is far smaller with these sizes.) Once you have appropriate calculations, you simple introduce random noise to the destination; dest = dest + random_vector, where the vector is smaller in proportion to the quality of your jump drive and/or navigation systems.
|
|
|
Kayle
Wizard
Group: Members
Posts: 979
Joined: Nov 27, 2006
|
#54 Posted Jul 9, 2009, 10:22 pm
|
So, I spent the afternoon researching this quadtree thing you talked about, and I couldn't find any guides/explanations that I could easily understand, anyone have any good examples of how these things work? Also, a lot of them dealt more with 3D Graphics then I expected.
|
......................... Owner/Coder Coder
Malevolent Whispers Star Wars: The Sith Wars
{Development Phase - Not accepting players} Open Alpha - Players Welcome - Full System Re-writes Imminent.
IMC2 Contact: Kayle@MW
FUSS Project Team Lead
SmaugMuds.Org - The Smaug MUDs Community Center
|
|
Runter
Wizard
Group: Members
Posts: 1,074
Joined: Jun 1, 2006
|
#55 Posted Jul 9, 2009, 10:33 pm
|
http://en.wikipedia.org/wiki/Quad_tree
If a quad tree is a tree with 4 nodes it actually could be used for a lot of things. I think this entry goes over some of the common uses for a quad tree and some of it seems relevant to what you want. Honestly, I think this is pretty involved and complex.
|
|
.........................
-Heath
For once you have tasted flight Ruby you will walk the earth with your eyes turned skywards,
for there you have been and there you will long to return. --
Leonardo Da Vinci Yukihiro Matsumoto
|
|
Kayle
Wizard
Group: Members
Posts: 979
Joined: Nov 27, 2006
|
#56 Posted Jul 9, 2009, 10:35 pm
|
Hrm. I wonder why Wikipedia didn't come up while I was searching earlier...
|
......................... Owner/Coder Coder
Malevolent Whispers Star Wars: The Sith Wars
{Development Phase - Not accepting players} Open Alpha - Players Welcome - Full System Re-writes Imminent.
IMC2 Contact: Kayle@MW
FUSS Project Team Lead
SmaugMuds.Org - The Smaug MUDs Community Center
|
|
|
|
David Haley
Wizard
Group: Members
Posts: 5,730
Joined: Jun 30, 2007
|
#58 Posted Jul 9, 2009, 11:20 pm
|
The galaxy is not 3d, so an octree is not an appropriate choice.
Note that you don't have to use clever data structures on the first go-around. As long as your interface is solidly designed, you can manage the internals in very many different ways. For example, a function like "give me all ships within distance X" could be implemented under the hood as a linear scan of all ships, a traversal of one of these clever spatial partitioning data structures, or something else entirely. Basically, design your interface in terms of your intentions, not in terms of the implementation, and then you can switch later.
It's better to have a working but slow game than no game at all, especially if you can speed things up as you go.
I also found that the vast majority of documents concerning spatial partitioning data structures have to do with 3D graphics. This is perhaps unsurprising since they are so completely essential to 3D graphics and to a large extent 3D graphics has driven the search for very efficient ways of storing and especially retrieving data.
|
|
|
Scandum
Wizard
Group: Members
Posts: 1,105
Joined: Aug 8, 2006
|
#59 Posted Jul 10, 2009, 12:44 am
|
David Haley said:The galaxy is not 3d, so an octree is not an appropriate choice.
Perhaps you need to read up on galaxies: http://en.wikipedia.org/wiki/Galaxy
|
|
|
Zenn
Sorcerer
Group: Members
Posts: 290
Joined: Apr 18, 2007
|
#60 Posted Jul 10, 2009, 12:46 am
|
Great thing about vspace is that it doesn't use too much memory.
Anyway, to answer a few questions:
In SWR each system has coordinates from -50000 -50000 -50000 to 50000 50000 50000 in it.
Each system itself is numbered and on a 2D plane.
When using the hyperdrive to get from system to system, fuel cost is calculated by looking at the distance between planets. Say one planet is at -50, 12 on the plane and another at 29, -5. Once you actually get into a system, the 3D coordinates come into play.
A good example is LotJ's Galaxy Map
Where you see each of those starsystems is on one point in the map. Now, with their system (virtual space) every single system on the grid can be accessed by directly typing the coordinates in (if it's in range) or setting your ship up to 'drift'. You can drift from any of the combinations of the xyz coordinates using positives and negatives and go in different directions on the 2D plane.
EDIT: Oh, wow. I didn't actually notice this thread had 3 pages I didn't read..
|
......................... 
Last edited Jul 10, 2009, 12:47 am by Zenn
|
|
