Sign in to follow this  

RTS 1000 Objects : which map data structure

Recommended Posts

TMGeorge    127
Hi, I wanna play around with an RTS style project in C++ Currently I think of using blockmap (max 1024x1024) for collision detection/path finding. I think of dynamic units covering form 1x1 to 3x3 cells. They have axis aligned bounding Squares. Each Block can only be covered by one unit und each block links to each unit. There should be around 300 living objects (player/computer controlled) and 700 Decorations/Buildings. For path finding and taking care of units > 1x1 each block contains a distance to the nearest block which is covered by a static object. (The area around is only scanned to radius 4 or so) So during path finding I can see if a large unit can go there. For “nearest ..” and LOS the algorithm should be pretty straight forward. I have to say I haven’t thought about rendering. I only thought about game mechanics yet. Now I worry about performance. On one side it’s always quite a lot of cells to check. On the other hand I think the algorithms are pretty straight forward and can be heavily tweaked. E.g. having direct links to neighbour cells instead of calculation them and using the [][]-operator. On the other hand I stumpled over quadtrees. The algorithms are not fully clear to. Most examples deal with points but I thing it should be spatial. A nice example to play around is -> select “rectangle applet” and under data structur -> rectangle quadtree. The most I worry here about are dynamic changes in the tree. With the block map I can easily check if the set of covered blocks is changed and I just can change the covering-flag and the link to the entity on the according blocks. But with the quadtree I have to rearrange the tree. And I don’t know how expensive this is. I am aware that the memory for 1024x1024 is 1MB per byte of blocksize is quite huge. So what do you think? [Edited by - TMGeorge on October 24, 2008 7:09:10 AM]

Share this post

Link to post
Share on other sites
De Cowboy    122
1024x1024 is rather small in sense of memory, but looping through each of them and scouting the surroundings will take time. However, you only need to do that when a new 'static object' is placed. When that happens, just update the surrounding 10x10 cells (that should be VERY fast).

If you are going to store all this data in a large array, I wouldn't worry about storing pointers to your neighbors, the compiler is going to find that more confusing than looking up grid[x][y+1].

A quad tree is (as far as I understand) mostly useful to quickly find objects in a given area, and it also works well when you look up a large area that's sparsely populated. But you're only going to look at rather small areas, so an array should suffice.

Also, if your array becomes that large, it might be worthwhile to think about the memory layout of your array: in c++, a 2 dimensional array gets stored as n arrays of an m-sized array. So, if you look up y+1 (or x+1, depending on the order), you might think they are 'close', but they could be very far apart in memory (=> cache misses.) But I don't think that's going to be a problem soon.

Good luck.

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