Perhaps you need to read up on what we've been talking about…! I'll even give you a hint and point you to posts 10 onwards. I know you have all kinds of nasty adjectives to describe me, but really, at least read the thread before calling me completely stupid. :wink:

One interesting thing to note about using an imprecise data type for long distance travel is that your set of fine-grained coordinates that match the coarse-grained coordinate will become larger as your travel distance gets larger. It will also tend to produce errors in the same direction. By that, I mean if the coordinate 3.456 happens to line up with local coordinates 34560 .. 34569, if you are approaching from one direction, you will tend to enter at 34560, whereas approaching from the opposite direction lands you at 34569 (taking the first match along the given vector).

As David said, you may not want to rely on the data type to do this… you could instead just model it yourself. EVE-Online does a nice job with this, in the distance of the vector tends to always be about the same (if you warp to the same location FROM the same origin, you always end up around the right distance), but the XZ plane gets a bit of seemingly random noise tossed in. This may not even BE noise, it may be variations in the exact angle your ship was pointing when the warp drive kicked in.

Personally, I think it's a mistake to not have a fully 3D galaxy, as it gives you much more freedom to add interesting events that are local to your main hubs. The cost isn't really that high to do so…. moving more than a few light years from the plane of rotation yields mostly empty space, so either unused cartesian coordinates, or non-existent vectors. It also leaves the door open for players to build things off the ecliptic plane, which actually does make them harder for many people to find.

But having said that, it's also not a huge deal. Even EVE allows you to collapse the map into a flat 2D view, although there are a few systems that overlap. :)

Couldn't find 'grid' in any of me algorithm books.
One wonders what it is.

Try looking under "spatial index".

http://en.wikipedia.org/wiki/Grid_(spati...

I was thinking it should be possible to have an octree always narrow itself till it reaches the volume of 1 cubic light year, and provide a single pointer to that location. So this way the octree would have a head pointer, 8 tail pointers, and a solar system/dead space pointer, which would add up to 40 bytes. The downside of this is that it always takes LogN steps to find the player's new location, which would be about 36 steps. Assuming inter-solar travel is rare this should be very doable, and you could have roughly 10.000 locations before reaching the 4MB memory point. You'd definitely have to add a way to remove locations when the visiting players have left.

From a game perspective it might be neat to work with additional star maps. Whenever you jump you know roughly where you ought to be, but you'd have to compare star maps to confirm your actual location. The ship's hardware, and the accuracy of the map, would determine the precise location. So a player would have their actual location, and their believed location. This could result in the hilarious situation where a player finds a valuable solar system, but is unable to find it back because their coordinates were several hundred light years off due to repeated jumps. It should also be possible for confused players to ignore the galactic coordinates, and determine their coordinates relative to another object, be that an enemy ship or the sun of the solar system they're currently in. Once again you could make this dependent on the ship's sensors and hardware, and if someone damages your sensors you're pretty much screwed, as you would be in an actual space situation.

So I'm working out a data structure and system that I think can handle/contain all of this, but I'm pretty new to this kind of thing. So I'm wondering exactly what kind of features should the implementation itself have? Currently all you can do with my container is add an object, remove an object, access an object, and calculate the distance between two objects. You can choose during initialisation how many dimensions the container should be composed of, but I only support distance calculation in the 1st 2nd and 3rd. :P

From what I read about, I should at least be able to relate a list of objects within a given distance, so I guess I will start with that. =)

It depends on the game mechanics, but I would like to see api's for:

Obtaining the absolute position of an object (relative to some point, IE: Galactic Center).
This could be either as a vector or as XYZ coordinates.

Obtaining the relative position of an object from another object (as a vector, so distance + angle(s))

Obtaining a list of objects within a finite conic section of another object.
That one is so you can have directional scanners, typically you'd want an omni-directional scanner that only reaches short distances, but a more focused directional scanner that resolves things further away Specifying an origin object allows you to get data from scan probes or installations, not just from your own ship.

Obtaining the relative velocity of an object to another object.
That way you can see if something is moving towards or away from you, and if your game implements turret tracking or other such things, the angular velocity becomes important.

Using EVE-Online as an example (yeah, I do like that game), here's how their scan probes<... work.

Obtaining the absolute velocity of an object (with respect to the object's fore/aft axis).
This is to show how fast your ship is moving, even if you are spun around on axis to shoot at things around you.

Obtaining the absolute velocity of an object (with respect to the GC).
This is how fast you're moving on the map.

It may be that the velocity information should be returned as part of the positional data, so asking for info on my ship with respect to your ship would give (in 3D) 2 angles, a distance, and a velocity. Add in a timestamp, and you can calculate current distance without having to query again (assuming neither object has changed velocity or heading).

I dunno, that's what I'm thinking at this point in time. YMMV. :)

So there's no question of going with a grid system at all. ;-)

It looks like SWR has two layers, one is a 2d grid at the galactic level and a 3d grid at the system level.
No mention though of how they are implemented here. Are they graphs, lists, arrays, trees, something else?

Well my data structure design is as follows (It obviously sucks, because my benchmarks use 900 MB of memory when I populate with a lot of things). I just don't understand why it's bad.
This isn't the same one I mentioned before either.
It is basically a binary tree, I tried to make a graphical depiction here in text but I can't really do it. So here is my explanation.

The tree is empty, and you add the data "foo" to coordinates [9,13,17]
Key 9 (the first coordinate added) becomes the root of of our tree. From key 9, a new child node is added "up" from 9, with the key of 13, and then 17 is added to the right of 13, holding the data "foo".
Now we add the data "bar" to coordinates [9,13,22]
We traverse to 9, and then up to 13, and then to 17, and then ceate the node 22, storing the data "bar"
Now we add the data "foobar" to coordinates [7,15,22]
We traverse to 9, and then we go left and create the node 7, then we go up and create the node 15, and then we go right and create the node 22 which holds the data.
Now we add the data "barfoo" to coordinates [7,6,12]
We traverse to 9, then we go left to 7, then we go down and create the node 6, and then we go right and create node 12, which holds the data.
So basically it's just a binary tree, with an addition "up" and "down" to keep the rest of the coordinates nearbly. If we were to use 4 dimensional coordinates, our second number would be created as a branch, just the like the first (with up's and downs) and the other two would branch from there.

Is this really that inefficient?

Well, I don't really see a reason it should be 900 megs regardless but…when you write in a pure high level language like this there's a lot going on under the hood. One variable becomes many, etc. For this type of thing you'd really need to extend it into Ruby in C.

Yeah, I agree. That's what I'm doing right now. extconf is awesome btw.

Quad and octrees are technically grids.

What data structures would you propose for building a galaxy?

How about a connected graph?

Each node (star) holds vector data about its neighbors, and one to the origin. Thus, lookup times between adjacent nodes are 1 hop, and lookups between non-adjacent nodes are 2 hops (one from source to origin, one from origin to destination). To avoid having congestion at the origin, you always do the lookups from the node TO the origin.

You can find the shortest path using A* if you're hopping from star to star, or a straight line if you have enough fuel to warp directly there.

Each star can then contain a connected graph of planets and other "interesting" objects for local travel.

Trees are useful when you know you're going to be accessing the top layers most often, if that's not the case, they aren't always the best choice.

I think I'd design the game first.

Yes, as I said, until you know what question you're trying to answer, trying to find an answer is a somewhat futile exercise.


Other than what has already been said – that you're paying a massive price in overhead due to the language – there's a further issue having to do with the general concept involved. The idea behind spatial partitioning is not really (or at least not necessarily) to exhaustively index every last coordinate. The idea is to have a quick means of dramatically cutting search space. You can cut search space by dividing your universe into just four parts, and then you can (usually) avoid looking in 3/4ths of your universe – already a massive improvement! Now consider that you build your divisions intelligently and try to balance the number of things in each division. If you divide each of those 4 segments into 4 again, you have 16 sectors, and searching can often remove 15/16ths of the world, or perhaps slightly less if you have to visit neighboring squares.

So basically, I'm not sure you're necessarily using the data structure correctly if you're trying to index everything. I would add things to the tree until you reach one of the following conditions: some maximum depth, or some number of nodes inside that leaf. For example, you might not want a tree that has more than, say, 10 levels to it. Or, you might be happy if your indexing is such that you end up with just a hundred nodes per leaf. It turns out of course that these are two ways of saying the same thing for a given universe size, as a tree's depth allows you to compute how many leaves it has, and therefore you divide the total number to get the number of nodes per leaf. (And vice-versa.)