Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 28.06.2011, 06:33   #1
Lestar
Бывалый
 
Аватар для Lestar
 
Регистрация: 24.05.2011
Адрес: Украина,Харьков
Сообщений: 890
Написано 359 полезных сообщений
(для 880 пользователей)
Генерация террайнов

Столкнулся с необходимостью генерации реалистичных террайнов.Из чего то вменяемого по алгоритмике нашел :
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км. Озера,болота,небольшие ручьи,реки.
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо Lestar за это полезное сообщение:
.Squid (11.09.2011), ABTOMAT (28.06.2011), Mr_F_ (28.06.2011)
Старый 28.06.2011, 15:08   #2
Lestar
Бывалый
 
Аватар для Lestar
 
Регистрация: 24.05.2011
Адрес: Украина,Харьков
Сообщений: 890
Написано 359 полезных сообщений
(для 880 пользователей)
Ответ: Генерация террайнов

Немного реализаций http://sourceforge.net/search/?q=terrain+generator
(Offline)
 
Ответить с цитированием
Старый 30.06.2011, 15:34   #3
Lestar
Бывалый
 
Аватар для Lestar
 
Регистрация: 24.05.2011
Адрес: Украина,Харьков
Сообщений: 890
Написано 359 полезных сообщений
(для 880 пользователей)
Ответ: Генерация террайнов

Продолжаю свой монолог.
Очень подробно рассмотрен вопрос генерации террайнов http://oddlabs.com/download/terrain_generation.pdf
Рассматриваем вопросы водной эрозии http://www-evasion.imag.fr/Publications/2007/MDH07/
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Mr_F_ (30.06.2011)
Старый 30.06.2011, 16:30   #4
moka
.
 
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений
(для 6,863 пользователей)
Ответ: Генерация террайнов

Имхо, корозия ликвидного поведения единицами один из самых реалистичных подходов к генерации ландшафта.
Одна часть - это сгенерировать вершинную карту. Другая часть, это корректно распределить горные породы, от земли, песка и т.п. И далее рассадить растительность, основываясь законам, с которой она распростроняется..
(Offline)
 
Ответить с цитированием
Старый 02.07.2011, 18:39   #5
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,354
Написано 2,470 полезных сообщений
(для 6,850 пользователей)
Ответ: Генерация террайнов

Мой простенький генератор карты высот на базе 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
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Lestar (02.07.2011)
Старый 02.07.2011, 19:39   #6
Lestar
Бывалый
 
Аватар для Lestar
 
Регистрация: 24.05.2011
Адрес: Украина,Харьков
Сообщений: 890
Написано 359 полезных сообщений
(для 880 пользователей)
Ответ: Генерация террайнов

Шум Перлина на C#. http://lotsacode.wordpress.com/2010/...in-noise-in-c/ .Пока за основу взял его,буду пробовать еще через пару фильтров пропускать,в качестве экспериментов с хайт мапами.Ну и в сторону водной коррозии не ровно дышу.
Кстати в сторону Minecraft.Я доподлинно не знаю так реализовано или нет,но при расширении ландшафта и генерации новых чанков(когда пользователь расширяет территорию)в алгоритм генерации в качестве соли я бы использовал ник игрока,расширяющего территорию.Так бы мы получили неоднозначность территории.В которой было бы все.И висячие сады и равнины и горы.
(Offline)
 
Ответить с цитированием
Старый 10.09.2011, 23:13   #7
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Генерация террайнов

Мой простенький генератор карты высот на базе 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;
}
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо dsd за это полезное сообщение:
Lestar (11.09.2011), Randomize (10.09.2011)
Старый 10.01.2012, 22:33   #8
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Генерация террайнов

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

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];}}}
(Offline)
 
Ответить с цитированием
Старый 30.09.2013, 08:25   #9
Лit}{Ъ
ПроЭктировщик
 
Аватар для Лit}{Ъ
 
Регистрация: 24.10.2009
Сообщений: 143
Написано 5 полезных сообщений
(для 7 пользователей)
Ответ: Генерация террайнов

Вторая ссылка умерла безвременно... И да, тема - шикарна.
__________________
Гомоморфный образ группы - путь во славу коммунизма - изоморфен фактор группе по ядру гомоморфизма.
(Offline)
 
Ответить с цитированием
Старый 09.03.2015, 22:01   #10
scorey
Оператор ЭВМ
 
Аватар для scorey
 
Регистрация: 07.02.2009
Адрес: Чебоксары
Сообщений: 28
Написано одно полезное сообщение
Ответ: Генерация террайнов

А как можно сделать отложенную генерацию карт высот? Например у нас есть сгенерированная карта высот 1000x1000. На основе этой карты сделан террайн. Игрок например идет к левому краю террайна, и рядом с нашим террайном генерируется новый (На основе карт высот, но при этом чтобы он был как бы "продолжением" первой карты. То есть если у нас на границе первого террайна есть пол - горы, чтобы при генерации эта же гора плавно спускалась уже на втором террайне
(Offline)
 
Ответить с цитированием
Старый 09.03.2015, 22:06   #11
RegIon
Элита
 
Аватар для RegIon
 
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений
(для 1,012 пользователей)
Ответ: Генерация террайнов

Сообщение от scorey Посмотреть сообщение
А как можно сделать отложенную генерацию карт высот? Например у нас есть сгенерированная карта высот 1000x1000. На основе этой карты сделан террайн. Игрок например идет к левому краю террайна, и рядом с нашим террайном генерируется новый (На основе карт высот, но при этом чтобы он был как бы "продолжением" первой карты. То есть если у нас на границе первого террайна есть пол - горы, чтобы при генерации эта же гора плавно спускалась уже на втором террайне
БООЛЬШАЯ карта высот, а терейн генерируется из кусочка карты - это самый примитивный способ, карта высот типо тайлсета терейнов, хотя можно просто усреднить края различных карт высот на некоторое расстояние по гаусу например (чем ближе к краю, тем сильнее усреднение^2), что бы переход был плавный.
__________________
Сайт: http://iexpo.ml
(Offline)
 
Ответить с цитированием
Старый 09.03.2015, 22:09   #12
scorey
Оператор ЭВМ
 
Аватар для scorey
 
Регистрация: 07.02.2009
Адрес: Чебоксары
Сообщений: 28
Написано одно полезное сообщение
Ответ: Генерация террайнов

Сообщение от RegIon Посмотреть сообщение
БООЛЬШАЯ карта высот, а терейн генерируется из кусочка карты - это самый примитивный способ, карта высот типо тайлсета терейнов
Я примерно так себе и представлял подобное решение. А как например в майнкрафте? неужели там сразу генерируется карта высот огромная?
(Offline)
 
Ответить с цитированием
Старый 10.03.2015, 11:02   #13
Arton
Быдлокодер
 
Аватар для Arton
 
Регистрация: 05.07.2009
Адрес: Проспит
Сообщений: 5,019
Написано 2,312 полезных сообщений
(для 5,349 пользователей)
Ответ: Генерация террайнов

Сообщение от scorey Посмотреть сообщение
Я примерно так себе и представлял подобное решение. А как например в майнкрафте? неужели там сразу генерируется карта высот огромная?
Сразу вся карта не генерируется, по частям когда игрок двигается в новое место, в противном случае мир создавался бы несколько часов хрен знает сколько.
P. S. Карта планеты Земля — 3.50 Гб.
(Offline)
 
Ответить с цитированием
Старый 12.03.2015, 12:50   #14
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Генерация террайнов

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

Что то типа такого я в виду имею:
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=0i<511i++) 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 xint yint z){
        
int x0 =(256+(x%256))%256;
        
int y0 =(256+(y%256))%256;
        
int z0 =(256+(z%256))%256;    
        return 
randDatax0 randDatay0 randDataz0 ] ] ];     
    }
    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;
    }

(Offline)
 
Ответить с цитированием
Старый 12.03.2015, 18:15   #15
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений
(для 790 пользователей)
Ответ: Генерация террайнов

Мне кажется, куча обращений к массиву не имеет смысла.
Я бы предложил просто построить какую-нибудь хитрую функцию от трёх переменных.
например, при инициализации задавать параметры a и с, и пусть функция rand возвращает (a + c * (x ^ (x >> 5) ^ (y<<3-1) ^ (z >> 3 + z))) & 0xFF.
Если хочется, можно запихать в массив данные с нужным распределением (например, нормальным), и один раз читать оттуда по "рандомной" позиции.
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


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


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com