Archived

This topic is now archived and is closed to further replies.

Ratman

Data Structures and Algorithms for large dynamic tile-based world

Recommended Posts

Ratman    181
Kind of a long shot here, as its pretty difficult to describe a problem like this (big and kind of vague), but I'll try: Currently working on a 2D multiplayer platform game. One of the key "features" of the game is the platforms, terrain, etc will be destroyable. That is, if a pillar holding up a platform is destoryed the platform will fall down. Its not really that hard of a concept. Its like a big game of tetris. Certain blocks give "support" (ie - they hold up on their own) and all other blocks need to be touching a supported block or they fall (ie - a support block or a block touching a support block, etc). I'm not looking for extreme realism with torque and weight and tipping; just something simple for making dynamic levels. here is the best concept art I have off hand. Ignore the water (blue) for right now, I'm just talking about the block shapes, look how when the red rectangle (which had support from the pillar) is removed the other irregular shaped blocks fall. Hopefully that gives you an idea of what Im looking for. I've tried a few different designs and I just cant seem to strike a nice balance between simplicity and robustness. I code in a very object-oriented fashion and keep all objects derived from a base game object which automates drawing, updating, and collision detection. Heres some of the ways I've tried approaching: 1) Treating blocks as "tile group objects" which are affected by gravity. When theres a collision with another block they stop moving. This works out ok except now every block is checking every frame if it collides with another block and has to be moved back to the correct place. If you see the image above you can hopefully get an idea of how many "tile group objects" there are on just one screen. 2) I went a step further with the above method and marked all the tile group objects as "deactive" or "active" to flag if they are moving or not. Once they've hit something and are at rest I removed them from the "active collision detection list" which means moving objects would still check for collision vs them, but they wouldnt be checking for collision vs all other objets themselves. I had an algorithm to traverse all the tiles and see which ones had support and which ones didnt, the ones that didnt would be flagged as "active" and would start falling the next frame. This worked alright, but the code began to get real messy. I had all these flags floating around, trying to insert and remove objects from lists sometimes several times a frame. Little problems started popping up and it became harder to debug. 3) I'm playing around now with just doing more of an old-school big array of ints that represent tiles. You'd have an array of ints where the ints represent tile types, and then I have an algorithm that would "link" the adjacent tiles and draw the correct images for each part of the tile. But now this seems to restrictive as I run into problems if I want two "tile groups" of the same tile type touching each other. It just seems like I lose a lot of control over everything when Im not treating the tiles as objects. Plus then I have to write more collision detection code, and overall the program just becomes a mess. ============================================ So I hope Ive presented the situation well. I'm just looking for some new ideas, maybe someone has a simpler method (though be carefull, a lot of simpler methods look like they will work but wont) or a tweak to one of my ideas up here. Sorry if this post seems a little disjointed I'm kind of wired right now. Thanks for any input. Dave Ratti [edited by - ratman on August 5, 2003 4:49:01 PM]

Share this post


Link to post
Share on other sites
JuNC    236
Well, to me option 2 sounds the best, I presume you have some sort of structure (like a grid or something) to narrow down the collision checking. 1) is obviously highly inefficient.

I see your problems with 3 so 2 is probably your best bet. Without a rough idea of how you''re laying out your code it''s hard to give you ideas on how to prevent it becoming messy, my suggestion would be to step back and take a look at it again, maybe refactor (hey a buzzword!) some of your systems and try to neaten it up.

Share this post


Link to post
Share on other sites
Ratman    181
Yeah I think option 2 is probably on the right track, but I''ve rewritten the system twice now. Probably just need to keep at it till Im satisfied.

What I have now is lists of the active and deactive tiles, all static/supporting tiles, and a grid of all the tiles in game so I can look them up with x,y coordinates in constant time. It provides everything I need, guess I just need to tweak the algorithms.

Thanks
Dave Ratti

Share this post


Link to post
Share on other sites
Xai    1838
I think you''ve got it ... but just to spell it out for others who might be reading ...

one of the keys to make this kinda system managable, is realizing you can have multiple views of the same data (mutliple lists of the same blocks) ... one organized by x,y coordinates (or in the case of a space game I worked on, 1 list by x then y, one by y then x) ... another view by static / dynamic ... others by active / inactive ... etc ... each object can be on as many lists as you want, in as many different orders ...

then it''s just a matter of making each list be notified at the right times to stay up to date ... and have each feature use the data it needs, however it wants ...

Share this post


Link to post
Share on other sites