October 30, 2013

Hexagonal Map Madness! (Part 1) - Basics and Map Generation


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
With hexagonal maps, you can use either 2- or 3-dimensional coordinates, but for the sake of simplicity, let's use 2-dimensional system. In the image above, you can see the coordinate system I'll be explaining. The bottom left cell with the '0' in it has the coordinates of (0, 0). The red cell is (2, 1) and the green one is (1, 2). To position the hexagons correctly, you have to check whether or not the X coordinate can be divided by two and add (or subtract) half of the hexagon's height of it (or, if you have "corners-up" layout, you check the Y coordinate and nudge the X coordinate instead).

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

            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.

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:

    public class Hex
    {
        private int x = 0; // X coordinate
        private int y = 0; // Y coordinate
        
        public Hex(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

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:

    public HashSet<Hex> drunkardWalk(int size, int steps)
    {
        // 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 
                    // 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
                    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