Hello. I have two questions relating to the appropriate data structures to use for a large 2d tilemap. I’m looking for opinions.

First, some background of why this is sort of a complex question. I have a half-made simple multiplayer game up and running. It is 2D, top down, and the ground is tile based. The world can hold objects at arbitrary positions, but in this thread, I’m just concerned with the tile-based portion. I already have a small basic tilemap on the client side just to give me some ground to walk around on. I’ve just been filling it randomly with one of four seamless grass tiles at run time.

My client is written in Actionscript 3, and my server is written in Java. It uses a MySQL database for persistence, so far only for player information. I would like to make the map server side, with each tile stored in the MySQL database. I want to allow the players to be able to make some modifications to the world, and I would also like to be able to make procedural modifications. I want all this to be persistent. I also would like to make the world seamless and quite large. I don’t need it to be that large right this minute, but I want to design with that goal in mind.

Because of this, I would like to stream the map to the clients in chunks. From what I’ve read, this isn’t an uncommon thing to do. As the player moves around, chunks of tiles would be read from the database, stored in memory on the server, and fed down to the player. This would allow some server side map functions (sanity checking, etc.), and allow the client to only hold the sections of the map that it needs. I might like to go one small step further, and procedurally generate parts of the map on the server as the player gets near them. This means that some of the map table itself might not be populated until run time.

My questions reflect my inexperience. I have implemented the above in a prototype last year, but now I want to figure out a smart way to do this so that it will be scalable.

1. This might seem dumb, but most of my DB experience has involved entities with a single unique sequential index. Since I will need to reference sets of rows based on X and Y indexes (not pixels, but indexes to tiles), should I make a function that can combine X and Y into a single unique index, something like:

long ID = (long)((10000000 * X) + Y) ;

or is it smarter / is there a way, to use two non-unique indexes so that I can actually access all my rows via the X and Y values, and skip the single unique ID entirely? I seem to remember reading about this when I was learning about database design. I’m not only asking if it is possible, but also, if it is, is it smart?

Same question, but taken one step further. If I use formulaically created IDs, like the example above, would I get any advantage from keeping my data on the server and client in 1D arrays rather than using 2D arrays? Since I can always reverse the formula to change an ID into X and Y indexes, would there be any benefit from just doing this everywhere in my code, not just in the database itself?

2. This one is more technical. On both the client and server side, I started by using arrays to store player data. However, I’ve been creating random, large integer IDs for players. I’ve recently been advised that arrays aren’t the best choice when they are sparsely populated. This has been shown to me on both the client (AS3) and server (Java) side. I was advised to use Dictionaries on the client side, and Hashmaps on the server side, which I’ve done. Since I won’t ever be loading the entire map / table into either the client or server, I’m going to end up with fairly sparse arrays. Do you have any experience with storing a large, but sparsely populated 2D grid-map in Java or even Actionscript? Should I be using Hashmaps and Dictionaries to store my map data as well?

I’ve read a few posts about using different types of trees to organize map data, but I’m afraid I’m not quite that experienced yet. I’ve gotten completely lost trying to understand them. I’m sure I could learn one if I knew it was perfect for what I needed, but I don’t know if I want to spend days struggling to understand that if it isn’t going to be practically more effective than something simpler.

Thank you in advance for any advice or opinions you can give me. I’m just a little bit nervous about implementing such a large change into my project without getting a second opinion first.

Quote:Original post by VildNinjaAbout the ID vs x,y coords, then the ID would be the fastest way. But integer searches are always fast in a db, especially if you make sure that the table is sorted correctly. Therefore, I don't think you'll experience a huge difference in speed, whether you are using ID or x,y.

Thanks! I'll give that a try. I'm not sure I understand the sorting part, though, if I have two indexes. Only one of the two can ever really be sorted, though I suppose the other can be a secondary sort after the first. I'm not sure I grasp the performance implications of that. I would generally be reading square chunks but writing either single tiles or chunks.

Quote:Original post by VildNinja
Hmm. Wouldn't it be far better, if you stored more than a single tile in the db? I think it would be far better, if you stored small tile maps (regions) in the db instead. Then you wouldn't have to get 400 results every time you loaded 20*20 tiles from the db.

I'm hoping I will be able to allow players to change single tiles. Imagine, for example, a 100 x 100 grid of grass. I want to be able to allow players to create a trail, or a lake, tile by tile. I'm thinking that would be much less efficient if each row held a 400 tile region, though maybe not.