0

我制作了一个简单的地形生成器，但是生成大于 50x50 的任何东西都需要花费大量时间。我可以做些什么来优化代码以便生成更大的东西吗？我知道 pygame 或 numpy 之类的东西可能更适合这样做，但在我的学校他们不会安装它们，所以这就是我必须使用的。

以下是相关代码：

def InitMap(self):
    aliveCells = []

    for x in range(self.width):
        for y in range(self.height):
            if random.random() < self.aliveChance:
                aliveCells.append(self.FindInGrid(x,y))

    return aliveCells

def GenerateMap(self):
    aliveCells = self.InitMap()
    shallowCells=[]

    self.count = 1
    for i in range(self.steps):
        aliveCells = self.DoGenStep(aliveCells)

    for i in aliveCells:
        self.canvas.itemconfig(i,fill="green")

    for i in aliveCells:
        for j in self.FindNeighbours(i):
            if j not in aliveCells:  self.canvas.itemconfig(i,fill="#0000FF")

def DoGenStep(self,oldAliveCells):
    newAliveCells = []
    for allCells in self.pos:
        for cell in allCells:

            self.root.title(str(round((self.count/(self.height*self.width)*100)/self.steps))+"%")
            self.count += 1

            aliveNeighbours = 0
            for i in self.FindNeighbours(cell):
                if i in oldAliveCells: aliveNeighbours += 1

            if cell in oldAliveCells:
                if aliveNeighbours < self.deathLimit:
                    pass
                else:
                    newAliveCells.append(cell)
            else:
                if aliveNeighbours > self.birthLimit:
                    newAliveCells.append(cell)

    return newAliveCells

def FindNeighbours(self,cell):
    cellCoords = self.GetCoords(cell) 
    neighbours = []

    for xMod in [-1,0,1]:
        x = xMod+cellCoords[0]
        for yMod in [-1,0,1]:
            y = yMod+cellCoords[1]

            if x < 0 or x >= self.width: pass
            elif y < 0 or y >= self.height: pass
            elif xMod == 0 and yMod == 0: pass
            else: neighbours.append(self.FindInGrid(x,y))

    return neighbours
4

1 回答 1

1

注意：你没有添加方法“FindInGrid”，所以我做了一些假设。如果我错了，请纠正我。

对于更大的地图以及在高密度的情况下，有一件非常有帮助的事情是不仅存储活细胞，还存储整个网格。通过存储活细胞，您可以按照 O( (x*y)^2) 的顺序执行程序的行为，因为您必须为每个活细胞迭代所有活细胞。如果您要存储整个网格，则没有必要这样做，并且可以使用与网格表面线性的时间复杂度而不是二次的时间复杂度来执行计算。

补充一点：

self.root.title(str(round((self.count/(self.height*self.width)*100)/self.steps))+"%")

这是一个字符串操作，这使得它相对昂贵。您确定每次更新单个单元格后都需要执行此操作吗？

于 2017-06-22T08:42:14.110 回答