Python

Question

这是我的寻路功能：

def get_distance(x1,y1,x2,y2):
    neighbors = [(-1,0),(1,0),(0,-1),(0,1)]
    old_nodes = [(square_pos[x1,y1],0)]
    new_nodes = []
    for i in range(50):
        for node in old_nodes:
            if node[0].x == x2 and node[0].y == y2:
                return node[1]
            for neighbor in neighbors:
                try:
                    square = square_pos[node[0].x+neighbor[0],node[0].y+neighbor[1]]
                    if square.lightcycle == None:
                        new_nodes.append((square,node[1]))
                except KeyError:
                    pass
        old_nodes = []
        old_nodes = list(new_nodes)
        new_nodes = []
        nodes = []
    return 50

问题是 AI 需要很长时间才能响应（响应时间 <= 100 毫秒）这只是 python 做 https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm

的方法

Answer 1

您应该将您的算法替换为 A*-search，并将曼哈顿距离作为启发式算法。

Answer 2

一个相当快速的解决方案是实现 Dijkstra 算法（我已经在 that question 中实现）：

构建原始地图。这是一个掩码数组，walker 不能在掩码元素上行走：

%pylab inline
map_size = (20,20)
MAP = np.ma.masked_array(np.zeros(map_size), np.random.choice([0,1], size=map_size))
matshow(MAP)

下面是Dijkstra算法：

def dijkstra(V):
    mask = V.mask
    visit_mask = mask.copy() # mask visited cells
    m = numpy.ones_like(V) * numpy.inf
    connectivity = [(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1] if (not (i == j == 0))]
    cc = unravel_index(V.argmin(), m.shape) # current_cell
    m[cc] = 0
    P = {}  # dictionary of predecessors 
    #while (~visit_mask).sum() > 0:
    for _ in range(V.size):
        #print cc
        neighbors = [tuple(e) for e in asarray(cc) - connectivity 
                     if e[0] > 0 and e[1] > 0 and e[0] < V.shape[0] and e[1] < V.shape[1]]
        neighbors = [ e for e in neighbors if not visit_mask[e] ]
        tentative_distance = [(V[e]-V[cc])**2 for e in neighbors]
        for i,e in enumerate(neighbors):
            d = tentative_distance[i] + m[cc]
            if d < m[e]:
                m[e] = d
                P[e] = cc
        visit_mask[cc] = True
        m_mask = ma.masked_array(m, visit_mask)
        cc = unravel_index(m_mask.argmin(), m.shape)
    return m, P

def shortestPath(start, end, P):
    Path = []
    step = end
    while 1:
        Path.append(step)
        if step == start: break
        if P.has_key(step):
            step = P[step]
        else:
            break
    Path.reverse()
    return asarray(Path)

结果：

start = (2,8)
stop = (17,19)
D, P = dijkstra(MAP)
path = shortestPath(start, stop, P)
imshow(MAP, interpolation='nearest')
plot(path[:,1], path[:,0], 'ro-', linewidth=2.5)

下面是一些计时统计数据：

%timeit dijkstra(MAP)
#10 loops, best of 3: 32.6 ms per loop

Answer 3

您的代码最大的问题是您没有采取任何措施来避免多次访问相同的坐标。这意味着您访问的节点数保证呈指数增长，因为它可以在前几个节点上来回多次。

避免重复的最佳方法是维护我们添加到队列中的坐标的 set（尽管如果您的 node 值是可散列的，您也许可以添加它们直接到集合而不是坐标元组）。由于我们正在进行广度优先搜索，我们将始终通过（一条）最短路径到达给定坐标，因此我们永远不必担心以后会找到更好的路线。

尝试这样的事情：

def get_distance(x1,y1,x2,y2):
    neighbors = [(-1,0),(1,0),(0,-1),(0,1)]
    nodes = [(square_pos[x1,y1],0)]
    seen = set([(x1, y1)])
    for node, path_length in nodes:
        if path_length == 50:
            break
        if node.x == x2 and node.y == y2:
            return path_length
        for nx, ny in neighbors:
            try:
                square = square_pos[node.x + nx, node.y + ny]
                if square.lightcycle == None and (square.x, square.y) not in seen:
                    nodes.append((square, path_length + 1))
                    seen.add((square.x, square.y))
            except KeyError:
                pass
    return 50

我还稍微简化了循环。无需在每个深度之后切换列表，您可以只使用一个循环并在迭代较早的值时添加到其末尾。如果没有找到少于 50 步的路径（使用存储在 2 元组中的距离，而不是外循环的遍数），我仍然会中止。进一步的改进可能是对队列使用 collections.dequeue，因为您可以从一端高效地 pop，而从另一端 append。它可能不会产生很大的不同，但可能会避免一点内存使用。

我还避免了大部分由 1 和 0 进行的索引，以支持在 for 循环中解包为单独的变量名。我认为这更容易阅读，并且它避免了混淆，因为两种不同的二元组具有不同的含义（一个是 node, distance 元组，另一个是 x, y）。

Python - 加速寻路

Python - speed up pathfinding

path-finding