为过程性游戏内容生成六边形内的随机点

Question

我正在使用程序技术为我正在编写的游戏生成图形。

为了生成一些树木，我想在以<0,0>为中心的规则六边形区域内随机散布树木。

以统一的方式生成这些点的最佳方法是什么？

Answer 1

如果它是一个正六边形，想到的最简单的方法就是把它分成三个菱形。这样(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

Answer 2

如果你能为你的六边形找到一个好的矩形边界框，那么生成均匀随机点的最简单的方法就是拒绝采样(http://en.wikipedia.org/wiki/Rejection_sampling)。

也就是说，找到一个完全包含您的六边形的矩形，然后在该矩形内生成均匀的随机点(这很简单，只需为正确范围内的每个坐标独立生成随机值)。检查随机点是否落在六边形内。如果是，就保留它。如果不是，则绘制另一个点。

只要你能找到一个好的边界框(矩形的面积不应该大于它所包围的六边形的面积的一个常数)，这将是非常快的。

Answer 3

一种可能简单的方法如下：

    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的线性组合，并且使得

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。

因此，它将采取三个随机的数字调用来选择一个点，这可能是足够好的，取决于您的情况。