0

テトリス ゲームの一部の実装では、ランダム ジェネレーターと呼ばれるアルゴリズムがあり、次のアルゴリズムに基づいて片側テトロミノのセットの順列の無限シーケンスを生成します。

Random Generator は、袋から取り出したかのように、ランダムに並べ替えられた 7 つの片側テトロミノ (I、J、L、O、S、T、Z) のシーケンスをすべて生成します。次に、別のバッグを生成する前に、ピース シーケンスに 7 つのテトロミノすべてを処理します。

この無限シーケンスの要素は、必要な場合にのみ生成されます。つまり、7 つの片側テトロミノのランダム順列は、キューが提供できるよりも多くのピースが必要な場合に、テトロミノのキューに追加されます。

Python でこれを行うには、主に 2 つの方法があると思います。

最初の方法はitertools.permutations、random.choice

import itertools, random, collections
bag = "IJLOSTZ"
bigbag = list(itertools.permutations(bag))
sequence = collections.deque(random.choice(bigbag))
sequence.extend(random.choice(bigbag))
sequence.extend(random.choice(bigbag))
# . . . Extend as necessary

2 番目の方法では、 のみを使用しrandom.shuffleます。

import random, collections
bag = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']
random.shuffle(bag)
sequence = collections.deque(bag)
random.shuffle(bag)
sequence.extend(bag)
random.shuffle(bag)
sequence.extend(bag)
# . . . Extend as necessary

テトリスのプレイヤーが熟練しており、ランダム ジェネレーターが片側テトロミノの大量のシーケンスを生成する必要があると仮定すると、どちらの方法の長所と短所は何ですか?

4

2 に答える 2

2

小さなリストをシャッフルする時間はほんのわずかなので、心配する必要はありません。どちらの方法も「同様にランダム」であるべきであるため、そこに決定する根拠はありません。

しかし、リストと両端キューの両方をいじくりまわすのではなく、代わりにタイル ジェネレーターを使用します。

def get_tile():
    from random import shuffle
    tiles = list("IJLOSTZ")
    while True:
        shuffle(tiles)
        for tile in tiles:
            yield tile

短く、甘く、明白です。

ピーカブルにする

私は年をとっているので、「ピーカブルキュー」と聞くと「循環バッファ」を思い浮かべます。固定サイズのバッファに一度メモリを割り当て、ラップアラウンドするインデックス変数で「次の項目」を追跡します。もちろん、これは Python よりも C でより多くの利益をもたらしますが、具体性については次のようになります。

class PeekableQueue:
    def __init__(self, item_getter, maxpeek=50):
        self.getter = item_getter
        self.maxpeek = maxpeek
        self.b = [next(item_getter) for _ in range(maxpeek)]
        self.i = 0

    def pop(self):
        result = self.b[self.i]
        self.b[self.i] = next(self.getter)
        self.i += 1
        if self.i >= self.maxpeek:
            self.i = 0
        return result

    def peek(self, n):
        if not 0 <= n <= self.maxpeek:
            raise ValueError("bad peek argument %r" % n)
        nthruend = self.maxpeek - self.i
        if n <= nthruend:
            result = self.b[self.i : self.i + n]
        else:
            result = self.b[self.i:] + self.b[:n - nthruend]
        return result

q = PeekableQueue(get_tile())

したがって、 を介して次のタイルを消費し、 を介してポップされる次のタイルq.pop()のリストをいつでも取得できます。そして、このコードの速度がまったく違いを生むのに十分な速さの有機テトリスプレーヤーは宇宙にありません;-)nq.peek(n)

于 2013-11-02T21:41:55.520 に答える