how to create a branching vein/river like structur

2019-01-26 22:37发布

站内文章 / 前沿技术
43 0 0

问题:

I am trying to procedurally generate some rivers.

I have a flat (no concept of elevation) square grid as base and want to draw a branching structure on it like shown in the image.

Can you share the steps that one may use to get that done?

I am not looking for the fastest implementation as there is no real time generation, but the simpler implementation will be prefered. Lua is my language but anything will do.

Few more things:

  1. The shape should be generated algorithmic ally.
  2. The shape should be controllable using a seed value.

回答1:

I think generating rivers is a backward approach as you would need to tweak a lot of things according to their shape later on which will be hard. I would instead create random terrain height map and extract features from it (as in the real world) which is much easier and closer to reality. In the final map you ignore the height and use flat one (if you really want a flat map). Here are few things you can extract from height map:

  1. Rivers and lakes

    by seeding random high altitude point and following it downhill to sea level or edge of map.

  2. vegetation or ground

    from slope and altitude you can determine if ground is sand,dirt,rock. If there are trees, bushes, grass or whatever.

Here look at this QA: random island generator

and some river overview:

The way you tweak the terrain generation will affect also the river shapes (no need to generate just islands).

The Seeds are working also for this approach.

[Edit1] promised C++ code

This basically generate random height map and then seed and downhill follow the rivers (lakes are generated automatically if the terrain block downhill watter flow). The terrain type is also determined from slope and altitude.

//---------------------------------------------------------------------------
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;
    }
//---------------------------------------------------------------------------

The code is based on the code from the linked Answer of mine but with added features (rivers included). I use my own picture class for images so some members are:

  • xs,ys size of image in pixels
  • p[y][x].dd is pixel at (x,y) position as 32 bit integer type
  • clear(color) - clears entire image
  • resize(xs,ys) - resizes image to new resolution
  • bmp - VCL encapsulated GDI Bitmap with Canvas access

You can tweak the adjust randomness in Diamond&Square to change the terrain smoothness. Also the height limits and tresholds can be tampered with.

To achieve more brunching like rivers seed more start points in clusters so they should merge in time into single or more rivers.



回答2:

Your river delta looks much like a tree. Here is some Python code using turtle for Graphics to draw a tree.

# You can edit this code and run it right here in the browser! # Try changing colors or adding your own shapes.

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)


标签： algorithm lua grid procedural-generation
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~