### Marching Squares with distance functions

Development on the “worms” project (blog 1, blog 2) has been going somewhat slowly, but today I have implemented a few key features I have been wanting to. At the point of my previous blog regarding this project, I had implemented marching squares and a player controller, the marching squares worked off of noise generation which was just a random number in each grid tile for the map data. Currently it works with distance functions for a controlled generation.

I began working on the distance functions last week with a circle being generated in the world with the algorithm:

``` float Circle (Vector2 circlePos, Vector2 pointPos, float r)
{
return (pointPos - circlePos).magnitude - r;
}```

This gave me the distance to the surface of the circle:

As you can see, the edges are rather… blocky. The reason behind this was the fact that I was just checking if grid space had a value less than 0, which meant that it looks the same as something made out of squares. To fix this, when I generated the vertices, I shifted them along the x and y axes depending on the value in their corresponding grid space and if any surrounding values were above 0:

``` void AdjustPosition(ref Vector3 orig, int x, int y)
{
//the offset that the vertice will have
Vector3 relative = new Vector3();
for (int xx = -1; xx <= 1; xx += 2)
{
for (int yy = -1; yy <= 1; yy += 2)
{
if (CoordWithinWorld(x + xx, y + yy))
{
if(world[x + xx][y + yy] >= 0)
{
//add to the offset
relative.x += xx * world[x + xx][y + yy];
relative.y += yy * world[x + xx][y + yy];
}
}
}
}

//shift the original by the offset
orig -= relative;
}```

The mesh generated is much more curved, but there are some problems with it, these of which I believe are created from the exclusion of the diagonal vertice adjustment (it only adjusts for the above, below, left, and right immediate grid spaces). While I was doing this, I found a funky outcome when I accidentally added the relative vector to the orig vector in the AdjustPosition method:

It was entertaining to me to see this, something I though you might have wanted to see as well.

I wanted to be able to generate multiple shapes in the mesh, something that would allow for a terrain of multiple shapes to be created, so I started with generating multiple circles. For doing the multiple circles, I decided to make a new class called ShapeData that has 1 variable and 1 method:

``` public abstract class ShapeData
{
public Vector3 position;

public abstract float Shape(Vector3 checkPos);
}```

The reason I made the class abstract was so I can never have an instance of this, I would need an instance of a child class, which would override the Shape method. The child class is:

``` public class CircleShape : ShapeData
{

public override float Shape(Vector3 checkPos)
{
return (checkPos - position).magnitude - radius;
}
}```

This holds all the information a circle should hold: a radius and position (in the parent class). The distance function of this is the same as the one created by Inigo Quilez for raymarching (Quilez).

Using an array of ShapeData, I put in CircleShapes and parse it into the GenerateWorldData method and have the grid value equal the smallest of the distances generated from the distance functions:

Shape generation:

``` ShapeData[] GenerateInitialShapeData()
{
ShapeData[] shapes = new ShapeData[5];

float positionScale = 2.0f;

//generate 5 circles in the shape of the olympic rings for testing
CircleShape circle1 = new CircleShape();
circle1.position = Vector3.left * positionScale * radius - Vector3.up * positionScale * 0.5f * radius;

CircleShape circle2 = new CircleShape();
circle2.position = Vector3.left * positionScale * 0.5f * radius + Vector3.up * positionScale * 0.5f * radius;

CircleShape circle3 = new CircleShape();
circle3.position = Vector3.zero - Vector3.up * positionScale * 0.5f * radius;

CircleShape circle4 = new CircleShape();
circle4.position = Vector3.right * 0.5f * positionScale * radius + Vector3.up * 0.5f * positionScale * radius;

CircleShape circle5 = new CircleShape();
circle5.position = Vector3.right * positionScale * radius - Vector3.up * positionScale * 0.5f * radius;

shapes[0] = circle1;
shapes[1] = circle2;
shapes[2] = circle3;
shapes[3] = circle4;
shapes[4] = circle5;

return shapes;
}```

Within a nested for-loop for assigning the grid values

``` newPoint = ScaleToWorldCoordinates(x, y);

//go through all of the shapes and get the distance to their surface
world[x][y] = shapeData[0].Shape(newPoint);

for (int i = 1; i < shapeData.Length; ++i)
{
world[x][y] = Mathf.Min(shapeData[i].Shape(newPoint), world[x][y]);
}```

Mesh:

Now that I have this, I want to add in another unique shape, a rectangle. The rectangle is a little different, I won’t be able to use the same distance function that Inigo has on his website for the 3D version of a box(plus I have no idea what freaky Maths he is doing), so I’ll have to do it myself. I want to be able to stretch the rectangle to whatever size I want as well as rotate it, so after a bit of fiddling around, I was able to get:

``` public class RectangleShape : ShapeData
{
public float rotation;

public Vector3 size;

public override float Shape(Vector3 checkPos)
{
//get where the position we are checking against is in local space
Vector3 relative = checkPos - position;

//rotate the rectangle by rotating the relative position we are checking
relative = new Vector3(
Mathf.Cos(rotation) * relative.x - Mathf.Sin(rotation) * relative.y,
Mathf.Sin(rotation) * relative.x + Mathf.Cos(rotation) * relative.y,
0);

//make the relative positive in both axes being used
relative.x = Mathf.Abs(relative.x);
relative.y = Mathf.Abs(relative.y);

relative -= size / 2.0f;

return Mathf.Max(relative.x, relative.y);
}
}```

Adding a rectangle to the mesh looked like:

``` RectangleShape rect = new RectangleShape();
rect.position = Vector3.zero;
rect.rotation = Mathf.PI * 0.125f;
rect.size = Vector3.one * radius + Vector3.right * 5.0f;

shapes[5] = rect;```

Which is exactly what I wanted. I had a few problems through this addition, but was able to get a rough result of what the end will be like. I am also able to distort the objects, which looks like:

That was a little fun to play around with, but all it is is just (in the Shape method for RectangleShape):

```float percentageAlong = relative.x / size.x + 0.5f;

relative.y += Mathf.Sin(Mathf.PI * 9 * percentageAlong) - 5 * Mathf.Sin(Mathf.PI * percentageAlong);```

A problem with the mesh generation I am currently doing is that the mesh is extremely high poly:

A problem with this is that performance will be lowered due to the number of faces being drawn and the size I am allowed to make the maps at will be affected. The above image shows a mesh created within the world of 400×400 grid spaces which has 36,030 vertices. The mesh has a bit over half of the maximum allowed vertices in a mesh, the maximum being 65,536 vertices, something 400×400 is greatly above (400×400 = 160,000). To overcome this, I’ll need to use an ear-clipping algorithm (Eberly 1) that I mentioned I wouldn’t be able to use due to the way ear-clipping works, but I can work around it by using an altered version that I’ll create later.

## References

Eberly, David. Triangulation By Ear Clipping. 1st ed. Geometric Tools, LLC, 2016. Web. 1 Aug. 2016.

Quilez, Inigo. “Inigo Quilez :: Fractals, Computer Graphics, Mathematics, Demoscene And More”.Iquilezles.org. N.p., 2016. Web. 1 Aug. 2016.