title: A* Pathfinding in a hexagonal grid
body: <p>Can anyone point me to a simple example that implements <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer">A* path-finding algorithm</a> on a <strong>hexagonal</strong> grid (in JS). I have made it working on a square grid, however all my attempts to make it work on a hexagonal grid have failed.</p>
  
  <p>This is how my grid looks like:</p>
  
  <p><a href="https://i.stack.imgur.com/q3G65.png" rel="noreferrer"><img src="https://i.stack.imgur.com/q3G65.png" alt="enter image description here"></a></p>
  
  <p>I'm using the same technique to both draw the grid and generate coordinates as seen in this <a href="https://stackoverflow.com/questions/20734438/algorithm-to-generate-a-hexagonal-grid-with-coordinate-system">topic</a>. </p>
  
  <p>Here's the grid coords data along with the start, end coords: </p>
  
  <pre><code>        [0, 0] , [0, 1],  [0, 2],
      [1, 0],  [1, 1],  [1, 2],  [1, 3],
   [2, 0],  [2, 1],  [2, 2],  [2, 3],  [2, 4],
      [3, 0],  [3, 1], [3, 2],  [3, 3], 
          [4, 0], [4, 1],  [4, 2]
  
  
  start_point: [0,2]
  end_point: [4.0]
  </code></pre>
  
  <p>After updating the manhattan distance calculation to:</p>
  
  <pre><code>var dx = pos1[0] - pos0[0];
      var dy = pos1[1] - pos0[1];
  
      var dist;
      if ( Math.sign(dx) == Math.sign(dy) ){
          dist = Math.abs (dx + dy);
      }else{
          dist = Math.max(Math.abs(dx), Math.abs(dy))
      }
  
  return dist;
  </code></pre>
  
  <p>I get this result: </p>
  
  <p><a href="https://i.stack.imgur.com/gCgId.png" rel="noreferrer"><img src="https://i.stack.imgur.com/gCgId.png" alt="enter image description here"></a></p>
  
  <p>and also the way I'm calculating the shortest path:</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>if (!Array.prototype.remove) {
      Array.prototype.remove = function(from, to) {
          var rest = this.slice((to || from) + 1 || this.length);
          this.length = from &lt; 0 ? this.length + from : from;
          return this.push.apply(this, rest);
      };
  }
  
  var astar = {
      init: function(grid) {
          for(var x = 0; x &lt; grid.length; x++) {
              for(var y = 0; y &lt; grid[x].length; y++) {
                  grid[x][y].f = 0;
                  grid[x][y].g = 0;
                  grid[x][y].h = 0;
      //grid[x][y].content = false;
                  grid[x][y].visited = false;
                  grid[x][y].closed = false;
                  grid[x][y].debug = "";
                  grid[x][y].parent = null;
      console.log([grid[x][y].coords[0],grid[x][y].coords[1]])
              }
          }
      },
      search: function(grid, start, end, heuristic) {
          this.init(grid);
          heuristic = heuristic || this.manhattan;
  
          var openList = [];
    
    //// find the start and end points in the grid ////
    start = grid[start.pos[0]][start.pos[1]];
    end =  grid[end.pos[0]][end.pos[1]];
    
    console.log( start, end )
    
          openList.push(start);
    
          while(openList.length &gt; 0) {
     
              // Grab the lowest f(x) to process next
              var lowInd = 0;
              for(var i=0; i&lt;openList.length; i++) {
                  if(openList[i].f &lt; openList[lowInd].f) { lowInd = i; }
              }
              var currentNode = openList[lowInd];
  
              // End case -- result has been found, return the traced path
              if( currentNode == end ) {
                  var curr = currentNode;
                  var ret = [];
                  while(curr.parent) {
                      ret.push(curr);
                      curr = curr.parent;
                  }
                  return ret.reverse();
              }
  
              // Normal case -- move currentNode from open to closed, process each of its neighbors
              openList.remove( lowInd );
              currentNode.closed = true;
  
              var neighbors = this.neighbors(grid, currentNode);
              for(var i=0; i&lt;neighbors.length;i++) {
                  var neighbor = neighbors[i];
  
                  if( neighbor.closed || neighbor.content == 2 ) { // not a valid node to process, skip to next neighbor
                      continue;
                  }
  
                  // g score is the shortest distance from start to current node, we need to check if
                  //   the path we have arrived at this neighbor is the shortest one we have seen yet
                  var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
                  var gScoreIsBest = false;
  
                  if(!neighbor.visited) {
                      // This the the first time we have arrived at this node, it must be the best
                      // Also, we need to take the h (heuristic) score since we haven't done so yet
                      gScoreIsBest = true;
                      neighbor.h = heuristic(neighbor.coords, end.coords);
                      neighbor.visited = true;
                      openList.push(neighbor);
                  }
                  else if(gScore &lt; neighbor.g) {
                      // We have already seen the node, but last time it had a worse g (distance from start)
                      gScoreIsBest = true;
                  }
  
                  if(gScoreIsBest) {
                      // Found an optimal (so far) path to this node.  Store info on how we got here and just how good it really is. ////
                      neighbor.parent = currentNode;
                      neighbor.g = gScore;
                      neighbor.f = neighbor.g + neighbor.h;
                      neighbor.debug = "F: " + neighbor.f + "&lt;br /&gt;G: " + neighbor.g + "&lt;br /&gt;H: " + neighbor.h;
                  }
              }
          }
  
          // No result was found -- empty array signifies failure to find path
          return [];
      },
      manhattan: function(pos0, pos1) { //// heuristics : use manhattan distances  ////
          var dx = pos1[0] - pos0[0];
          var dy = pos1[1] - pos0[1];
    
          return  Math.abs (dx + dy);
      },
      neighbors: function(grid, node) {
          var ret = [];
          var x = node.coords[0];
          var y = node.coords[1];
    
          if(grid[x-1] &amp;&amp; grid[x-1][y] ) {
              ret.push(grid[x-1][y]);
          }
          if( grid[x+1] &amp;&amp; grid[x+1][y] ) {
              ret.push(grid[x+1][y]);
          }
          if( grid[x][y-1] &amp;&amp; grid[x][y-1] ) {
              ret.push(grid[x][y-1]);
          }
          if( grid[x][y+1] &amp;&amp; grid[x][y+1] ) {
              ret.push(grid[x][y+1]);
          }
          return ret;
      }
  };</code></pre>
  </div>
  </div>
  </p>
  
  <p>Tried looking around for some good examples or documents on the internet but couldn't really find anything of use. </p>