Haven't written anything for a while now, so it's time for another game dev topic! This time, I'm going to write something about hexagonal maps.
Why this topic? Well, I noticed that there's very little concrete examples about hexagonal map generation and manipulation. Sure, there's lots of theory available, but the practice-oriented stuff was missing. I ran into this while searching for information about generating random hexagonal maps (for my upcoming Android game which shall remain nameless for now), and basically I ended up doing it from scratch, using some hints I found here and there.
Next, I'll go through the very basics of hexagonal maps, and then I'll cover a map generation method I found quite useful. In the future parts, I'll cover more complex stuff like how to divide the map between players and how to make the manipulation more efficient. All the examples are written in Java, but the basic principle is rather simple to extrapolate to other languages as well.
Crash Course to Hexagonal Maps
So, here's a quick briefing about hexagonal maps. A hexagon has six sides, and also, six corners. If you've seen honeycomb pattern, you're already an expert of hexagonal maps. Each hexagon has six neighbors, so basically, when you traverse the map, you always have six directions to go.
Layout
Now, a map can be laid out in two ways: "corners-up" or "sides-up":
"Sides-up" layout |
"Corners-up" layout |
Which of these you should use? It's usually the matter of preference. In a game like Heroes of Might and Magic, the combat scenes use "corners-up" layout because the majority of movement happens horizontally and as such, it makes sense to make it possible to traverse from left to right without zig-zagging. In some games, the "sides-up" layout is preferred. For example, if you have graphics lined up with the edges, you may want to be able to show those graphics for all the edges. If you have "corners-up" layout, two edges are always vertically aligned and it may make the graphics "messy".
In the examples, I will use "sides-up" layout, but you can quite easily modify the snippets for your own scenario.
Coordinates
Simple (X, Y) coordinates |
// Width of a single hex
float width = 128.0f;
// Height of a single hex
float height = 105.0f;
// Offset to get rid of gaps between columns
// TODO Set the hexagon graphics to posX, posY
float offset = 0.3f * width;
// Find out the position for each hexagon
for(int y = 0; y < mapSizeY; ++y)
{
for(int x = 0; x < mapSizeX; ++x)
{
float posX = x * (width - offset); // X position
float posY = y * height; // Y position
float posY = y * height; // Y position
if(x % 2 == 1)
{
// Nudge down every other column
posY -= height / 2.0f;
}
// TODO Set the hexagon graphics to posX, posY
}
}
In the code sample above, we position each hexagon correctly based on the coordinates. Again, this sample is intended for "sides-up" layout, and for the "corners-up" layout, you have to change X and Y accordingly.
public class Hex
// Here we'll do the steps
In the code sample above, we position each hexagon correctly based on the coordinates. Again, this sample is intended for "sides-up" layout, and for the "corners-up" layout, you have to change X and Y accordingly.
Drunkard Walk
Okay, time to get funky! Drunkard walk is an algorithm which, as the name implies, is an analogy of a drunk person trying to walk. In its essence, we choose a root cell, take a random direction, take a step to that direction, choose a new direction, take a new step and so on until certain criteria are met, for example when we have taken 30 steps or when we have covered an area of 100 cells.
In the example I'm going to show, we will start the walk from the origin (0, 0), and walk for a certain amount of steps. Each walk will start from the origin to ensure that the map is "cohesive enough" and that all cells are connected to each other.
The basic principle is really simple, so here's the code example. First, a simple "Hex" class:
{
private int x = 0; // X coordinate
private int y = 0; // Y coordinate
public Hex(int x, int y)
{
this.x = x;
this.y = y;
}
}
public HashSet<Hex> drunkardWalk(int size, int steps)
As you can see, we only store the X and Y coordinates for now, as that's all we need. Moving on, here's the actual drunkard walk algorithm:
{
// A set of hexagon cells
HashSet<Hex> map = new HashSet<Hex>();
// We'll start from the origin
Hex root = new Hex(0, 0);
map.add(root);
// The main generation loop. We will continue
// walking until we have met the total size 'size'
while(map.size() < size)
{
// These store the current cell coordinates
int cx = 0;
int cy = 0;
// Here we'll do the steps
for(int step = 0; step < steps; ++step)
{
// Select a random direction between 0 and 5
int d = (int)(Math.random() * 6);
if(d == 0)
{
// 0 is a step to the south-west if
// x % 2 == 0 OR
// x % 2 == 0 OR
// north-west if x % 2 == 1
cx--;
}
else if(d == 1)
{
// 1 is a step to the south-east if
// x % 2 == 0 OR
// north-east if x % 2 == 1
// 1 is a step to the south-east if
// x % 2 == 0 OR
// north-east if x % 2 == 1
cx++;
}
else if(d == 2)
{
cy--; // 2 is a step to the south
}
else if(d == 3)
{
cy++; // 3 is a step to the north
}
else if(d == 4)
{
if(cx % 2 == 0)
{
cx++; // 4 is a step to the north-east
cy++;
}
else
{
cx++; // 4 is a step to the south-east
cy--;
}
}
else if(d == 5)
{
if(cx % 2 == 0)
{
cx--; // 5 is a step to the north-west
cy++;
}
else
{
cx--; // 5 is a step to the south-west
cy--;
}
}
// Finally, create the hex and add it to the set
map.add(new Hex(cx, cy));
// If you want, you can check for the accurate
// map size here and break out of the while-loop
// so you won't get maps bigger than 'size'
}
}
}
There! In its essence, it's simple as that. It should be noted though that this results in a map that is slightly larger than the size, but it is guaranteed to be at least that big. By tweaking the step count, you can create maps that are either very "condensed" or very, err, "tentacle-y". Here's a couple of examples generated by the algorithm, as well as the parameters used:
Map 1: Size: 100, Steps: 40 |
Map 2: Size: 100, Steps: 10 |
Map 3: Size: 170, Steps: 80 |
Map 4: Size: 170, Steps: 150 |
As you can see, the size directly relates to how big the map is, and the steps value dictates how long the paths become. Personally, I really like how the map #4 formed two bigger islands that are connected with an isthmus. There's even a larger cape in the far right side, with a lagoon. As you can see, the bigger the step value gets, the more it produces holes in the map. I like this feature as they can be interpreted as lakes or untraversable mountains, but if for some reason you don't want such features, you can do a second pass over the map and fill up the holes (search for continuous areas that are completely surrounded by cells and fill these coordinates up).
Just for curiosity, let's bump up the values and create a huge map!
Map 5: Size: 5000, Steps: 1000 |
This. This I like a lot! We even got a couple of big lakes, lots of cool bays and capes, some isthmuses and a huge, vast area in the middle. This is starting to look really cool... Oh, what the hell, let's bump it up just a bit more!
Map 6: Size: 20000, Steps: 5000 |
Neat result as always, but the coolness starts to suffer from the lack of resolution. Anyway, the results can be used for a range of purposes, whether it be a small-scale strategy game, or if you want to use a hexagon-based solution for your huge, open-world adventure game.
Conclusions and Tips'n'tricks
So, there's the "drunkard walk" method for generating hexagonal maps. I used the origin (0, 0) as the starting point for each walk, but that's not mandatory. If you want to have even more bizarre maps, you can choose the starting point from the already-plotted coordinates (to ensure connectivity between all cells), or you can choose the starting points randomly (which does not guarantee connectivity). This of course depends of your need, for example by choosing random starting points you can achieve islands that are not connected to each other. Of course, it's not guaranteed that you get islands. To guarantee that you have islands, I suggest you run the method multiple times and offset the generated coordinates by a certain (random?) amount which is at least the distance from the origin to the furthest cell traversed.
On a side note, you should be careful when choosing the size and the step values. As you increase the size of your map, you must increase the step value as well. Too small step value will make the algorithm loop forever, as there is not enough range for it to function correctly. Based on my trial runs, the step value should be at least 1/10th of the size.
Well, that wraps up this post. Hope you enjoyed it, there is more to come. Feel free to ask questions and comment, I'll try my best to answer. Also, if you find any errors or have suggestions, you are more than welcome to point them out to me as well. :)
No comments:
Post a Comment