July 31, 2014

Project "Tremor" Devlog - Part 1

Yo ho ho and... two cups of coffee to get my day going? Yesterday, I finally started working on a project I've fantasized about for a looooo-ong time. It even got a name: this over-ambitious project shall be named "Tremor" - it will be ground-shaking, it will destroy everything on its way, and... it was the first word that came up to my head when I was creating the VS solution. It's all good.

So, what's Tremor, then? It's (or rather, it should become) a light-weight library that abstracts platform-specific code and has some features that aid game development. Basically, it's a game engine, although calling it an "engine", at least at this point, is, well, pointless. The grand vision is that it'll run on desktop, Android, and Windows Phone 8(.1), and it will feature 2D graphics support, scene graph and action system, pretty much what you can find in any modern game library (Cocos2D-X, LibGDX and others).

All in all, the first baby-steps are going well. The code compiles on all platforms, and each platform already features a platform-specific stub that prints out a platform-specific "Hello World!". On Windows and WP8, I've tested the build with Visual Studio, and using NDK, I managed to build the same code successfully for Android.

Next step? I want to draw a triangle. Preferably, a white triangle. And it has to be awesome.

July 29, 2014

Cocos2D-X series - Actions

Lately, I've tried to dabble a bit with Cocos2D-X. Pretty much all the time while trying to do something, I get stuck for a loooong time trying to figure how to do something. For the purpose of creating a "cheat-sheet" of some sort - and to help out others who struggle with learning Cocos2D-X - I'm writing these categorized posts about features of Cocos2D-X.

Actions

Cocos2D-X relies quite heavily on actions. If you've used LibGDX's Scene2D system or something similar, you may already know about action system. Actions are basically commands for objects like sprites to do something. They can be commands to move to a new location, rotate for a bit or something else. Almost all properties can be changed via actions.

So, how do we use actions? Basically, like this:


// Create a new sprite called 'tile', using an image file 'tile.png'
Sprite* tile = Sprite::create("tile.png");

// Add the tile sprite to the scene
this->addChild(tile);

// Tell the sprite to rotate 90 degrees clockwise during the next three seconds
tile->runAction(RotateBy::create(3.f, 90.f));

The last line here is the most important one. As you can see, you take the sprite, call its 'runAction()' method, and pass an action to it - in this case, RotateBy action, which rotates the sprite 90 degrees clockwise and uses three seconds on the action, making the rotation quite slow. Cool!

Action types

So, what types of actions are there? Let's take a look! First off, the actions are divided into two categories called "interval actions" and "instant actions". The "interval actions" are executed for a period of time, while the "instant actions" are, well, instant.

Instant actions

CallFunc is an action that calls a callback function. You can give it a function pointer and the function gets called. Doesn't sound that useful right away? "Why not just call the function?" As it turns out, you can chain actions (we'll learn about that later), and you can - for example - put CallFunc as the final action in a sequence, for example to inform about a completed sequence of actions.

FlipX and FlipY flip a sprite horizontally or vertically, in that order. For a quick reminder, horizontal flip makes "left to be right and right to be left", while vertical flip flips the sprite upside-down..!

Hide is pretty self-explanatory. It hides the node so it's not visible anymore. Show, on the other hand, makes a node visible again. ToggleVisibility is closely related; it hides the node if it's visible, and shows the node if it's hidden.

Place is an instant location change actions. It basically just places the node to the specified location.

RemoveSelf removes the node from the scene.

ReuseGrid is a bit more complicated - it basically lets you reuse a grid. I'd say this is a bit more advanced usage of actions - don't panic if you don't understand this right away. StopGrid is related to this, but I haven't yet figured out what it does.

Interval actions

AccelAmplitude is a complex action class that has an amplitude and a duration. Again, it's a bit more advanced stuff. AccelDecelAmplitude and DeccelAmplitude are related.

ActionCamera is a base class for camera-related actions - that is, actions that control camera properties.

ActionEase is a base class for all "easings". Easings are simply modificators on the value changes on other actions - I'll discuss these in depth a bit later.

ActionTween is an interval action that can modify custom properties.

Animate is used to animate a sprite. It automatically changes frames and plays the animation for a certain duration.

Animate3D is similar to Animate, but it uses Sprite3D and Animation3D objects instead.

BezierBy moves a target along a bezier curve.

Blink makes a sprite blink for a certain time and at certain rate. Remember those old NES games where whenever you took damage, your character started blinking? It's really easy to do using this action!

CardinalSplineTo is a bit similar to BezierBy, but uses a cardinal spline instead.

DelayTime takes another action and delays it for a certain amount of time. It can be useful sometimes to delay something happening immediately, and this is the way to do it.

FadeTo fades an object's opacity - that is, the alpha channel - to the given value. If the value is 0, it fades the object out until it's completely invisible. If the value is 1, it fades the object in until it's completely visible.

GridAction is a base class for all grid-based actions. Grid-based actions are more special kind of actions that perform certain cool effects like shattering the object into tiny parts or creating a ripple effect that traverses through the object like if something was dropped in water.

JumpBy is a command that makes an object to travel like it jumped. The movement follows the parabolic curve of a jump.

MoveBy is probably the most common one of these. It makes an object move a certain distance.

MoveTo is closely related to MoveBy, but it takes an absolute location where the object is then moved to.

ProgressFromTo changes a percentage value from one value to another.

ProgressTo progresses a percentage value from zero to the given value.

Repeat takes another action and repeats it.

RepeatForever takes another action and, well, repeats it forever.

ReverseTime takes another action and executes it backwards.

RotateBy rotates the object by a certain amount of degrees.

RotateTo rotates the objects to a certain orientation.

ScaleBy scale the object by a certain scale. If an object's scale is 1 and you first run an action to scale it by 3 and then by 2, the resulting scale will be 6.

ScaleTo scales the object to a certain scale. If an object's scale is 1 and you first run an action to scale it to 3 and then to 2, the resulting scale will be 2.

Sequence is an action that takes a number of actions and executes them as a sequence, first running the first action, and when it's done, continuing with the second one and so on until all the actions are done.

SkewTo skews a node, either horizontally or vertically.

SkewBy skews a node, either horizontally or vertically, adding to the skewness it already has.

TargetedAction overrides the target set by the node's runAction() method, allowing you to specify another target instead.

TintBy changes the node's color by the amount specified.

TintTo changes the node's color to the color specified.

Phew! There's a whole lot of actions there already! It's not all of them, but those are probably the ones you're going to use the most. Next time, I'll write more about the easings and action chaining.

June 3, 2014

Power of JSON in Game Development - Items

Hey there, it's been a while since I last time wrote anything here, so... It's time to fix that!

This time, I'm going to tell you about JSON and how it's one of the greatest things ever. Lately, I've been fiddling around with a game that relies heavily on persistent data - I need to store high scores, whether or not the player has seen a certain tutorial tip, what kind of items there are available and so on. All this could be achieved via simple binary files and code to represent everything, but this would soon become rather cumbersome to deal with.

Let's think of an item system in a generic RPG game. You have your swords, bows, daggers and wands, as well as helmets, chest armors, gloves and boots. All of them share similarities: each of them has a unique name, they only fit certain slots, and they provide certain bonuses. Now, often times you would rush into coding and do something like this:


public class Item {

    String name;
    Slot slot;
    Sprite sprite;
    public Item(String name) {
        this.name = name;
    }

}

public class Sword extends Item {
  
    public Sword(String name) {
        super(name);
    }
}

public class SwordOfDoom extends Sword {

    public SwordOfDoom() {
        super("Sword of Doom");
        slot = Slot.MainHand;
    }

}

Now, this seems viable at first, but what if there's tons of items in your game? I'm sure you don't want to go creating as many classes as there are items! To make this so much more easier, let's use JSON!

What's JSON?

As you may already know, JSON is a simple way of storing data in text form. It's really lightweight and allows for easy transfer and storage of data. What you may not know is that you can store Java objects in JSON too. Whaaat?

Yeah, it's true. In libgdx, there's really good JSON classes that do this for you. You can create all your items in JSON and the game will create the actual objects automatically. Talk about awesome, eh?

How?

If you use libgdx, it's rather simple. Let's take item system as an example and write some nifty JSON:

{
    items: [
        SwordOfDoom: {
            class: com.manabreak.awesomerpg.Sword,
            name: "Sword of Doom",
            texture: "swordofdoom",
            damageMin: 7,
            damageMax: 9
        },
        DaggerOfKnowledge: {
            class: com.manabreak.awesomerpg.Dagger,
            name: "Dagger of Knowledge",
            texture: "dagger_green",
            damageMin: 5,
            damageMax: 15
        }
    ]
}

I think it's already pretty clear what's going on in here. We have an array of JSON objects called 'items'. Each item has a name (SwordOfDoom and DaggerOfKnowledge in this case), and each of these items has a set of properties, such as which class to instantiate, which name it should use in-game and so on. As you can also see here, you can mention the name of the texture you want to use and any other properties such as damage output.

Now, to load these items in the game, we'll have to create the classes first:


public class Item {

    // Name of the item
    private String name;

    // Texture to use for the item
    private String texture;

    // We need an empty constructor for (de)serialization
    public Item() {}

}

public class Weapon extends Item {
    
    // Minimum damage
    int damageMin = 0;

    // Maximum damage
    int damageMax = 0;

    // Again, empty constructor
    public Weapon() {}
}

public class Sword extends Weapon {

    public Sword() {}

}

public class Dagger extends Weapon {

    public Dagger() {}

}


Now we have our classes. Notice how the names of the fields are exactly the same as in the JSON. This is important for the reflection and (de)serialization. Now, all we need to do is write a controller that will load the JSON for us:

public class ItemController {

    // Hashmap where we store our items as "item name"-"item" pairs
    private HashMap<String, Item> items = new HashMap<String, Item>();

    public ItemController() {
        loadItemsFromJSON();
    }

    private void loadItemsFromJSON() {
        Json json = new Json();
        items = json.fromJson(HashMap.class, Gdx.files.internal("items.json"));
    }
}


If everything went OK, you should now have both of your weapons in the hash map!

Why separate classes for Sword and Dagger? Why not just Weapon?

This is to provide different functionality to different items. If both swords and daggers behave similarly, then it's OK to use a single class for both of them. However, if you have different functionality for them, you'll need to write the code for both of them. While you still need to write code for each different item type, you still end up writing a lot less code as you don't have to write separate classes for each individual item. You can write hundreds of different swords in the JSON file, and if they all behave the same, you'll only need the one Sword class! Hooray!

Hope you find this post useful. It's written in Java and uses libgdx as an example, but similar reflection systems can be used in other languages and with other tools as well. Cheers!




February 19, 2014

Hashrate Hunt: XFX R9 280X Black Edition

A few weeks ago I, like many other before me, got hooked by mining. In its essence, it's all about calculating hashes really, REALLY fash and hoping to find a small enough hash. If you do, you get money!

The problem was that my old graphics card, GTX 560 Ti, was slow. It pumped about 150 kilohashes per second. Now, to give some contrast, recently released graphics cards tend to push over 700 kilohashes per second. So, I decided to update to a bit more modern graphics card (I mean, I was going to need a new one anyway, now I had one more reason!). After two days of online window-shopping, I came across a viable choice: XFX R9 280X Black Edition. I had read that 280X has a good bang-for-buck ratio, boosting out 750 Kh / s. So, I ordered the card, feeling really enthusiastic.

Come last friday, I unbox the card, swap it with the old one, install drivers and launch cgminer...

...and boy was I disappointed. 550 Kh / s.

I crawled through some cryptocurrency forums and subreddit, and decided to try out sgminer. Result? 580 Kh / s. Sigh. I mean, I was "happy" that it was about four times faster than my old card, but I was still disappointed as I hoped more.

The next few days, I tried a lot of stuff: flashing modified BIOS, overclocking, revising the cooling system, adjusting launch parameters... Nothing seemed to do the trick. 580 Kh /s was the magic barrier. Feeling utterly defeated, I was browsing the forums once again, sipping cold coffee, listening to the crappy, slow graphics card going "WWWWWWWWWWWWWZZZZZZZZZZZZZ" under the desk... And then, I found some discussions about newer Sapphire cards having this weird "feature" where the BIOS throttles the graphics card if it overheats. Hmm... The BIOS version in question was a tad older than the one in my card, so it could be true for my card as well.

At this point, let me recap the clock values of my card. The card is factory-overclocked to 1100 MHz core clock and 1650 MHz memory clock. Many other cards available have a lot smaller clocks, but they still hash faster.

Anyway, I came across a post that claimed that the magic values would be 1020 MHz for core and 1500 MHz for memory. Well, why not? Seems a bit counter-intuitive, but what the hell...

... 670 Kh / s. 670 Kh / s! Wow. By underclocking the card, I got over 17% more hashing speed! I even tweaked it a bit more, setting the core clock to 1028 MHz, and it gave a tad over 680 Kh / s. Awesome.

The problem seems to be abou throttling with this card. Now, if I set the memory clock to, say, 1520 MHz, the speed will instantly drop to ~500 Kh / s. What about 1490 MHz? it drops to 650 Kh / s. It seems that I can't touch these values anymore at all. Bummer.

Well, it's a victory for now. But I'm not done yet. It MUST to go over 700! In the meantime, here's my batch file for those who are interested:

setx GPU_MAX_ALLOC_PERCENT 100
setx GPU_USE_SYNC_OBJECTS 1
sgminer.exe -o <address_here> -u <user.worker> -p <pass> --lookup-gap 2 -g 2 -I 13 --thread-concurrency 8193 -w 256 --gpu-memclock 1500,1500 --gpu-engine 1028,1028 --gpu-powertune -20,-20 --expiry 1 --scantime 1 --queue 0 --no-submit-stale --gpu-threads 2 --gpu-dyninterval 7

Thanks for reading through, and if you found this useful, feel free to donate some coins :)

DogeCoin (DOGE): DG5PDSTiZd8KPxTgb8uSgBS4XRKdD31dcc
AuroraCoin (AUR): ALtibmHLSg3j54P8xGs8pYFKdooKAZjNyL

December 21, 2013

Howto: Use Unity3D as a level editor for your own game

I ran into a small problem while I was writing my own hobby game. I needed a level editor, and I wrote one. The real problem was, though, that the editor wasn't very quick to use, and it lacked a lot of optimization code. Instead of further developing this small editor, I came up with a thought: What if I used Unity3D as an editor?

... Challenge accepted!


It turned out to be quite a simple task, in the end. I wrote the export code as an editor extension, which would save the scene in my own binary format. This way, I can design a level just like I would when developing a "full" Unity3D game.

So, let's begin! First, create a new Unity3D project:


After you've created the project, create a new C# script. I called it "ExportScript.cs":


Now, the actual script! In its basic form, the export script is like this:


using UnityEditor;
using UnityEngine;
using System.Collections;
using System.IO;

// This class is responsible for exporting the scene to our own file format
public class ExportScript : EditorWindow
{
    [MenuItem("File/Export")]
    public static void ShowWindow()
    {
        EditorWindow.GetWindow(typeof(ExportScript));
    }
 
    void OnGUI()
    {
        // Create a button that will start the export function
        GUILayout.Label("Export Level", EditorStyles.boldLabel);
        if(GUI.Button(new Rect(10, 50, 100, 32), "Export"))
        {
            // Start the export
            Export();
        }
    }

    // Our output writer
 BinaryWriter writer;
 
 // The export function
 void Export()
 {
  // Create a new output file stream
  writer = new BinaryWriter(new FileStream("out.lvl", FileMode.Create));
  
  // TODO: Write all the data we need (gameobjects, lights, components etc.)
  
  // All done, close the writer
  writer.Close();
 }
}

And that's it! Now, what do we actually want to write to the file? It depends. In my own game project, I wanted to get textures, meshes, game objects, lights, colliders, joints, sounds, background music... Just about everything contained in the scenes. I will not show all the code for this as it would be too much, but the basic concept goes like this: First, write the basic information about the game objects, like name, location, orientation, and scale. Then, for each component you require, check if the game object has that component (say, a mesh filter), and if it does, write all the information available for that component.

It's really simple to do, although it takes some time to write all the component stuff down. When doing this, Unity3D's script reference helps a lot, and you can always check the inspector view to see if you've missed something. :)

Anyhoo, let's take a look at the final example. In this example, the script goes through all the game objects in the scene and saves their names and transforms, as well as checks for the mesh filter components.


    void Export()
 {
  // Create a new output file stream
  writer = new BinaryWriter(new FileStream("out.lvl", FileMode.Create));
  
  // Loop through the transforms in the scene, exporting only what's necessary
  foreach(Transform t in Object.FindObjectsOfType(typeof(Transform)))
  {
   Debug.Log("Exporting " + t.gameObject.name);
   WriteTransform(t);
  }
  
  // All done, close the writer
  writer.Close();
 }

    // Writes the transform object
 void WriteTransform(Transform t)
 {
  // Write the basic transform components (location, orientation, scale)
  writer.Write(t.position.x);
  writer.Write(t.position.y);
  writer.Write(t.position.z);
  writer.Write(t.rotation.x);
  writer.Write(t.rotation.y);
  writer.Write(t.rotation.z);
  writer.Write(t.rotation.w);
  writer.Write(t.localScale.x);
  writer.Write(t.localScale.y);
  writer.Write(t.localScale.z);
  
  // Write the mesh renderer (cast / receive shadows, materials)
  WriteMeshRenderer(t.GetComponent<meshrenderer>());
  
  // Write the actual mesh
  WriteMesh(t.GetComponent<meshfilter>());
 }
 
 void WriteMeshRenderer(MeshRenderer mr)
 {
  if(mr != null)
  {
   // Mesh renderer found, write '1'
   writer.Write(1);
   
   // Write the mesh renderer properties
   writer.Write(mr.castShadows);
   writer.Write(mr.receiveShadows);
   
   // TODO: Write the materials
   
  }
  else
  { 
   // No mesh renderer found, write '0'
   writer.Write(0);
  }
 }
 
 void writeMesh(MeshFilter mf)
 {
  if(mf != null)
  {
   writer.Write(1);
   Mesh mesh = mf.mesh;
            // TODO: Write the mesh data (vertices, indices, UVs etc.)
  }
  else
  {
   writer.Write(0);
  }
 }

There! When you want to run the script, go to the menu "File > Export". The level will be saved to a file called "out.lvl" in the Unity3D project root.

Now, things to consider: You should keep track of all the assets you've written (meshes, materials, textures, sounds etc.), and only write them once. You can also create multiple files, for example save materials to one file, meshes to one and so on. A more sophisticated approach is to create atlas files where you have every asset you need neatly packed. You can also create texture atlases on-the-fly, create dummy scripts in Unity3D to have references about doors between scenes, set dummy objects for player spawns, and just about whatever you need! Remember, you can take full advantage of the tags, layers and such Unity3D has to offer. You can also write the output in JSON, do conversions between classes with reflection, you name it!

I hope you found this small tutorial useful, and as always, feel free to comment and ask questions. You can also make requests about future blog posts and tutorials. :)

December 4, 2013

Hexagonal Map Madness! (Part 2) - Division Between Players

Last time, we took a look on how to generate hexagonal maps using a method called "drunkard walk". Now that we have randomly generated maps we like, I think it's time to see how we could set up areas for each player.

First, before we dive into the areas, we have to make some additions to the code we wrote last time. :)

Storing Neighbors

To make life easier, we can keep track of each cell's neighbors. As you probably already know, a hexagonal cell can have at most six neighbors. These neighbors can be stored as references in the Hex class like this:

public class Hex
{
 private int x = 0; // X coordinate
 private int y = 0; // Y coordinate
 private HashSet<hex> neighbors; // Neighbors        

 public Hex(int x, int y)
 {
  this.neighbors = new HashSet<hex>();
  this.x = x;
  this.y = y;
 }

 public HashSet<hex> getNeighbors()
 {
  return this.neighbors;
 }

 public void addNeighbor(Hex hex)
 {
  this.neighbors.add(hex);
 }

 public int getX()
 {
  return this.x;
 }

 public int getY()
 {
  return this.y;
 }
}

Wow, the word "neighbor" really starts to look funny when you write it that many times. Anyway... Note that we also added 'get' methods for the coordinates, as we will need them later on.

Now that we have the possibility to keep track of the neighbors, we can modify the map generation algorithm to store the references. It is wise to do this neighbor referencing stuff right after the map generation, as it (in most cases) has to be done only once per map. Here's how we do it:

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)
 {
  // (Check part 1 for this)
 }

 // Set up the neighbor references
 for(Hex hex : map)
 {
  for(Hex other : map)
  {
   if(hex == other) continue;
   if(hex.getX() == other.getX())
   {
    if(hex.getY() == other.getY() - 1 ||
       hex.getY() == other.getY() + 1)
    {
     hex.addNeighbor(other);
    }
   }
   else if(hex.getY() == other.getY())
   {
    if(hex.getX() == other.getX() - 1 ||
       hex.getX() == other.getX() + 1)
    {
     hex.addNeighbor(other);
    }
   }
   else
   {
    if(hex.getX() % 2 == 0)
    {
     if(hex.getX() == other.getX() - 1 &&
        hex.getY() == other.getY() - 1)
     {
      hex.addNeighbor(other);
     }
     else if(hex.getX() == other.getX() + 1 &&
       hex.getY) == other.getY() - 1)
     {
      hex.addNeighbor(other);
     }
    }
    else
    {
     if(hex.getX() == other.getX() - 1 &&
        hex.getY() == other.getY() + 1)
     {
      hex.addNeighbor(other);
     }
     else if(hex.getX() == other.getX() + 1 &&
       hex.getY() == other.getY() + 1)
     {
      hex.addNeighbor(other);
     }
    }
   }
  }
 }
}


Phew! I know this isn't the most efficient (or the most clear, for that matter) way of doing this, but it gets the work done. Remember that if you are not doing "sides-up" layout, you have to swap X and Y coordinates in some cases. You could speed this up by doing other.addNeighbor(hex) as well and checking for existing neighbor situations before doing the jungle of 'if' checks, although it adds to the complexity as well.

Well, we managed to get through that, and now it's time for the actual area division!

Starting Areas and Neutral Areas

Okay, time to assign cells to players. First off, let's add 'owner' property to the Hex class:

private int owner = -1;

public int getOwner()
{
 return this.owner;
}

public void setOwner(int owner)
{
 this.owner = owner;
}

In this code, the 'owner' is just a number of the player. '0' is the first player, '1' is the second player and so on. '-1' means that the cell is not owned by anyone (e.g. it's neutral).

Let's start with a scenario that we want each player to have an equal amount of continuous area when the game starts, and the rest of the map is "neutral", that is, not assigned to anyone. This is rather simple to achieve: for each player, we choose a root cell (pretty much like we did in the drunkard walk method), and expand the area from that cell until we have the size we want.

// Generate a map (check the part 1!)
HashSet<Hex> map = drunkard(150, 50);

// Convert the set to an array
Hex[] mapArray = map.toArray(new Hex[map.size()]);

// Generate starting areas for each player
for(int i = 0; i < playerCount; ++i)
{
 // Select randomly until we have a hex with six neighbors
 Hex root = null;
 while(root == null)
 {
  int cellIndex = (int)(Math.random() * map.size());
  Hex tmp = mapArray[cellIndex];
  if(tmp.getNeighbors().size() == 6 &&
     tmp.getOwner() == -1)
  {
   // Check that the neighbors are neutral
   boolean suitable = true;
   for(Hex n : tmp.getNeighbors()
   {
    if(n.getOwner() != -1)
    {
     suitable = false;
     break;
    }
   }

   // Neighbors not neutral, pick a new root...
   if(!suitable) continue;
   
   // The root is suitable!
   root = tmp;
  }
 }

 // Now, 'root' is the center cell, we can set
 // the owners to 'root' and its neighbors
 root.setOwner(i);
 for(Hex neighbor : root.getNeighbors())
 {
  neighbor.setOwner(i);
 }
}

There we go, now we have a simple population method. Here's what the result looks like:

Simple map population with three players

The way the area should be expanded is pretty much up to you. If you want a nice, circular area, you add the root cell plus all the neighboring cells - although if you want to have seven cells per area, you must choose the root cell so that it has six neighbors, just like in the code exampla above. Another method could be to use the drunkard walk with suitable step value. This approach will produce (usually) non-uniform areas, if you wish to get that kind of areas.

Well, that's it for now. The next post will be about populating the map in a bit more difficult fashion. Stay tuned. :)





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