有一个有趣的游戏,在网格中有数字,每个数字的字体逐渐变小。玩家的任务是连续点击数字。
我对为数字创建框的算法感兴趣,我想不出它的工作方式。
显然网格有 N 个数字(除了图中的 1.88),数字 1 的字体最大,字体大小依次减小。然后以某种方式将数字放置在网格上,并在它们周围增长盒子。但它似乎并不完全随机,因为有一些水平线穿过整个网格。
你知道这可能如何工作吗?
在我看来,这些盒子好像是通过连续划分生成的。即从整个矩形开始,放置一条分割线(水平或垂直),然后将得到的两个矩形依次细分,直到有足够的矩形供游戏使用。
这是我将尝试的第一个算法的草图。N是我想将原始矩形划分成的矩形数量,A是用于阻止小矩形变得太窄的关键纵横比。(也许A = 1.5 会是一个好的开始。)
创建一个空的优先级队列并将整个矩形添加到其中。
如果优先队列的长度大于或等于N,则停止。
从优先级队列中删除最大的矩形R 。
选择是水平分割还是垂直分割:如果它的纵横比(宽/高)大于A,则垂直分割;如果小于 1/ A,则将其水平划分,否则随机选择。
决定在哪里放置分界线。(可能沿所选维度随机介于 40% 和 60% 之间。)
这将R分成两个较小的矩形。将它们都添加到优先级队列中。转到第 2 步。
当这个算法完成时,队列中有N个矩形。将数字 1 放在其中最大的位置,将数字 2 放在第二大的位置,依此类推。
事实证明,将数字放入框中并不像我第一次尝试时想象的那么简单。面积度量可以很好地细分矩形,但它不适用于将数字放入框中,因为要将文本放入框,高度和宽度都必须考虑(面积不是这样)有用)。
我不会解释将数字放入框中的算法,而是给你一些 Python 示例代码,让你对其进行逆向工程!
import heapq, itertools, random
import Image, ImageDraw, ImageFont
# ALGORITHM PARAMETERS
aspect_max = 1.5 # Above this ratio, always divide vertically
aspect_min = 1.0 # Below this ratio, always divide horizontally
div_min = 0.4 # Minimum position for dividing line
div_max = 0.6 # Maximum position for dividing line
digit_ratio = 0.7 # Aspect ratio of widest digit in font
label_margin = 2 # Margin around label (pixels)
class Rectangle(object):
def __init__(self, x, y, w, h):
self.x = x
self.y = y
self.w = w
self.h = h
self.area = self.w * self.h
self.aspect = float(self.w) / self.h
def __le__(self, other):
# The sense of this comparison is inverted so we can put
# Rectangles into a min-heap and be able to pop the largest.
return other.area <= self.area
def __repr__(self):
return 'Rectangle({0.x}, {0.y}, {0.w}, {0.h})'.format(self)
def divide(self, n):
"""
Divide this rectangle into `n` smaller rectangles and yield
them in order by area (largest first).
"""
def division(l):
return random.randrange(int(l * div_min), int(l * div_max))
queue = [self]
while len(queue) < n:
r = heapq.heappop(queue)
if (r.aspect > aspect_max
or r.aspect > aspect_min
and random.random() < 0.5):
# Vertical division
w = division(r.w)
heapq.heappush(queue, Rectangle(r.x, r.y, w, r.h))
heapq.heappush(queue, Rectangle(r.x + w, r.y, r.w - w, r.h))
else:
# Horizontal division
h = division(r.h)
heapq.heappush(queue, Rectangle(r.x, r.y, r.w, h))
heapq.heappush(queue, Rectangle(r.x, r.y + h, r.w, r.h - h))
while queue:
yield heapq.heappop(queue)
def font_height(self, n):
"""
Return the largest font height such that we can draw `n`
digits in this rectangle.
"""
return min(int((self.w - label_margin * 2) / (digit_ratio * n)),
self.h - label_margin * 2)
def draw_rectangles(rectangles, fontfile):
"""
Create and return an Image containing `rectangles`. Label each
rectangle with a number using the TrueType font in `fontfile`.
"""
rectangles = list(rectangles)
im = Image.new('RGBA', (1 + max(r.x + r.w for r in rectangles),
1 + max(r.y + r.h for r in rectangles)))
draw = ImageDraw.Draw(im)
for digits in itertools.count(1):
rectangles = sorted(rectangles,
key = lambda r: r.font_height(digits),
reverse = True)
i_min = 10 ** (digits - 1)
i_max = 10 ** digits
i_range = i_max - i_min
for i in xrange(i_range):
if i >= len(rectangles): return im
r = rectangles[i]
draw.line((r.x, r.y, r.x + r.w, r.y, r.x + r.w, r.y + r.h,
r.x, r.y + r.h, r.x, r.y),
fill = 'black', width = 1)
label = str(i + i_min)
font = ImageFont.truetype(fontfile, r.font_height(digits))
lw, lh = font.getsize(label)
draw.text((r.x + (r.w - lw) // 2, r.y + (r.h - lh) // 2),
label, fill = 'black', font = font)
rectangles = rectangles[i_range:]
这是一个示例运行:
>>> R = Rectangle(0, 0, 400, 400)
>>> draw_rectangles(R.divide(30), '/Library/Fonts/Verdana.ttf').save('q10009528.png')
切割的模式看起来是递归的。也就是说,将区域划分为矩形的过程包括将矩形一分为二,一遍又一遍。有两个切口将整个矩形区域分开(上方和下方的水平切口1
),因此我们无法判断哪个切口先出现,但我们将切口视为一种树:分开的切口1
产生10
了一个大矩形在它下面(20
、21
、4
、10
等),然后被 和 之间的垂直切割分割21
,4
包含的矩形4
后来被分隔4
和的切割分割14
,依此类推。有 N 个切割产生 N 个区域加上一个剩余区域(“1.88”),这不是必需的,但可能会给我们一个线索。
现在我们只需要弄清楚切割的顺序,比例的选择和方向的选择。
连续的数字很少是邻居,所以看起来好像没有随着切割的进行分配数字。相反,该区域被切成矩形,矩形按大小排序,然后分配数字(注意20
和21
是相邻的,但它们是由分割它们之后的其他切割形成的)。
切割顺序的一个合理假设是算法总是切割最大的矩形。如果这不是真的,我们可能会看到,例如,14
大于15
和18
合并,我看不到这样的例子。
比例...通过仔细测量,我们可以看到比例的实际分布,但我不想做那么多工作。我们没有看到很长、很细的矩形,也没有 50/50 的切割,所以我猜测算法是随机选择的,在 [0.6, 0.8] 这样的范围内。也许它试图避免使矩形非常接近已经存在的矩形的大小。在所有切割之后,选择留下的矩形(“1.88”)既不是最大的也不是最小的;也许它是随机的,也许它是第二大的,也许是别的东西——更多的例子会很有用。
方向似乎强烈倾向于在其狭窄宽度上切割矩形,而不是“纵向”。这具有产生更像正方形而不像书架上的书的矩形的效果。我能看到的唯一可能的例外是1
-9
切割,它可能会分割右下角数字为1
纵向的块。但这取决于上方和下方的切割顺序1
,因此它会导致一个假设:算法总是沿其较短的维度切割一个矩形,而1
-9
切割实际上是第一个。
这大概是我能做到的,没有打破尺子和计算器。