Tìm đường Dijkstra

[tungsoul (thanh tung phan)]

mình muốn làm 1 cái NPC auto follow với auto đánh quái cho RPG, chả nghĩ ra cách nào cả nên dùng dijkstra cho NPC tìm đường. Nhưng mà cái algorithm này nọ chậm quá, tầm 300 nodes là lag tung cả lên. Ngồi 1 hồi thì cũng đỡ hơn tí nhưng mà cảm giác cái này nó còn nặng hơn cả cái game của mình. Ai có cách nào chỉ mình optimize với. Nếu không dc nữa thì đi học cái A* quá.

import heapq

class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.name = str(self.x) + ' ' + str(self.y)

    def __str__(self):
        return self.name

    def __lt__(self, other):
        return self.name < other.name

class Graph:
    def __init__(self):
        self.nodes = []

    def add_node(self, node):
        if node not in self.nodes:
            self.nodes.append(node)

    def remove_node(self, posi):
        node = self.find_node(posi)
        self.nodes.remove(node)

    def neighbor(self, node):
        result = dict()
        if node:
            n = self.find_node((node.x-32, node.y))
            if n:
                result[n] = 1
            n = self.find_node((node.x + 32, node.y))
            if n:
                result[n] = 1
            n = self.find_node((node.x, node.y - 32))
            if n:
                result[n] = 1
            n = self.find_node((node.x, node.y +32))
            if n:
                result[n] = 1
        return result

    def find_node(self, posi):
        for n in self.nodes:
            if n.x == posi[0] and n.y == posi[1]:
                return n
        return None

    def find_path(self, node1, node2):
        src = self.find_node(node1)
        dst = self.find_node(node2)
        result = []
        distance = {node: None for node in self.nodes}
        previous = {}
        distance[src] = 0
        nodes = []
        heapq.heapify(nodes)
        heapq.heappush(nodes, (distance[src], src))
        while nodes:
            current_node = heapq.heappop(nodes)[1]
            for node, weight in self.neighbor(current_node).items():
                if distance[node] == None or distance[node] > weight + distance[current_node]:
                    distance[node] = weight + distance[current_node]
                    previous[node] = current_node
                    heapq.heappush(nodes, (distance[node], node))
                    if current_node == dst:
                        nodes = []
                        break
        node = dst
        while node != src:
            node = previous[node]
            result.append(node)
        return result

[tntxtnt]

• tại sao Node __lt__ lại đi so sánh chuỗi? Sao ko so sánh x y :V (so sánh x y lẹ hơn chuyển thành chuỗi rồi so sánh)
• tại sao Graph nodes lại là list mà ko phải là set :V (list tìm kiếm O(n), set tìm kiếm O(1))
• tại sao neighbor(node) trả về dict mà ko trả về list :V :V (tạo dict chậm hơn tạo list rất nhiều)
• tại sao find_node lại có tham số là 1 tuple mà ko phải là 1 node :V (có cần thiết phải tạo class Node ko hay chỉ cần xài tuple (x,y) là đủ rồi?)
• heappq có phải là Dijkstra heap ko? :V Trong Dijkstra heap các giá trị key là duy nhất. Trong heappq các giá trị key có thể trùng lặp. Nếu chỉnh sửa heappq lại 1 tí có thể tăng tốc độ thêm chút xíu :V
• nếu đồ thị là đồ thị 2 chiều x y thì mỗi node đều có tối đa 4 neighbor, cần gì phải nhờ tới hàm find_node làm gì :V Ví dụ (0,0) có neighbor là (-1,0), (1,0), (0,-1), (0,1), vì -1 < 0 nên bỏ 2 neighbor (-1,0) và (0,-1), còn lại 2 neighbor hợp lệ. Ko cần find_node làm gì :V

[tungsoul (thanh tung phan)]

cảm ơn bác, mình vừa ngồi chỉnh lại giờ game mượt mà lắm rồi
cái đoạn heapq mình không hiểu lắm, mình xài python3 quen dùng PriorityQueue nhưng cái này python 2 nên mò trên mạng dc heapq
bác xem có thể optimize cái gì nữa không chỉ mình với, nhưng mà thực ra thế này chắc cũng nộp bài dc rồi
còn hàm neighbor mình vẫn check nó ở trong set ko vì sợ nó là cái blocker của game

import heapq

class Graph:
    def __init__(self):
        self.nodes = set()

    def neighbor(self, node):
        result = []
        if (node[0]-32, node[1]) in self.nodes:
            result.append((node[0]-32, node[1]))
        if (node[0]+32, node[1]) in self.nodes:
            result.append((node[0]+32, node[1]))
        if (node[0], node[1]-32) in self.nodes:
            result.append((node[0], node[1]-32))
        if (node[0], node[1]+32) in self.nodes:
            result.append((node[0], node[1]+32))
        return result

    def find_path(self, src, dst):
        result = []
        distance = {}
        previous = {}
        distance[src] = 0
        nodes = []
        heapq.heapify(nodes)
        heapq.heappush(nodes, (distance[src], src))
        while nodes:
            current_node = heapq.heappop(nodes)[1]
            for node in self.neighbor(current_node):
                if node not in distance or distance[node] > 1 + distance[current_node]:
                    distance[node] = 1 + distance[current_node]
                    previous[node] = current_node
                    heapq.heappush(nodes, (distance[node], node))
                    if current_node == dst:
                        nodes = []
                        break
        node = dst
        while node != src:
            result.append(node)
            node = previous[node]
        return result

[tntxtnt]

sợ nó là chướng ngại vật thì làm 1 cái map 2 chiều, map[y][x] = 0 nếu ko có chướng ngại vật, map[y][x] = 1 nếu có chướng ngại vật :V Viết hàm ktra (x,y) hợp lệ riêng: (x,y) hợp lệ khi 0 <= x < w và 0 <= y < h và map[y][x] == 0. Truy cập mảng 2 chiều có lẽ lẹ hơn set() :V

chuyển priority queue thành dijkstra heap cũng tương đối dễ: thêm 1 cái set visited

visited = set()
while nodes:
    current_node = heapq.heappop(nodes)[1]
    if current_node in visited: continue # đã hỏi thăm rồi
    for node in self.neighbor(current_node):
        if node not in visited and (node not in distance or distance[node] > 1 + distance[current_node]): # nếu neighbor_node này chưa được hỏi thăm và gì gì đó :V 
            ...
    visited.add(current_node) # hỏi thăm xong, oánh dấu nó trong danh sách đã hỏi thăm

mỗi node chỉ duyệt neighbor của nó 1 lần nên trước khi duyệt neighbor thì kiểm tra xem đã “hỏi thăm” nó chưa :V

vì đây là mảng 2 chiều, visited có thể là mảng 2 chiều mỗi ô có giá trị 0/1 luôn, lẹ hơn truy cập set :V