09 Jul, 2009, Banner wrote in the 41st comment:
Votes: 0
David Haley said:
I wouldn't make dead space just for the sake of realism. The other things you described sound far more interesting because they actually involve game play.

If dead space truly is empty, i.e. you're not going to be auto-generating content etc., that's a pretty important thing to know when choosing a data structure.

I will be generating mob ships, space stations, debris, asteroids, but I'm not sure how that will be accomplished yet, but I need a data structure that will allow me to encompass it.
09 Jul, 2009, David Haley wrote in the 42nd comment:
Votes: 0
Debris and asteroids are very easy because you don't really need to track anything. If a player ends up in space, just generate a bunch randomly and you're done. Space stations could be treated like asteroids, except that I would have an expectation that if I leave and come back, the station is still there. Asteroids can just be thrown away; I'm not sure you can do that with space stations. Mobs are a little different in that you don't necessarily have the expectation that they stay in place, so maybe they're more like asteroids.

My first-stab inclination here, based on what I've heard so far, would be to use some form of spatial partitioning data structure. Since the "world" is 2d, it's simple enough to represent; you only need 3d space in relatively local places. A quadtree sounds like an easy enough first data structure (although a kd-tree would give better granularity).

The idea is that you divide space into subspaces depending on where things actually are (where "things" can be static such as star systems and other "interesting locations", or dynamic as well based on players – static should be sufficient). You keep on doing this until you reach some granularity that you are satisfied with (such as the size of a typical "playing field", or something) – these are the tree nodes. Players have a pointer to their current node. When you want to find neighbors, you can use the tree to very quickly prune the total list of things and get only those nodes that are within the bounding box of "neighborhood".

If you have a very large world with big empty spaces, this kind data structure is very good at not wasting much space on that whole swath. It's also rather good at efficiently finding neighboring things. It's most applicable when you have a very large world with a bunch of stuff happening in it.
09 Jul, 2009, Scandum wrote in the 43rd comment:
Votes: 0
David Haley said:
Then stop acting like the only alternative to your "pointer grid hash map" is a balanced binary tree. :rolleyes:

Is it that time of the month again?

Banner said:
I would like this whole grid thing explained as well. The whole basis for me wanting to redesign is to put all of space and ships into one 'galaxy'. You wouldn't need to 'calculate starsystem x y z', you'd 'calculate x y z'. Planets, ships, stations and all of that would be in one giant starsystem. I don't know what you mean by putting it into a grid, but the method KaVir described with the tracking a player's plot over one does seem intriguing and would be of great use if I knew how to sontruct it.

I guess a good question would be how much memory you're willing to spend.
09 Jul, 2009, Banner wrote in the 44th comment:
Votes: 0
Scandum said:
I guess a good question would be how much memory you're willing to spend.


Are we talking 2, 3, 10, 20mb here or hundreds? Or less? I dare say more than 10mb would be too much.
09 Jul, 2009, David Haley wrote in the 45th comment:
Votes: 0
Any kind of literal grid mechanism is likely to be rather expensive given the size of your universe. A straight binary tree is likely to be inefficient, again given the size of your universe and the number of things it will apparently have.

Memory is only one of your concerns when dealing with very large domain representation problems.
09 Jul, 2009, KaVir wrote in the 46th comment:
Votes: 0
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.
09 Jul, 2009, Scandum wrote in the 47th comment:
Votes: 0
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.
09 Jul, 2009, David Haley wrote in the 48th comment:
Votes: 0
What is a "wobbly data structure"?
09 Jul, 2009, Runter wrote in the 49th comment:
Votes: 0
David Haley said:
What is a "wobbly data structure"?


wobbly data structure == 'unbalanced' tree? :)
09 Jul, 2009, quixadhal wrote in the 50th comment:
Votes: 0
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 coordi.... 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.
09 Jul, 2009, David Haley wrote in the 51st comment:
Votes: 0
I think that if you want to introduce imprecision for gameplay, you should do it explicitly rather than relying on artifacts of floating point arithmetic. If you did it with floats and then changed to doubles, suddenly your gameplay would change, probably unintentionally so.
09 Jul, 2009, Kayle wrote in the 52nd comment:
Votes: 0
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
10 Jul, 2009, David Haley wrote in the 53rd comment:
Votes: 0
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.
10 Jul, 2009, Kayle wrote in the 54th comment:
Votes: 0
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.
10 Jul, 2009, Runter wrote in the 55th comment:
Votes: 0
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.
10 Jul, 2009, Kayle wrote in the 56th comment:
Votes: 0
Hrm. I wonder why Wikipedia didn't come up while I was searching earlier…
10 Jul, 2009, Scandum wrote in the 57th comment:
Votes: 0
Might as well go for an octree while at it in that case.
10 Jul, 2009, David Haley wrote in the 58th comment:
Votes: 0
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.
10 Jul, 2009, Scandum wrote in the 59th comment:
Votes: 0
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
10 Jul, 2009, Zenn wrote in the 60th comment:
Votes: 0
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..
40.0/76