|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
28.06.2011, 06:33
|
#1
|
Бывалый
Регистрация: 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 за это полезное сообщение:
|
|
28.06.2011, 15:08
|
#2
|
Бывалый
Регистрация: 24.05.2011
Адрес: Украина,Харьков
Сообщений: 890
Написано 359 полезных сообщений (для 880 пользователей)
|
Ответ: Генерация террайнов
|
(Offline)
|
|
30.06.2011, 16:30
|
#4
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: Генерация террайнов
Имхо, корозия ликвидного поведения единицами один из самых реалистичных подходов к генерации ландшафта.
Одна часть - это сгенерировать вершинную карту. Другая часть, это корректно распределить горные породы, от земли, песка и т.п. И далее рассадить растительность, основываясь законам, с которой она распростроняется..
|
(Offline)
|
|
02.07.2011, 18:39
|
#5
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,360
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Генерация террайнов
Мой простенький генератор карты высот на базе 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)
|
|
Сообщение было полезно следующим пользователям:
|
|
02.07.2011, 19:39
|
#6
|
Бывалый
Регистрация: 24.05.2011
Адрес: Украина,Харьков
Сообщений: 890
Написано 359 полезных сообщений (для 880 пользователей)
|
Ответ: Генерация террайнов
Шум Перлина на C#. http://lotsacode.wordpress.com/2010/...in-noise-in-c/ .Пока за основу взял его,буду пробовать еще через пару фильтров пропускать,в качестве экспериментов с хайт мапами.Ну и в сторону водной коррозии не ровно дышу.
Кстати в сторону Minecraft.Я доподлинно не знаю так реализовано или нет,но при расширении ландшафта и генерации новых чанков(когда пользователь расширяет территорию)в алгоритм генерации в качестве соли я бы использовал ник игрока,расширяющего территорию.Так бы мы получили неоднозначность территории.В которой было бы все.И висячие сады и равнины и горы.
|
(Offline)
|
|
10.09.2011, 23:13
|
#7
|
Мастер
Регистрация: 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 за это полезное сообщение:
|
|
10.01.2012, 22:33
|
#8
|
Мастер
Регистрация: 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
|
ПроЭктировщик
Регистрация: 24.10.2009
Сообщений: 143
Написано 5 полезных сообщений (для 7 пользователей)
|
Ответ: Генерация террайнов
Вторая ссылка умерла безвременно... И да, тема - шикарна.
__________________
Гомоморфный образ группы - путь во славу коммунизма - изоморфен фактор группе по ядру гомоморфизма.
|
(Offline)
|
|
09.03.2015, 22:01
|
#10
|
Оператор ЭВМ
Регистрация: 07.02.2009
Адрес: Чебоксары
Сообщений: 28
Написано одно полезное сообщение
|
Ответ: Генерация террайнов
А как можно сделать отложенную генерацию карт высот? Например у нас есть сгенерированная карта высот 1000x1000. На основе этой карты сделан террайн. Игрок например идет к левому краю террайна, и рядом с нашим террайном генерируется новый (На основе карт высот, но при этом чтобы он был как бы "продолжением" первой карты. То есть если у нас на границе первого террайна есть пол - горы, чтобы при генерации эта же гора плавно спускалась уже на втором террайне
|
(Offline)
|
|
09.03.2015, 22:06
|
#11
|
Элита
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,158
Написано 502 полезных сообщений (для 1,012 пользователей)
|
Ответ: Генерация террайнов
Сообщение от scorey
А как можно сделать отложенную генерацию карт высот? Например у нас есть сгенерированная карта высот 1000x1000. На основе этой карты сделан террайн. Игрок например идет к левому краю террайна, и рядом с нашим террайном генерируется новый (На основе карт высот, но при этом чтобы он был как бы "продолжением" первой карты. То есть если у нас на границе первого террайна есть пол - горы, чтобы при генерации эта же гора плавно спускалась уже на втором террайне
|
БООЛЬШАЯ карта высот, а терейн генерируется из кусочка карты - это самый примитивный способ, карта высот типо тайлсета терейнов, хотя можно просто усреднить края различных карт высот на некоторое расстояние по гаусу например (чем ближе к краю, тем сильнее усреднение^2), что бы переход был плавный.
|
(Offline)
|
|
09.03.2015, 22:09
|
#12
|
Оператор ЭВМ
Регистрация: 07.02.2009
Адрес: Чебоксары
Сообщений: 28
Написано одно полезное сообщение
|
Ответ: Генерация террайнов
Сообщение от RegIon
БООЛЬШАЯ карта высот, а терейн генерируется из кусочка карты - это самый примитивный способ, карта высот типо тайлсета терейнов
|
Я примерно так себе и представлял подобное решение. А как например в майнкрафте? неужели там сразу генерируется карта высот огромная?
|
(Offline)
|
|
10.03.2015, 11:02
|
#13
|
Быдлокодер
Регистрация: 05.07.2009
Адрес: Проспит
Сообщений: 5,023
Написано 2,312 полезных сообщений (для 5,349 пользователей)
|
Ответ: Генерация террайнов
Сообщение от scorey
Я примерно так себе и представлял подобное решение. А как например в майнкрафте? неужели там сразу генерируется карта высот огромная?
|
Сразу вся карта не генерируется, по частям когда игрок двигается в новое место, в противном случае мир создавался бы несколько часов хрен знает сколько.
P. S. Карта планеты Земля — 3.50 Гб.
|
(Offline)
|
|
12.03.2015, 12:50
|
#14
|
Мастер
Регистрация: 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=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; } }
|
(Offline)
|
|
12.03.2015, 18:15
|
#15
|
Мастер
Регистрация: 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)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 08:37.
|