title: How could I use Euclidean Distance formula to calculate the heuristic here? and make the algorithm searches in eight directions?
body: <p>I'm working on A star algorithm and I set my heuristic as below : </p>
  
  <pre><code>heuristic = [[9, 8, 7, 6, 5, 4],
               [8, 7, 6, 5, 4, 3],
               [7, 6, 5, 4, 3, 2],
               [6, 5, 4, 3, 2, 1],
               [5, 4, 3, 2, 1, 0]]
  </code></pre>
  
  <p>And the movement of the algorithm just for four directions as below:</p>
  
  <pre><code>delta = [[-1, 0 ], # go up
           [ 0, -1], # go left
           [ 1, 0 ], # go down
           [ 0, 1 ]] # go right    
  delta_name = ['^','&lt;','V','&gt;']
  </code></pre>
  
  <p>and the output of my algorithm like this:</p>
  
  <pre><code>[11, 11, 0, 4, 5]
  ############## Search is success
  [0, -1, -1, -1, -1, -1]
  [1, -1, -1, -1, -1, -1]
  [2, -1, -1, -1, -1, -1]
  [3, -1, 8, 9, 10, 11]
  [4, 5, 6, 7, -1, 12]
  
  ['V', ' ', ' ', ' ', ' ', ' ']
  ['V', ' ', ' ', ' ', ' ', ' ']
  ['V', ' ', ' ', ' ', ' ', ' ']
  ['V', ' ', ' ', '&gt;', '&gt;', 'V']
  ['&gt;', '&gt;', '&gt;', '^', ' ', '*']
  </code></pre>
  
  <p>How could I calculate the heuristic by Euclidean Distance formula and make the algorithm moves in eight directions, not just four?. </p>
  
  <p>This is my code:</p>
  
  <pre><code>import random
  grid = [[0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],
          [0, 0, 0, 0, 1, 0]]
  heuristic = [[9, 8, 7, 6, 5, 4],
               [8, 7, 6, 5, 4, 3],
               [7, 6, 5, 4, 3, 2],
               [6, 5, 4, 3, 2, 1],
               [5, 4, 3, 2, 1, 0]]
  init = [0,0]                           
  goal = [len(grid)-1,len(grid[0])-1]
  #Below the four potential actions to the single field
  delta = [[-1 , 0],   #up 
           [ 0 ,-1],   #left
           [ 1 , 0],   #down
           [ 0 , 1]]   #right
  
  delta_name = ['^','&lt;','V','&gt;']  #The name of above actions
  cost = 1
  def search():
      #open list elements are of the type [g,x,y]
      closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
      action = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
  
      #We initialize the starting location as checked
      closed[init[0]][init[1]] = 1
      expand=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
  
      # we assigned the cordinates and g value
      x = init[0]
      y = init[1]
      g = 0
      h = heuristic[x][y]
      f = g + h 
  
      #our open list will contain our initial value
      open = [[f, g, h, x, y]]
      found  = False   #flag that is set when search complete
      resign = False   #Flag set if we can't find expand
      count = 0
  
      #print('initial open list:')
      #for i in range(len(open)):
              #print('  ', open[i])
      #print('----')
  
      while found is False and resign is False:    
          #Check if we still have elements in the open list
          if len(open) == 0:    #If our open list is empty, there is nothing to expand.
              resign = True
              print('Fail')
              print('############# Search terminated without success')
              print()
          else: 
              #if there is still elements on our list
              #remove node from list
              open.sort()             #sort elements in an increasing order from the smallest g value up
              open.reverse()          #reverse the list
              next = open.pop()       #remove the element with the smallest g value from the list
              #print('list item')
              #print('next')
  
              #Then we assign the three values to x,y and g. Which is our expantion.
              x = next[3]
              y = next[4]
              g = next[1]
  
              expand[x][y] = count
              count+=1
  
              #Check if we are done
              if x == goal[0] and y == goal[1]:
                  found = True
                  print(next) #The three elements above this "if".
                  print('############## Search is success')
                  print()
  
              else:
                  #expand winning element and add to new open list
                  for i in range(len(delta)):       #going through all our actions the four actions
                      #We apply the actions to x and y with additional delta to construct x2 and y2
                      x2 = x + delta[i][0]
                      y2 = y + delta[i][1]
  
                      #if x2 and y2 falls into the grid
                      if x2 &gt;= 0 and x2 &lt; len(grid) and y2 &gt;=0 and y2 &lt;= len(grid[0])-1:
  
                          if closed[x2][y2] == 0 and grid[x2][y2] == 0:
                              g2 = g + cost            
                              h2 = heuristic[x2][y2]
                              f2 = g2 + h2 
  
                              open.append([f2,g2,h2,x2,y2])   
                              #print('append list item')
                              #print([g2,x2,y2])
                              #Then we check them to never expand again
                              closed[x2][y2] = 1
                              action[x2][y2] = i
  
      for i in range(len(expand)):
          print(expand[i])
      print()
  
      policy=[[' ' for row in range(len(grid[0]))] for col in range(len(grid))]
      x=goal[0]
      y=goal[1]
      policy[x][y]='*'
      while x !=init[0] or y !=init[1]:
          x2=x-delta[action[x][y]][0]
          y2=y-delta[action[x][y]][1]
          policy[x2][y2]= delta_name[action[x][y]]
          x=x2
          y=y2
      for i in range(len(policy)):
          print(policy[i])
  
  search()
  </code></pre>