Creating and storing map data

[DrKane]

I'm working on a tile-based rpg engine. Up until now I've just kept a large array within my source code to represent the map. I Now want to keep an external map file and I'm trying to figure out exacrtly how to? Do I keep a text file and read the text in through some interpretive routine? I've read that I should create my own resource using rez, well if so, how should I do this and where can I get rez? Also once I have my whole external map data set up, I want to be able to read parts of the map incrementaly so that I can have a huge world, how would I do that?

[w_reade]

no-one's answered yet, so herewith my two penceÖ

I'm afraid I'm not sure about the best format to store your data in; that'll depend on your engine, and what you need to store for each tile, and so on. I have normally just used text files when I've needed to store things myself. It feels a bit wrong, to me at least, butÖ whatever you're comfortable with.

When it comes to reading parts of the map incrementally, I'd break the world into map squares and store each map square separately. The world would just be a grid of map squares. You'll always have the current map square in memory, but will need up to three others at the same time (if you're standing at the corner of one map square, you'll need all four to see what's around you, but if you're in the centre of one you'll only need that one). You'll never need more than four at a time, though, unless they're smaller than a screen.

When it comes to choosing when to load them, I'd suggest you only bother when the player's within a few squares of being able to actually see them, otherwise you might have to do a lot of unnecessary loading and reloading while players do the standard TB-RPG thing of "check every wall tile for secret passages", which tends to involve a fair amount of walking back and forth in a smallish area.

[NCarter]

Have you seen Level Creator <http://www.swarming.net/levelcreator/>? If you're not using SpriteWorld you can apparently write plugins to support your own map data format.

Binary data files would be more space-efficient than text files, but you might want to be careful that you don't make the data format inflexible. If you use a text based data format, it could be easier to extend the format at a later date, although you could equally well design a binary format that allows arbitrary data for each and any tile in the map.

I wouldn't use resources for this kind of thing, personally. It's easy to swap out separate data files while developing, whereas resources (especially source code based resources) may need to be recompiled or relinked into the game. Application bundling helps to hide the extra files this would create.

As far as incrementally loading data goes, unless you're planning to run on machines with very small amount of memory, it might be simpler to just load the whole lot all at once. I mean, how big is your map? If your map is 1000x1000 tiles overall, and you had 8 bytes per tile (for whatever reason), you'd only be using 7.6Mb of memory. You could use a look-up table to reduce the number of bytes per tile. You'd probably still want to compress it on disk, though.

[DrKane]

My world map is going to be much, much larger than 1000 tiles. Probably more in the neighborhood of 80-100,000 tiles. I have read about a technique where you keep 9 nodes of the map, loaded into memory at any given time. The player being in the center node at all times, so if he crosses over to any node next to him, then he just reloads the nodes so that he's centered again:

each square representing a node:
---------------
|__|___|__|
|__|_x_|__|
| | | |
---------------

If you keep all 9 nodes (including center) surrounding the playerloaded into memory at all times, what would be the best way to calculate which node should be loaded and when to load the nodes?

[NCarter]

Originally posted by DrKane
My world map is going to be much, much larger than 1000 tiles. Probably more in the neighborhood of 80-100,000 tiles.

Really? That's massive!

I used to think I wanted to do an RPG of that kind of scale until I realised that it would take me the rest of my life to design the levels. Unless your tiles are very small relative to your rate of travel, 1000x1000 is actually quite a lot. For example, how long would it take your character to walk from one side of the map to the other? Consider also that there are things for the player to do along the way, so they'll be kept busy in particular places for a while.

That said, your proposal for nodular levels is perfectly reasonable and would allow for very large designs.

While I was thinking about my idea, I thought it might be better to generate the level designs algorithmically, a bit like NetHack (if you've ever seen that), but much more sophisticated. That would allow me to have a potentially infinitely large area, because I'd generate it as I went along.

You could of course get other people to design some of the levels :) or supply a level editor!


If you keep all 9 nodes (including center) surrounding the playerloaded into memory at all times, what would be the best way to calculate which node should be loaded and when to load the nodes?

Basically, whenever the player crosses a node boundary, you need to load the nodes on the opposite side of the new node. You could also cache the nodes the player has been in recently in case they keep walking back and forth, as w_reade said.

[DrKane]

<<I used to think I wanted to do an RPG of that kind of scale until I realised that it would take me the rest of my life to design the levels. Unless your tiles are very small relative to your rate of travel, 1000x1000 is actually quite a lot. For example, how long would it take your character to walk from one side of the map to the other? Consider also that there are things for the player to do along the way, so they'll be kept busy in particular places for a while.>>

I've contemplated whether or not to split the game up into 3 smaller maps, and I would like to come up with some sort of transportation system to easily navigate the player to different parts of the map. These, however, are the least of my worries at the moment. I'm just working on getting my core engine features up and running.

<<You could of course get other people to design some of the levels or supply a level editor!>>

[DrKane]

Okay I am working on just a basic routine for loading a generic map. It works except that from 0,0 each diagnal tile is not read from the map file. Here's the code


// I'm not actually loading the tiles, I'm just setting there type so that they'll
//show up on screen for my tile drawing routine.

#define kArraySizeH 10
#define kArraySizeV 10


UInt32 mapIndex;
short row, column;
char tile;
FILE* filePtr;

filePtr = fopen( "MapFile", "r" );

if (filePtr == NULL)
{
gDone = true;
return;
}

for (row = 0; row < kArraySizeV; row++)
{
for (column = 0; column < kArraySizeH; column++)
{

tile = fgetc(filePtr);
mapIndex = (row * kArraySizeH) + column;

switch (tile)
{
case 'm':
map[mapIndex].type = empty;
break;

default:
map[mapIndex].type = tree
break;
}

}
}

fclose(filePtr);

// m = emp
// 0 = tree

MapFile:

mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm
mmmmmmmmmm


actual screen:

// differs sometimes
m0mmmmmmm0
mm0mmmmmm0
mmm0mmmmm0
mmmm0mmmm0
mmmmm0mmm0
mmmmmm0mm0
mmmmmmm0m0
mmmmmmmm00
mmmmmmmmm0
mmmmmmmm00


Anyone know what's wrong here?

[OneSadCookie]

Doesn't look like you're taking into account the end-of-line characters in your file.

[DrKane]

What's a good way to fix this?

[OneSadCookie]

Either take all the newlines out of your file, or (as long as your file has either Mac or Unix line endings) read a single character at the end of each row & ignore it.

[DrKane]

Even when I use the return character at the end of my line (\n) it still doesn't work. Can someone give me a code snippet for reading a simple 5x5
text file of chars into an array?

[Jeff Binder]

This reads the characters into an array, ignoring newlines. Keep in mind that with this code, a newline doesn't necessarily start a new row, it's just ignored.

#define ARRAY_WIDTH 5
#define ARRAY_HEIGHT 5

char g_array[ARRAY_WIDTH][ARRAY_HEIGHT];

/* Fills g_array with characters read from f, ignoring
newlines. Returns 0 if not enough characters to fill
the array were found. */
int read_array(FILE *f)
{
char c;
int i, j;

i = j = 0;
while ((c = getc(f)) != EOF) {
if (c != '\n') {
g_array[i++][j] = c;
/* Start the next row. */
if (i == ARRAY_WIDTH) {
i = 0;
if (++j == ARRAY_HEIGHT) {
/* Array is full. */
return 1;
}
}
}
}

/* The arrays weren't completely filled. */
return 0;
}

[DrKane]

It's not working for some reason. I'm trying just about every variation I can think of. Some of the chars are still not being loaded. Is there any resource, documentation, or open suorce file/project where I can find an in-depth explanation regarding reading text files? BTW, if my map looks like this:

mmmmm
mmmmm
mmmmm
mmmmm
mmmmm

would putting '\n' at each of the end of rows, make it automatically return to the next row? Or would I have to specify that myself?

[Iceman]

Well you could always look at the hooptie source code it uses the exact same idea for loading maps. http://inkubator.idevgames.com/
Looks like they also changed their license to be more programmer friendly; I should probably look at it too for my next game.

Iceman

[DrKane]

Is it only for PB, because the larger version i downlaoded didn't even work, and then the small version only had a couple global and header files, and the rest of the files it wouldn't even let me open.

[Feanor]

Originally posted by NCarter
Basically, whenever the player crosses a node boundary, you need to load the nodes on the opposite side of the new node. You could also cache the nodes the player has been in recently in case they keep walking back and forth, as w_reade said.

I'll describe my idea of how to do this. Untested!

This kind of thing comes up a lot, like in doing Level of Detail model swapping. Basically you want to avoid what is analogous to vertex popping in LOD swapping. In this case, you don't want to load/unload data repeatedly when the user is walking on a threshold. So the fix is to have two thresholds: near and far. So you load a map tile when the user is X tiles away, and unload when it is Y tiles away, and Y would be X+d, with d the distance between the thresholds. It's like a buffer.

How well this works depends upon how complicated your map details are. Sometimes you won't be able to avoid load pauses, in which case you want to create your maps to limit the places where loads occur, and then load a lot at once. But if you want map areas where the free movement space is bigger than the memory to hold it, you have to do thresholds.

The easy thing about thresholds is that the player can only move one square at a time East/West and one square North/South, so you in fact would load tiles in strips X tiles away in the direction movement, and unload them Y tiles away in the opposite direction. I suggest making X so it's just outside of visibility, but make Y as far away as you can. You can keep less tiles in memory if you make the thresholds octagon shaped instead of square. If this user is walking left (or West), the map tile status chart look like:

O.O.O.O.O.O.O.O.O.O.O.O
O.O.O.X.X.X.*.*.*.O.O.O
O.O.X.X.X.X.X.*.*.*.O.O
O.X.X.X.X.X.X.X.*.*.*.O
O.X.X.X.+.X.X.X.*.*.*.O
O.X.X.X.X.X.X.X.*.*.*.O
O.O.X.X.X.X.X.*.*.*.O.O
O.O.O.X.X.X.*.*.*.O.O.O
O.O.O.O.O.O.O.O.O.O.O.O

(O is not loaded, * is inside far threshold, X is in near threshold, + is player)

That just means that the load/unload algorithms are a bit more complicated, but you would probably just use a list of loads and unloads with the offsets in them already. If the user is located at grid(x,y), then when he moves one square left, do:

load( x-2, y+3);
load( x-3, y+2);
load( x-4, y+1);
load( x-4, y);
load( x-4, y-1);
load( x-3, y-2);
load( x-2, y-3);
unload( x+4, y-3);
unload( x+5, y-2);
unload( x+6, y-1);
unload( x+6, y);
unload( x+6, y+1);
unload( x+5, y+2);
unload( x+4, y+3);

Just adjust the threshold distances as necessary. The harder challenge is remembering which tiles between the thresholds are already loaded. You could have a giant grid of bits to toggle, but that seems very wasteful. I should think a linked list of linked lists of tiles would do the trick. (This would be easier with a square pattern than an octogon :) You could have ten linked lists for East/West, and have a single list of all these lists pointing at the tiles directly North and South of the player. If she walks East or West, you are adding/removing single tiles from the East/West lists. If she walks North/South, you are adding/removing entire lists of tiles. Each time the player crosses to a new tile, you walk the lists, load/unload, and update the addresses of the centre lines.

If this is confusing, maybe I'll write some sample code in C that would demonstrate it...

--FÎanor

[Jeff Binder]

The code I posted automatically starts a new row once enough characters have been read. Putting the rows on separate lines is just for readability, it doesn't matter where the newlines are. So, for example, this input:
mmmmmm
mmmm
mmmmm
mm
mmmmmmmm
mmmmm

is interpreted as this array:
m m m m m
m m m m m
m m m m m
m m m m m
m m m m m

I tested the code and it worked right with stdin as the file. Could you post the code you're trying now?

[DrKane]

<<I tested the code and it worked right with stdin as the file. Could you post the code you're trying now? >>

You're right. It does work fine, I just wrote it slightly differently and meesed up. Thanks for the code.

[Feanor]

So I lied, and I wrote a program in Objective-C instead of C to demonstrate my (possibly not that interesting :o ) dynamic map-data loading/unloading algorithm. I dunno, it was kind of fun to write. It might still be buggy, but I tested it pretty thoroughly -- oh, except the colour-coding doesn't quite work the way it should, but you'll get the idea.

It will be interesting if I convert it to use a texture for the surface of the "map tiles" instead of just drawing flat green squares. But hey, it's an algorithm demo.

DynaMap! (http://homepage.mac.com/brentgulanowski/.cv/brentgulanowski/Public/DynaMap.dmg-link.dmg)

--FÎanor

[DrKane]

I tried downloading the file but it will only open using a hex editor.

[OneSadCookie]

Are you using OS X?! It worked fine for me....

[Feanor]

Originally posted by DrKane
I tried downloading the file but it will only open using a hex editor.
It's a .dmg disk image file -- you need Disk Copy OS X as OSC hinted. I can repackage it with Stuffit so you can read the code if necessary, but I'm trying to get away from that program now. -- FÎanor

edit - ok I've put up a .sit (so small why not?): DynaMap.sit (http://homepage.mac.com/brentgulanowski/.cv/brentgulanowski/Public/DynaMap.sit-link.sit)

Also, fixed the bug with drawing some squares wrong colour -- just needed a couple more if statements.