mik*_*era 9 language-agnostic random algorithm procedural-generation
我正在使用程序技术为我正在编写的游戏生成图形.
为了生成一些树林,我想在以<0,0>为中心的正六边形区域内随机散布树木.
以统一的方式生成这些点的最佳方法是什么？
Aar*_*ron 13
如果你能为六边形找到一个好的矩形边界框,那么生成均匀随机点的最简单方法就是拒绝采样(http://en.wikipedia.org/wiki/Rejection_sampling)
也就是说,找到一个完全包含六边形的矩形,然后在矩形内生成均匀的随机点(这很容易,只需为右边的每个坐标独立生成随机值).检查随机点是否落在六边形内.如果是,请保留它.如果不是,请提出另一点.
只要你能找到一个好的边界框(矩形的面积不应该大于它所包围的六边形面积的常数因子),这将是非常快的.
小智 8
一个可能简单的方法如下:
F ____ B
/\ /\
A /__\/__\ E
\ /\ /
\/__\/
D C
考虑平行四边形ADCO(中心为O)和AOBF.
其中的任何一点都可以写成两个矢量AO和AF的线性组合.
这两个平行四边形中的点P满足
P = x*AO + y*AF或x AO + y AD.
其中0 <= x <1且0 <= y <= 1(我们对与BECO共享的边缘进行折扣).
类似地,平行四边形BECO中的任何点Q可以被写为矢量BO和BE的线性组合,使得
Q = x BO + y BE其中0 <= x <= 1且0 <= y <= 1.
从而选择一个随机点
我们选择
A概率为2/3,B概率为1/3.
如果选择了A,则选择[0,1]中的x(注意,半开区间[0,1))和[-1,1]中的y,如果y> 0 ,则选择点P = x AO + y AF选择P = x*AO + | y |*AD.
如果选择了B,请选择[0,1]中的x和[0,1]中的y,然后选择点Q = x BO + y BE.
因此,需要三个随机数调用来选择一个点,这可能足够好,具体取决于您的情况.
如果它是正六边形,最简单的方法就是把它分成三个菱形.这样(a)它们具有相同的区域,并且(b)你可以在任何一个菱形中选择一个随机点,其中包含0到1的两个随机变量.这是一个有效的Python代码.
from math import sqrt
from random import randrange, random
from matplotlib import pyplot
vectors = [(-1.,0),(.5,sqrt(3.)/2.),(.5,-sqrt(3.)/2.)]
def randinunithex():
x = randrange(3);
(v1,v2) = (vectors[x], vectors[(x+1)%3])
(x,y) = (random(),random())
return (x*v1[0]+y*v2[0],x*v1[1]+y*v2[1])
for n in xrange(500):
v = randinunithex()
pyplot.plot([v[0]],[v[1]],'ro')
pyplot.show()
讨论中的几个人提出了均匀采样离散版六边形的问题.最自然的离散化是三角形格子,并且上述解决方案的一个版本仍然有效.您可以稍微修剪菱形,使它们各自包含相同数量的点.他们只是错过了原点,必须作为一个特例单独允许.这是一个代码:
from math import sqrt
from random import randrange, random
from matplotlib import pyplot
size = 10
vectors = [(-1.,0),(.5,sqrt(3.)/2.),(.5,-sqrt(3.)/2.)]
def randinunithex():
if not randrange(3*size*size+1): return (0,0)
t = randrange(3);
(v1,v2) = (vectors[t], vectors[(t+1)%3])
(x,y) = (randrange(0,size),randrange(1,size))
return (x*v1[0]+y*v2[0],x*v1[1]+y*v2[1])
# Plot 500 random points in the hexagon
for n in xrange(500):
v = randinunithex()
pyplot.plot([v[0]],[v[1]],'ro')
# Show the trimmed rhombuses
for t in xrange(3):
(v1,v2) = (vectors[t], vectors[(t+1)%3])
corners = [(0,1),(0,size-1),(size-1,size-1),(size-1,1),(0,1)]
corners = [(x*v1[0]+y*v2[0],x*v1[1]+y*v2[1]) for (x,y) in corners]
pyplot.plot([x for (x,y) in corners],[y for (x,y) in corners],'b')
pyplot.show()
这是一张照片.
alt text http://www.freeimagehosting.net/uploads/0f80ad5d9a.png
