Tile-Based Game Object System

This is a rather perplexing dilemma that I've had while developing a tile-based RTS (Real Time Strategy) game.  But, first off, all I'm really interested in here is theory and possible code snippets, I don't need (or want) a complete engine or anything like that.

In the game I need to be able to store the objects that are scattered about the game world (trees, rocks, buildings, units, etc.).  At first glance, this is a simple problem: just create a linked list of objects in the world, when a new object is created, simply add it to the end of the list.  This has one huge problem though: drawing efficiency.  Somehow drawing must occur from upper-left to lower-right to avoid overlap.  So, what I have implemented right now is a sorted linked list (sorted by Y, X).  Then, I have an array that is the size of the map (in a 192x192 map, the array is declared as: Object_List object_list[192][192];).  The basic design of the Object_List structure is:

struct Object_List
Object* object;
Object_List* next;

A simple linked list.  Now, the complicated part; if you look at that structure and the array, it looks like you get hundreds of little linked lists.  However, the way I have it implemented, each of those small lists are connected to each other.  So, object_array[80][80].next points to object_array[81][80] and so forth.  The reason for splitting up the list like this is that I needed to allow multiple objects per tile on the map, and this seemed to work.

So, here is where I need help.  This system falls apart as soon as you add height.  I could declare Object_Array object_array[h][x][y]; -- but then you have a whole slew of wasted memory.  Because there is only one height for each tile, that array would waste (h-1)*x*y*sizeof(Object_Array) bytes of memory -- which is completely unacceptable.

So, are there any ideas on better, more efficient implementations that will work with height but still be able to be drawn on the screen properly?

I appreciate the help,
- Alex
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

how about adding another pointer to the struct that will point to a list of objects that are on the same tile ? This way you can dynamicly allocate memory when needed (i.e. when you have more than one object on a tile). This will waste a lot less memory (in the long run....).

If you need a more detailed explanation of my suggestion,  just say so....

Arnon David.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
maybe the same as armond's idea.. although i dont think so:

suppose it had to go on top of [80][80]

>allocate a new Object_List

> put your object in it.

>unlink [80][80] -> [80][81]

>link [80][80] to new Object_List

>link new Object_List to [80][81]

this way you can still directly access [80][80] and [80][81], but the list got extended to include the extra object. Also it doesn't require an extra pointer.

Floris, who wished he could change his nick on EE :-)
EgoreAuthor Commented:
Well, Maniac, I've been very tempted to do this.  I think that arnond's answer was basically the same thing.  Arnond, if your answer is alluding to something different, could you please explain further?

If I don't receive any new posts in the next day or two, I'll give Maniac the points.

- Alex
Not realy, but since both of our ideas are basicly the same, should the first to suggest it (....me....)  be the one to get the points ?

Arnon David.
EgoreAuthor Commented:
Well, since there has been no activity here for some time, I'm going to award the points to the first person to propose the solution: arnond.

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.