Python - ускорить алгоритм поиска траектории звезды

Я закодировал свой первый слегка сложный алгоритм, реализацию алгоритма Star Pathfinding. Я последовал за советом Python.org по внедрению графов, поэтому словарь содержит все узлы, каждый из которых связан с node. Теперь, поскольку это все для игры, каждый node на самом деле является просто черепицей в сетке узлов, поэтому я разрабатываю эвристику и мою случайную ссылку на них.

Благодаря timeit я знаю, что я могу успешно запустить эту функцию чуть более ста раз в секунду. Понятно, что это меня немного волнует, это без каких-либо других "игровых вещей", таких как графика или расчет игровой логики. Поэтому я хотел бы узнать, сможет ли кто-нибудь из вас ускорить мой алгоритм, я совершенно не знаком с Cython или его родственником, я не могу закодировать строку C.

Без каких-либо дополнительных функций, вот моя функция A Star.

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path

Ответы

Ответ 1

Легкая оптимизация заключается в использовании наборов вместо списков для открытых и закрытых множеств.

openSet   = set()
closedSet = set()

Это сделает все теги in и not in проверяет O (1) вместо O (n).

Ответ 2

Я бы использовал множество, как было сказано, но я бы также использовал кучу, чтобы найти минимальный элемент (тот, который будет следующим current). Это потребует сохранения как openSet, так и openHeap, но память не должна быть проблемой. Кроме того, устанавливает вставки в O (1) и кучи в O (log N), чтобы они были быстрыми. Единственная проблема заключается в том, что модуль heapq на самом деле не предназначен для использования с ним ключей. Лично я бы просто изменил его, чтобы использовать ключи. Это не должно быть очень сложно. Кроме того, вы можете просто использовать кортежи (tile.H, tile) в куче.

Кроме того, я бы выполнил aaronasterling идею использования итерации вместо рекурсии, но также, я бы добавил элементы в конец path и обратный path в конце. Причина в том, что вставка элемента на 0-е место в списке происходит очень медленно, (полагаю, O (N)), а при добавлении - O (1), если я правильно помню. Конечным кодом для этой части будет:

def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

Я положил путь возврата в конец, потому что оказалось, что это должно быть из вашего кода.

Здесь конечный код с использованием наборов, кучи, а что нет:

import heapq


def aStar(graph, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()

    def retracePath(c):
        path = [c]
        while c.parent is not None:
            c = c.parent
            path.append(c)
        path.reverse()
        return path

    openSet.add(current)
    openHeap.append((0, current))
    while openSet:
        current = heapq.heappop(openHeap)[1]
        if current == end:
            return retracePath(current)
        openSet.remove(current)
        closedSet.add(current)
        for tile in graph[current]:
            if tile not in closedSet:
                tile.H = (abs(end.x - tile.x)+abs(end.y-tile.y))*10
                if tile not in openSet:
                    openSet.add(tile)
                    heapq.heappush(openHeap, (tile.H, tile))
                tile.parent = current
    return []

Ответ 3

Как указано выше, сделайте closedSet в набор.

Я пробовал кодирование openList как кучу import heapq:

import heapq

def aStar(self, graph, current, end):
    closedList = set()
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList = [(-1, current)]
    heapq.heapify(openList)
    while openList:
        score, current = openList.heappop()
        if current == end:
            return retracePath(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.heappush((tile.H, tile))
                tile.parent = current
    return path

Однако вам все равно нужно искать в if tile not in openList, поэтому я бы сделал следующее:

def aStar(self, graph, current, end):
    openList = set()
    closedList = set()

    def retracePath(c):
        def parentgen(c):
             while c:
                 yield c
                 c = c.parent
        result = [element for element in parentgen(c)]
        result.reverse()
        return result

    openList.add(current)
    while openList:
        current = sorted(openList, key=lambda inst:inst.H)[0]
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                openList.add(tile)
                tile.parent = current
    return []