1

グリッドに数字があり、各数字が次第に小さいフォントになっているこの興味深いゲームがあります。プレーヤーのタスクは、数字を連続してクリックすることです。

数字のボックスを作成するアルゴリズムに興味がありますが、それが機能する方法が思いつきません。

どうやらグリッドには N 個の数字 (写真の 1.88 を除く) があり、数字の 1 が最大のフォントを持ち、フォント サイズが連続して小さくなります。次に、数字が何らかの方法でグリッドに配置され、ボックスがそれらの周りに成長します。しかし、グリッド全体を横切る水平線がいくつかあるため、完全にランダムに見えるわけではありません。

これがどのように機能するかについてのアイデアはありますか?

ここに画像の説明を入力

4

2 に答える 2

3

箱は連続して分割されて生成されたように見えます。つまり、完全な長方形から始めて、分割線 (水平または垂直) を配置し、ゲームに十分な長方形ができるまで、結果の 2 つの長方形を順番に細分割しました。

これは、私が試す最初のアルゴリズムのスケッチです。Nは、元の四角形を分割する四角形の数です。Aは、小さな四角形が狭くなりすぎるのを防ぐために使用される重要な縦横比です。(おそらく、A = 1.5 から始めるのがよいでしょう。)

  1. 空のプライオリティ キューを作成し、完全な四角形をそれに追加します。

  2. プライオリティ キューの長さがN以上の場合、停止します。

  3. 優先キューから最大の四角形Rを削除します。

  4. 水平に分割するか垂直に分割するかを選択します。アスペクト比 (幅/高さ) がAより大きい場合は、垂直に分割します。1/ A未満の場合は水平に分割し、それ以外の場合はランダムに選択します。

  5. 分割線をどこに入れるかを決めます。(おそらく、選択した次元に沿って 40% から 60% の間でランダムに)。

  6. これにより、Rが 2 つの小さな四角形に分割されます。両方を優先キューに追加します。ステップ 2 に進みます。

このアルゴリズムが完了すると、キューにはN 個の四角形があります。それらの最大のものに数字の 1 を入れ、2 番目に大きいものに数字の 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')

サンプル出力

于 2012-04-04T12:31:45.790 に答える
2

カットのパターンは再帰的に見えます。つまり、領域を四角形に分割するプロセスは、四角形を 2 つに分割する作業を繰り返します。長方形領域全体を分割する2 つのカット ( の上下の水平カット1) があるため、どちらのカットが最初に来たかはわかりませんが、カットは一種の木として見ることができます。その下 ( 、、、など) は、との間の垂直カットによって分割され、を含む長方形は、とを分離するカットによって後で分割されました。N 領域を生成する N カットと 1 つの残り物 ("1.88") があり、これは必要ではありませんが、手がかりになる可能性があります。11020214102144414

あとは、カットの順序、プロポーションの選択、向きの選択を理解するだけです。

連続した番号が隣り合うことはほとんどないため、カットが進むにつれて番号が割り当てられていないように見えます。代わりに、領域は長方形に細断され、長方形はサイズでソートされ、番号が割り当てられます (20と21は隣り合っていますが、それらを分割するカットの後の別のカットによって形成されていることに注意してください)。

カットの順序に関するもっともらしい仮説は、アルゴリズムが常に最大の長方形をカットするというものです。もしそうでなければ、例えば、14より大きなもの15や18結合したものを見るかもしれませんが、その例は見当たりません。

プロポーション… よく測るとプロポーションの分布が見えてきたのですが、あまりやりたくないですね。非常に長くて薄い長方形や 50/50 カットは見られないため、アルゴリズムは [0.6, 0.8] のような範囲でランダムに選択すると思います。おそらく、既存の長方形のサイズに非常に近い長方形を作成しないようにしようとします。すべてのカットの後、残るように選択された長方形 ("1.88") は、最大でも最小でもありません。ランダムかもしれませんし、2 番目に大きいかもしれませんし、別のものかもしれません。より多くの例が役に立ちます。

向きは、「縦方向」ではなく、狭い幅で長方形をカットする方向に強く偏っているようです。これにより、長方形がより正方形に近づき、棚の上の本のようにはなりません。私が見ることができる唯一の例外は1-9カットです。これは、右下の数字が1縦方向のブロックを分割する可能性があります。しかし、それは上下のカットの順序に依存するため1、仮説につながります。アルゴリズムは常に長方形をその短い方の次元に沿ってカットし、実際には1-カットが最初でした。9

定規と電卓を分解するまでは、私ができる限りのことです。

于 2012-04-04T12:35:12.330 に答える