# A* Pathfinding - Euclidean Distance Heuristic Behaving Worse Than Diagonal Distance

I implemented the A* pathfinding algorithm according to this: https://www.redblobgames.com/pathfinding/a-star/introduction.html

My grid has a lot of obstacles (more than ten thousand) and is very big. I understand that, in order to get one of the shortest paths, I need to implement an admissible heuristic, so it doesn't over-estimate the distance between the current point and the goal. In theory, euclidean distance must always be less or equal. However, using it, I don't get the shortest path at all, because using diagonal (Chebyshev or octile) distance I get a shorter path. Why is that? Am I missing something? Here is the code:

**graph.cost always returns 1**

**graph.neighbors returns the 8 adiacent positions (less if there are obstacles)**

```
def a_star_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
return get_path(came_from, start, goal)
def heuristic(a, b):
dx = abs(b[0] - a[0])
dy = abs(b[1] - a[1])
D = 1
#with D2 = 1 it's even slower but more accurate
D2 = math.sqrt(2)
#Diagonal distance - this is more accurate
#return D*(dx + dy) + (D2 - 2*D)*min(dx, dy)
#Euclidean distance - this is faster and less accurate
return math.sqrt(dx*dx + dy*dy)
```

## Answer

The problem is that because the neighbours are all 8 adjacent grid points, and the cost between all of them is 1, euclidean distance is overestimating the cost between diagonal points.

Real distance between diagonal points: 1

Estimated distance : sqrt(2) = 1.41421356237

So euclidean distance is **not admissible** for your graph!

## Related Questions

- → What are the pluses/minuses of different ways to configure GPIOs on the Beaglebone Black?
- → Django, code inside <script> tag doesn't work in a template
- → React - Django webpack config with dynamic 'output'
- → GAE Python app - Does URL matter for SEO?
- → Put a Rendered Django Template in Json along with some other items
- → session disappears when request is sent from fetch
- → Python Shopify API output formatted datetime string in django template
- → Can't turn off Javascript using Selenium
- → WebDriver click() vs JavaScript click()
- → Shopify app: adding a new shipping address via webhook
- → Shopify + Python library: how to create new shipping address
- → shopify python api: how do add new assets to published theme?
- → Access 'HTTP_X_SHOPIFY_SHOP_API_CALL_LIMIT' with Python Shopify Module