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
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
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
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.