分形地形/高度图生成

Question

我正在尝试重新实现之前成功做过的一个项目，但现在总是感觉有点不对劲……

我用的这个生成分形高度图的算法，基本上是递归的菱形-方形算法。它看起来运行得挺顺利，但生成的地图就是“感觉不太对”……地图似乎没有成功访问网格中的每一个点来确定颜色，而且地图上还残留着一些“结构”，这似乎和网格的递归方式有关。我不太确定问题出在哪里，导致我看到的结果是这样的。

我目前的代码是：

import matplotlib.pyplot as plt
import matplotlib.cm as cm
from math import sqrt
from collections import namedtuple
import random

Coord=namedtuple('Coord','x y')

class Grid(object):
    '''grid handedness, 0,0=topleft  max,max=bottomr right'''    

    def __init__(self,x,y):
        self.size_x=x
        self.size_y=y
        self.data=[ [0 for _ in xrange(x)] for _ in xrange(y) ]

    def _render_to_text(self):
        print '\n\n'
        for row in self.data:
            print [ int(n) for n in row ]

    def _render_to_colormap(self):
        plt.imshow(self.data, interpolation='nearest',cmap=cm.gist_rainbow)
        plt.show()

    def render(self):
        self._render_to_colormap()
        #self._render_to_text()

    def make(self,coordinate,value):
        self.data[coordinate.x][coordinate.y]=value

    def make_new(self,coordinate,value):
        if self.data[coordinate.x][coordinate.y]==0:
            self.make(coordinate,value)

    def get(self,coordinate):
        return self.data[coordinate.x][coordinate.y]

class FractalHeightmap(object):
    '''populates a 'grid' with a fractal heightmap'''
    def __init__(self,grid,rng_seed,roughness,
                 corner_seeds=[(0,100),(0,100),(0,100),(0,100)],
                 max_depth=3):
        self.grid=grid
        self.max_depth=max_depth
        self._set_initial_corners(corner_seeds)
        self.roughness=roughness
        self.generate_heightmap([Coord(0,0),
                                 Coord(self.grid.size_x-1,0),
                                 Coord(0,self.grid.size_y-1),
                                 Coord(self.grid.size_x-1,self.grid.size_y-1)],1
                                )

    def _set_initial_corners(self,corner_seeds):
        tl,tr,bl,br=corner_seeds
        seeds=[[tl,tr],[bl,br]]
        for x_idx,x in enumerate([0,self.grid.size_x-1]):
            for y_idx,y in enumerate([0,self.grid.size_y-1]):
                try:
                    minval,maxval=seeds[x_idx][y_idx]
                    val=minval+(random.random()*(maxval-minval))
                except ValueError:
                    val=seeds[x_idx][y_idx]
                self.grid.make_new(Coord(x,y),val)

    def generate_heightmap(self,corners,depth):
        '''corners = (Coord(),Coord(),Coord(),Coord() / tl/tr/bl/br'''
        if depth>self.max_depth: return

        #
        tl,tr,bl,br=corners
        center=Coord((tr.x-tl.x)/2,(br.y-tr.y)/2)

        #define edge center coordinates
        top_c=Coord(tl.x+((tr.x-tl.x)/2),tl.y)
        left_c=Coord(tl.x,tl.y+((bl.y-tl.y)/2))
        right_c=Coord(tr.x,tr.y+((br.y-tr.y)/2))
        bot_c=Coord(bl.x+((br.x-bl.x)/2),bl.y)

        #calc the center and edge_center heights
        avg=sum([self.grid.get(tl),
                self.grid.get(tr),
                self.grid.get(bl),
                self.grid.get(br)]
                )/4.0  ###NOTE, we can choose to use the current corners, the new edge-centers, or all
                #currenty we use the current corners
                #then do the edge centers
        offset=((random.random())-.5)*self.roughness 
        self.grid.make_new(center,avg+offset)

        #top_c
        avg=sum([self.grid.get(tl),
                self.grid.get(tr)]
                )/2.0
        offset=((random.random())-.5)*self.roughness
        self.grid.make_new(top_c,avg+offset)

        #left_c
        avg=sum([self.grid.get(tl),
                 self.grid.get(bl)]
                )/2.0
        offset=((random.random())-.5)*self.roughness
        self.grid.make_new(left_c,avg+offset)

        #right_c        
        avg=sum([self.grid.get(tr),
                 self.grid.get(br)]
                )/2.0
        offset=((random.random())-.5)*self.roughness
        self.grid.make_new(right_c,avg+offset)

        #bot_c
        avg=sum([self.grid.get(bl),
                 self.grid.get(br)]
                )/2.0
        offset=((random.random())-.5)*self.roughness
        self.grid.make_new(bot_c,avg+offset)

        self.generate_heightmap((tl,top_c,left_c,center),depth+1)
        self.generate_heightmap((top_c,tr,center,right_c),depth+1)
        self.generate_heightmap((left_c,center,bl,bot_c),depth+1)
        self.generate_heightmap((center,right_c,bot_c,br),depth+1)



if __name__ == '__main__':
    g_size=32 #//must be power of 2
    g=Grid(g_size+1,g_size+1)
    f=FractalHeightmap(g,1,10,max_depth=sqrt(g_size))
    g.render()

如果你直接运行这段代码，你应该能看到颜色图，并且能明白为什么它看起来不太对。把深度改成不同的2的幂次方，可以看到不同的效果——值在256及以上的生成会花费一些时间。

非常感谢任何帮助。

Answer 1

我自己解决了这个问题，经过一步一步地检查网格是如何构建的。

中心点的计算是错误的，

原来的写法是：center=Coord((tr.x-tl.x)/2,(br.y-tr.y)/2)

应该改成：

center=Coord(tl.x+((tr.x-tl.x)/2),tr.y+((br.y-tr.y)/2))

之前的写法忘记把子网格的起始位置的x和y坐标加到计算出的中点坐标上了。

Answer 2

抱歉这个话题有点跑题，但我想分享一个生成地形的不错算法。我开始使用这个算法是因为我发现自己不喜欢钻石和方形的方式。这里有个描述，下面是一个实现的代码：

#/usr/bin/python
#coding=UTF-8

import random,math

class HillGrid:

    def __init__(self,KRADIUS =(1.0/5.0),ITER=200,SIZE=40):
        self.KRADIUS = KRADIUS
        self.ITER = ITER
        self.SIZE = SIZE

        self.grid = [[0 for x in range(self.SIZE)] for y in range(self.SIZE)]

        self.MAX = self.SIZE * self.KRADIUS
        for i in range(self.ITER):
            self.step()

    def dump(self):
        for ele in self.grid:
            s = ''
            for alo in ele:
                s += '%s ' % str(alo)
            print s

    def __getitem__(self,n):
        return self.grid[n]

    def step(self):
        point = [random.randint(0,self.SIZE-1),random.randint(0,self.SIZE-1)]
        radius = random.uniform(0,self.MAX)

        x2 = point[0]
        y2 = point[1]    

        for x in range(self.SIZE):
            for y in range(self.SIZE):

                z = (radius**2) - ( math.pow(x2-x,2) + math.pow(y2-y,2) )
                if z >= 0:
                    self.grid[x][y] += int(z)


if __name__ == '__main__':
    h = HillGrid(ITER=50,SIZE = 20)
    h.dump()