Sign in to follow this  
MARS_999

Best data structure layout for 3D space game

Recommended Posts

I am in the planning stage of how I want to represent the space data in my game. I am not sure if just using a 3d array or a linked list, or a simple 1d array would be the way to go...

The user is going to click on a star system or type in some coordinate system point e.g. x1,y1,z1 to go to that location...

And this data would have to be iterated each frame to update each systems info...

This all new to me, so I am not sure what to expect....

Thanks! Edited by MARS_999

Share this post


Link to post
Share on other sites
[quote name='MARS_999' timestamp='1339386302' post='4948054']
I am in the planning stage of how I want to represent the space data in my game. I am not sure if just using a 3d array or a linked list, or a simple 1d array would be the way to go...

The user is going to click on a star system or type in some coordinate system point e.g. x1,y1,z1 to go to that location...

And this data would have to be iterated each frame to update each systems info...

This all new to me, so I am not sure what to expect....

Thanks!
[/quote]

Ultimately the data structure you choose should be based on how the data is going to be accessed. It sounds like the way you are going to be accessing the data is that you have a set of control points that the user can click on, and each one has a distinct coordinate in world space. This sounds to me like a perfect use case for an array or a map. For the array solution each control point is assigned an index, and when one is clicked, you fetch the coordinates from your array. You could also use a map, if having a distinct key for each object is more helpful, or makes more sense.

I hope this helps.

Share this post


Link to post
Share on other sites
[quote name='metsfan' timestamp='1339388989' post='4948057']
[quote name='MARS_999' timestamp='1339386302' post='4948054']
I am in the planning stage of how I want to represent the space data in my game. I am not sure if just using a 3d array or a linked list, or a simple 1d array would be the way to go...

The user is going to click on a star system or type in some coordinate system point e.g. x1,y1,z1 to go to that location...

And this data would have to be iterated each frame to update each systems info...

This all new to me, so I am not sure what to expect....

Thanks!
[/quote]

Ultimately the data structure you choose should be based on how the data is going to be accessed. It sounds like the way you are going to be accessing the data is that you have a set of control points that the user can click on, and each one has a distinct coordinate in world space. This sounds to me like a perfect use case for an array or a map. For the array solution each control point is assigned an index, and when one is clicked, you fetch the coordinates from your array. You could also use a map, if having a distinct key for each object is more helpful, or makes more sense.

I hope this helps.
[/quote]

Also I forgot to say, this will have to be something that can be unlimited... So I am assuming a vector container or use of realloc or map container still?

thanks!

Share this post


Link to post
Share on other sites
Look into [url="http://en.wikipedia.org/wiki/Graph_(mathematics)"]Graphs[/url].

You could use two layers of graphs. One layer to connect stars together (via some sort of hyperspace gates), and another layer to connect planets together within a star solar system. The UI could just be a simple 2D interface where you click on a star/planet you want to travel to and you'll get there by computing the "shortest path" (check out [url="http://en.wikipedia.org/wiki/Dijkstra"]Dijkstras Algorithm[/url] as a starting point).

Share this post


Link to post
Share on other sites
[quote name='MARS_999' timestamp='1339409264' post='4948105']
Also I forgot to say, this will have to be something that can be unlimited... So I am assuming a vector container or use of realloc or map container still?
[/quote]
That is not a good term to use.

If it really must be unlimited, then having access to databases with many petabytes of space still won't be enough; that is still a limit.

If instead the data is roughly several megabytes in size with no fixed length, then a map container is great. A map is a binary tree and additions and removals are fast, searching the tree is pretty fast, etc. About the only thing a vector of that size would outperform it with is random access, and something of that size is rarely accessed through random access but instead by searching.

Share this post


Link to post
Share on other sites
Great input guys! Really helping me out here.

Now with a std::map container, or whatever I end up using, lets say player is at location (x1,y0,z0) I don't want to allow them to jump to the end of the star map as they haven't explored it yet.... but if they have they should be able to jump to it.... So in that behavior what do you recommend?

Thanks!

BTW I thought about the graph structure but IIRC std lib doesn't have anything pre built for graphs correct?

Share this post


Link to post
Share on other sites
Just store a boolean on each node in the map; if it's true, the player has been there, and can go back via teleport/jump. If false, they can't. Whenever a player enters an area of space, set the flag to true.

Share this post


Link to post
Share on other sites
ApochPiQ yeah that is what I was thinking, but what the player is at a node(x1,y1,z1) and all around him the nodes are false, how can I allow him to move into one since it's set as false due to he is adjacent to those nodes... he should be able to move into them....

Or you suggesting two bool variables...
bool visited; //used to check if they have been there before
bool canJumpTo;//used to check if they player can move to there by typing in coords or clicking on some GUI.... Edited by MARS_999

Share this post


Link to post
Share on other sites
Just have one boolean variable canJumpTo; once they've visited it you set this to true. you dont need to check it for moving onto the space, only check if you jump to it

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this