title: What heuristic functions can I use for a graph based (non-grid) A*?
body: <p>I'm learning the A* path finding algorithm and all of the examples I'm finding are grid based. Because of this, all their heuristics functions rely on some sort of physical distance (ie Manhattan based, Diagonal or Euclidian). </p>
  
  <p>But what if instead of a grid we have a freeform graph? Say the example below where <code>S</code> is the start and <code>G</code> is the goal: </p>
  
  <pre><code>S---A
  |   
  |   G
  |   |
  B---C---D
  </code></pre>
  
  <p>In this case a 'as the crow flies' approximation wouldn't be meaningful because this graph is equivocal to </p>
  
  <pre><code>S---A
  |   
  B---C---D
      |
      G
  </code></pre>
  
  <p>So what kind of heuristic function could I use in this case?</p>