Tuesday, November 16, 2010

Rendering Multi-layered Map

Similar to the previous snippet only now the
green squares and diamonds represent some foliage.
Note: That the map generation algorithm still needs
a bit of work to make decent looking terrain.
When using a map in a game you always are going to want to draw items equipment and perhaps buildings and structures on top of terrain. This is known as layering, you may be familiar with it if you have done used photoshop or perhaps in making your own games. It is even used in GUI programming although it is usually referred to as z-ordering. You want to use it anytime you have a rendering order in which something you are drawing will appear on top of a part of something else but doesn't fully cover it. In 3D graphics many times you don't have to worry about the order in which you draw objects since the graphics card will automatically determine per pixel drawn if it is covered by something else, that entails using a depth buffer.

If we wanted to we could implement our own depth buffering system on the CPU side, however it would take a lot of processing power and be inefficient. So we will draw in top left to bottom right order drawing the bottom layer and then each layer above that separately.


So how do we determine this order and make it flexible for pretty much any game we want to create. Ones first instinct is usually to make a list or map of layers each layer containing all the objects to be rendered on that layer, and traverse these nested lists in order. This results in some nested for loops which I try to avoid at all costs. So my solution is to order each rendered element when you insert it into the collection of all elements to draw. This makes the rendering loop a single continuous loop we can't get much more efficient than that. The only other optimization we can do is to make sure we only draw what is visible on the screen, and nothing we draw is unnecessary, sometimes the cost of removing those unnecessary loop cycles is to expensive so it's best to just try and determine them beforehand or not at all.

Code Snippet

This snippet is based off of the previous snippet Rendering Basic Tiled Maps. Not much has changed between the two except the tile class, map generation function, and tileset generation function have added support for layers demonstrated by some placeholder images. The map generation algorithm I'm afraid is a little bit confusing.

How Layers Work

This implementation sets each tile with a layer integer that is used in the TreeSet red-black tree sorting. Which makes it efficient because you are going to order the tiles and layers when creating the map and you don't need to touch it after that. Another way of doing this would be to use an ArrayList or any other sortable collection in the Java Collections package and sort when you need to, especially if you need constant time access into the collection. Alternatively you can create another collection of the tiles or containers of subsets of the map in order to do whatever you need. I choose to use TreeSet as it is simple enough for this example, and I won't be needing to do anything but draw the list of objects on the map.

The rendering loop remains the same, just as simple as we can possibly make it.
protected void render(Graphics2D g) {
  // keeping it simple, and fast
  for (Tile tile : world) {
Any simpler and it'd just be a completed list drawing each tile individually in the order we wanted.

The real meat of this snippet is in the compareTo function of the Tile. Because the TreeSet either requires a comparator to order the elements or requires the element type to implement the Comparable interface we need to provide one of the two. For simplicity I choose the later of the two, even though making a Comparator would be advantageous because then it would be easier to add different types of objects to our map other than just Tile objects.
/* (non-Javadoc)
   * @see java.lang.Comparable#compareTo(java.lang.Object)
  public int compareTo(Tile o) {
   if (layer > o.layer) {
    // this object should be displayed after o because it is
    // on a higher layer than o
    return 1;
   } else if (layer < o.layer) {
    // o should be displayed before this object because it is
    // on a lower layer than o
    return -1;
   } else {
    // if there are on the same layer sort them top,left to bottom
    // right order
    if (y < o.y) {
     return -1;
    } else if (y > o.y) {
     return 1;
    } else if (x < o.x) {
     return -1;
    } else if (x > o.x) {
     return 1;
    } else {
     // their in the same position same layer, this is probably
     // not intentional, but could happen
     return 0;
A bit messy but it gets the job done efficiently. So we compare the layers, if the two objects are not on the same layer there is no need to go any further we return 1 meaning that the tile compareTo was called on should come after the tile o because its on a higher layer, and -1 if it should come before the tile o.

If they are on the same layer we are going to order the objects from top-left to bottom-right order. So we compare the coordinates of each tile. This is actually something that can be handled by the indexing method I explained in the previous post.

So here is the snippet for you to play around with comments are welcome as always.

No comments:

Post a Comment