Warning: file_put_contents(): Only 0 of 10 bytes written, possibly out of free disk space in /var/web/h/heller.christian/htdocs/www.plomlompom.de/PlomRogue/plomwiki.php on line 287
PlomRogue Development Blog: The Creation of Space, Rectangular and Hexagonal

PlomRogue Development Blog

The Creation of Space, Rectangular and Hexagonal

I wanted to populate PlomRogue with landscapes, monsters, items. But these things need ground to stand on: a game map. A virtual space in which things have positions, can move and collide.

As a human, I have some experience of space. I know a bit about the physical space of my cosmos: It seems to have three spatial dimensions. It has no border that I know of. It can be measured in Cartesian coordinates. Distances can get infinitely small. This space that I live in is quite a complex thing. But for my game world, I wanted to start with something much simpler. Roguelikes' map space usually is much more chessboard-like: It is of two dimensions, and enclosed in tight borders. It stores only a finite number of positions to be in. Such limits greatly simplify coding things like movement. So I adopted them.

Square Grid Maps

First, I did for my map what most console / ASCII roguelikes do for theirs: copy terminals' character positioning geometry. A terminal screen prints some number (y) of lines. Each contains some number (x) of possible character positions. The screen may thus be divided into y rows and x columns. It defines y × x possible positions. All rows start at the same width, and all columns at the same height. Horizontal moves of n steps equal n jumps between columns. Vertical moves by n steps equal n jumps between rows.

Representation

Maps copying this screen geometry fit on it easily. Here's an example map of 8 rows × 8 columns (imagine this to be an island: "~" stands for water, "." stands for land and "@" stands for the player character):

~~~~~~~~ 
~~~...~~ 
~~~....~ 
~.....~~ 
~..@...~ 
~~....~~ 
~~~~.~~~ 
~~~~~~~~ 

This style of display is highly efficient: Within the map's confines, each screen position equals one map cell. That way, a lot of map fits on the screen. There is one drawback: Terminal characters usually are not as wide as they are high. This map's width may equal its height in number of cells (both: eight). But on-screen, the map may look much higher than wide. There's a simple way to mitigate this visual distortion: Put empty padding cells between horizontal neighbor cells:

~ ~ ~ ~ ~ ~ ~ ~ 
~ ~ ~ . . . ~ ~ 
~ ~ ~ . . . . ~ 
~ . . . . . ~ ~ 
~ . . @ . . . ~ 
~ ~ . . . . ~ ~ 
~ ~ ~ ~ . ~ ~ ~ 
~ ~ ~ ~ ~ ~ ~ ~ 

This style doubles the screen width necessary to show the map. But screen estate is expensive: I also wanted to fit much other stuff (stats, inventory, helper texts) on the screen. Thus I decided against this wasteful map display style. ASCII roguelikes in general seem to prefer the denser approach. Players' minds may learn quickly to correct its visual distortion. And those truly bothered by it may use more square terminal fonts.

Encoding

Game maps do not just look pretty. They define certain relations of game objects to each other: How great are their distances? Are they neighbors? Do they sit on top of each other? Such questions' answers are encoded in objects' map positions. What is a position in the geometry defined above? It consists of two values: a row y and a column x:

    01234567 (x-axis) 
  
 0  ~~~~~~~~ 
 1  ~~~...~~ 
 2  ~~~....~ 
 3  ~.....~~ 
 4  ~..@...~ 
 5  ~~....~~ 
 6  ~~~~.~~~ 
 7  ~~~~~~~~ 
(y-axis) 

The player's position on this map is: y=4, x=3. Such positions are easily analyzed mathematically: Two objects sit on top of each other if they share y and x. They are neighbors if y or x differ by one step only. Their x's the same, their distance is the difference between their y's. Their y's the same, their distance is the difference between their x's. (Distance is more complicated if both y and x differ. But let's stick to the most simple cases first.)

So much for maps as Cartesian 2D coordinate systems. But that is not how PlomRogue stores game maps at their lowest level: There, they cannot be anything but raw computer memory. This is roughly where I had to start from to code my maps in C. The address space available in C lacks y- and x-axes. Basic C coding deals with linear sequences of bytes only. You walk or jump forward or backward in them, but not up or down. At least not until you define certain regions as "up" or "down". In other words: I had to craft my own 2D geometry.

I started with a quite simple data type / C struct for my maps. It stored the map square's edge length and a pointer to some memory (source file):

struct Map 
{ 
    char * cells;            /* sequence of bytes encoding map cells */ 
    uint16_t length;         /* map's edge length, i.e. both height and width */ 
}; 

(Originally, I defined height and width separately. But after a while, I failed to see any use in non-square maps. Height and width would always be equal. So I needed to store only one of the two.)

The map's content lies at what map.cells points to: an array of map cell values, which encode terrain types – a one-dimensional series of (single-byte) values. In this form, map cells are indexed by single, not (as in the system of y and x coordinates) double numbers. To set a cell, I must refer to it by its array index. Like this:

/* Set map's 1st (upper-left) cell to "~" (water). */ 
map.cells[0] = '~'; 
 
/* Set map's 3rd cell (which is the 3rd cell in its 1st row) to "." (earth). */ 
map.cells[3] = '.'; 
 
/* Set to "X" (wood/tree) the four cells in the map's center. */ 
map.cells[27] = 'X'; 
map.cells[28] = 'X'; 
map.cells[35] = 'X'; 
map.cells[36] = 'X'; 

What indexes refer to what 2D map coordinates? That depends on the order that I store the map's cell values in. I start the array with the leftmost upper cell. From there, I move to the right: The second leftmost upper cell is the array's second value. The third leftmost upper cell follows. And so on. The first row is finished after map.length steps. At this point, I jump to the leftmost cell of the next row. This whole process is repeated until map.length rows are finished. The whole map's possible positions are thus indexed like this (the x-/y-axes enclose a square of array index numbers):

      0  1  2  3  4  5  6  7 (x-axis) 
 
 0    0  1  2  3  4  5  6  7 
 1    8  9 10 11 12 13 14 15 
 2   16 17 18 19 20 21 22 23 
 3   24 25 26 27 28 29 30 31 
 4   32 33 34 35 36 37 38 39 
 5   40 41 42 43 44 45 46 47 
 6   48 49 50 51 52 53 54 55 
 7   56 57 58 59 60 61 62 63 
(y-axis) 

I could try to work with just these map array index numbers. But it's much easier to work with y and x coordinates. So I wrote code to translate map array indexes from and to them. First, here's my struct for y and x coordinates (source file):

/* Coordinate for maps of max. 256x256 cells. */ 
struct yx_uint8 
{ 
    uint8_t y; 
    uint8_t x; 
}; 

(Why uint8_t? I decided my maps would not need to be bigger than 256×256 cells. Therefore, unsigned chars / 8 bit integers would suffice.)

Translation from a map array index is rather simple. How to get the y of a position? Divide its array index by map.length, round the result toward zero. The position's x is that division's remainder:

struct yx_uint8 yx; 
yx.y = map_array_index / map.length; 
yx.x = map_array_index % map.length; 

Translation into a map array index turns this on its head: Multiply y with map.length, then add x:

map_array_index = (yx.y * map.length) + yx.x; 

Movement

Movement is easily solved with y and x coordinates. Just increment y to move down. Decrement y to move up. Increment x to move to the right. Decrement x to move to the left:

/* Move one step up. */ 
yx.y--; 
 
/* Move one step down. */ 
yx.y++; 
 
/* Move one step to the left. */ 
yx.x--; 
 
/* Move one step to the right. */ 
yx.x++; 

Or I could manipulate the array indexes directly:

/* Move one step up. */ 
map_index = map_index - map.length; 
 
/* Move one step down. */ 
map_index = map_index + map.length; 
 
/* Move one step to the left. */ 
map_index--; 
 
/* Move one step to the right. */ 
map_index++; 

Border Checks

What happens when moving down from the lowest row? What happens when moving to the left from the leftmost column? There are two ways to treat such border-cases: I might allow wrapping of moves: What leaves the map on the left will re-enter it on the right. Or I might check for such cases and forbid them. I went with the latter option. Movement should happen only when it stays within the map borders:

/* Move one step up, if possible. */ 
if (yx.y > 0) 
{ 
    yx.y--; 
} 
 
/* Move one step down, if possible. */ 
if (yx.y < map.length - 1) 
{ 
    yx.y++; 
} 
 
/* Move one step to the left, if possible. */ 
if (yx.x > 0) 
{ 
    yx.x--; 
} 
 
/* Move one step to the right, if possible. */ 
if (yx.x < map.length - 1) 
{ 
    yx.x++; 
} 

The same checks may be done for array index movements, too. But if-conditions get a bit more complicated then:

/* Move one step up, if possible. */ 
if (map_index >= map.length) 
{ 
    map_index = map_index - map.length; 
} 
 
/* Move one step down, if possible. */ 
if (map_index < (map.length * map.length) - map.length) 
{ 
    map_index = map_index + map.length; 
} 
 
/* Move one step to the left, if possible. */ 
if (map_index % map.length) 
{ 
    map_index--; 
} 
 
/* Move one step to the right, if possible. */ 
if ((map_index + 1) % map.length) 
{ 
    map_index++; 
} 

Diagonal Movement

There's nothing controversial about orthogonal moves (to the left, right, up or down). Roguelike map geometries like the above always support them. But what about diagonal moves – to the upper left, the lower left, the upper right, the lower right?

Let's imagine the map grid as a real-life chessboard. Draw a circle centered on one square's center point. Extend the circle's radius to this square's left neighbor square's center. Something interesting then happens with the circle's border: It does not just hit the left neighbor square's center. It also hits all three other orthogonal neighbor squares' centers. Orthogonal neighbor squares' center points all share the same distance. But the circle won't hit the diagonal neighbor squares' centers: Those are a tiny bit farther away.

This "tiny bit farther away" grows when the circle's radius grows. Let's assume one orthogonal step crosses 1 centimeter. One diagonal step then crosses roughly 1.4 centimeters. Three orthogonal steps would cross 3 centimeters. Three diagonal steps would then cross roughly 4.2 centimeters. Ten diagonal steps would cross roughly 14 centimeters – which would be the distance of fourteen orthogonal steps. Diagonal moves cover more distance than orthogonal ones. Therefore, they should be more costly. If orthogonal moves take time, diagonal moves should take more.

There are different solutions to this among roguelikes. Some treat orthogonal and diagonal moves as equals. This distorts planar distances as compared to real world physics. But realism is rarely a top priority. Some roguelikes give it a try, though: They penalize diagonal moves to some degree. Diagonal moves may cost as much as two orthogonal ones. Or one-and-a-half. Or seven fifths. Or (most precisely) the orthogonal move's cost times the square root of two. There is, however, a drawback to such precision: Players might want to plan their moves' costs in advance in their minds. This gets much more complicated with more complicated numbers. Planar distortion may be a small price for keeping things simple. Some roguelikes make things even simpler: They drop diagonal movement altogether. Each of these solutions has its pros and cons. None of them is optimal in all cases.

As I wrote earlier, I fail at making decisions. So I coded support for not one, but all of these solutions. Originally, I worked with orthogonal moves only. Then I added diagonal moves, with a move cost penalty: Diagonal moves cost as much as orthogonal moves times a multiplier – the quotient of two (positive) integers to be set by the user. The user might choose a multiplier of 3/2, or 7/5, etc. They might choose one of 1/1 to drop the penalty altogether. (They might even choose a multiplier smaller than 1/1. I never tested that. The effect might have been interesting: Don't fight the diagonal movement distortion, but embrace it. Heighten the distortion's strategic value!)

The two numbers were set in a config file with these two lines (shown are the default values):

DIST_ORTHOGONAL 5 
DIST_DIAGONAL 7 

"DIST_DIAGONAL" would be the dividend, "DIST_ORTHOGONAL" the divisor. The above therefore would create the multiplier 7/5: If orthogonal moves' cost was 1, diagonal moves' cost was 1.4.

Hex Grid Maps

I got comfortable in my map grid of rectangles. Diagonal moves were a bit of a hassle, but mostly solved. Everything else worked fine in this geometry. Then something horrible happened: Benni Bärmann asked me why I did not use hex maps.

Pros and Cons

At first, the answer seemed obvious to me: They're much harder to represent in ASCII. Hex map cells are not rectangular like the ASCII display's cells. I can't just map screens' rows and colums to hex maps' grids. I thought hexagons would need to be drawn as large ASCII art. A bit like these ideas of erlehmann. But Benni answered: Why not draw a hex map like this?:

~ ~ ~ ~ ~ ~ ~ ~ 
 ~ ~ ~ . . . ~ ~ 
~ ~ ~ . . . . ~ 
 ~ . . . . . ~ ~ 
~ . . @ . . . ~ 
 ~ ~ . . . . ~ ~ 
~ ~ ~ ~ . ~ ~ ~ 
 ~ ~ ~ ~ ~ ~ ~ ~ 

There's one empty screen cell between each two horizontal neighbors. It doesn't count as a map cell by itself – it's just for padding. Every second row starts one such padding cell indented. Each map cell thus has six neighbors: two horizontal ones (reachable by jumping over the empty padding cells), and four diagonal ones.

This display style eats more screen than the dense square grid map display style. But not much more. I had refused such horizontal padding for square grid maps. There, I considered it a waste of screen estate. But it's hard to come up with a denser display style for hex maps. I therefore did not consider it as wasteful here. And it brought the visual benefit of horizontal padding: Maps as high as wide look it in terminal fonts higher than wide.

This might be considered a merely cosmetic advantage. A stronger one was the lack of diagonal movement hassles: Neighbor cells' centers are equally distant in all directions (provided the hexagons are regular, which I assume of course). No need to treat orthogonal and diagonal moves differently. No need for cost penalties on moves of certain directions. No need to parse user input defining cost multipliers. With hex maps, I could drop or simplify several parts of my code.

But I saw another problem with hex maps: How to represent rectangular structures in them? Straight lines could be drawn horizontally, but not vertically. An approximated square would look rather distorted:

. . . . . . . . 
 . # # # # # # . 
. # . . . . # . 
 . # . . . . # . 
. # . . . . # . 
 . # . . . . # . 
. # # # # # # . 
 . . . . . . . . 

I could rotate it a bit, but that would not help all that much:

. . . # # . . . 
 . . # . # # . . 
. . # . . . # #   
 . # . . . . . # 
. # . . . . . # 
 . # # . . . # . 
. . . # # . # . 
 . . . . # # . . 

Rectangular stuff will always look somewhat distorted on hex maps. That may suck if the game world demands much rectangularity. What's usually rectangular? Man-made objects and buildings. Dungeons as imagined by roguelike classics like NetHack. Natural environments are more forgiving: There are few right angles in deserts, jungles, oceans, outer space. Even natural processes (erosion, gravity) may create flatness and straight lines. But hex maps aren't much less capable of approximating these. Compare some "straight" lines on a square grid …:

. O . . O . . $ . O O O . . . . . . . . $ . . . . . . . . . O . . . . . . $ . . 
. O . . O . $ . . . . . O O . . . . . $ . . . . . . . . . . . O . . . . $ . . . 
. O . . . O $ . . . . . . . O O O . $ . . . . . . . . . . . . . O . . $ . . . . 
# O # # # O # # # # # # # # # # # O O # # # # # # # # # # # # # # O $ # # # # # 
. O . . . $ O . . . . . . . . . . § . O O O . . . . . . . . . . . $ O . . . . . 
. O . . $ . O . . . . . . . . . $ . . . . . O O . . . . . . . . $ . . O . . . . 
. O . . $ . . O . . . . . . . $ . . . . . . . . O O O . . . . $ . . . . O . . . 
. O . $ . . . O . . . . . . $ . . . . . . . . . . . . O O . $ . . . . . . O . . 

… and a hex grid:

. O . . O . . $ . O O O . . . . . . . . $ . . . . . . . . . O . . . . . . $ . . 
 . O . . O . $ . . . . O O O . . . . $ $ . . . . . . . . . . O O . . . $ $ . . . 
. O . . . O $ . . . . . . . O O O . $ . . . . . . . . . . . . . O . . $ . . . .  
 # O # # # O # # # # # # # # # # O O O # # # # # # # # # # # # # O O $ # # # # # 
. O . . . $ O . . . . . . . . . . $ . O O O . . . . . . . . . . . $ O . . . . . 
 . O . . $ . O . . . . . . . . $ $ . . . . O O O . . . . . . . . $ . O O . . . . 
. O . . $ . . O . . . . . . . $ . . . . . . . . O O O . . . . § § . . . O . . . 
 . O . $ . . . O . . . . . . $ . . . . . . . . . . . O O O . $ . . . . . O O . . 

Square grids distort shapes, too. For some cases, more so than hex grids. Square grids are great for one thing: lines orthogonal or diagonal to screens' height verticals. Rotate such lines by just some degrees, and the advantage is gone. To keep it, the game world must look like the grid plan of Manhattan: all straight lines of very few angles, parallel to each other. This suggests orderliness and predictability in maps – strange guides for the arcane dungeons and caves favored in the genre. Those were not the principles I wanted to build my worlds by. Lack of orthogonality would not put me off hex maps. To the contrary: It might improve maps by not favoring a small subset of shapes. In hex grids, almost all shapes look equally ugly. (Certain hexagons and triangles and shapes made of them look great. But I doubt they'd quickly become as abundant as rectangles. They're too unusual in most conventions of architecture.)

Re-Writing Code

I lacked further excuses to not use hex maps. I decided to drop rectangularity and switch to them. But how would I encode hex maps? Actually, I did not have to change much. I could keep my map structs. Maps would remain a column of rows. Positions could still be refered to by y and x coordinates. The visual representation needed to change only slightly: Rows needed to be widened by empty padding cells. Every second row had to be indented by one padding cell. The only major change concerned movements.

Movement

Calculation of horizontal moves could remain the same: Increment x to move forward. Decrement x to move backward. Movement up and down could not remain the same, though: It was to be replaced by four diagonal moves: one to the upper left, one to the lower left, one to the upper right, one to the lower right. And these did not always work like diagonal moves in square grid maps. Consider this player position:

    0 1 2 3 4 5 6 7 (x-axis) 
  
 0  ~ ~ ~ ~ ~ ~ ~ ~ 
 1   ~ ~ ~ . . . ~ ~ 
 2  ~ ~ ~ . . . . ~ 
 3   ~ . . . . . ~ ~ 
 4  ~ . . @ . . . ~ 
 5   ~ ~ . . . . ~ ~ 
 6  ~ ~ ~ ~ . ~ ~ ~ 
 7   ~ ~ ~ ~ ~ ~ ~ ~ 
(y-axis) 

The player's position is y=4, x=3. Moving to the upper left seems to work as in square grid movement: Decrement y to 3 to move up. Then move to the left, i.e. decrement x to 2. The result looks okay ("T" be the player move's target cell):

    0 1 2 3 4 5 6 7 (x-axis) 
  
 0  ~ ~ ~ ~ ~ ~ ~ ~ 
 1   ~ ~ ~ . . . ~ ~ 
 2  ~ ~ ~ . . . . ~ 
 3   ~ . T . . . ~ ~ 
 4  ~ . . @ . . . ~ 
 5   ~ ~ . . . . ~ ~ 
 6  ~ ~ ~ ~ . ~ ~ ~ 
 7   ~ ~ ~ ~ ~ ~ ~ ~ 
(y-axis) 

But what about moving to the upper right? Again, let's do it the old way: Decrement y to 3. Then increment x to 4:

    0 1 2 3 4 5 6 7 (x-axis) 
  
 0  ~ ~ ~ ~ ~ ~ ~ ~ 
 1   ~ ~ ~ . . . ~ ~ 
 2  ~ ~ ~ . . . . ~ 
 3   ~ . . . T . ~ ~ 
 4  ~ . . @ . . . ~ 
 5   ~ ~ . . . . ~ ~ 
 6  ~ ~ ~ ~ . ~ ~ ~ 
 7   ~ ~ ~ ~ ~ ~ ~ ~ 
(y-axis) 

That looks wrong. The player would move too far to the right. The result looks much better if x remains the same:

    0 1 2 3 4 5 6 7 (x-axis) 
  
 0  ~ ~ ~ ~ ~ ~ ~ ~ 
 1   ~ ~ ~ . . . ~ ~ 
 2  ~ ~ ~ . . . . ~ 
 3   ~ . . T . . ~ ~ 
 4  ~ . . @ . . . ~ 
 5   ~ ~ . . . . ~ ~ 
 6  ~ ~ ~ ~ . ~ ~ ~ 
 7   ~ ~ ~ ~ ~ ~ ~ ~ 
(y-axis) 

Internally, that's the same as a mere old-style move up. Internally, no move to the right happens. Why?

In this hex map encoding system, diagonal moves work like this: Internally, half of them keep x the same – either all diagonal moves to the left, or all to the right. Which half is affected depends on the row from which to start. From indented rows, all leftward diagonal moves keep their x. From non-indented rows, all rightward diagonal moves do. Indentation depends on the evenness of the row number. This allows easy handling of this issue in the movement code:

/* Move one step to the upper right. */ 
yx.x = yx.x + (yx.y % 2); 
yx.y--; 
 
/* Move one step to the right. */ 
yx.x++; 
 
/* Move one step to the lower right. */ 
yx.x = yx.x + (yx.y % 2); 
yx.y++; 
 
/* Move one step to the lower left. */ 
yx.x = yx.x - !(yx.y % 2); 
yx.y++; 
 
/* Move one step to the left. */ 
yx.x--; 
 
/* Move one step to the upper left. */ 
yx.x = yx.x - !(yx.y % 2); 
yx.y--; 

Border Checks

Let's finish the movement code by adding border checks. The checks for mere horizontal moves are easy: x must be too great to drop below 0, or too small to grow to map.length. The checks for diagonal moves are more complex: On the one hand, they must check the vertical part of the move. That's as simple as the horizontal move check: y must be too great not to drop below 0, or too small to grow to map.length. On the other hand, the move's horizontal move part must be checked. For that part to be legal, one of two conditions must be met: No horizontal move happens (due to the indentation rule described above). Or: x (again) is too great to drop below 0, or too small to grow to map.length:

/* Move one step to the upper right, if possible. */ 
if (yx.y > 0              && (!(yx.y % 2) || yx.x < map.length - 1)) 
{ 
    yx.x = yx.x + (yx.y % 2); 
    yx.y--; 
} 
 
/* Move one step to the lower right, if possible. */ 
if (yx.y < map.length - 1 && (!(yx.y % 2) || yx.x < map.length - 1)) 
{ 
    yx.x = yx.x + (yx.y % 2); 
    yx.y++; 
} 
 
/* Move one step to the right, if possible. */ 
if (yx.x < map.length - 1) 
{ 
    yx.x++; 
} 
 
/* Move one step to the lower left, if possible. */ 
if (yx.y < map.length - 1 && (!(yx.y % 2) || yx.x > 0)) 
{ 
    yx.x = yx.x - !(yx.y % 2); 
    yx.y++; 
} 
 
/* Move one step to the left, if possible. */ 
if (yx.x > 0) 
{ 
    yx.x--; 
} 
 
/* Move one step to the upper left, if possible. */ 
if (yx.y > 0              && (!(yx.y % 2) || yx.x > 0)) 
{ 
    yx.x = yx.x - !(yx.y % 2); 
    yx.y--; 
{ 

That's the basics by which moves in PlomRogue's hex maps work. How about direct manipulation of map array indexes? I might come up with code for that too, but saw no need for it so far. For now, I leave that as an exercise for the reader.

Further Complications

That's the basics of how maps currently work in PlomRogue. It's enough to allow landscapes and move actors around on them. How those landscapes are built is another matter. So is how those landscapes' terrains affect moves. Map positions may be operated on in more complex ways: How to draw straight lines of any angle between two positions? That's an important issue for computing actors' lines of sight. I hope to write more on such matters in later posts.

Comments

Why didn't you consider a two-dimensional array? This would solve the coordinates problem nicely and since the map is of fixed size it wouldn't make any problems. Actually this is the way I do store the map in tinyRL.

I truly did not consider that. I am going to think about it.

I did consider, and test it: http://www.plomlompom.de/PlomRogue/plomwiki.php?title=ArraysFor2DMaps1DOr2D

Write your own comment

Commenting currently impossible: Captcha not set.