Как отредактировать алгоритм поиска A *, чтобы найти только прямые ходы?

Question

Я нашел этот алгоритм, чтобы найти путь в 2D массива (source):

# Author: Christian Careaga (christian.careaga7@gmail.com) 
# A* Pathfinding in Python (2.7) 
# Please give credit if used 

import numpy 
from heapq import * 


def heuristic(a, b): 
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2 

def astar(array, start, goal): 

    neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)] 

    close_set = set() 
    came_from = {} 
    gscore = {start:0} 
    fscore = {start:heuristic(start, goal)} 
    oheap = [] 

    heappush(oheap, (fscore[start], start)) 

    while oheap: 

     current = heappop(oheap)[1] 

     if current == goal: 
      data = [] 
      while current in came_from: 
       data.append(current) 
       current = came_from[current] 
      return data 

     close_set.add(current) 
     for i, j in neighbors: 
      neighbor = current[0] + i, current[1] + j    
      tentative_g_score = gscore[current] + heuristic(current, neighbor) 
      if 0 <= neighbor[0] < array.shape[0]: 
       if 0 <= neighbor[1] < array.shape[1]:     
        if array[neighbor[0]][neighbor[1]] == 1: 
         continue 
       else: 
        # array bound y walls 
        continue 
      else: 
       # array bound x walls 
       continue 

      if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0): 
       continue 

      if tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1]for i in oheap]: 
       came_from[neighbor] = current 
       gscore[neighbor] = tentative_g_score 
       fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal) 
       heappush(oheap, (fscore[neighbor], neighbor)) 

    return False 

'''Here is an example of using my algo with a numpy array, 
    astar(array, start, destination) 
    astar function returns a list of points (shortest path)''' 

nmap = numpy.array([ 
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
    [1,1,1,1,1,1,1,1,1,1,1,1,0,1], 
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
    [1,0,1,1,1,1,1,1,1,1,1,1,1,1], 
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
    [1,1,1,1,1,1,1,1,1,1,1,1,0,1], 
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
    [1,0,1,1,1,1,1,1,1,1,1,1,1,1], 
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
    [1,1,1,1,1,1,1,1,1,1,1,1,0,1], 
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0]]) 

print astar(nmap, (0,0), (10,13)) 

Я полностью потерял в том, как это работает, но это работает, так что нормально. Но проблема в том, что этот алгоритм также использует 45 градусов, перемещается из одной строки в другую, например. (0,0) - (1,1), а не (0,0) -> (0, 1) -> (1,1). Это не очень хорошо для меня, так может кто-то сказать мне, как я могу отредактировать это, чтобы использовать только прямые ходы?

Answer 1

Список соседей определяет возможные ходы:

neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)] 

Если вы не хотите, чтобы диагональные ходы, использовать

neighbors = [(0,1),(0,-1),(1,0),(-1,0)]