파이썬이 내 길 찾기 기능입니다

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의 응답을 오래하는 데 걸리는입니다 (응답 시간 < = 100ms의) 이 일을 그냥 파이썬 방법입니다 https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm

Answer 1

알고리즘을 휴먼리스 (Heuristic)로 사용하여 A*-search으로 바꾸어야합니다.

원래지도를 구축 :

Answer 2

한 합리적으로 빠른 해결책은 (이미 that question에서 구현 한 것을) 익스트라 알고리즘을 구현하는 것입니다.

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) 

%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) 

다음

이 다 익스트라 알고리즘 : 그것은 워커 마스크 요소에 걸을 수있는 마스크 배열입니다

일부 타이밍 통계 아래 617,451,515,

는 :

%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-tuple에 저장된 거리를 사용한다.) 추가 개선 사항은 큐에 collections.dequeue을 사용하는 것일 수 있습니다. 한쪽 끝에서 pop을 효율적으로 처리 할 수 ​​있고 다른 쪽 끝에서 append 끝낼 수 있기 때문입니다. 아마도 큰 차이는 없지만 약간의 메모리 사용은 피할 수 있습니다.

for 루프에서 별도의 변수 이름으로 압축을 풀기 위해 대부분의 색인 생성을 1과 0으로 피할 수있었습니다. 두 개의 다른 튜플이 다른 의미를 가졌기 때문에 혼동을 피할 수 있습니다 (하나는 node, distance 튜플이고 다른 하나는 x, y입니다).