Sign in to follow this  
ZeHa

Decision about object storage

Recommended Posts

Hello! Well I hope this won't get too long, so I'll try to explain everything very straight. I'm programming an isometric game (but I think this thread should fit here in the general forum as well). At the moment, I use a quadtree where ALL objects - except floors - are stored in. The problem is, it doesn't work too well, because I need to store those objects which are placed across or right beside the tree's borders TWICE (or in the worst case, even four times), because I'll need that for collision detection. Now of course, the tree gets pretty "fat". Another thing I have to do is to pull out those objects who moved since the last frame and then re-insert them, so that they are always located in the correct leaf. This means stepping through the WHOLE tree and checking EVERY object if it is moveable. Then, in the end, I collect all those objects from the visible leaves and put them into a render list, which gets sorted by the Z value, so that they are displayed correctly (because of isometric view). There are several reasons why I'm thinking about a change - one is that I don't want to have so many objects twice or even more often in that tree. And another is, to be honest, that my tree just doesn't seem to work correctly and I always get angry just because of that %§@# tree. By now it REALLY SHOULD be alright but then again there pops up another bug or something and I have to debug the tree over and over again. --- Now I'm thinking about the following alternative: - one array, storing floors AND all static objects (walls etc) - one linked list for all moving objects - another linked list for moving AND static objects -> for collision detection The array would just store everything that doesn't move of course, and that's pretty much compared to those objects who CAN move. A typical level would contain e.g. over 500 walls, but just about 10 to 40 moving objects. So I would have those static objects nicely separated from those few who need to be tested if they moved since the last frame. The list with BOTH types of objects could then be sorted by Z value for collision detection. When an object moves, it would also be taken out and inserted right afterwards, but the following re-sorting should be very quick because most of that list would already be sorted. Of course other techniques for collision detection, WITHOUT the need of an additional list, would be possible - e.g. scanning the array fields which are located around the moving object. I can see some clear advantages for this kind of data storage. But... --- ...I'm still not sure which way to choose. The game isn't too far programmed, so the change wouldn't be a huge action. But which way would you go? Originally, a friend recommended the use of a quadtree and it seemed like a very good idea. It surely has its advantages and all. But at the moment I'm just frustrated and the other way seems so much more easier - though I don't know if that's true in the end. So I'd really like to hear your opinion - which alternative would be the "better" one? And why? And of course, if you would like to propose something completely different :) please let me know! Thanks in advance and thanks for reading :) ZeHa

Share this post


Link to post
Share on other sites
Btw, to make things clearer, that's again in a short form what is used NOW:
- one array for floors
- one quadtree, storing walls, persons, other objects
- the quadtree stores some objects twice or more times, when they are located near or across the borders
- every object has to be checked if it is moveable and then if it moved

Also, it would be cool if someone could mention some arguments WHY a quadtree would be a GOOD idea in this case (if it IS the case, of course :)

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