Tuesday, December 21, 2010

Scrolling Multi-layered Map

Only the top-left most part of the
generated map
The next logical step for a tilemap is to add scrolling. The problem is you don't want to be drawing every tile in the map all the time so our basic approach will not work for larger and larger maps. We need a solution that will only ever loop through and draw the tiles that are going to be visible. This snippet makes sure that only the visible tiles in the background layer are drawn. Its limited though because all the foliage tiles are drawn, however a quick bounds check might be enough to skip the expensive render calls but we would want to find a way to remove those loops entirely.

See Rendering Multi-layered Map and Rendering Basic Tiled Maps for details on other pieces in this snippet.

What's Different
Larger section of the same map
Using scrolling
The map generation is pretty much the same aside from keeping around the mapping of integers to tiles the method discussed the previous map snippets. Sorry to say it's not a very good implementation but that is an area that can be improved upon in a future snippet :) . It works for the time being.

A new update method has been added and the unused passed variable in the render thread is now being used to passed the number of seconds passed each frame to the update method. NOTE: this isn't the most accurate way of time keep as it is directly effected by frame rates and could cause jittery and inconsistent animation. But then we're not worried about animation here so it doesn't really matter. I added a keylistener to track when and which arrow keys are down in order to scroll the map. The update method handles the actual calculations to move around the map based on the keys that are pressed, it's just simple input handling nothing special. Here is the update method implementation.

  * This method will move our position in the map.
  * @param d
 protected void update(double d) {

  Dimension screenSize = getPreferredSize();

  if (up) {
   y -= scrollSpeed * d;
  } else if (down) {
   y += scrollSpeed * d;

  if (right) {
   x += scrollSpeed * d;
  } else if (left) {
   x -= scrollSpeed * d;

  //clamp display area to inside the map
  if(x < 0) {
   x = 0;

  if(y < 0) {
   y = 0;

  // handle what happens when we reach over the edge of the map
  if(x + screenSize.width > mapSize.width) {
   x = mapSize.width - screenSize.width; //revert to last position

  if(y + screenSize.height > mapSize.height) {
   y = mapSize.height - screenSize.height; //revert to last position

So there is some extra handling if we try and scroll outside the visible area of the map. There is bottom and left edge handling which works pretty accurately. So no matter what our speed is we ensure that as soon as the visible area is outside the map we will reset them to be exactly at the edge and never beyond.

The rendering method has been altered heavily for this snippet as it now needs to be able to handle a larger map.

  * We only want to render what is currently visible on screen, so we need to
  * take into account the current starting x,y coordinates which will be used
  * to scroll through the map during updates. Our world object holds the
  * tiles in terms of a single index value
  * @param g
 protected void render(Graphics2D init) {
  // draw only the tiles that are visible, the visible area is given by
  // the size of the component and the current x,y starting position on
  // screen.
  Dimension screenSize = getPreferredSize();
  Graphics2D g = (Graphics2D) init.create();
  g.fillRect(0, 0, screenSize.width, screenSize.height);
  g.translate(-x, -y); // move the graphics object to the new position

  // this will give us the row in the map grid we are starting from
  int sRow = (int)y / tileHeight;
  int sCol = (int)x / tileWidth;
  int cols = 1 + screenSize.width / tileWidth; // total number of columns
  int rows = 1 + screenSize.height / tileHeight; // total rows
  int row, col;
  Tile t;
  int index = 0;
  for (int i = 0; i < rows * cols; ++i) {
   row = i / cols;
   col = i - row * cols;

   // transform to new position in the map
   row += sRow;
   col += sCol;

   index = row * (mapSize.width/tileWidth) + col;

   // we are outside the bounds of the map, safety check
   if(index >= tiles.size()) {

   // draw the tile at the given index

  // keeping it simple, and fast
  // TODO: Optimize to only loop over visible objects in the world
  for (Tile tile : world) {

  // draw debug string on top of everything
  g = init;
  g.drawString(String.format("%.2f (%d), %.2f (%d)", x, sCol,y, sRow), 10, 10);

One of the benefits of using the HashMap approach is evident here we can pull the tile to draw from this map with O(1) constant time lookup. This is huge here because we don't need to rebuild a list of all visible tiles nor do we have to partition the map in any way. We've kept the background tiles in a single collection increasing memory efficiency and locality, hopefully. After working with Java's HashMaps you begin to wonder what you would ever do without them. 

How it works?
Going back to a previous snippet "Rendering Basic Tiled Maps" I outlined a way of indexing tiles from top-left to bottom-right.

+-x 0   1   2
y .---.---.---.
0 | 0 | 1 | 2 |
1 | 3 | 4 | 5 |
2 | 6 | 7 | 8 |
Basically we will create an index like this for the visible area which is only a subset of the larger map.
+-x 0   1   2
y .---.---.---.
0 | 0 | 1 | 2 |      0   1
  |---@@@@@@@@@ => .---.---.
1 | 3 @ 4 | 5 @  0 | 0 | 1 |
  |---@---|---@    |---|---|
2 | 6 @ 7 | 8 @  1 | 2 | 3 |
  '---@@@@@@@@@    '---^---'
    Full Map        Visible
We will iterate through the indexes of the visible area grid 0,1,2,3 and for each column and row of that visible area which will be 0-0, 1-0, 0-1 and 1-1 respectively we will add an column and row offset to them based on the visible areas position in the larger map. The offset in the example above would be 1,1 now the corresponding indexes into the larger map will be (0+1) * 3 + (0 + 1) = 4 then (0+1) * 3 + (1+1) = 5 now we move down one row (1+1) * 3 + (0+1) = 7 and the last is (1+1) * 3 + (1+1) = 8. Pretty neat huh, well at least I thought so when I came up with it years ago while making my first small game in Visual Basic 5, yeah it's been a long time since then.

Where's the Snippet
So here it is, a bit lengthy now at 639 lines but it's all in a single source file if you've been following along with the previous examples it shouldn't be hard to pickup and use these concepts in your own way, if you find them useful. I of course would love to hear more opinions on this method or better implementations. Always looking for more efficient ways to do things and squeeze every nanosecond out of that CPU. Happy Holiday coding everyone!