forum.boolean.name - Генерация террайнов

Страница 1 из 2

Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Генерация террайнов (http://forum.boolean.name/showthread.php?t=15011)

Lestar

28.06.2011 06:33

Генерация террайнов

Столкнулся с необходимостью генерации реалистичных террайнов.Из чего то вменяемого по алгоритмике нашел :
http://habrahabr.ru/blogs/algorithm/111538/
Немного здесь:
http://www.metalgear.ru/ru/content/a...eneratsii-kart
И здесь:
http://pcg.wikidot.com/pcg-algorithm:map-generation

У кого был опыт разработки генераторов,поделитесь о подводных камнях и предпочитаемых алгоритмах.Задача-получить как можно более реалистичный террайн с лесными массивами.Размеры террайнов 12х12км. Озера,болота,небольшие ручьи,реки.

Lestar

28.06.2011 15:08

Ответ: Генерация террайнов

Немного реализаций http://sourceforge.net/search/?q=terrain+generator

Lestar

30.06.2011 15:34

Ответ: Генерация террайнов

Продолжаю свой монолог.
Очень подробно рассмотрен вопрос генерации террайнов http://oddlabs.com/download/terrain_generation.pdf
Рассматриваем вопросы водной эрозии http://www-evasion.imag.fr/Publications/2007/MDH07/

moka	30.06.2011 16:30

Ответ: Генерация террайнов

Имхо, корозия ликвидного поведения единицами один из самых реалистичных подходов к генерации ландшафта.
Одна часть - это сгенерировать вершинную карту. Другая часть, это корректно распределить горные породы, от земли, песка и т.п. И далее рассадить растительность, основываясь законам, с которой она распростроняется..

Randomize

02.07.2011 18:39

Ответ: Генерация террайнов

Мой простенький генератор карты высот на базе diamondsquare (blitzmax):

Код:

Type THMapGenerator

        Field gRoughness:Float

        Field gBigSize:Float

        

        Method Generate:Float[,] (iWidth:Int, iHeight:Int, iRoughness:Float)

                SeedRnd(0) 

                Local c1:Float, c2:Float, c3:Float, c4:Float

                Local points:Float[,] = New Float[iWidth + 1, iHeight + 1]



                'Assign the four corners of the intial grid random color values

                'These will end up being the colors of the four corners

                c1 = Rnd()

                c2 = Rnd()

                c3 = Rnd()

                c4 = Rnd()

                

                gRoughness = iRoughness

                gBigSize = iWidth + iHeight

                

                DivideGrid(points, 0, 0, iWidth, iHeight, c1, c2, c3, c4)

                

                Return points

        EndMethod

        

        Method DivideGrid(points:Float[,] Var, x:Float, y:Float, width:Int, height:Int, c1:Float, c2:Float, c3:Float, c4:Float)



                Local Edge1:Float, Edge2:Float, Edge3:Float, Edge4:Float, Middle:Float

                

                Local newWidth:Int = Floor(width / 2)

                Local newHeight:Int = Floor(height / 2)



                If (width > 1 Or height > 1)

  

                        Middle = ((c1 + c2 + c3 + c4) / 4) + Displace(newWidth + newHeight) 'Randomly displace the midpoint!

                        Edge1 = ((c1 + c2) / 2)        'Calculate the edges by averaging the two corners of each edge.

                        Edge2 = ((c2 + c3) / 2) 

                        Edge3 = ((c3 + c4) / 2) 

                        Edge4 = ((c4 + c1) / 2) '

                        'Make sure that the midpoint doesn't accidentally "randomly displaced" past the boundaries!

                        Middle = Rectify(Middle) 

                        Edge1 = Rectify(Edge1) 

                        Edge2 = Rectify(Edge2) 

                        Edge3 = Rectify(Edge3) 

                        Edge4 = Rectify(Edge4) 

                        'Do the operation over again for each of the four new grids.

                        DivideGrid(points, x, y, newWidth, newHeight, c1, Edge1, Middle, Edge4) 

                        DivideGrid(points, x + newWidth, y, width - newWidth, newHeight, Edge1, c2, Edge2, Middle) 

                        DivideGrid(points, x + newWidth, y + newHeight, width - newWidth, height - newHeight, Middle, Edge2, c3, Edge3) 

                        DivideGrid(points, x, y + newHeight, newWidth, height - newHeight, Edge4, Middle, Edge3, c4) 



                Else        'This is the "base case," where each grid piece is less than the size of a pixel.

 

                        'The four corners of the grid piece will be averaged and drawn as a single pixel.

                        Local c:Float = (c1 + c2 + c3 + c4) / 4



                        points[Int(x), Int(y)] = c

                

                        If (width = 2) Then

                                points[Int (x + 1), Int (y)] = c

                        EndIf

                

                        If (height = 2) Then

                

                                points[Int(x), Int (y + 1)] = c

                        EndIf

                        If ((width = 2) And (height = 2)) Then

                

                                points[Int(x + 1), Int(y + 1)] = c

                        EndIf

                EndIf

        EndMethod

                

        Method Rectify:Float(iNum:Float)

                If (iNum < 0)

                        iNum = 0

                ElseIf (iNum > 1.0)

                        iNum = 1.0

                EndIf

                Return iNum

        EndMethod



        Method Displace:Float(SmallSize:Float)

                Local _Max:Float = SmallSize / gBigSize * gRoughness

                Return (Rnd() - 0.5) * _Max

        EndMethod

EndType

Lestar

02.07.2011 19:39

Ответ: Генерация террайнов

Шум Перлина на C#. http://lotsacode.wordpress.com/2010/...in-noise-in-c/ .Пока за основу взял его,буду пробовать еще через пару фильтров пропускать,в качестве экспериментов с хайт мапами.Ну и в сторону водной коррозии не ровно дышу.
Кстати в сторону Minecraft.Я доподлинно не знаю так реализовано или нет,но при расширении ландшафта и генерации новых чанков(когда пользователь расширяет территорию)в алгоритм генерации в качестве соли я бы использовал ник игрока,расширяющего территорию.Так бы мы получили неоднозначность территории.В которой было бы все.И висячие сады и равнины и горы.

dsd	10.09.2011 23:13

Ответ: Генерация террайнов

Мой простенький генератор карты высот на базе diamondsquare (с++ & xors3d):

Код:

void xSeedRnd(int seed){

    srand(seed);

}



double xRnd(double min, double max){

    double length=max-min;

    double var =((double) rand() / (double)RAND_MAX);

    double value=min+var*length;

return value;

}



int ARGB (int a,int r,int b, int g){

int color=(a<<24)+(r<<16)+(b<<8)+g;

return color;

}



Handle Map_Generator(int size, double sharp){

xSeedRnd(xMillisecs());

//создается массив для значений



double *m0[size+1];

for(int i=0;i<=size;i++){

    m0[i]= new double[size];

}

for(int i=0;i<=size;i++){

    for(int j=0;j<=size;j++){

        m0[i][j]=0;

        }

    }

//заполнение краев случайными числами (1;5)

m0[0][0]=xRnd(-5,5);

m0[size][0]=xRnd(-5,5);

m0[0][size]=xRnd(-5,5);

m0[size][size]=xRnd(-5,5);

//определяю степень size

int m=size;

int repetitions=0;

while(m!=1){

repetitions++;

m=size>>repetitions;

}

repetitions--;



int step=size>>1;

while(step>0){

    //первая строка

    for(int i=step;i<=size-step;i=i+step){

        for(int j=step;j<=size-step;j=j+step){



        double val00=m0[i-step][j-step];

        double val01=m0[i-step][j+step];

        double val10=m0[i+step][j-step];

        double val11=m0[i+step][j+step];



        if(m0[i][j]==0 && val00!=0 && val01!=0 && val10!=0 && val11!=0){m0[i][j]=0.25*(val00+val01+val10+val11)+step*xRnd(-sharp,sharp);}

        if(m0[i-step][j]==0 && val00!=0 && val01!=0){m0[i-step][j]=0.5*(val00+val01)+0.5*step*xRnd(-sharp,sharp);}

        if(m0[i+step][j]==0 && val10!=0 && val11!=0){m0[i+step][j]=0.5*(val10+val11)+0.5*step*xRnd(-sharp,sharp);}

        if(m0[i][j-step]==0 && val00!=0 && val10!=0){m0[i][j-step]=0.5*(val00+val10)+0.5*step*xRnd(-sharp,sharp);}

        if(m0[i][j+step]==0 && val01!=0 && val11!=0){m0[i][j+step]=0.5*(val01+val11)+0.5*step*xRnd(-sharp,sharp);}

        }

    }

step=step>>1;

}

//приведение значений в массиве в интервал (0;1)

double max=0;

double min=0;

for (int i=0;i<=size;i++){

    for (int j=0;j<=size;j++){

        if(m0[i][j]>=max){max=m0 [i][j];}

        if(m0[i][j]<=min){min=m0 [i][j];}

    }

}



double length=max-min;

for (int i=0;i<=size;i++){

    for (int j=0;j<=size;j++){

        m0[i][j]=(m0 [i][j]-min)/length;

    }

}

//*************************************

//дальше вывод значений

Handle tex=xCreateTexture(size,size);

xSetBuffer(xTextureBuffer(tex));

xLockBuffer(xTextureBuffer(tex));

for (int i=0;i<size;i++){

    for (int j=0;j<size;j++){

        int color=255*m0 [i][j];

        xWritePixelFast(i,j,ARGB(255,color,color,color),xTextureBuffer(tex));

    }

}

xSetBuffer(xBackBuffer());

xUnlockBuffer(xTextureBuffer(tex));



return tex;

}

dsd	10.01.2012 22:33

Ответ: Генерация террайнов

Я категорически настаиваю на закреплении этой темы в важном из-за ссылок в первых постах.

Код:

void Perlin(int size, int grain){



srand(grain);

int resolution=1<<size;

//создание структуры данных

float **m1[size];

for(int i=0;i<size;i++){

m1[i]=new float*[resolution];

for(int j=0;j<resolution;j++){m1[i][j]=new float[resolution];}}

//обнуление

for(int i=0;i<size;i++){for(int j=0;j<resolution;j++){for(int k=0;k<resolution;k++){m1[i][j][k]=0;}}}

//создание исходного шума

float length=0;

for(int i=0;i<size;i++){

    int width=1<<(i+1);

        //kof  коэффициент веса октавы

        float detsize=2.0f;

        float kof=(size-i);

        if(i==0){kof=detsize*16;}

        if(i==1){kof=detsize*32;}

        if(i==2){kof=detsize*64;}

        if(i==3){kof=detsize*64;}

        if(i==4){kof=detsize*4;}

        if(i==5){kof=detsize*8;}

        if(i>5){kof=detsize*4;}



        for(int j=0;j<width;j++){for(int k=0;k<width;k++){m1[i][j<<(size-i-1)][k<<(size-i-1)]=kof*(1-2*(float)rand()/(float)RAND_MAX);}}

        //cуммируется вес октав это будет максимально возможный перепад высот

        length=length+kof;}

//что бы коегде заменить все деления умножением

    float len=(0.5/length);

//тут градиентный шум считается

for(int k=0;k<size-1;k++){

int step=resolution>>1;

while(step>0){

    for(int i=step;i<resolution-step;i=i+2*step){

        for(int j=step;j<resolution-step;j=j+2*step){

        //данные в углах текущей клетки

        float val00=m1[k][i-step][j-step];

        float val01=m1[k][i-step][j+step];

        float val10=m1[k][i+step][j-step];

        float val11=m1[k][i+step][j+step];

        //если текущая клетка пуста, то пишется в клетку крест значений

        if(m1[k][i][j]==0){

        m1[k][i][j]=0.25*(val00+val01+val10+val11);

        m1[k][i-step][j]=0.5*(val00+val01);

        m1[k][i+step][j]=0.5*(val10+val11);

        m1[k][i][j-step]=0.5*(val00+val10);

        m1[k][i][j+step]=0.5*(val01+val11);}

    }}

step=step>>1;}}



//суммирование в последний массив

for(int i=0;i<resolution;i++){for(int j=0;j<resolution;j++){for(int k=0;k<size-1;k++){m1[size-1][i][j]=m1[size-1][i][j]+m1[k][i][j];}}}

Лit}{Ъ

30.09.2013 08:25

Ответ: Генерация террайнов

Вторая ссылка умерла безвременно... И да, тема - шикарна.

scorey

09.03.2015 22:01

Ответ: Генерация террайнов

А как можно сделать отложенную генерацию карт высот? Например у нас есть сгенерированная карта высот 1000x1000. На основе этой карты сделан террайн. Игрок например идет к левому краю террайна, и рядом с нашим террайном генерируется новый (На основе карт высот, но при этом чтобы он был как бы "продолжением" первой карты. То есть если у нас на границе первого террайна есть пол - горы, чтобы при генерации эта же гора плавно спускалась уже на втором террайне

RegIon

09.03.2015 22:06

Ответ: Генерация террайнов

Цитата:

Сообщение от scorey (Сообщение 293967)

БООЛЬШАЯ карта высот, а терейн генерируется из кусочка карты - это самый примитивный способ, карта высот типо тайлсета терейнов, хотя можно просто усреднить края различных карт высот на некоторое расстояние по гаусу например (чем ближе к краю, тем сильнее усреднение^2), что бы переход был плавный.

scorey

09.03.2015 22:09

Ответ: Генерация террайнов

Цитата:

Сообщение от RegIon (Сообщение 293968)

БООЛЬШАЯ карта высот, а терейн генерируется из кусочка карты - это самый примитивный способ, карта высот типо тайлсета терейнов

Я примерно так себе и представлял подобное решение. А как например в майнкрафте? неужели там сразу генерируется карта высот огромная?

Arton

10.03.2015 11:02

Ответ: Генерация террайнов

Цитата:

Сообщение от scorey (Сообщение 293969)

Сразу вся карта не генерируется, по частям когда игрок двигается в новое место, в противном случае мир создавался бы ~~несколько часов~~ хрен знает сколько.
P. S. Карта планеты Земля — 3.50 Гб.

dsd	12.03.2015 12:50

Ответ: Генерация террайнов

Цитата:

Сообщение от scorey (Сообщение 293969)

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

Что то типа такого я в виду имею:

PHP код:




using UnityEngine; 
using System.Collections; 
using System; 
 
public class Noise3D{ 
     
        private static System.Random randGen;  
        private static int[] randData = new int[512]; 
     
    public static void init ( int seed) { 
        randGen = new System.Random(seed); 
        for(int i=0; i<511; i++) randData[i] = randGen.Next(0,255);  
    } 
    //сплайн для апроксимации 
     private static float fade(float t) { 
         return t*t*t*(t*(t*6-15)+10); 
    }     
     
     //выдает по координате значение из фэйкового бесконечного массива 
    private static int rand(int x, int y, int z){ 
        int x0 =(256+(x%256))%256; 
        int y0 =(256+(y%256))%256; 
        int z0 =(256+(z%256))%256;     
        return randData[ x0 + randData[ y0 + randData[ z0 ] ] ];      
    } 
    public static float noise(Vector3 pos){ 
        int x0 = Mathf.FloorToInt(pos.x); 
        int y0 = Mathf.FloorToInt(pos.y); 
        int z0 = Mathf.FloorToInt(pos.z); 
        //смещение внутри ячейки 
        float dx = pos.x-x0; 
        float dy = pos.y-y0; 
        float dz = pos.z-z0; 
        //читаю 8 точек из фэйкового рандома 
        int x000 = rand(x0,y0,z0); 
        int x001 = rand(x0,y0,z0+1); 
        int x010 = rand(x0,y0+1,z0); 
        int x011 = rand(x0,y0+1,z0+1); 
        int x100 = rand(x0+1,y0,z0); 
        int x101 = rand(x0+1,y0,z0+1); 
        int x110 = rand(x0+1,y0+1,z0); 
        int x111 = rand(x0+1,y0+1,z0+1);     
        //смешиваю 
        float dif00 = Mathf.Lerp(x000,x001,fade(dz)); 
        float dif01 = Mathf.Lerp(x010,x011,fade(dz)); 
        float dif10 = Mathf.Lerp(x100,x101,fade(dz)); 
        float dif11 = Mathf.Lerp(x110,x111,fade(dz)); 
         
        float diff0 = Mathf.Lerp(dif00,dif01,fade(dy)); 
        float diff1 = Mathf.Lerp(dif10,dif11,fade(dy)); 
         
        return Mathf.Lerp(diff0,diff1,fade(dx))*0.0039215686274509803921568627451f; 
    } 
}

Igor	12.03.2015 18:15

Ответ: Генерация террайнов

Мне кажется, куча обращений к массиву не имеет смысла.
Я бы предложил просто построить какую-нибудь хитрую функцию от трёх переменных.
например, при инициализации задавать параметры a и с, и пусть функция rand возвращает (a + c * (x ^ (x >> 5) ^ (y<<3-1) ^ (z >> 3 + z))) & 0xFF.
Если хочется, можно запихать в массив данные с нужным распределением (например, нормальным), и один раз читать оттуда по "рандомной" позиции.

Часовой пояс GMT +4, время: 02:41.

Страница 1 из 2

Показывать 64 сообщений этой темы на одной странице