Sign in to follow this  
Methodic

Universe Entity Storing and Retrieving

Recommended Posts

Hello,

I'm thinking of making an space exploration game and I'm wondering what would be the most effective way of storing and retrieving information about entities existing in the universe. Say, for instance, the player is moving in a direction in space - how would I load the incoming planets and stars from a storage without having to go through all existing entities and check their relative position to the player?

Share this post


Link to post
Share on other sites
[quote name='Methodic' timestamp='1318860394' post='4873456']
Hello,

I'm thinking of making an space exploration game and I'm wondering what would be the most effective way of storing and retrieving information about entities existing in the universe. Say, for instance, the player is moving in a direction in space - how would I load the incoming planets and stars from a storage without having to go through all existing entities and check their relative position to the player?
[/quote]

Hi There,

I read somewhere else regarding a similar topic to this, that the answer could like in quadtrees or a similar data structure - where you can recursively page back through local nodes in order to retrieve 'nearby' objects without having to traverse too far.

A similarly intelligent data structure would be your answer, though.

Share this post


Link to post
Share on other sites
Hidden
[quote name='PixelPrime11' timestamp='1318862043' post='4873462']
[quote name='Methodic' timestamp='1318860394' post='4873456']
Hello,

I'm thinking of making an space exploration game and I'm wondering what would be the most effective way of storing and retrieving information about entities existing in the universe. Say, for instance, the player is moving in a direction in space - how would I load the incoming planets and stars from a storage without having to go through all existing entities and check their relative position to the player?
[/quote]

Hi There,

I read somewhere else regarding a similar topic to this, that the answer could like in quadtrees or a similar data structure - where you can recursively page back through local nodes in order to retrieve 'nearby' objects without having to traverse too far.

A similarly intelligent data structure would be your answer, though.
[/quote]


It really does sound like the way to go. So basically the screen would "frame" a bunch of nodes in the quadtree, and load all of the "framed" nodes respective nodes till it reaches a leaf containing an entity? I should probably do a lot of reading up on quadtrees first before asking too many questions, but the question is now how I would tell which nodes that are relevant to go through depending on the position of the player. I believe there are lots of information on this to read, but any more input on this is still appreciated of course. :)

Thanks PixelPrime11 for the reponse!

Share this post


Link to post
[quote name='PixelPrime11' timestamp='1318862043' post='4873462']
[quote name='Methodic' timestamp='1318860394' post='4873456']
Hello,

I'm thinking of making an space exploration game and I'm wondering what would be the most effective way of storing and retrieving information about entities existing in the universe. Say, for instance, the player is moving in a direction in space - how would I load the incoming planets and stars from a storage without having to go through all existing entities and check their relative position to the player?
[/quote]

Hi There,

I read somewhere else regarding a similar topic to this, that the answer could like in quadtrees or a similar data structure - where you can recursively page back through local nodes in order to retrieve 'nearby' objects without having to traverse too far.

A similarly intelligent data structure would be your answer, though.
[/quote]

It really does sound like the way to go. So basically the player position (possibly the center of the screen) would tell which node the player is currently at, and then it would page back from there loading entities till it reaches a node that covers the entire screen? I should probably do a lot of reading up on quadtrees first before asking to many questions as I believe there there are lots of information on this to read, but any more input on this is still appreciated of course. :)

Thanks PixelPrime11 for the response![size="2"] [/size]

Share this post


Link to post
Share on other sites
[quote name='Methodic' timestamp='1318864195' post='4873475']
It really does sound like the way to go. So basically the player position (possibly the center of the screen) would tell which node the player is currently at, and then it would page back from there loading entities till it reaches a node that covers the entire screen? I should probably do a lot of reading up on quadtrees first before asking to many questions as I believe there there are lots of information on this to read, but any more input on this is still appreciated of course. :)

Thanks PixelPrime11 for the response!
[/quote]

No worries at all.

I just had a thought - if you're making a 3D game then a quadtree might not be the ultimate solution since that deals mainly with 2D data structures. The last time I checked we lived in more than 2-dimensions!

Octrees are the 3D equivalent, although it's possible to still represent a galaxy in a Quadtree - providing, of course, you don't have one element sharing the same Y position in space as another. Of course, that's impractical, so looking at Octress for full space partitioning would be the way forward, I think.

Your reasoning is sound, however. You'd locate your player's position in relation to the relevant tree node and work outwards until you've encompassed your entire 'active' region. Superimposing your intended new position into the quadtree should give you the overlapping nodes and give you the new data structures to peek inside. Quad or Octree, it's pretty much the same theory either way, just more dimensions to think about.

I don't have a tremendous amount of experience working with anything other than quadtrees, though, so you might need some advice from someone else much more versed in these matters :)

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