python - 创建一个具有对象之间链接的类似迷宫的游戏

Question

我正在编写一个基于文本的角色扮演游戏，它将根据以下规则创建自己的洞穴系统:

1. 它必须随机生成链接

2. 一个洞穴只能与另一个洞穴链接一次

3. 每个洞穴总共必须有四个链接

这是我到目前为止所拥有的:

import random

class Game(object):
    def __init__(self):
        self.caves = []

    def main(self):
        self.createCaves()
        Caves.setLinks(self)

    def createCaves(self):
        self.caves.append(StartCave())
        number_of_caves = random.randrange(10)+5
        for cave in range(1,((number_of_caves) if number_of_caves%2 != 0 else (number_of_caves+1))):
            self.caves.append(NormCave())
        self.caves.append(EndCave())

class Caves(Game):
    def __init__(self):
        self.events = 3
        self.links = []

    def setLinks(self):
        possible = self.caves
        while True:
            for cave in possible:
                while len(cave.links) != 4:
                    link = possible[random.randint(0,(len(possible)-1))]
                    while len(link.links) == 4 or link == cave or cave in link.links:
                        link = possible[random.randint(0,(len(possible)-1))]
                    cave.links.append(link)
                possible.remove(cave)

class StartCave(Caves):
    def __init__(self):
        self.events = 3
        self.links = []

class EndCave(Caves):
    pass
#    def __init__(self):
#        pass

class NormCave(Caves):
    pass
#    def __init__(self):
#        pass

B = Game()
B.main()

经过setLinks函数多次迭代后，名为possible的数组仅包含一个洞穴，因此它无法创建更多链接，并且剩下的洞穴没有链接到任何其他洞穴。它应该做的是在洞穴之间创建 4 个随机链接，将这些链接存储在其 links 数组中，然后移动到下一个链接少于 4 个的洞穴。

Answer 1

这是一个相当简单的暴力算法。我们使用集合来保存每个洞穴的链接。 make_links 函数尝试为每个洞穴分配 4 个随机双向链接。如果失败，它将返回 None，我们只需再次调用它，直到获得有效的洞穴系统。

from random import seed, choice

def make_caves(num):
    caves = None
    while caves is None:
        caves = make_links(num)
    return caves

def make_links(num):
    numrange = range(num)
    rset = set(numrange)

    caves = [set() for _ in numrange]
    for i in numrange:
        others = list(rset - set([i]) - caves[i])
        while len(caves[i]) < 4:
            if not others:
                return None
            x = choice(others)
            others.remove(x)
            if len(caves[x]) == 4:
                continue
            caves[x].add(i)
            caves[i].add(x)
    return caves

# Test

seed(13)
num = 12
numrange = range(num)

caves = make_caves(num)

for i in numrange:
    print(i, caves[i])
print()

for i in numrange:
    row = ''.join(['* ' if j in caves[i] else '. ' for j in numrange])
    print('{:>2} {}'.format(i, row))

典型输出

0 {9, 3, 5, 6}
1 {8, 9, 4, 5}
2 {9, 11, 4, 6}
3 {0, 8, 10, 5}
4 {1, 2, 9, 7}
5 {0, 1, 3, 11}
6 {0, 10, 2, 11}
7 {8, 10, 11, 4}
8 {1, 10, 3, 7}
9 {0, 1, 2, 4}
10 {8, 3, 6, 7}
11 {2, 5, 6, 7}

 0 . . . * . * * . . * . . 
 1 . . . . * * . . * * . . 
 2 . . . . * . * . . * . * 
 3 * . . . . * . . * . * . 
 4 . * * . . . . * . * . . 
 5 * * . * . . . . . . . * 
 6 * . * . . . . . . . * * 
 7 . . . . * . . . * . * * 
 8 . * . * . . . * . . * . 
 9 * * * . * . . . . . . . 
10 . . . * . . * * * . . . 
11 . . * . . * * * . . . . 

网格的每行每列都有 4 个星号，这表明我们每个洞穴有 4 个双向链接。