Войти
ПрограммированиеФорумОбщее

Реализация алгоритма Diamond-Square

#0
15:46, 25 янв. 2015

Думаю многие слышали об этом алгоритме процедурной генерации чего либо, в моем случае карты высот. Пишу на C# + Unity3d. Никак не получается его реализовать, руководствовался этой статьей. Но получается как всегда:

+ Показать

Картинка, конечно, интересная, но абсолютно не в тему. Это уже моя третья попытка реализации этого алгоритма, до этого получались шумные картинки с черными полосами вокруг квадратов, замучился уже. Вот код:
+ Показать

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

Проверял перепроверял, ошибок в координатах сторон не нашел. Теперь уж и не знаю, что может быть не так. Подозрение падало на неправильные координаты смещения при выходе их за ноль в Diamond, но сколько я их не менял, ничего не поменялось. Может в генераторе случайных чисел проблема? Подозрительно, что так много точек просто ноль. Или все - таки надо точки в другом порядке считать?

На всякий случай, выводил в readable текстуру таким скриптом:

+ Показать


#1
18:48, 25 янв. 2015

из рабочего кода :

procedure DS_DiamondPass(i,j,w,h: integer;bits: TBitmap; range: integer);
var
  a,b,c,d,cl: byte;
  r: integer;
  w1,h1: integer;
  mpx,mpy: integer;
begin
{
Taking a square of four points, generate a random value at the square midpoint, where the two diagonals
meet. The midpoint value is calculated by averaging the four corner values, plus a random amount. This gives you a diamond
when you have multiple squares arranged in a grid.
}
  w1:=bits.Width;
  h1:=bits.Height;
  GetPixel(i,j,w1,h1,bits,a,a,a);
  GetPixel(i+w-1,j,w1,h1,bits,b,b,b);
  GetPixel(i,j+h-1,w1,h1,bits,c,c,c);
  GetPixel(i+w-1,j+h-1,w1,h1,bits,d,d,d);
  cl:=trunc((a+b+c+d)/4);
  r:=GetRandomSign*random(range);
  if not (((cl+r)<0) or ((cl+r)>255)) then
  cl:=cl+r;
  mpx:=(w div 2)+i;
  mpy:=(h div 2)+j;
  PutPixel(mpx,mpy,w1,h1,bits,cl,cl,cl);
end;

procedure DS_SquarePass(i,j,w,h: integer;bits: TBitmap; range: integer);
var
  w1,h1: integer;
  mpx,mpy: integer;
  a,b,cl: byte;
begin
{
Taking each diamond of four points, generate a random value at the corner of the diamond. Calculate the
midpoint value by averaging the corner values, plus a random amount generated in the same range as used for the diamond step.
This gives you squares again.
}
  w1:=bits.Width;
  h1:=bits.Height;
  mpx:=(w div 2)+i;
  mpy:=(h div 2)+j;

  GetPixel(i,j,w1,h1,bits,a,a,a);
  GetPixel(i+w-1,j,w1,h1,bits,b,b,b);
  //average...
  cl:=trunc((a+b)/2);
 // write to map
  PutPixel(mpx,j,w1,h1,bits,cl,cl,cl);

  ////////////////////////////////////////
  GetPixel(i,j+h-1,w1,h1,bits,a,a,a);
  GetPixel(i+w-1,j+h-1,w1,h1,bits,b,b,b);
  //average...
  cl:=trunc((a+b)/2);
  //write to map
  PutPixel(mpx,j+h-1,w1,h1,bits,cl,cl,cl);
  //////////////////////////////
  GetPixel(i,j,w1,h1,bits,a,a,a);
  GetPixel(i,j+h-1,w1,h1,bits,b,b,b);
  //average...
  cl:=trunc((a+b)/2);
  //write to map
  PutPixel(i,mpy,w1,h1,bits,cl,cl,cl);

  ////////////////////////////////////
  GetPixel(i+w-1,j,w1,h1,bits,a,a,a);
  GetPixel(i+w-1,j+h-1,w1,h1,bits,b,b,b);
  //average...
  cl:=trunc((a+b)/2);
  //write to map
  PutPixel(i+w-1,mpy,w1,h1,bits,cl,cl,cl);
end;

инициализация начального состояния и вызов:

    cl:=random(255);
    PutPixel(0,0,w,h,Buf,cl,cl,cl);
    cl:=random(255);
    PutPixel(w-1,0,w,h,Buf,cl,cl,cl);
    cl:=random(255);
    PutPixel(0,h-1,w,h,Buf,cl,cl,cl);
    cl:=random(255);
    PutPixel(w-1,h-1,w,h,Buf,cl,cl,cl);

      RndRange:=255;
      SubdivX:=trunc(log2(w-1));
      w1:=w;
      h1:=h;

      Rx:=1;
      for i:=1 to SubdivX do
      begin
        for j:=1 to Rx*Rx do
        begin
          PosX:=(j-1) mod Rx;
          PosY:=(j-1) div Rx;

          px:=PosX*w1;
          py:=PosY*h1;

          px:=px-posX;
          py:=py-PosY;
          randomize;
          DS_DiamondPass(px,py,w1,h1,buf,RndRange);
          randomize;
          DS_SquarePass(px,py,w1,h1,buf,RndRange);
        end;

        Rx:=Rx*2;
        RndRange:=RndRange div 2;
        w1:=(w1 div 2)+1;
        h1:=(h1 div 2)+1;
      end;

не забудь еще что картинка должна быть квадратной и со стороной 2^x + 1

вот результат:
diamond-square | Реализация алгоритма Diamond-Square

#2
1:08, 26 янв. 2015

Спасибо, правда, если честно, я почти ничего в коде не понял, но заставил все работать сам, это даже приятнее. Треугольники рисовались из-за одной банальной опечатки в координате, а красивую рекурсию пришлось убрать, т.к. с ней алгоритм не учитывает "послойность" просчета. Вот что получилось:
Изображение
Если кому надо, вот конечный код (вычисляет значения в разбросе от 0.0 до 1.0:

public static int size = 2049;
    public static float[,] heighmap = new float[size, size];
    public static float roughness = 2f;

    public static void Square(int lx, int ly, int rx, int ry)
    {
        int l = (rx - lx) / 2;

        float a = heighmap[lx, ly];              //  B--------C
        float b = heighmap[lx, ry];              //  |        |
        float c = heighmap[rx, ry];              //  |   ce   |
        float d = heighmap[rx, ly];              //  |        |
                                                 //  A--------D
        int cex = lx + l;
        int cey = ly + l;

        heighmap[cex, cey] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);
    }
    public static void Diamond(int tgx, int tgy, int l)
    {
        float a, b, c, d;

        if (tgy - l >= 0)
            a = heighmap[tgx, tgy - l];                        //      C--------
        else                                                   //      |        |
            a = heighmap[tgx, size - l];                       // B---t g----D  |
                                                               //      |        |
                                                               //      A--------
        if (tgx - l >= 0)
            b = heighmap[tgx - l, tgy];
        else
            b = heighmap[size - l, tgy];


        if (tgy + l <= size - 1)
            c = heighmap[tgx, tgy + l];
        else
            c = heighmap[tgx, l];


        if (tgx + l <= size - 1)
            d = heighmap[tgx + l, tgy];
        else
            d = heighmap[l, tgy];
   
        heighmap[tgx, tgy] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);

    }
    public static void DiamondSquare(int lx, int ly, int rx, int ry)
    {
        int l = (rx - lx) / 2;
        if (l > 0)
        {
            Square(lx, ly, rx, ry);

            Diamond(lx, ly + l, l);
            Diamond(rx, ry - l, l);
            Diamond(rx - l, ry, l);
            Diamond(lx + l, ly, l);
        }
    }

    public static void MidPointDisplacement(int lx, int ly, int rx, int ry)
    {
        int l = (rx - lx) / 2;
        if (l > 0)
        {
            float a = heighmap[lx, ly];              //  B--------C
            float b = heighmap[lx, ry];              //  |        |
            float c = heighmap[rx, ry];              //  |   ce   |
            float d = heighmap[rx, ly];              //  |        |
            //  A--------D
            int cex = lx + l;
            int cey = ly + l;

            heighmap[cex, cey] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);

            heighmap[lx, cey] = (a + b) / 2 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);
            heighmap[rx, cey] = (c + d) / 2 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);
            heighmap[cex, ly] = (a + d) / 2 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);
            heighmap[cex, ry] = (b + c) / 2 + Random.Range(-l * 2 * roughness / size, l * 2 * roughness / size);

            MidPointDisplacement(lx, ly, cex, cey);
            MidPointDisplacement(lx, ly + l, lx + l, ry);
            MidPointDisplacement(cex, cey, rx, ry);
            MidPointDisplacement(lx + l, ly, rx, cey);
        }
    }

    public static void Generate()
    {
        heighmap[0, 0] = Random.Range(0.3f, 0.6f);
        heighmap[size - 1, 0] = Random.Range(0.3f, 0.6f);
        heighmap[size - 1, size - 1] = Random.Range(0.3f, 0.6f);
        heighmap[0, size - 1] = Random.Range(0.3f, 0.6f);

        for (int l = (size - 1) / 2; l > 0; l /= 2)
            for (int x = 0; x < size - 1; x += l)
                for (int y = 0; y < size - 1; y += l)
                    DiamondSquare(x, y, x + l, y + l);

    }
*MidpointDisplacement в качестве бонуса.

ПрограммированиеФорумОбщее

Тема в архиве.