Поиск в ширину со списком координат python - PullRequest
Новая
       14

Поиск в ширину со списком координат python

0 голосов
/ 26 февраля 2019

Я строю простой ИИ для «игры в паука» (почти такая же концепция, как в игре со змеями, но движущаяся логика немного отличается).Я пытаюсь реализовать алгоритм BFS так, чтобы паук нашел путь, который ведет его к муравью.Алгоритм, кажется, работает в течение нескольких итераций, но когда я запускаю его вне отладчика, он получает значение None внутри node_list, что приводит к сбою других методов (поскольку вы не можете получить следующий шаг ни для чего).

Это алгоритм BFS: 

def BFS(spider_state, ant_state):
    goal = False
    count = 0
    initial_node = Node(spider_state, None, 0)
    node_list = [initial_node]
    initial_ant_state = ant_state

    while goal == False or len(node_list) == 0:
        e = node_list.pop(0)
        future_ant_state = initial_ant_state
        for i in range(0, e.depth):
            future_ant_state = get_next_ant_move(border_choice, initial_ant_state)
        for move in POSSIBLE_MOVES:
            count += 1
            next_node = Node(None, None, None)
            next_node.state = get_next_spider_move(deepcopy(e.state), move)
            next_node.parent = e
            next_node.depth = e.depth + 1
            if next_node.state == future_ant_state:
                goal = True
                break
            else:
                node_list.append(next_node)
    return node_list

Узел: 

class Node():
    def __init__(self, state, parent, depth):
        self.state = state
        self.parent = parent
        self.depth = depth

Паук и муравей представлены в виде простого списка x и y позиций: 

spider = [15, 35]
ant = [20, 10]

Методы get next move выглядят так: 

def get_next_spider_move(spidy, move):
    if spidy:
        # check the bounds and assign the new value to spidy
        spidy = spider_bounds(spidy)
        # farthest right
        if move == 0:
            spidy[1] += 2
            spidy[0] -= 1
        # furhter up and right
        if move == 1:
            spidy[1] += 1
            spidy[0] -= 2
        # backwords
        if move == 2:
            spidy[0] += 1
        # farthest left
        if move == 3:
            spidy[1] -= 2
            spidy[0] -= 1
        # furhter up and to the left
        if move == 4:
            spidy[1] += 1
            spidy[0] -= 2
        # one left
        if move == 5:
            spidy[1] -= 1
        # one right
        if move == 6:
            spidy[1] -= 1
        # side right
        if move == 7:
            spidy[1] += 1
            spidy[0] += 1
        # side left
        if move == 8:
            spidy[1] -= 1
            spidy[0] -= 1
        else:
            # if no valid direction was given
            return spidy
    else:
        raise ValueError('spidy must contain an x and y position. %s',  spidy, ' was found')

Результирующая ошибка при запуске: 

    File "spider_game_bfs.py", line 141, in <module>
    path = BFS(spider, ant)
  File "spider_game_bfs.py", line 130, in BFS
    next_node.state = get_next_spider_move(deepcopy(e.state), move)
  File "spider_game_bfs.py", line 100, in get_next_spider_move
    raise ValueError('spidy must contain an x and y position. %s',  spidy, ' was found')
ValueError: ('spidy must contain an x and y position. %s', None, ' was found')

1 Ответ

0 голосов
/ 26 февраля 2019

У вас логическая ошибка в нижней части функции перемещения.Последний полный оператор: 

    if move == 8:
        spidy[1] -= 1
        spidy[0] -= 1
    else:
        # if no valid direction was given
        return spidy

Ваш комментарий неверен: предложение else выполняется любым ходом , отличным от , отличным от 8. Если ход равен 8, затем вы возвращаете None, так как вы пропустили оператор, который возвращает spidy.

Как упоминалось в первом комментарии, вам будет лучше с if ... elif ... else в качестве логической структуры.Более того, следуйте многочисленным онлайн-примерам для перемещения предмета: составьте список или диктуйте ходы, что-то вроде этого: 

move_dir = [
    (-1, +2),  # move 0
    (-2, +1),  # move 1
    (+1,  0),  # move 2
    ...        # fill in the rest
]

if move in range(len(move_dir)):
    spidy[0] += move_dir[move[0]]
    spidy[1] += move_dir[move[1]]
    return spidy
else:
    raise ValueError ...
...