Как рекурсию переделать в итеративный метод.(Diamond-Square)

#c_sharp #алгоритм #unity3d #генерация_случайных_данных

Вот тут человек говорит:


  переделал все в итеративный метод, чтобы корректно считалось по слоям 


У меня такая-же ситуация есть методы, только не знаю как их вызывать послойно?
Я не могу зарегистрироваться на этом форуме, что бы спросить его.
Там же на форуме он кратко объясняет принцип работы алгоритма.


  Попытаюсь объяснить. Метод Square на вход получает два угла, левый нижний и правый
верхний и считает центральную точку заданного таким образом квадрата. Diamond принимает
на вход только координаты точки, которую надо посчитать (т.е. середины квадрата из
предыдущего шага) и половинную сторону этого квадрата, считает координаты четырех точек
справа, слева, сверху и снизу от принятой точки и также, как и в Square, усредняет
их и прибавляет случайное число, пропорциональное стороне. Если любая из координат
этих четырех точек выходит за границы карты, то он берет значение точки, лежащей с
другой стороны, т.е. как бы сворачивает плоскость. Метод DiamondSquare комбинирует
эти два метода, принимая те же параметры, что и Square. Сначала он вызывает Square
для входного квадрата, потом Diamond для всех четырех середин своих сторон, а потом
рекурсивно вызывает сам себя для четырех под-квадратов до тех пор, пока не посчитает
все пиксели. 


Сама рекурсивная функция:

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);
    }
}


Остальной код:

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 (R.x - l, R.y - l);
    float a = map [L.x, L.y];
    float b = map [L.x, R.y];
    float c = map [R.x, R.y];
    float d = map [R.x, L.y];
    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 (L.x, L.y + l),
        new Vec2int (R.x - l, R.y),
        new Vec2int (R.x, R.y - l),
        new Vec2int (L.x + l, L.y)
    };
}
public struct Vec2int
{
    public int x;
    public int y;
    public Vec2int(int x,int y){
        this.x=x;
        this.y=y;
    }
}


Так-же я был бы рад ссылкам на то что можно почитать в этом направлении.


  Важно заметить, что эти две высоты, которые достались нам на предыдущем шаге, должны
быть уже посчитаны — поэтому обсчет нужно вести «слоями», сначала для всех квадратов
выполнить шаг «square» — затем для всех ромбов выполнить шаг «diamond» — и перейти
к меньшим квадратам.


Из статьи на хабре.

В моём случае рекурсия уходит в глубь для левого нижнего квадрата и каждая его правая
и верхняя стороны неверно считается, и только после того как эта рекурсия заканчивается,
начитается следующая для правого верхнего, для которого тоже неверно считаются левая
и нижняя стороны.


Количество вызовов методов на первых 3 итерациях при разрешение картинки 64px 
1 x Square и Diamond
4 x Square и Diamond
16 x Square и Diamond
И для каждого метода нужно знать координаты.
    

Ответы

Ответ 1

Пару дней я только размышлял как решить мою проблему, начал смотреть в сторону yield,
изучал его(правда так практически ни чего о нем и не понял), сегодня принялся экспериментировать
с ним, и в это время пришла небольшая идея, которую я реализовал отказавшись от yield
в процессе. 
В общем проблема решена, картинка генерируется правильно и достаточно быстро, с настройкой
разрешения и шумности.
Вот такие картинки генерирует:


Сам код:

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().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 = new List();
        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 Generate(List input)
    {
        List next = new List();
        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.R.x - box.HalfLength, box.R.y - box.HalfLength);
        map[Center.x, Center.y] = (map[box.L.x, box.L.y] + map[box.L.x, box.R.y]
+ map[box.R.x, box.R.y] + map[box.R.x, box.L.y]) / 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.L.x, box.L.y + box.HalfLength),new Vec2int (box.R.x
- box.HalfLength, box.R.y)),
            new Box(new Vec2int (box.L.x+box.HalfLength, box.L.y),new Vec2int (box.R.x
, box.L.y+box.HalfLength))
        };
    }
    public void diamond(Box box)
    {
        float a, b, c, d;
        Vec2int Center = new Vec2int(box.L.x + box.HalfLength, box.R.y - 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 = R.x - L.x;
            HalfLength = Length / 2;
        }
    }
}



  Структура из Global
  public struct Vec2int
  {
     public int x;
     public int y;
     public Vec2int(int x, int y)
     {
        this.x = x;
        this.y = y;
     }
  }


Ответ 2

Смотрите.

Чтобы переделать (нехвостовую) рекурсию в итерацию, нужно использовать явную очередь
заданий.

Получаем структуру, реализующую одно задание:

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;
    }
}


Теперь в коде функции можно явно управлять заданиями:

public void diamondSquare(Vec2int L, Vec2int R, int l)
{
    Queue queue = new Queue();
    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));
        }
    }
}


При этом решении порядок выполнения заданий немного другой. Если нужно сохранить
и порядок, нужно превратить очередь в стек и класть задания в обратном порядке.

public void diamondSquare(Vec2int L, Vec2int R, int l)
{
    Stack stack = new Stack();
    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));
        }
    }
}