Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
96 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Contents
 Introduction
 The Map
 Unit Data
 Structures

 RAM Considerations

 Printable version
 Discuss this article
 in the forums


The Map

The map is probably the single most important data structure in a game of this type. The map serves as the central repository of nearly all game data and is the primary source of information used by the game logic. The various units, "fog of war", unit AI, and so on, all rely extensively on the map.

The most basic structure of the map is the map cell. A map cell is simply a single map location. The information you store in a map cell depends on the game you're creating, but there are a few common elements. Such common elements include an indicator of the type of map cell (for instance, the terrain), the structure (or structure segment) built on the cell, and a pointer to the first mobile unit on the map.

Artifact's map cell structure is shown in Figure 1. It's not the most space-efficient structure, but since it's used on the server side where plenty of RAM is available, that's not an issue.

Figure 1: Artifact's Map Cell

struct world_struct {/* map cell */ unsigned char reg; TRP_TYPE *trp; long ore,crops,wood,stone; /* raw materials */ char structure; /* bdg is a: 0 city, 1 facility, 2 artifact STR_* */ BDG_TYPE bdg; /* pointer to union of city or facility */ };

Once you have your map cell defined, you have to decide how you want to structure the entire map. Here we have to refer back to your game design concept and how you want the finished game to look. There are 3 primary "looks" that are popular: straight overhead, angled isometric, and layered isometric. WarCraft is a good example of a straight overhead map, with Railroad Tycoon 2 and Civilization 2 demonstrating angled isometric and layered isometric respectively.

The straight overhead map and angled isometric map have the simplest possible scenario: a two-dimensional array of map cells. The layered isometric map can also use a two-dimensional array, but there are several complexities. The biggest difference concerns adjacencies in the map.

For overhead and angled isometric maps, adjacent cells are easily determined. If a map cell is at location (x,y), then it's adjacent cells are as seen in Table 1. Horizontal (east-west or left-right) and vertical (north-south or up-down) "wrapping" on the map are also very simple.

Table 1: Overhead and Angled Isometric Adjacency

DirectionLocation
North(x,y-1)
Northeast(x+1,y-1)
East(x+1,y)
Southeast(x+1,y+1)
South(x,y+1)
Southwest   (x-1,y+1)    
West(x-1,y)
Northwest(x-1,y-1)

Layered isometric maps, however, are significantly more complex. This is because, while the map is still a two dimensional array, the adjacencies work differently because of their on-screen representation. How adjacency is calculated varies according to whether the map cell is on an even-numbered row or an odd-numered row. See Table 2 below. Also, while the X dimension can be either even or odd, if the map is to wrap vertically then the Y dimension must be an even number. This is so that bottom and top edges "mesh" correctly.

Table 2: Layered Isometric Adjacency

DirectionLocation
North(x,y-2)
Northeast(x,y-1) (even rows)
(x+1,y-1) (odd rows)
East(x+1,y)
Southeast(x,y+1) (even rows)
(x+1,y+1) (odd rows)
South(x,y+2)
Southwest   (x-1,y+1) (even rows)     
(x,y+1) (odd rows)
West(x-1,y)
Northwest(x-1,y-1) (even rows)
(x,y-1) (odd rows)
even rows = 0, 2, 4, 6, 8, ...
odd rows = 1, 2, 3, 4, 5, ...

Figure 2 shows a small layered isometric grid, with the cells labelled (col,row) to show their position in the map array. You can use Figure 2 to verify that the adjacency calculations in Table 2 are correct. Cell "A" is on an even numbered row and cell "B" is on an odd numbered row.

Figure 2: Layered Isometric Grid Adjacencies

In my projects so far, we've always used a straight overhead map. We considered using a layered isometric map structure for Artifact, but decided not to because of the increased complexity. However, the layed isometric view is becoming more and more the "standard" for this kind of game.

Rendering these maps to the screen, whether overhead or isometric, is a subject for another article. Right now we're simply buildng the necessary data structures.



Next : Unit Data Structures