Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Landscapes  (Прочитано 24292 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Faust
Гость
« : 26-03-2004 09:45 » 

Здравствуйте.
Хочу предложить новый алгоритм генерирования холмов. Алгорит достаточно прост для реализации и дает более натуральный вид холма, чем математическое моделирование.

Мой алгоритм (не знаю, может нечто подобоное уже и существует...) основан на т.н. "Доске Гальтона". Она представляет собой вертикально поставленую коробку. В верхней части есть отверстие, через которое внутрь попадают шарики. Внутри коробки (в верхней ее части) расположена пирамида препятствий. В процессе падения шарик натыкается на препятствия и каждый раз выбирает один из вариантов траектории - влево или вправо. В конце концов он попадает в нижнюю часть доски. Она поделена на отсеки вертикальными перегородками. Количество отсеков на 1 больше, чем количество препятствий в нижнем ряду пирамиды. В итоге в отсеках собираются шарики. Наибольшее их количество - в центральных отсеках. Наименьшее - в боковых. Это нормальное распределение.
Алгоритм работает похожим образом. В начале работы алгоритма две переменных (они являются координатами точки на карте высот) устанавливаются в выбраный центр будущего холма.  Затем в цикле генерируется случайное число - от 0 до 8. Это число можно представить как индекс в матрице 3х3. Эта матрица задает направление. Точка сдвигается в соответствии с матрицей (8 направлений и центральная клетка - в ней координаты не меняются).
Количество итераций в цикле равно диаметру холма в пикселях. После окончания цикла значение высоты в полученой точке увеличивается на 1. Процесс продолжается до тех пор, пока какая-либо точка не достигет требуемой высоты холма. Форма полученого холма будет иметь вид нормальной кривой. Случайность в выборе траектории придает холму натуральный вид.
Алгоритм был испытан (я написал простенький генератор ландшафтов на С) и показал хорошее качество работы.
Записан
Sommer
Молодой специалист

us
Offline Offline

« Ответ #1 : 26-03-2004 09:53 » new

клево
я никогда таким не зханимался
но очень интересно

я так понял, что Вы создали алгоритм который рисует холм в профиль?(в разрезе?)
где это нужно? где применить?
Записан

когда-нибудь, я верю, ты будешь ехать по этому городу и поймёшь, что хочешь увидеть меня за рулём мчащейся по соседней полосе машины.
но тогда меня уже не будет
в этом городе
forever yours.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 26-03-2004 10:37 » 

Faust, если не ошибаюсь, это называется Гауссово распределение. Зачем делать иммитацию фариков, если существуют формулы?
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Sommer
Молодой специалист

us
Offline Offline

« Ответ #3 : 26-03-2004 10:56 » 

RXL,
распреджеление Гаусса имеет гладкие ровные склоны
в реале же такого не найдешь... а контур холма наврное хотелось получить с максимальным приближеением к реалии
единственное что можно было делать случайный разброс небольшой величины по оси абсциссна основе распределения Гаусса
но предыдущий способ короче получился
Записан

когда-нибудь, я верю, ты будешь ехать по этому городу и поймёшь, что хочешь увидеть меня за рулём мчащейся по соседней полосе машины.
но тогда меня уже не будет
в этом городе
forever yours.
Lex
Специалист

ru
Offline Offline

WWW
« Ответ #4 : 26-03-2004 11:30 » 

Sommer, не уверен, что по скорости генерации новый способ будет быстрее чем Гаусс плюс какой-то шум
Записан

Megabyte be with you!
Sommer
Молодой специалист

us
Offline Offline

« Ответ #5 : 26-03-2004 12:08 » 

Lex,

ну.. может быть(это надо проверять)
Записан

когда-нибудь, я верю, ты будешь ехать по этому городу и поймёшь, что хочешь увидеть меня за рулём мчащейся по соседней полосе машины.
но тогда меня уже не будет
в этом городе
forever yours.
Faust
Гость
« Ответ #6 : 26-03-2004 22:52 » 

Я так понял, что меня не совсем поняли  Улыбаюсь
Да, действительно, существую формулы, описывающие Гауссово (или нормальное - это одно и то же) распределение. Если строить холм по этим формулам, то мы действительно получим образование гладкой формы, слабо похожее на реальные природные холмы. И никакой шум по высоте тут не поможет. Но я потому и описывал процесс со ссылкой на доску Гальтона. При построении холма я не использую формулу нормального распределения. Я моделирую выпадение шариков. Это приводит к тому, что хотя холм и имеет форму колокола, но он не гладкий. Шарики падают случайно. Вместо гладкой Гауссовой кривой (в нашем случае - поверхности) мы получим именно холм. Он не будет иметь постоянной формы, так как точки "падают" случайно. Попробуйте - и сами убедитесь - получается очень похоже на натуральные природные холмы.
Алгорит действительно более медленный, чем если рисовать по кривым Гаусса с шумом по высоте, но реалистичность очень высока.
К стати, этот процесс очень напоминает образование холмов в природе!

2Sommer. Холм генерится не в разрезе, а как полностью трехмерный обьект. Я ведь, кажется, упоминал, что все происходит на карте высот...
Записан
Faust
Гость
« Ответ #7 : 26-03-2004 22:57 » 

2Sommer. Это применяется при генерации ландшафтов.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #8 : 27-03-2004 15:32 » 

Faust, а если применить разные генераторы случайных чисел - не пробовал? Ведь они дадут разное распределение случайной величины.

Кстати, у тебя программа действующая? Как на счет экспорта результата в какой-нибудь 3D формат? Может ее, если ты не против, на шелеке выложить?
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Anonymous
Гость
« Ответ #9 : 05-04-2004 06:23 » 

Да, программа действующая, но она написана на С++ под ОС DOS.  Могу выложить ее исходник, но с экспортом иметь дело пока не хочу - это нужно изучать форматы файлов, писать конвертор... Просто сейчас нету времени. Да и прога ничего полезного не делает - это просто проверка алгоритма. Если кто-то хочет на ее основе создать более мощный продукт - пишите, поработаем вместе.
Записан
Lex
Специалист

ru
Offline Offline

WWW
« Ответ #10 : 05-04-2004 10:01 » 

Можешь кинуть мне исходники  в мыло?
Хочу попробовать сгенерить ланшафт.
Записан

Megabyte be with you!
Кот
Гость
« Ответ #11 : 06-04-2004 05:34 » 

Да было бы неплохо посмотреть исходники
Записан
Anonymous
Гость
« Ответ #12 : 07-04-2004 09:56 » 

Исходник. Смотрите, разбирайтесь, оценивайте... Сорри, что без коментариев, но писал "на скорую руку", только для проверки алгоритма, так что если чего-то не поймете - спрашивайте...
Код:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <graphics.h>

#define SIZEX 128
#define SIZEY 128
#define ZERO -128

char Buf[256];

char HMap[SIZEX][SIZEY]={0};

int XOff=320,
    YOff=240;

float WaterLevel=0;

float kX=8;
float kY=8;
float kZ=1;

float CamX=100;
float CamY=100;
float CamZ=50;

float XX, XY, YX, YY, YZ;

struct TPoint {
 int X,Y;
};

void InitMap();
void InitCam();
void Soft();
void AddWater(int);
void AddHill(int, int, int, int);
void AddHole(int, int, int, int);
void AddNoize(int);
void InitGraph();
void Draw();
void Done();
void Project(float, float, float, int &, int &);

void main()
{randomize();
 InitMap();
 InitCam();
 InitGraph();
 Draw();
 while(!kbhit());
 while(kbhit())getch();
 Done();
}

void Soft()
{int i,j;
 float p=0;
 printf("Process:  0%");
 for(i=1;i<SIZEX-1;i++)
  for(j=1;j<SIZEY-1;j++)
  {HMap[i][j]=(HMap[i][j]+
      HMap[i+1][j]+
      HMap[i][j+1]+
      HMap[i+1][j+1]+
      HMap[i-1][j]+
      HMap[i][j-1]+
      HMap[i-1][j-1]+
      HMap[i-1][j+1]+
      HMap[i+1][j-1])/9;
  printf("%c%c%c%c%3d%",8,8,8,8,(int)p);
  p+=(float)100/(SIZEX-2)/(SIZEY-2);
  }
 for(i=1;i<SIZEX-1;i++)
 {HMap[i][0]=(HMap[i][0]+
     HMap[i+1][0]+
     HMap[i-1][0]+
     HMap[i+1][1]+
     HMap[i][1]+
     HMap[i-1][1])/6;
  HMap[i][SIZEY-1]=(HMap[i][SIZEY-1]+
   HMap[i+1][SIZEY-1]+
   HMap[i-1][SIZEY-1]+
   HMap[i+1][SIZEY-2]+
   HMap[i][SIZEY-2]+
   HMap[i-1][SIZEY-2])/6;
 }
 for(j=1;j<SIZEY-1;j++)
 {HMap[0][j]=(HMap[0][j-1]+
     HMap[0][j]+
     HMap[0][j+1]+
     HMap[1][j-1]+
     HMap[1][j]+
     HMap[1][j+1])/6;
  HMap[SIZEX-1][j]=(HMap[SIZEX-1][j-1]+
   HMap[SIZEX-1][j]+
   HMap[SIZEX-1][j-1]+
   HMap[SIZEX-2][j-1]+
   HMap[SIZEX-2][j]+
   HMap[SIZEX-2][j+1])/6;
 }
 HMap[0][0]=0.25*(HMap[0][0]+
 HMap[1][0]+
 HMap[0][1]+
 HMap[1][1]);
 HMap[SIZEX-1][0]=0.25*(HMap[SIZEX-1][0]+
HMap[SIZEX-2][0]+
HMap[SIZEX-1][1]+
HMap[SIZEX-2][1]);
 HMap[0][SIZEY-1]=0.25*(HMap[0][SIZEY-1]+
HMap[1][SIZEY-1]+
HMap[0][SIZEY-2]+
HMap[1][SIZEY-2]);
 HMap[SIZEX-1][SIZEY-1]=0.25*(HMap[SIZEX-1][SIZEY-1]+
     HMap[SIZEX-2][SIZEY-1]+
     HMap[SIZEX-1][SIZEY-2]+
     HMap[SIZEX-2][SIZEY-2]);
}

void InitMap()
{int i,j;
 AddWater(1);
 AddHill(SIZEX/2,SIZEY/2,SIZEX/2,127);
 AddHole(SIZEX/2+2,SIZEY/2-2,2,-100);
 AddNoize(50);
 for(i=0;i<4;i++)
  Soft();
}

void InitGraph()
{int GD=VGA, GM=VGAHI;
 initgraph(&GD,&GM,"");
}

void Draw()
{TPoint Buf[4];
 int SX=0;
 int SY=0;
 int FX=SIZEX-1;
 int FY=SIZEY-1;
 int dX,dY;
 int i,j,k;
 float X,Y,Z,Average;
 int OX=SIZEX/2,
     OY=SIZEY/2;
 setcolor(15);
 if(CamX>0&&CamY>0)
 {for(i=SX;i<FX;i++)
   for(j=SY;j<FY;j++)
   {X=(i-OX);
    Y=(j-OY);
    Average=(HMap[i][j]+
    HMap[i+1][j]+
    HMap[i][j+1]+
    HMap[i+1][j]+1);
    if(HMap[i][j]<=0)Z=0;
    else Z=HMap[i][j];
    Project(X*kX,Y*kY,Z*kZ,Buf[0].X,Buf[0].Y);
    if(HMap[i+1][j]<=0)Z=0;
    else Z=HMap[i+1][j];
    Project((X+1)*kX,Y*kY,Z*kZ,Buf[1].X,Buf[1].Y);
    if(HMap[i+1][j+1]<=0)Z=0;
    else Z=HMap[i+1][j+1];
    Project((X+1)*kX,(Y+1)*kY,Z*kZ,Buf[2].X,Buf[2].Y);
    if(HMap[i][j+1]<=0)Z=0;
    else Z=HMap[i][j+1];
    Project(X*kX,(Y+1)*kY,Z*kZ,Buf[3].X,Buf[3].Y);
    for(k=0;k<4;k++){Buf[k].X+=XOff;Buf[k].Y+=YOff;}
    if(Average<=WaterLevel){setfillstyle(1,8);setcolor(8);}
    else{setfillstyle(1,7);setcolor(15);}
    fillpoly(4,(int *)Buf);
   }
  setfillstyle(1,7);
  j=SIZEY-1;
  for(i=SX;i<FX;i++)
  {X=(i-OX);
   Y=(SIZEY-1-OY);
   Project(X*kX,Y*kY,HMap[i][j]*kZ,Buf[0].X,Buf[0].Y);
   Project((X+1)*kX,Y*kY,HMap[i+1][j]*kZ,Buf[1].X,Buf[1].Y);
   Project((X+1)*kX,Y*kY,ZERO*kZ,Buf[2].X,Buf[2].Y);
   Project(X*kX,Y*kY,ZERO*kZ,Buf[3].X,Buf[3].Y);
   for(k=0;k<4;k++){Buf[k].X+=XOff;Buf[k].Y+=YOff;}
   fillpoly(4,(int *)Buf);
  }
  i=SIZEX-1;
  for(j=SY;j<FY;j++)
  {X=(SIZEX-1-OX);
   Y=(j-OY);
   Project(X*kX,Y*kY,HMap[i][j]*kZ,Buf[0].X,Buf[0].Y);
   Project(X*kX,Y*kY,ZERO*kZ,Buf[1].X,Buf[1].Y);
   Project(X*kX,(Y+1)*kY,ZERO*kZ,Buf[2].X,Buf[2].Y);
   Project(X*kX,(Y+1)*kY,HMap[i][j+1]*kZ,Buf[3].X,Buf[3].Y);
   for(k=0;k<4;k++){Buf[k].X+=XOff;Buf[k].Y+=YOff;}
   fillpoly(4,(int *)Buf);
  }
 }
}

void Done()
{closegraph();
}

void InitCam()
{float Alpha=atan2(CamY,CamX),
       Betta=atan2(sqrt(CamX*CamX+CamY*CamY),CamZ),
       Temp=cos(Betta);
 XX=cos(Alpha);
 XY=sin(Alpha);
 YX=XY*Temp;
 YY=XX*Temp;
 YZ=sin(Betta);
}

void Project(float X, float Y, float Z, int &px, int &py)
{px=XX*X-XY*Y;
 py=YX*X+YY*Y-YZ*Z;
}

void AddWater(int Lvl)
{WaterLevel=Lvl;
}

void AddHill(int X, int Y, int R, int H)
{int MaxH=-128,Temp;
 int x,y,k,i;
 while(MaxH<H)
 {x=X; y=Y;
  for(i=1;i<R*2;i++)
  {k=random(9);
   switch(k){
    case 0:x--;y--;
     break;
    case 1:y--;
     break;
    case 2:x++;y--;
     break;
    case 3:x--;
     break;
    case 4:
     break;
    case 5:x++;
     break;
    case 6:x--;y++;
     break;
    case 7:y++;
     break;
    case 8:x++;y++;
     break;
   }
  }
  Temp=++HMap[x][y];
  if(MaxH<Temp)MaxH=Temp;
 }
}

void AddHole(int X, int Y, int R, int H)
{int MinH=128,Temp;
 int x,y,k,i;
 while(MinH>H)
 {x=X; y=Y;
  for(i=1;i<R*2;i++)
  {k=random(9);
   switch(k){
    case 0:x--;y--;
     break;
    case 1:y--;
     break;
    case 2:x++;y--;
     break;
    case 3:x--;
     break;
    case 4:
     break;
    case 5:x++;
     break;
    case 6:x--;y++;
     break;
    case 7:y++;
     break;
    case 8:x++;y++;
     break;
   }
  }
  Temp=--HMap[x][y];
  if(MinH>Temp)MinH=Temp;
 }
}

void AddNoize(int Intensity)
{int i,j;
 int R=Intensity/2;
 for(i=0;i<SIZEX;i++)
  for(j=0;j<SIZEY;j++)
   HMap[i][j]+=random(Intensity)-R;
}
« Последнее редактирование: 09-08-2010 08:54 от Джон » Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines