How to convert a recursion into an iterative method. (Diamond-Square)

Question

Here the man says:

remade everything into an iterative method so that it was correctly counted by layers

I have the same situation, there are methods, but I do not know how to call them in layers?
I can not register on this forum to ask him.
There on the forum he briefly explains the principle of the algorithm.

I will try to explain.
The Square method receives two corners at the entrance, the lower left and the upper right, and considers the center point of the square thus defined.
Diamond accepts only the coordinates of the point to be counted (i.e. the midpoint of the square from the previous step) and the half side of this square, considers the coordinates of four points to the right, left, top and bottom of the accepted point and also, as in Square, averages them and adds a random number proportional to the side. If any of the coordinates of these four points goes beyond the boundaries of the map, then it takes the value of the point lying on the other side, i.e. as if collapses the plane.
The DiamondSquare method combines these two methods, taking the same parameters as Square. First, he calls Square for the input square, then Diamond for all four means of his sides, and then recursively calls himself for four sub-squares until he counts all the pixels.

The recursive function itself:

public void diamondSquare(Vec2int L, Vec2int R, int l) { if (l > 0) { Vec2int[] points = GetPoints(L, R, l); foreach (Vec2int elem in points) { diamond (elem, l); } square (L, new Vec2int (points [3].x, points [2].y), l); square (new Vec2int (points [3].x, points [2].y), R, l); square (points [0], points [1], l); square (points [3], points [2], l); diamondSquare (L, new Vec2int (points [3].x, points [2].y), l / 2); diamondSquare (new Vec2int (points [3].x, points [2].y), R, l / 2); diamondSquare (points [0], points [1], l / 2); diamondSquare (points [3], points [2], l / 2); } }

The rest of the code:

 public int size = 32; [Range(0,1f)] public float Roughnees = 0.5f; private float[,] map; public void square(Vec2int L, Vec2int R, int l) { Vec2int Center = new Vec2int (Rx - l, Ry - l); float a = map [Lx, Ly]; float b = map [Lx, Ry]; float c = map [Rx, Ry]; float d = map [Rx, Ly]; map [Center.x, Center.y] = (a + b + c + d) / 4 + Random.Range (-l / (size - 1) * (Roughnees), l / (size - 1) * (Roughnees)); } public void diamond(Vec2int point,int l) { float a, b, c, d; if (point.y - l >= 0) a = map [point.x, point.y - l]; else a = map[point.x, size - l]; if (point.x - l >= 0) b = map [point.x - l, point.y]; else b = map [size - l, point.y]; if (point.y + l < size) c = map [point.x, point.y + l]; else c = map [point.x, l]; if (point.x + l < size) d = map [point.x + l, point.y]; else d = map [l, point.y]; map [point.x, point.y] = (a + b + c + d) / 4 + Random.Range (-l / (size - 1) * Roughnees, l / (size - 1) * Roughnees); } public static Vec2int[] GetPoints(Vec2int L, Vec2int R, int l) { return new Vec2int[] { new Vec2int (Lx, Ly + l), new Vec2int (Rx - l, Ry), new Vec2int (Rx, Ry - l), new Vec2int (Lx + l, Ly) }; } public struct Vec2int { public int x; public int y; public Vec2int(int x,int y){ this.x=x; this.y=y; } }

So I would be glad to links to what you can read in this direction.

It is important to note that these two heights that we got in the previous step should already be calculated - so you need to calculate the “layers”, first perform the “square” step for all squares - then perform the “diamond” step for all diamonds - and go to smaller squares.

From an article on Habré.

In my case, the recursion goes deep into the left lower square and each of its right and upper sides is incorrectly considered, and only after this recursion ends, the next one starts for the right upper one, for which the left and lower sides are also incorrectly considered.

The number of method calls in the first 3 iterations with a picture resolution of 64px
1 x Square and Diamond
4 x Square and Diamond
16 x Square and Diamond
And for each method you need to know the coordinates.

It would be more correct if you move the code here, which needs to be redone into iterative
... moreover, unnecessary detailing will be thrown out of this code to the maximum.
I'll write as soon as I get to the computer :) There is a general method for such things.

CGLike CGLike 176 13 bronze marks · Accepted Answer · 2016-11-25T12:36:08

For a couple of days, I only thought about how to solve my problem, started looking towards yield, studied it (though I didn’t understand almost anything about it), today I started experimenting with it, and at that time I came up with a small idea that I gave up yield in the process.
In general, the problem is solved, the image is generated correctly and quickly enough, with the resolution and noise setting.
These are the images that generate:

The code itself:

 using System.Collections; using System.Collections.Generic; using Global; using UnityEngine; public class DiaSqu : MonoBehaviour { public int size; public float Roughnees = 0.5f; Material mat; float[,] map; Texture2D GeneratedTexture; void Awake() { size++; mat = gameObject.GetComponent<Renderer>().material; GeneratedTexture = new Texture2D(size, size); map = new float[size, size]; map[0, 0] = Random.Range(0.3f, 0.6f); map[0, size - 1] = Random.Range(0.3f, 0.6f); map[size - 1, size - 1] = Random.Range(0.3f, 0.6f); map[size - 1, 0] = Random.Range(0.3f, 0.6f); } void Start() { Vec2int Left = new Vec2int(0, 0); Vec2int Right = new Vec2int(size - 1, size - 1); List<Box[]> box = new List<Box[]>(); box.Add(new Box[] { new Box(Left, Right) }); for (int l = size; l > 0; l /= 2) //Генерация box = Generate(box); for (int i = 0; i < size; i++) //Запись в текстуру for (int j = 0; j < size; j++) GeneratedTexture.SetPixel(i, j, new Color(map[i, j], map[i, j], map[i, j], 0)); GeneratedTexture.filterMode = FilterMode.Trilinear; GeneratedTexture.Apply(); mat.mainTexture = GeneratedTexture; } public List<Box[]> Generate(List<Box[]> input) { List<Box[]> next = new List<Box[]>(); foreach (Box[] Arr in input) foreach (Box item in Arr) next.Add(Square(item)); foreach (Box[] Arr in input) foreach (Box item in Arr) diamond(item); return next; } public Box[] Square(Box box) { Vec2int Center = new Vec2int(box.Rx - box.HalfLength, box.Ry - box.HalfLength); map[Center.x, Center.y] = (map[box.Lx, box.Ly] + map[box.Lx, box.Ry] + map[box.Rx, box.Ry] + map[box.Rx, box.Ly]) / 4 + Random.Range(-box.Length * Roughnees / (size - 1), box.Length * Roughnees / (size - 1)); return new Box[]{ new Box(box.L,Center), new Box(Center,box.R), new Box(new Vec2int (box.Lx, box.Ly + box.HalfLength),new Vec2int (box.Rx - box.HalfLength, box.Ry)), new Box(new Vec2int (box.L.x+box.HalfLength, box.Ly),new Vec2int (box.Rx , box.L.y+box.HalfLength)) }; } public void diamond(Box box) { float a, b, c, d; Vec2int Center = new Vec2int(box.Lx + box.HalfLength, box.Ry - box.HalfLength); Vec2int[] points = new Vec2int[] { new Vec2int (Center.x-box.HalfLength,Center.y), //Left new Vec2int (Center.x,Center.y+box.HalfLength), //Top new Vec2int (Center.x+box.HalfLength,Center.y), //Right new Vec2int (Center.x,Center.y-box.HalfLength) //Bottom }; foreach (Vec2int point in points) { if (point.y - box.HalfLength >= 0) a = map[point.x, point.y - box.HalfLength]; else a = map[point.x, size - 1 - box.HalfLength]; if (point.x - box.HalfLength >= 0) b = map[point.x - box.HalfLength, point.y]; else b = map[size-1 - box.HalfLength, point.y]; if (point.y + box.HalfLength < size - 1) c = map[point.x, point.y + box.HalfLength]; else c = map[point.x, box.HalfLength]; if (point.x + box.HalfLength < size - 1) d = map[point.x + box.HalfLength, point.y]; else d = map[box.HalfLength, point.y]; map[point.x, point.y] = (a + b + c + d) / 4 + Random.Range(-box.Length * Roughnees / (size - 1), box.Length * Roughnees / (size - 1)); } } public struct Box { public Vec2int L; public Vec2int R; public int HalfLength; public int Length; public Box(Vec2int L, Vec2int R) { this.L = L; this.R = R; Length = Rx - Lx; HalfLength = Length / 2; } } }

Structure from Global
public struct Vec2int
{
public int x;
public int y;

public Vec2int (int x, int y)
{
this.x = x;
this.y = y;
}
}

Answer 2 · 2016-11-23T09:30:21

See it.

To redo (non-tail) recursion into iteration, you need to use an explicit job queue.

We get a structure that implements one task:

 struct RecTask { public Vec2int L, R; public int l; public RecTask(Vec2int L, Vec2int R, int l) { this.L = L; this.R = R; this.l = l; } }

Now in the function code, you can explicitly manage tasks:

 public void diamondSquare(Vec2int L, Vec2int R, int l) { Queue<RecTask> queue = new Queue<RecTask>(); queue.Enqueue(new RecTask(L, R, l)); while (queue.Count > 0) { var task = queue.Dequeue(); Vec2int[] points = GetPoints(task.L, task.R, task.l); foreach (Vec2int elem in points) { diamond(elem, task.l); } square(task.L, new Vec2int(points[3].x, points[2].y), task.l); square(new Vec2int(points[3].x, points[2].y), task.R, task.l); square(points[0], points[1], task.l); square(points[3], points[2], l); var newL = task.l/2; if (newL > 0) { queue.Enqueue(new RecTask(task.L, new Vec2int(points[3].x, points[2].y), newL)); queue.Enqueue(new RecTask(new Vec2int(points[3].x, points[2].y), task.R, newL)); queue.Enqueue(new RecTask(points[0], points[1], newL)); queue.Enqueue(new RecTask(points[3], points[2], newL)); } } }

With this decision, the order of execution of tasks is slightly different. If you want to keep and order, you need to turn the queue in the stack and put the job in the reverse order.

 public void diamondSquare(Vec2int L, Vec2int R, int l) { Stack<RecTask> stack = new Stack<RecTask>(); stack.Push(new RecTask(L, R, l)); while (stack.Count > 0) { var task = stack.Pop(); Vec2int[] points = GetPoints(L, R, l); foreach (Vec2int elem in points) { diamond(elem, l); } square(L, new Vec2int(points[3].x, points[2].y), l); square(new Vec2int(points[3].x, points[2].y), R, l); square(points[0], points[1], l); square(points[3], points[2], l); var newL = l/2; if (newL > 0) { stack.Push(new RecTask(points[3], points[2], newL)); stack.Push(new RecTask(points[0], points[1], newL)); stack.Push(new RecTask(new Vec2int(points[3].x, points[2].y), R, newL)); stack.Push(new RecTask(L, new Vec2int(points[3].x, points[2].y), newL)); } } }

Correct me if I'm wrong ... But this is - especially with the stack - essentially a direct emulation of recursion?
Usually recursion is translated into iteration (if I understand correctly) to speed up (remove the call) and reduce the load on the stack (if the recursion is very deep).
As I understand it, the performance here can be even less, only that the load on the stack is transferred to the dynamic memory ... ...
@Harry: Well, the performance of the idea should be no worse due to the fact that we allocate only the data, and not a full-fledged stack frame.
I now ran a little eyes, and I think the result will be the same as from my recursion.
I hope you understand how Diamond-Square works, in my version the problem is that already at 1 recursive call one or even two points that Diamond () refers to is determined in the next recursive call by the Square () function.
In general, if you write in the comments will be a lot and incomprehensible.
@CGLike: Well, yes, I did not change the meaning of the code, I just turned the recursive function into an iterative function.
The code does exactly the same thing as the recursive variant.

How to convert a recursion into an iterative method. (Diamond-Square)

2 answers 2

More articles: