Вот тут человек говорит:
переделал все в итеративный метод, чтобы корректно считалось по слоям
У меня такая-же ситуация есть методы, только не знаю как их вызывать послойно?
Я не могу зарегистрироваться на этом форуме, что бы спросить его.
Там же на форуме он кратко объясняет принцип работы алгоритма.
Попытаюсь объяснить. Метод 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));
}
}
}
