Data Structure for Levels in Games

Question

I am creating a platform game in JavaScript using canvas which is entirely tile-based. What is the best method of storing the blocks of items in the game (walls, floors, items)? The thing is every tile can be destroyed or created.

Currently I have a 2D array so I am able to quickly check if an item is at a specific X & Y position. The problem with this is when the user moves and the map needs to scroll, I need to reassign every block. And what happens when the item is at x = 0? I can't use negative indexes.

I would rather the scrolling analogue as aposed to a tile at a time. Also I plan on randomly generating maps as the user moves and if it hasn't previously been generated. So once something is generated, it should stay that way forever.

Another point I should mention is that it will also be multiplayer. So chunking the screen is a great idea until the cached data becomes dirty and needs to get the latest from the database. Gah I'm so new to all this; seems impossible, any help is greatly appreciated.

Answer 1

Since you have infinite levels I'd suggest a structure similar to what you already have, with a slight tweak.

Instead of storing everything in one big array, and moving stuff around inside that array every time the user moves (ouch) instead store 9 chunks of map (each one a size such that it's roughly twice the size of the screen), when the user approaches the edge of the current chunk, dispose the chunks which are offscreen, move all the chunks left, and load new ones into the gap.

Hopefully that was clear, but just in case, here's a diagram:

The lettered squares are the chunks of map, and the red square is the viewport (I drew it slightly too large, remember the viewport is smaller than the black squares). As the viewport moves right, you unload chunks A B and C, move all the others left, and load new data into the right most ones. Since a chunk is twice the width of the screen, you have the time it takes the user to cross the screen to generate/load the level into those chunks. If the user moves around the world fast, you can have a 4x4 set of chunks for extra buffering.

To address the returning to previous chunks of map. there are a couple of ways to do that:

• Write out the chunks to hard disk when they're no longer in use (or whatever the equivalent would be in javascript)
• Expand your chunk set infinitely in memory. Rather than an array of chunks have an assosciative array which takes x/y position of the chunk, and returns the chunk (or null, which indicates that the user has never been here before and you need to generate it).
• Procedurally generate your levels, that's complex but means that once a chunk goes off screen you can just dispose it, and be confident you can regenerate exactly the same chunk again later

Answer 2

There are obviously lots of ways to do this.

If they levels aren't too large, you can keep your original design of a 2d array and use a variable to store the current x/y scroll position. This means that you store all of the map information in memory at all times, and only access the parts you need to display on the screen.

When painting you work out which tile is visible at current scroll position x/y, how many tiles fit on the screen with the current screen width and only paint the ones you need.

If you scroll whole tiles at a time, then its pretty easy. If its a more analog scrolling, you will need some finer grain control of where in the tile you start drawing, or you can cheat and draw the whole set of tiles to an in memory bitmap and then blit that to the drawing canvas with an negative offset.

Answer 3

I once defined this very thing in XML and JSON... I think the JSON serialization would be alot faster and more efficient (not to mention easy) to work with in JavaScript, especially since JSON lends itself so well to variable length lists as you would require for "N" levels in each game.

Using a standard format would also make it more reusable and (ideally) encourage more collaboration (if that's what you're looking for). You can check out my first attempt to create a Video Game schema for level structure.

As fileoffset says, there are many ways to do it, but I highly suggest keeping your level data (i.e. concepts) separate from your rendering (i.e. objects in motion, paths, speed, timing, x/y/z co-ordinate positioning, etc...).

Again, as the article said that area is the most quickly changing, and there's no telling if WebGL, SMIL+SVG, Canvas+Javascript, good ol' Flash/Actionscript or something else will be the best route for you, depending on your needs and the type of game you are developing.