Deform algorithms for dehexifying process

In my last post I talked about how to make hexagon map look less dull using dehexifying algorithm. I mentioned that we need to deform vertices but I did not give any examples how to do it. As you probably remember we need to do deformation in two steps, first for the hexagon vertices and later for segment vertices.

Deforming the hexagon vertices is pretty straightforward. We just move all the vertices by certain random amount. One thing to remember though, do not move any vertex more than half the width of the hexagon, and tag vertices that have already been deformed because same vertex can be referenced by several hexagons. Below is a very simple deformation algorithm implemented in Java.
[xscode etext=”Click to show example code” ctext=”Click to hide example code”]
// Vertex
class Vertex {
static Random R = new Random();

public float x;
public float y;
boolean deformed;

public void deform(float range) {
if (!deformed) {
deformed = true;
x += (R.nextFloat() – 0.5f) * range;
y += (R.nextFloat() – 0.5f) * range;
}
}
}

// Hexagon
class Hexagon {
List<Vertex> vertices;

public void deformVertices(int size) {
for (Vertex v in vertices) {
v.deform(size);
}
}
}
[/xscode]
Next I will show the simplest possible segment deformation algorithm. It is virtually same as Hexagon vertex deformation algorithm except for the range of deformation and how it is calculated. I have added Rules class to maintain creation variables. In example below we query segment deformation range from Rules class using method segmentVertexDeformRange() which takes number of vertices in the segment as parameter.

Using the number of vertices as damping factor we have better control of what the deformation result will look like. It is also good for preventing overflows in deformation which would result in silly looking hexagons.

In Hexagon class we just loop through every segment and call deformVertices() for each one. In Segment class deform() is called for each Vertex referenced by the segment.
[xscode etext=”Click to show example code” ctext=”Click to hide example code”]
// Hexagon
class Hexagon {
List<Segment> segments;

public void deformSegments() {
for (Segment s in segments) {
s.deformVertices(Rules.segmentVertexDeformRange(s.vertexCount()));
}
}
}

// Segment
class Segment {
List<Vertex> vertices;

public void deformVertices(float range) {
for (Vertex v in vertices) {
v.deform(range);
}
}
}
[/xscode]
In this naive solution borders can appear jagged. Jagginess can be controlled by tweaking the Rules, but what if we wanted smoothly curved borders? One possible solution would be the use of splines. Below is a sample implementation that uses Java 2D API for this task.
[xscode etext=”Click to show example code” ctext=”Click to hide example code”]
class Segment {
public void deformSplines(float range) {
deformVertices(range);
createSplineVertices(range);
}

void createSplineVertices() {
// Create path
Path2D.Float path = new Path2D.Float();
Vertex v = vertices[0];
path.moveTo(v.x, v.y);
for (int i = 1; i < vertices.size; i++) {
Vertex vold = v;
v = vertices[i];
Point2D.Float[] cps = randomControlPoints(vold, v);
path.curveTo(cps[0].x, cps[0].y, cps[1].x, cps[1].y, v.x, v,y);
}

// Collect new vertices from path
List<Vertex> cubicVertices = new ArrayList<Vertex>();
PathIterator pi = path.getPathIterator(null);
FlatteningPathIterator fi = new FlatteningPathIterator(pi, 0.1f);
while (!fi.isDone()) {
float[] p = new float[6];
fi.currentSegment(p);
cubicVertices.add(new Vertex(p[0], p[1]));
fi.next();
}

// Preserve reference starting and ending points
cubicVertices[0] = vertices[0];
cubicVertices[cubicVertices.size() – 1] = vertices[vertices.size() – 1];

// Apply new vertices
vertices = cubicVertices;
}

Point2D.Float[] randomControlPoints(Vertex b, Vertex e) {
Point2D.Float[] cps = new Point2D.Float[2];
float r = b.distanceFrom(e) / 2.0f;
float a = R.nextFloat() * PI_2;
cps[0].x = b.x + r * cos(a);
cps[0].y = b.y + r * sin(a);
a = R.nextFloat() * PI_2;
cps[1].x = e.x + r * cos(a);
cps[1].y = e.y + r * sin(a);
return cps;
}
}
[/xscode]
It is possible to mix naive and curved implementations to create even more realistic looking tiles. Just add random threshold point that will decide which implementation to use for the segment.
[xscode etext=”Click to show example code” ctext=”Click to hide example code”]
class Segment {
public void deformRandomly(float range) {
if (R.nextFloat() <= Rules.percentageOfCurvedSegments() / 100.0f) {
deformSplines(range);
} else {
deformVertices(range);
}
}
}
[/xscode]
We have seen that using deform algorithms it is possible to create realistic looking map tiles for hexagon maps. Deformation can be done in many ways and I have shown two different algorithms to do this. Next I would suggest you to experiment with different algorithms to generate even more realistic looking tiles.

Leave a Reply