随机行走问题（逃逸递归）

Question

作为练习，作为一个更复杂，更大的项目的先驱，我记住，我已经使用Turtle模块创建了一个随机行走脚本。我意识到有更简单的方法来做随机游走而无需找到相邻的坐标，但据我所知，这对于较大的实现是必要的。

我遇到的问题是，当python发现它已经访问了getnext()函数中的每个相邻单元时，它正在达到其最大递归深度。我不确定我会如何逃脱那个循环，并且如果发生这种情况，将继续照常进行。

import turtle 
import random 




class cell(object): 
def __init__(self, pos, visited = False): 
    self.xCoord = pos[0] 
    self.yCoord = pos[1] 
    self.visited = visited 
    self.neigh = [] 
    self.neighbors = self.getneighbors() 

def getneighbors(self): 
    for j in (-1, 0, 1): 
     for i in (-1, 0, 1): 
      self.neigh.append((self.xCoord+i, self.yCoord+j)) 



def getnext(): 
    nextindex = random.randint(0, len(c.neigh)-1) 
    nextcoordt = c.neigh[nextindex] 
    nextcoord = list(c.neigh[nextindex]) 
    if nextcoordt in coords: 
     getnext() 
    else: 
     turtle.goto(nextcoord[0], nextcoord[1]) 



coords = {} 

turtle.setup(width =200, height = 200, startx = 0, starty = 0) 
turtle.trace = False 

for i in range(1000): 
    c = cell(list(turtle.pos())) 
    coords[turtle.pos()] = (c) 
    getnext() 

此外，这实际上是我的第一个真正的应用程序的OOP，我想知道这是否是一个很好的方式来使用它。

非常感谢！

Answer 1

如果你的随机游走发现它已经访问了每个相邻的单元格，它将永远循环。由于您正在使用递归，它很快就会超过最大递归限制。

我确定这可以用OOP方式编写，但问题在于使用递归比使用cell类更有用。例如，我简化了代码以线性方式运行。更改如下：

• 消除（0，0）方向，因为它没有进展。 （根据您的目标可选，即如果您认为“保持投入”有效举动）。使用random.choice()来挑选下一步的方向。
• 删除递归，以便通过将方向向量添加到当前位置来计算下一个坐标。一个简单的循环就足够了。
• 由于返回先前空间对随机性完全有效，因此不会检查下一个仓位与最近仓位历史的位置。

代码：

import itertools 
import random 
import turtle 

# change step size if you like 
STEP = 1 
PTS = [-STEP, 0, STEP] 
DIRS = [(x, y) for x in PTS for y in PTS if x or y] 

turtle.setup(width=400, height=400, startx=0, starty=0) 
turtle.trace = False 
pos = turtle.pos() 

for i in range(1000): 
    px, py = turtle.pos() 
    # direction of next move 
    xd, yd = random.choice(DIRS) 
    # set pos to current pos + direction vector 
    turtle.goto(px + xd, py + yd)