Solved

Tile-Based Game Object System

Posted on 2000-01-10
Medium Priority
465 Views
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
0
Question by:Egore
• 2
• 2

LVL 3

Accepted Solution

arnond earned 600 total points
ID: 2340823
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.
0

LVL 1

Expert Comment

ID: 2341576
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.

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 :-)
0

LVL 3

Author Comment

ID: 2346993
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
0

LVL 3

Expert Comment

ID: 2347045
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 ?

Humbly,
Arnon David.
0

LVL 3

Author Comment

ID: 2368660
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.

Thanks
0

Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.