0

在俄罗斯方块游戏的一些实现中，有一种称为随机生成器的算法，它基于以下算法生成一组单边四联骨牌的无限排列序列：

Random Generator 生成随机排列的所有七个单面四元骨牌（I、J、L、O、S、T、Z）的序列，就好像它们是从袋子里抽出来的一样。然后它在生成另一个袋子之前将所有七个四格骨牌处理到片段序列中。

这个无限序列的元素只在必要时生成。即，当需要的片数超过队列所能提供的数量时，将 7 个单面四联骨牌的随机排列附加到四联骨牌的队列中。

我相信在 Python 中有两种主要的方法可以做到这一点。

第一种方法使用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

第二种方法只使用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

简短，甜美，明显。

让它可窥视

由于我老了，当我听到“可窥视队列”时，我会想到“循环缓冲区”。为固定大小的缓冲区分配一次内存，并使用环绕的索引变量跟踪“下一项”。当然，这在 C 中比在 Python 中得到的回报要多得多，但是为了具体：

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()，并且在任何时候您都可以获得将通过 弹出的下一个n图块的列表。并且在宇宙中没有有机俄罗斯方块播放器的速度足以让这段代码的速度产生任何影响；-)q.peek(n)

于 2013-11-02T21:41:55.520 回答
1

有7! = 50407 个不同对象的序列的排列。因此，就时间复杂度 (O(n!*n)) 和空间复杂度 (O(n!*n)) 而言，生成所有排列都是非常昂贵的。然而，从排列序列中选择随机排列很容易。让我们看一下choicefrom的代码random.py。

def choice(self, seq):
    """Choose a random element from a non-empty sequence."""
    return seq[int(self.random() * len(seq))]  # raises IndexError if seq is empty

如您所见，索引的计算是 O(1)，因为len(seq)对于任何序列都是 O(1)，self.random()也是 O(1)。在 Python 中从列表类型中获取元素也是 O(1)，因此整个函数是 O(1)。

另一方面，使用random.shuffle将就地交换包中的元素。因此它将使用 O(1) 空间复杂度。然而，就时间复杂度而言，它并不是那么有效。让我们看一下shufflefrom的代码random.py

def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

random.shuffle实现了费舍尔-耶茨洗牌，“类似于从帽子中随机挑选编号的票，或者从一副牌中随机挑选一张牌，直到没有更多的牌。” 然而，计算次数明显大于第一种方法，因为必须进行len(x)-1调用，并且还需要交换操作。每个交换操作需要从列表中提取 2 次，并生成一个 2 元组用于解包和分配。random()len(x)-1

基于所有这些信息，我猜想提到的第一种方法会占用大量内存来存储排列并且需要 O(n!*n) 时间复杂度开销，但从长远来看，它可能效率更高与第二种方法相比，并且可能会在俄罗斯方块游戏的实际实现中保持帧速率稳定，因为在实际游戏循环期间要做的计算更少。甚至可以在显示器初始化之前生成排列，这很好地给人一种你的游戏没有执行很多计算的错觉。

在这里，我使用 Tim Peters 对生成器和循环缓冲区的建议发布了最终代码。由于循环缓冲区的大小在缓冲区创建之前是已知的，并且永远不会改变，因此我没有实现循环缓冲区通常具有的所有功能（您可以在Wikipedia 文章中找到）。在任何情况下，它都非常适合 Random Generator 算法。

def random_generator():
    import itertools, random
    bag = "IJLOSTZ"
    bigbag = list(itertools.permutations(bag))
    while True:
        for ost in random.choice(bigbag):
            yield ost


def popleft_append(buff, start_idx, it):
    """ This function emulates popleft and append from
        collections.deque all in one step for a circular buffer
        of size n which is always full,
        The argument to parameter "it" must be an infinite 
        generator iterable, otherwise it.next() may throw
        an exception at some point """
    left_popped = buff[start_idx]
    buff[start_idx] = it.next()
    return (start_idx + 1) % len(buff), left_popped


def circular_peek(seq, start_idx):
    return seq[start_idx:len(seq)] + seq[:start_idx]


# Example usage for peek queue of size 5
rg = random_generator()
pqsize = 5
# Initialize buffer using pqsize elements from generator
buff = [rg.next() for _ in xrange(pqsize)]
start_idx = 0
# Game loop
while True:
    # Popping one OST (one-sided tetromino) from queue and 
    # adding a new one, also updating start_idx
    start_idx, left_popped = popleft_append(buff, start_idx, rg)
    # To show the peek queue currently
    print circular_peek(buff, start_idx)
于 2013-11-02T21:16:43.980 回答