Tile Maps of Unusual Size

My original tinyMMO had very small zones.  There were several reasons for this.  First, drawing out large tile maps that are interesting is hugely time consuming and I was on a tight deadline.  Second (and more relevant to this post) is that large maps can drag a game's performance down if you don't know how to manage them.

If you want the camera to be centered on the player, each time the player takes a step you need to shift all of the surrounding tiles around them.  If you have a poor tile management strategy, this means all the tiles waaay over there that the player can't possibly see need to be moved as well.  This can bring your processor(s) to their knees.

Is he dancing again?  He'll be the death of us!

Many game engines handle this automatically but I am using CrafyJS, which is more of a framework than an engine.  I like it because its easy to understand and lets me tinker with stuff under the hood.

For the new game I want big, seamless maps where players can explore and feel wonder.  So I need a way to display only what the player can see and forget about everything else.  Lets use a simple example.  A 100x20 tile map with only grass and bushes.

Feel the wonder yet?

Now lets plop a character in there and try walking around.  Runs like molasses on a cold day, right?  The reason is that every frame, 50 times per second, all 2000 tiles need to be moved and redrawn.  Even the ones that are nowhere near your character. Also, at the start all 2000 tiles need to be loaded into memory at once.  Even the ones you will never see.  I want much bigger maps than this so I need a better way.

Lets come up with a way to load and show only what is around the player.  We need to break the map up into smaller chunks (I'll call them boxes) and load them one at a time.  I have found that a good box size is one third of the screen width by one third of the screen height.

Nine boxes in a screen.

While we are walking around we need all of the edges to be already loaded and ready for display.

Sixteen surrounding boxes ready for display.

Now whenever we move from one box to another, we need to load a new set of surrounding tiles and unload those that are no longer surrounding.

Out with the old, in with the new.

Since I am lazy, I just mark each box with a flag: loaded or unloaded.  Whenever I detect that the player has moved to a new box, I unload everything 3 tiles away and reload (if loaded flag not set) everything 2 tiles or closer.

There is probably a better way but as I said, lazy.

This is great.  The game is now pretty much only loading what the player can see with just a little bit of overhead.  But there is still a problem.  Creating and destroying tiles is expensive.  When the players hits the edge of a box there is a noticeable hiccup while five new boxes worth of tiles are created from scratch.  And what about the old tiles no longer in use?  Tossed away like used kleenex.  What a waste!

Those bits once proudly roamed the plains.

The old tiles are pretty much the same as the new tiles so lets recycle them!  I'll create a tile cache which is basically just an object with an array defined for each tile identifier.  My tiles ids are '0' and '#' so I have one array defined for each.  Now each time a box is cleared, I push each tile it contained into the corresponding array.  I also set its visibility to false and move it to -10000,-10000 so the framework pretty much ignores it. Each time a new tile is needed, I check the array of its type to see if any are available and pop them off and use them first.

Here is an example running and here is my finished implementation of map manager.

      function MapHandler(initX, initY) {  
           var self = this;  
           var boxStore = {};          // tiles within a map segment  
           var tileStore = {};          // cache of re-usable tiles  
           self.tileCount = 0;  
           var TILESIZE = 64;  
           var MAP_WIDTH = 100;  
           var MAP_HEIGHT = 20;  
           var tilesX = Math.ceil(VIEW_WIDTH / TILESIZE);          // screen width in tiles  
           var tilesY = Math.ceil(VIEW_HEIGHT / TILESIZE);          // screen height in tiles  
           var boxW = Math.ceil(tilesX/3);  
           var boxH = Math.ceil(tilesY/3);  
           console.log('box size ' + boxW + ' x ' + boxH);  
           var oldBox = -1;  
           self.changeLoc = function(newX, newY) {  
                var boxX = Math.floor(newX / (TILESIZE*boxW));  
                var boxY = Math.floor(newY / (TILESIZE*boxH));  
                var curBox = boxX + boxY * Math.ceil(MAP_WIDTH/boxW);  
                if (curBox != oldBox) {  
                     changeBox(curBox);  
                }  
           }  
           var changeBox = function(curBox) {  
                oldBox = curBox;  
                // clear surrounding out-of-frame boxes  
                var y = -3;  
                for (var x=-3;x<=3;x++) {  
                     clearBox(curBox + y * Math.ceil(MAP_WIDTH/boxW) + x);  
                }  
                var x = -3;  
                for (var y=-2;y<=2;y++) {  
                     clearBox(curBox + y * Math.ceil(MAP_WIDTH/boxW) + x);  
                }  
                var x = 3;  
                for (var y=-2;y<=2;y++) {  
                     clearBox(curBox + y * Math.ceil(MAP_WIDTH/boxW) + x);  
                }  
                var y = 3;  
                for (var x=-3;x<=3;x++) {  
                     clearBox(curBox + y * Math.ceil(MAP_WIDTH/boxW) + x);  
                }  
                // fill in surrounding boxes  
                for (var y=-2;y<=2;y++) {  
                     for (var x=-2;x<=2;x++) {  
                          loadBox(curBox + y * Math.ceil(MAP_WIDTH/boxW) + x);  
                     }  
                }  
           };  
           var clearBox = function(boxId) {  
                if (!boxStore[boxId] || boxStore[boxId].loaded == false) {  
                     return;          // not loaded  
                }  
                // don't block  
                setTimeout(function() {  
                     // clear old box tiles  
                     while (boxStore[boxId] && boxStore[boxId].tiles.length) {  
                          var tile = boxStore[boxId].tiles.pop();  
                          tile.visible = false;  
                          tile.attr({ x: -10000, y: -10000 });  
                          tileStore[tile.tmmo_type].push(tile);  
                     }  
                     if (boxStore[boxId]) {  
                          boxStore[boxId].loaded = false;  
                     }  
                }, 10);  
           };  
           var loadBox = function(curBox) {  
                // init box  
                if (!boxStore[curBox]) {  
                     boxStore[curBox] = { loaded: false, tiles: [] };  
                }  
                if (boxStore[curBox].loaded) {  
                     return;     // already loaded  
                }  
                var newX = (curBox % Math.ceil(MAP_WIDTH/boxW)) * boxW;  
                var newY = Math.floor(curBox / Math.ceil(MAP_WIDTH/boxW)) * boxH;  
                for (var y=newY;y < newY + boxH && y < MAP_HEIGHT && y >= 0; y++) {  
                     for (var x=newX;x < newX + boxW && x < MAP_WIDTH && x >= 0; x++) {  
                          var tileId = g_map.charAt(x + y*MAP_WIDTH);  
                          var tile = undefined;  
                          if (!tileStore[tileId]) {  
                               tileStore[tileId] = [];  
                          }  
                          if (tileStore[tileId].length) {  
                               tile = tileStore[tileId].pop();  
                               tile.visible = true;  
                          }  
                          else {  
                               if (tileId == '0') {  
                                    tile = Crafty.e('2D, ' + RENDERING_MODE + ', grass').attr({ z: 1 });  
                               }  
                               else if (tileId == '#') {  
                                    tile = Crafty.e('2D, ' + RENDERING_MODE + ', treetop_tall').attr({ z: (y*TILESIZE) * 10 + 10 });  
                               }  
                               tile.tmmo_type = tileId;  
                               self.tileCount++;  
                               g_game.status.attr({ text: 'tileCount: ' + self.tileCount });  
                          }  
                          tile.attr({ x: x*TILESIZE, y: y*TILESIZE });  
                          boxStore[curBox].tiles.push(tile);  
                     }  
                }  
                boxStore[curBox].loaded = true;  
           };  
           self.changeLoc(initX, initY);  
           return this;  
      }