algorithm - cómo crear una estructura ramificada de veta/río en una cuadrícula

lua grid

Question

Estoy tratando de generar algunos ríos de procedimiento.

Tengo una cuadrícula plana (sin concepto de elevación) como base y quiero dibujar una estructura de ramificación en ella como se muestra en la imagen.

¿Puedes compartir los pasos que uno puede usar para lograrlo?

No busco la implementación más rápida, ya que no hay generación en tiempo real, pero se preferirá una implementación más simple. Lua es mi lenguaje, pero cualquier cosa servirá.

Pocas cosas más:

1. La forma se debe generar aliado algorítmico.
2. La forma debe ser controlable usando un valor inicial.

Answer 1

El delta de tu río se parece mucho a un árbol. Aquí hay un código de Python que usa tortuga para que Graphics dibuje un árbol.

# ¡Puedes editar este código y ejecutarlo aquí mismo en el navegador! # Intente cambiar colores o agregar sus propias formas.

import turtle
from random import randint
def tree(length,n, ps):
""" paints a branch of a tree with 2 smaller branches, like an Y"""
if length < (length/n):
return # escape the function
turtle.pensize(max(ps,1))
turtle.forward(length) # paint the thik branch of the tree
lb = 45+randint(-20,20)
turtle.left(lb) # rotate left for smaller "fork" branch
tree(length * 0.5*(1+randint(-20,20)/100),length/n,ps-1) # create a smaller branch with 1/2 the lenght of the parent branch
rb = 45+randint(-20,20)
turtle.right(lb+rb) # rotoate right for smaller "fork" branch
tree(length * 0.6,length/n,ps-1) # create second smaller branch
turtle.left(rb) # rotate back to original heading
rt = randint(-20,20)
turtle.right(rt)
tree(length * 0.45,length/n,ps-1)
turtle.left(rt)
turtle.backward(length) # move back to original position
return # leave the function, continue with calling program
turtle.left(90)
turtle.penup()
turtle.backward(250)
turtle.pendown()
tree(150,5,5)

Answer 2

Creo que la generación de ríos es un enfoque retrógrado ya que tendrías que modificar muchas cosas de acuerdo con su forma más adelante, lo cual será difícil. En su lugar, crearía un mapa aleatorio de altura del terreno y extraería características de él (como en el mundo real) que es mucho más fácil y más cercano a la realidad. En el mapa final ignoras la altura y usas la plana (si realmente quieres un mapa plano). Aquí hay algunas cosas que puede extraer del mapa de altura:

1. Rios y lagos

   sembrando un punto aleatorio de gran altitud y siguiéndolo cuesta abajo hasta el nivel del mar o el borde del mapa.

2. vegetación o suelo

   desde la pendiente y la altitud puede determinar si el terreno es arena, tierra, roca. Si hay árboles, arbustos, hierba o lo que sea.

Aquí mire este control de calidad : generador de isla aleatorio

y alguna descripción del río:

La forma en que ajusta la generación del terreno afectará también las formas del río (no es necesario generar solo islas).

Las Semillas están trabajando también para este enfoque.

[Edit1] prometió código C ++

Esto genera básicamente un mapa de alturas aleatorias y luego sembrar y descender siguiendo los ríos (los lagos se generan automáticamente si el terreno bloquea el flujo de aguas abajo). El tipo de terreno también se determina a partir de la pendiente y la altitud.

//---------------------------------------------------------------------------
picture pic;
//---------------------------------------------------------------------------
void map_random(int _xs,int _ys)
{
// config
int h0=-1000,h1=3000; // [m] terrain elevation range
int h_water= 0; // [m] sea level
int h_sand=15; // [m] sand level
int h_evergreen=1500; // [m] evergreen level
int h_snow=2000; // [m] snow level
int h_rock=1800; // [m] mountine rock level
float a_rock=60.0; // [deg] mountine rock slope
float d_pixel=35.0; // [m] pixel size
int d_river_w=5; // [pixel] river max width
int d_river_l=150; // [pixel] river base length per width increase
bool _island=true;
// types
enum _cover_enum
{
_cover_none=0,
_cover_water, // sea
_cover_snow,
_covers,
_cover_shift=0,
_cover_mask=15,
};
DWORD _cover[_covers]=
{
// RRGGBB
0x00000000, // none
0x00003080, // watter (sea)
0x00EEEEEE, // snow
};
enum _terrain_enum
{
_terrain_dirt=0,
_terrain_sand,
_terrain_rock,
_terrain_water, // streams,rivers,lakes
_terrain_temp, // temp
_terrains,
_terrain_shift=4,
_terrain_mask=15,
};
DWORD _terrain[_terrains]=
{
// RRGGBB
0x00301510, // dirt
0x00EEC49A, // sand
0x006F6F6F, // rock
0x00006080, // water (streams,rivers,lakes)
0x00006080, // temp
};
enum _flora_enum
{
_flora_none=0,
_flora_grass,
_flora_hardwood,
_flora_evergreen,
_flora_deadwood,
_floras,
_flora_shift=8,
_flora_mask=15,
};
DWORD _flora[_floras]=
{
// RRGGBB
0x00000000, // none
0x007F7F3F, // grass
0x001FFF1F, // hardwood
0x00007F00, // evergreen
0x007F3F1F, // deadwood
};
// variables
float a,b,da; int c,t,f;
int x,y,z,xx,yy,mxs,mys,dx,dy,dx2,dy2,r,r2,ix,l;
int xh1,yh1; // topest hill position
int **ter=NULL,**typ=NULL;
Randomize();
// align resolution to power of 2
for (mxs=1;mxs+1<_xs;mxs<<=1); if (mxs<3) mxs=3;
for (mys=1;mys+1<_ys;mys<<=1); if (mys<3) mys=3;
ter=new int*[mys+1]; for (y=0;y<=mys;y++) ter[y]=new int[mxs+1];
typ=new int*[mys+1]; for (y=0;y<=mys;y++) typ[y]=new int[mxs+1];
// [Terrain]
for (;;)
{
// diamond & square random height map -> ter[][]
dx=mxs; dx2=dx>>1; r=(mxs+mys)<<1; // init step,half step and randomness
dy=mys; dy2=dy>>1; r2=r>>1;
// set corners values
if (_island)
{
t=-r2;
ter[ 0][ 0]=t;
ter[ 0][mxs]=t;
ter[mys][ 0]=t;
ter[mys][mxs]=t;
ter[dy2][dx2]=r+r; // top of central hill
}
else{
ter[ 0][ 0]=Random(r);
ter[ 0][mxs]=Random(r);
ter[mys][ 0]=Random(r);
ter[mys][mxs]=Random(r);
}
for (;dx2|dy2;dx=dx2,dx2>>=1,dy=dy2,dy2>>=1) // subdivide step until full image is filled
{
if (!dx) dx=1;
if (!dy) dy=1;
// diamond (skip first one for islands)
if ((!_island)||(dx!=mxs))
for (y=dy2,yy=mys-dy2;y<=yy;y+=dy)
for (x=dx2,xx=mxs-dx2;x<=xx;x+=dx)
ter[y][x]=((ter[y-dy2][x-dx2]+ter[y-dy2][x+dx2]+ter[y+dy2][x-dx2]+ter[y+dy2][x+dx2])>>2)+Random(r)-r2;
// square
for (y=dy2,yy=mys-dy2;y<=yy;y+=dy)
for (x=dx ,xx=mxs-dx ;x<=xx;x+=dx)
ter[y][x]=((ter[y][x-dx2]+ter[y][x+dx2]+ter[y-dy2][x]+ter[y+dy2][x])>>2)+Random(r)-r2;
for (y=dy ,yy=mys-dy ;y<=yy;y+=dy)
for (x=dx2,xx=mxs-dx2;x<=xx;x+=dx)
ter[y][x]=((ter[y][x-dx2]+ter[y][x+dx2]+ter[y-dy2][x]+ter[y+dy2][x])>>2)+Random(r)-r2;
for (x=dx2,xx=mxs-dx2;x<=xx;x+=dx)
{
y= 0; ter[y][x]=((ter[y][x-dx2]+ter[y][x+dx2]+ter[y+dy2][x])/3)+Random(r)-r2;
y=mys; ter[y][x]=((ter[y][x-dx2]+ter[y][x+dx2]+ter[y-dy2][x])/3)+Random(r)-r2;
}
for (y=dy2,yy=mys-dy2;y<=yy;y+=dy)
{
x= 0; ter[y][x]=((ter[y][x+dx2]+ter[y-dy2][x]+ter[y+dy2][x])/3)+Random(r)-r2;
x=mxs; ter[y][x]=((ter[y][x-dx2]+ter[y-dy2][x]+ter[y+dy2][x])/3)+Random(r)-r2;
}
if (_island)
{
// recompute middle position after first pass so there can be more central hills
if (dx==mxs) ter[dy2][dx2]=Random(r2);
// adjust border to underwatter
for (y=0;y<=mys;y+=dy2) { ter[y][0]=t; ter[y][mxs]=t; }
for (x=0;x<=mxs;x+=dx2) { ter[0][x]=t; ter[mys][x]=t; }
}
// adjust randomness
r>>=1; if (r<2) r=2; r2=r>>1;
}
// rescale to <h0,h1>
xx=ter[0][0]; yy=xx;
for (y=0;y<=mys;y++)
for (x=0;x<=mxs;x++)
{
z=ter[y][x];
if (xx>z) xx=z;
if (yy<z){ yy=z; xh1=x; yh1=y; }
}
for (y=0;y<=mys;y++)
for (x=0;x<=mxs;x++)
ter[y][x]=h0+(((ter[y][x]-xx)*(h1-h0))/(yy-xx));
// test for correctness
if (_island)
{
l=0;
for (x=0;x<=mxs;x++) { if (ter[0][x]>h_water) l++; if (ter[mys][x]>h_water) l++; }
for (y=0;y<=mys;y++) { if (ter[y][0]>h_water) l++; if (ter[y][mxs]>h_water) l++; }
if (l>1+((mxs+mys)>>3)) continue;
}
break;
}
// [Surface]
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=ter[y][x];
// max slope [deg]
a=atan2(ter[y][x+1]-z,d_pixel);
b=atan2(ter[y+1][x]-z,d_pixel);
if (a<b) a=b; a*=180.0/M_PI;
c=_cover_none;
if (z<=h_water) c=_cover_water;
if (z>=h_snow ) c=_cover_snow;
t=_terrain_dirt;
if (z<=h_sand) t=_terrain_sand;
if (z>=h_rock) t=_terrain_rock;
if (a>=a_rock) t=_terrain_rock;
f=_flora_none;
if (t==_terrain_dirt)
{
r=Random(100);
if (r>10) f=_flora_grass;
if (r>50)
{
if (z>h_evergreen) f=_flora_evergreen;
else{
r=Random(h_evergreen);
if (r<=z) f=_flora_evergreen;
else f=_flora_hardwood;
}
}
if (r<5) f=_flora_deadwood;
}
typ[y][x]=(c<<_cover_shift)|(t<<_terrain_shift)|(f<<_flora_shift);
}
// [Rivers]
for (ix=10+Random(5),a=0.0,da=2.0*M_PI/float(ix);ix;ix--)
{
// random start around topest hill
a+=da*(0.75+(0.50*Random()));
for (l=0;l<10;l++)
{
b=Random(mxs>>3);
x=xh1; x+=float(b*cos(a));
y=yh1; y+=float(b*sin(a));
if ((x<1)||(x>=mxs)) continue;
if ((y<1)||(y>=mys)) continue;
if (typ[y][x]&0x00F==_cover_water) continue;
l=-1;
break;
} if (l>=0) continue; // safety check
for (l=0,r2=0;;)
{
// stop on map edge
if ((x<=0)||(x>=mxs-1)||(y<=0)||(y>=mys-1)) break;
// decode generated surface
r=typ[y][x];
c=(r>> _cover_shift)& _cover_mask;
t=(r>>_terrain_shift)&_terrain_mask;
f=(r>> _flora_shift)& _flora_mask;
// stop if reached sea
if (c==_cover_water) break;
// insert river dot radius = r2
dx=x-r2; if (dx<0) dx=0; dx2=x+r2; if (dx2>=mxs) dx2=mxs-1;
dy=y-r2; if (dy<0) dy=0; dy2=y+r2; if (dy2>=mys) dy2=mys-1;
for (yy=dy;yy<=dy2;yy++)
for (xx=dx;xx<=dx2;xx++)
if (((xx-x)*(xx-x))+((yy-y)*(yy-y))<=r2*r2)
if (((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)
typ[yy][xx]=(typ[yy][xx]&0x00F)|(_terrain_temp<<_terrain_shift);
// step to smalest elevation neighbor
dx=x; dy=y; z=h1; typ[y][x]=(typ[y][x]&0x00F)|(_terrain_water<<_terrain_shift); xx=x; yy=y;
xx--; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
yy--; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
xx++; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
xx++; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
yy++; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
yy++; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
xx--; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
xx--; r=ter[yy][xx]; if ((z>=r)&&(((typ[yy][xx]>>_terrain_shift)&_terrain_mask)!=_terrain_water)) { z=r; dx=xx; dy=yy; }
if ((dx==x)&&(dy==y))
{
// handle invalid path or need for a lake!!!
if (dx>mxs>>1) dx++; else dx--;
if (dy>mys>>1) dy++; else dy--;
}
x=dx; y=dy;
// increase river volume with length
l++; if (l>d_river_l*(r2+1)) { l=0; if (r2<d_river_w) r2++; }
}
// make merging of rivers possible
for (y=0;y<=mys;y++)
for (x=0;x<=mxs;x++)
if (((typ[y][x]>>_terrain_shift)&_terrain_mask)==_terrain_water)
typ[y][x]=(typ[y][x]&0x00F)|(_terrain_temp<<_terrain_shift);
}
for (y=0;y<=mys;y++)
for (x=0;x<=mxs;x++)
if (((typ[y][x]>>_terrain_shift)&_terrain_mask)==_terrain_temp)
typ[y][x]=(typ[y][x]&0x00F)|(_terrain_water<<_terrain_shift);
// [copy data] rewrite this part to suite your needs
for (y=1;y<_ys;y++)
for (x=1;x<_xs;x++)
{
float nx,ny,nz,x0,y0,z0,x1,y1,z1;
// (nx,ny,nz) = surface normal
nx=0.0; ny=0.0; nz=ter[y][x];
x0=-d_pixel; y0=0.0; z0=ter[y][x-1];
x1=0.0; y1=-d_pixel; z1=ter[y-1][x];
x0-=nx; x1-=nx;
y0-=ny; y1-=ny;
z0-=nz; z1-=nz;
nx=(y0*z1)-(z0*y1);
ny=(z0*x1)-(x0*z1);
nz=(x0*y1)-(y0*x1);
x0=1.0/sqrt((nx*nx)+(ny*ny)+(nz*nz));
nx*=x0;
ny*=x0;
nz*=x0;
// z = ambient light + normal shading
nz=(+0.7*nx)+(-0.7*ny)+(+0.7*nz);
if (nz<0.0) nz=0.0;
nz=255.0*(0.2+(0.8*nz)); z=nz;
// r = base color
r=typ[y][x];
c=(r>> _cover_shift)& _cover_mask;
t=(r>>_terrain_shift)&_terrain_mask;
f=(r>> _flora_shift)& _flora_mask;
r=_terrain[t];
if (c) r= _cover[c];
if (f){ if (c) r|=_flora[f]; else r=_flora[f]; };
// sea color is depending on depth not surface normal
if (c==_cover_water) z=256-((ter[y][x]<<7)/h0);
// apply lighting z to color r
yy=int(r>>16)&255; yy=(yy*z)>>8; if (yy>255) yy=255; r=(r&0x0000FFFF)|(yy<<16);
yy=int(r>> 8)&255; yy=(yy*z)>>8; if (yy>255) yy=255; r=(r&0x00FF00FF)|(yy<< 8);
yy=int(r )&255; yy=(yy*z)>>8; if (yy>255) yy=255; r=(r&0x00FFFF00)|(yy );
// set pixel to target image
pic.p[y][x].dd=r;
}
// free ter[][],typ[][]
for (y=0;y<=mys;y++) delete[] ter[y]; delete[] ter; ter=NULL;
for (y=0;y<=mys;y++) delete[] typ[y]; delete[] typ; typ=NULL;
}
//---------------------------------------------------------------------------

El código se basa en el código de la Respuesta mía vinculada pero con características adicionales (ríos incluidos). Utilizo mi propia clase de imágenes para las imágenes, por lo que algunos miembros son:

• xs,ys tamaño de la imagen en píxeles
• p[y][x].dd es píxel en la posición (x,y) como tipo entero de 32 bits
• clear(color) : borra toda la imagen
• resize(xs,ys) - cambia el tamaño de la imagen a una nueva resolución
• bmp - Mapa de bits GDI encapsulado en VCL con acceso de lienzo

Puede ajustar la adjust randomness en Diamante y Cuadrado para cambiar la suavidad del terreno. También se pueden alterar los límites de altura y los umbrales.

Para lograr más brunching como los ríos, sembrar más puntos de inicio en grupos para que se fusionen en el tiempo en uno o más ríos.