3.4. OBJECT-BASED 2D MAPS (1/2)

 Intro

During this lesson we have seen how to make a very simple 2D map. The map had three different layers, Ground, Transparent and Roof. This way, the map was "Visual-oriented": The map as a visual thing and other information (e.g. physical information of walking/not walking) had no relationship.
But now we are going a little step ahead, learning how to make a object-based map1. No layers - you will learn how to make a map similar to the ones used in Ultima VII.
But what is that Object-based map? A map created by objects, not by layers of images. You will understand this concept soon ^_-

 Object-based maps Vs Tile-based maps

1 1 2 1
1 1 2 2
1 1 1 1
3 3 3 3
1 1 1 1

Tile-Based map

Above you can see a Tile-Based map. All the graphics are of the same size, and they are "inside" a tile. The map is composed by layers - one for the ground, one for the transparent things (e.g. rivers) and one for the roof images (clouds). All NPCs move tile-by-tile, and the movement issue is managed using movement flags (see parts 0 and 1 of this lesson).
What are the problems with this type of map?

NPC movement is tile-to-tile. Can be changed with some internal programming, but it's a little mess.
If you want to draw images with a size bigger than the size of a tile, you have to split that image.
The movement flags have no relationship with the content of the layers (again can have with some tweaks, but again is a [less] little mess).

El hombre y su tanque :P El hombre y su tanque :P

Object-based map

But now, look above. This is an Object-based map2. In this map, as before, we have a ground layer (water, grass, and a "sort of" wood bridge). But now, we have also three objects: Two dragon-like statues and a (lame) tank. Objects can have any size (no need to split them into two or more tiles for drawing), and have the physical information embedded inside them. When you are creating the map, just "drag" the object into its position and it will indicate the map if somebody can pass through/behind/in front of it.
Now look at the image on the right. Yep, the map is still tile-based3, but the tile size (at least the size of tiles regarding to objects) is smaller. Why? Continue reading...

 Layers and Tile size in Object-based maps

In object-based maps, we still have two layers: Ground layer and Object layer. In the ground layer we draw tiles where NPCs walk and objects stand (water, grass, and so on). In the object layer, we draw the objects. Both layers can be managed using tiles (the coordinates of their elements can be expressed as a multiply of a certain tile size). But... what size we must choose when dealing with these type of maps?.

El hombre y su tanque :P El hombre y su tanque :P

Grid size comparison (Ground Vs Object)

For the ground layer (left image), it's better to have a big tile size, because usually the images of the ground are very similar, so it's better to draw the map using big images rather than using little images.
However, when we are dealing with objects, it's better to use a smaller tile size (right image). The reasons are simple:

Objects need more accuracy than ground images. Objects can be as big as a house, but also can be as small as a picture, jar or plant.
Objects must be a multiple of the tile size (for managing physical issues), so it's better to have a smaller tile size.
NPCs coordinates can be expressed using objects' coordinates. And since the tile size is smaller, also the NPCs movement will be more accurate.

 The Grid of an object-based map

Remember lesson 3.0, "tiles and maps". Storing a map is just storing the numbers of the images of every layer in a grid:

1 1 2 1
1 1 2 2
1 1 1 1
3 3 3 3
Ground Layer
-1 4 -1 -1
-1 4 -1 -1
-1 4 -1 -1
-1 4 -1 -1
Transparent Layer
-1 5 -1 -1
-1 -1 -1 -1
-1 -1 5 -1
-1 -1 -1 -1
Roof Layer
is equal to
1 1 2 1
1 1 2 2
1 1 1 1
3 3 3 3

If we want to store a object-based map, we have to do the same thing : having two grids of numbers, one for the ground tiles (a number that indicates the image of a tile) and another for the objects (a number that indicates the type of object). But... since the size of the tiles in the object layer is smaller, we have to use a bigger grid in order to store where are the objects.

El hombre y su tanque :P

So many tiles, so few indexes (of objects) to store...

But if we have only a few objects per map, we don't need to create a grid (that it's going to be empty - memory wasted!). You can use a list with all the objects in a map, and when you need to make an operation regarding an object (e.g. there is an object in this tile), just check the list. Of course the list will be slower to access  [O(1) the grid and O(n) or O(n/2) the list4], but all depends on the memory you have and the speed you need5.

 Notes

1 Object-Based map is a map primarily composed by objects. I am not talking about Object-Oriented programming here ^_-
2 Looks a bit better than the previous one, even if the tank is very lame :-P
3 Well, there is no need of the map being tile-based, but it's for the sake of simplifying. Consider a little exercise (after reading this lesson and the next one ^_-) to manage an Object-based map without tile coordinates.
4 This is a way to tell the complexity of accessing to certain information/make a certain task. O(1) means direct access (the dream of every computer scientist!) and O(n) means that depends on the size of an structure of size n. [If you manage to use a tree instead of a list you can obtain O(log n)... well, that's another story ^_-]
5 Another optimization: You can have a grid of bits (1/8th of a byte: 0..255 byte, 0..1: bit) and store a single 1 in the coordinate of an object. This way, you only check the list of objects only when you need it.