Game Maps in Off Topic

ID:182391
 
Jul 19 2008, 4:26 am
How are maps in tile-based games done in DM (and in general)? Do they make a multi-dimensional list that reference all the objects and then each time a player moves, it renders relative to their position? The reason I ask is that I want to make a very simple tile based game where you can move around just for experience.
#1 Jul 19 2008, 6:59 am
It's very likely something like that, though if you can do the math, you can do it in a single-dimensional array. Of course, that greatly impedes altering the size of the x, y, or z axes are runtime.
#2 Jul 19 2008, 11:57 pm
I wouldn't bet on a multi-dimensional list. They can be pretty slow or memory-costly. Think simple math. Here is a map with HEIGHT 3 and WIDTH 8.

OOOOOOOO
OOOOOOOO
OOOOOOOO

You want location x = 1, y = 3. It is tile 17 in a single-dimension list. To find that location is rather simple. Use the solution: (WIDTH * (y - 1) + x) for finding the location of the container of the x and y variable.

Now lets look at a procedure not unlike that of BYOND's view(). This will be generalized. I will provide code in DM to show you the concept in the easiest way possible for me.

proc/view(var/dist, var/atom/center)
    var/list_pos = (WIDTH * (center.y - 1) + center.x)
    return MAP_CONTAINER.Copy(max(list_pos - dist, 1), min(lost_pos + dist + 1, MAP_CONTAINER.len))


You can use the contents of the MAP_CONTAINER list to draw the screen according to the screen's width and the like. Just make sure that MAP_CONTAINER is always in order. Also, make sure to check the position of the first object view() returns as relative to the center, or the first position of the screen.

As for the class of MAP_CONTAINER, I have no idea. I imagine a vector class, but that may be too slow. I originally thought array (C++ anyone?) and it very well could be, but I have absolutely no idea how to size those dynamically (as of yet!). But I imagine BYOND uses a lot of these same types of lists.

[EDIT]
The code and equation also assume that the first index of the MAP_CONTAINER is 1.
#3 Jul 20 2008, 5:58 am
In response to CaptFalcon33035 (#2)
You could use a linked list to dynamically add objects into a list in C++ and all the other languages that don't support generic variables like in DM.
#4 Jul 20 2008, 10:11 pm
In response to Kakashi24142 (#3)
I'd do that if I could find a sweet way to index them.
#5 Jul 21 2008, 1:16 am
In response to CaptFalcon33035 (#2)
CaptFalcon33035 wrote:
I wouldn't bet on a multi-dimensional list. They can be pretty slow or memory-costly.

I'm pretty sure that C/C++ compilers implement multi-dimensional arrays much the same way as someone would were they to crash it into a single-dimension, having array[y][x] refer to array + x*y + x. I don't see why this would be any more costly than doing it manually.
#6 Jul 21 2008, 11:46 am
In response to Kuraudo (#5)
If you want to get really fancy, some games/systems actually store tile data in memory ordered as a Z order curve because it improves cache coherency. (This means that close-together tiles on screen tend to be stored close together in memory, thus improving the chance that all tiles you need to refer to will be in the cache).

#7 Jul 21 2008, 1:10 pm
In response to CaptFalcon33035 (#2)
CaptFalcon33035 wrote:
I wouldn't bet on a multi-dimensional list. They can be pretty slow or memory-costly.

Accesing time is not slow at all as a multi-dimensional list
is accessed like this:

array[x_index][y_index][z_index]


Arrays are merely constant pointers to contiguintous memory (which can be hard to find if you start reaching memory limits and is a pain in the @$$ to fix).

STL vectors (since Byond uses C++) is re-sizeable and is even able to reserve memory (they are like arrays but incur a very slight overhead). Linked lists would be slower then anything.

And yes Capt, look at std::vector<> for resizeable arrays.

George Gough
#8 Jul 21 2008, 1:24 pm
Honestly these are handled a number of ways. Depending on the LOD and other factors that the game gives. If you're talking a very simple rendering model than a multideminsional list would work.

I'll give you a pointer though if you're going to be coding all of the system and not using libraries. Then be sure that when you render you use at least double buffering. As this keeps one instance in memory for editing then throws it onto the client view when it's finished. The reason for this is to prevent ugly errors in pixel manipulation and things like that. This way even if they exist the client won't see them.
#9 Jul 21 2008, 8:34 pm
In response to KodeNerd (#7)
KodeNerd wrote:
Accesing time is not slow at all as a multi-dimensional list

I didn't mean so much slow as I meant overhead with all of those indexes (arrays within arrays). How's the overhead with that?
#10 Jul 22 2008, 6:44 am
In response to StolenSoul (#8)
StolenSoul wrote:
Honestly these are handled a number of ways. Depending on the LOD and other factors that the game gives. If you're talking a very simple rendering model than a multideminsional list would work.

I'll give you a pointer though if you're going to be coding all of the system and not using libraries. Then be sure that when you render you use at least double buffering. As this keeps one instance in memory for editing then throws it onto the client view when it's finished. The reason for this is to prevent ugly errors in pixel manipulation and things like that. This way even if they exist the client won't see them.

I already use double buffering, and I plan to make a simple tile-based game in Java. I already have make a few simple applets.
#11 Jul 22 2008, 10:56 am
In response to CaptFalcon33035 (#9)
CaptFalcon33035 wrote:
I didn't mean so much slow as I meant overhead with all of those indexes (arrays within arrays). How's the overhead with that?

Not much more unless you use a very badly implemented container.

George Gough
#12 Jul 22 2008, 12:02 pm
In response to Kakashi24142 (#10)
Kakashi24142 wrote:
I plan to make a simple tile-based game

Wait... What?
#13 Jul 22 2008, 12:25 pm
In response to Naokohiro (#12)
His goal isn't to make a byond game but rather a rudimentary engine and game to go on it merely for the experience of doing so.