Проблема случайного блуждания (Escape Recursion) - PullRequest
Новая
       8

Проблема случайного блуждания (Escape Recursion)

0 голосов
/ 01 мая 2011

В качестве практики и в качестве предшественника более сложного, более крупного проекта, который я имею в виду, я создал скрипт случайного блуждания с использованием модуля 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()

Кроме того, это на самом деле мое первое настоящее применение ООП, и мне было интересно, если это хороший способиспользуйте его.

Большое спасибо!

1 Ответ

2 голосов
/ 01 мая 2011

Если ваша случайная прогулка обнаружит, что она посетила каждую соседнюю ячейку, она зациклится навсегда.Поскольку вы используете рекурсию, она быстро превышает максимальный предел рекурсии.

Я уверен, что это может быть написано ООП, но проблема больше в том, что вы используете рекурсию, чем в том, полезен ли класс 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)
...