Tile-Based Game Object System

Posted on 2000-01-10
Medium Priority
Last Modified: 2008-03-17
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
Question by:Egore
  • 2
  • 2

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.

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.

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

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

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 ?

Arnon David.

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.


Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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.

Join & Write a Comment

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

597 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question