Fixed a couple of bugs which was keeping the generation from truly finishing which makes increasing the frequency of the branches more feasible. I tweaked the previous generation to increase how often it branched as it approaches the centre. It's still way to messy and chaotic to be a workable solution but for something so basic and naive it actually does better than I expected.
Refining Terrain
Tweaking values - went a little high on the mountain frequency.
Refining it down. Kind of fun to jump around right until you fall to the bottom ;)
That's more like it!
The 9th iteration of the Sierpinski triangle.
An Evening of Code: Sierpinski Triangle
An extension of yesterday's work with L-Systems. The Sierpinski Triangle.
Firstly, I updated the implementation to draw the shape over a number of frames. This is not the end goal of this work so I'm doing it in Unity by drawing to a texture which is easy to implement but far from the most efficient ;) In this case it was best to limit the texture size to 512x512 to avoid a severe performance hit when redrawing the texture. If I needed to, I could simulate a larger texture by mapping it to multiple smaller ones but that's out of scope for the moment.
Next I updated the rules implementation to support multiple rules. Previously I used a single string and a regular expression. This no longer worked because the rules have to be applied simultaneously. Instead, I used a Dictionary to store the rules and, since the rules I need at the moment are only applied to a single character I could simply enumerate the axiom and use the character as the key to the dictionary. If there's a match I append the rule to a new string. If not I append the character.
There is one additional change that is not described in the notation - after each iteration the angle gets flipped so that it goes from 60 to -60, and back again. This is required to keep the triangle facing the same way at each iteration.
A= Step forward
B = Step forward
+ = +60 degrees
- = -60 degrees
A → B-A-B
B → A+B+A
Axiom: A
After 9 iterations the string has gone from 1 to 39,365 characters.
string Iterate(string axiom) { string newAxiom = ""; foreach (char c in axiom) { string ch = c.ToString(); string replace = null; rules.TryGetValue(ch, out replace); if (replace != null) { newAxiom += replace; } else { newAxiom += ch; } } angle = -angle; Debug.Log ("Axiom Length: " + newAxiom.Length); return newAxiom; } void FixedUpdate() { int length = axiom.Length; for (int i = 0; i < 200; i++) { if (index < axiom.Length) { char c = axiom[index]; if (c == 'F' || c == 'A' || c == 'B') { Vector2 newPoint = NewPoint(currentPoint, stepLength, angle); DrawLine (new Line(currentPoint, newPoint), colors[colIndex % 3]); colIndex++; currentPoint = newPoint; } else if (c == '-') { angle -= angleStep; } else if (c == '+') { angle += angleStep; } index++; } } texture2D.Apply(); }
An Evening of Code: Koch Snowflake
The Koch Snowflake is the one of the first, and simplest, of the fractals.
Starting with an equilateral triangle:
- Start at the first line and remove it.
- Set the step length by dividing the line length by 3.
- Set the angle to that of the line.
- Step forward.
- Rotate 60 degrees left.
- Step forward.
- Rotate 120 degrees right.
- Step forward.
- Rotate 60 degrees left.
- Step forward.
In total, we've added four new lines and increased the total length of the shape by 1/3. Repeat for the remaining lines and we have completed an iteration. Starting again on the new shape we can repeat the same steps for each of the new lines. As can be seen from the above animation, which only iterates 5 times, the complexity rapidly increases.
Technically this is not actually a Koch Snowflake as that is the shape we approach as we iterate. However, we would need to iterate an infinite number of times to generate a true Snowflake.
Iterating on a single line generates a Koch Curve. The Snowflake, starting from a triangle, is made of three curves.
The Koch Curve can be described by a Lindenmayer (L-) System. This is where we create a string and, each iteration, run a set of rules to replace characters in the string with others. Each character defines a drawing rule which we can follow to draw the shape after the iterations have completed.
F = Step Forward
+ = Rotate 60 degrees right
- = Rotate 60 degrees left
Rules
F → F-F++F-F
Starting with: F++F++F++
Our drawing instructions give us our starting triangle. Iterating, we increase the size of the string and generate more rules. Following them generate the animation above.
float stepLength = 256; string rule = "F-F++F-F"; Vector2 start = new Vector2(128, 128); protected override void Draw () { string axiom = "F++F++F++"; for (int i = 0; i < 5; i++) { axiom = Iterate(axiom); } int index = 0; Color[] colors = new Color[3]{Color.black, Color.red, Color.blue}; int length = axiom.Length; Vector2 currentPoint = start; float angle = 0; int colIndex = 0; while(index < axiom.Length) { char c = axiom[index]; if (c == 'F') { Vector2 newPoint = NewPoint(currentPoint, stepLength, angle); DrawLine (new Line(currentPoint, newPoint), colors[colIndex % 3]); colIndex++; currentPoint = newPoint; } else if (c == '-') { angle -= 60; } else if (c == '+') { angle += 60; } index++; } } string Iterate(string axiom) { Regex regex = new Regex("F"); stepLength /= 3; return regex.Replace(axiom, rule); } Vector2 NewPoint(Vector2 point, float step, float angle) { float radAngle = angle * Mathf.Deg2Rad; float x1 = (point.x + (step * Mathf.Cos(radAngle))); float y1 = (point.y + (step * Mathf.Sin(radAngle))); return new Vector2(x1, y1); }
Try modifying the above to generate new shapes. For example, replacing the '+' with '-' symbols in the starting axiom will create the equilateral triangle facing in the other direction and which starts a different pattern which will never exceed the bounds of the initial equilateral triangle.
An Evening of Code: Drawing a Line
Not hugely exciting but I did also spend a little time cleaning up an old project. Didn't end up doing as much as I thought was needed so instead I started looking at ways to start learning L-systems. To begin, I'll need a way to get them on the screen. For the first go I figured being able to draw lines to a texture would be sufficient. This is a quick and dirty implementation of Bresenham's line algorithm. I don't need it to be fast so substituted floats for the bit shifting just to make it easy. Nothing to be proud of here but it does get me what I need for tonight.
public void DrawLine(int x0, int y0, int x1, int y1, Color color) { int dy = y1 - y0; int dx = x1 - x0; float error = 0; float deltaError = 0; if (dx != 0 && dy != 0) { deltaError = Mathf.Abs((float)dy / (float)dx); } int y = y0; int x = x0; for (int i = 0; i < Mathf.Abs(dx); i++) { texture2D.SetPixel(x, y, color); error = error + deltaError; while (error >= 0.5f) { texture2D.SetPixel (x, y, color); y += Mathf.RoundToInt(Mathf.Sign(dy)); error = error - 1.0f; } x += Mathf.RoundToInt(Mathf.Sign(dx)); } }
LinkDump: L-Systems
http://en.wikipedia.org/wiki/L-system
http://algorithmicbotany.org/papers/abop/abop-ch1.pdf
https://graphics.ethz.ch/Downloads/Publications/Papers/2001/p_Par01.pdf
http://www.citygen.net/files/citygen_gdtw07.pdf
For later follow up. I've got some other things to check offline as well. I'll put up a more thorough post when I've had chance to look through them some more.
An Evening of Code: Simplex Noise and Mesh Building
On advice from the tutorials out there I've moved to using Simplex noise. It also now creates two layers of noise so that we can have dirt on top of the stone.
Probably the biggest single change is that chunks now generate a mesh, rather than instantiating a cube for each voxel. This is (unsurprisingly) a lot faster and actually allows me to have stacks of blocks.
Creating a mesh in Unity is pretty straightforward. Specify four Vector3s and define as two triangles to form a square face. Use 6 square faces to form a cube.
// Top Face
Vector3[] vertices = new Vector3[4];
vertices[0] = new Vector3 (x, y, z + 1);
vertices[1] = new Vector3 (x + 1, y, z + 1);
vertices[2] = new Vector3 (x + 1, y, z );
vertices[3] new Vector3 (x, y, z );
// Triangles
int[] triangles = new int[6]; // Two triangles, 3 points each, 2 verts are shared
triangles[0] = 0;
triangles[1] = 1;
triangles[2] = 2;
triangles[3] = 0;
triangles[4] = 2;
triangles[5] = 3;
mesh.Clear();
mesh.vertices = vertices;
mesh.triangles = triangles;
mesh.Optimize();
mesh.RecalculateNormals();
col.sharedMesh = mesh; // Use render mesh for collisionsA simple optimisation then is to check if there is another cube adjacent. Since there is no gap we don't need to include the face on that side.
Lastly, track the block type and assign the appropriate texture.
It's lacking a lot of features that would make it a game. I might look into some basic changes like supporting just because it's straightforward. Really though, this was to serve as a refresher in how to think about 3D and procedural content. In that, it's served its purpose.