Directional Map Path Finding with a Hexagon Grid

Creating the Hexagon grid:

   We first need to create the hexagon grid, we start off with a simple data structure that contains pointers to each of its neighbours. We also need an isWall flag to determine if the node is a wall node. We also keep a x and y index of were the node is stored in our 2D array.
class HexMapNode
  int x,y;
  boolean isWall = false;
  HexMapNode *top,*topLeft,*topRight = null;
  HexMapNode *bottom, *bottomLeft,*bottomRight = null;
  HexMapNode *selectedNeighbour = null;
  int nodesUntilGoal = 9999;
   We then create each node, link their neighbours and add them into a 2D array. This can be a little tricky because since we chose a Hexagon grid, and we can't link a node before its created. It is also a tricky because I chose the nodes to go from 0 to size from left to right in a horizontal fashion. Another article suggested going up at an angle but I feel that once the array is built its easier to deal with and it also saves space.

Note that topLeft,topRight,bottomLeft and bottomRight differ if x%2 is 1 or 0;
void buildMap()
  for( int x = 0, x< gridWidth,x++)
    for(int y = 0, y<gridHeight,y++)
      hexGrid[x][y] = new HexMapNode();
      if(y!=0)
        hexGrid[x][y].bottom = hexGrid[x][y-1];
        hexGrid[x][y-1].top = hexGrid[x][y];
      if(x%2 == 0)
        if(x!=0)
           hexGrid[x][y].topLeft = hexGrid[x][y-1];
           hexGrid[x][y-1].bottomRight = hexGrid[x][y];
        if(x!=0 && y!=0)
           hexGrid[x][y].bottomLeft = hexGrid[x-1][y-1];
           hexGrid[x-1][y-1].topRight = hexGrid[x][y];
        if(y!=0)
           hexGrid[x][y].bottomRight = hexGrid[x+1][y-1];
           hexGrid[x+1][y-1].topLeft = hexGrid[x][y];
      else
        if(x!=0)
           hexGrid[x][y].bottomLeft = hexGrid[x-1][y];
           hexGrid[x-1][y].topRight = hexGrid[x][y];

Building the Directional Map:

 To build the Directional Map we do a breadth first search from the goal nodes. Each goal node is added to the openSet. We add two properties to our data structure, nodesUntilGoal and selectedNeighbour, at the goal node they are zero and null. We keep two sets in memory, the open set and the closed set. We iterate through the open set, for each node we add each of its neighbour to the openset unless it is in the openSet already, in the closedSet or isWall is true, then we move it to the closeSet. We repeat until the openSet is empty.
void buildDirectionMap()
  foreach(node in goalNodes)
    openSet.add(node);
    node.nodesUntilGoal = 0;
  while(openSet.length > 0)
    currentNode = openSet[0];
    foreach(neighbour in currentNode.allNeighbours)
      if(neibhour != null && neighbour.isWall == false &&
         openSet.cotains(neighbour) == false &&
         closedSet.contains(neighbour = false)
           openSet.add(neighbour);
           neighbour.nodesUntilGoal = currentNode.nodesUntilGoal + 1;
           neighbour.selectedNeighbour = neighbour.getBestNeighbour();
    closedSet.add(currentNode);
    openSet.remove(currentNode);
  Every time we add a neighbour we update nodesUntilGoal and selectedNeighbour.
The getBestNeighbour function uses the nodesUntilGoal to decide which neighbour is the best. If there is a tie break we use the node that is closest to the goal by its position.
HexMapNode* getBestNeighbour()
  int min = 9999;
  HexMapNode *bestNode;
  foreach(node in this.neighbours)
    if(node!=null)
      if(node.nodesUntilGoal < min)
        bestNode = node;
        min = bestNode.nodesUntilGoal;
      else if(node.nodesUntilGoal == min &&
           node.getDistanceFromGoal() < bestNode.getDistanceFromGoal())
        bestNode = node;
  return bestNode;

Moving towards the Destination:

  Since we now know the selectedNeighbour at any position in the map, all we have to do is follow it to our goal node.

Why a Directional Map:

   With a directional map, the benefit is that given any position we know how to get to the goal. If the grid stays the same, we can add players anywhere on the map and not have to recalculate anything.
  It is simpler than other methods, we only have to execute one breath-first search.

Why not A*:

   We could of went with A* instead of a full breadth first search because it would take less execution time. If we only have one player A* would be optimal, but since we can have multiple players and multiple walls it is very likely we would explore most of the nodes anyways. 
  If our grid was much much larger the current solution might cause performance problems, but currently it is a reasonable size.

Why a Hexagonal Grid not a square grid:

   Why a Hexagon Grid and not a traditional square grid. The nice thing with a Hexagon grid is the distance from one grid to another is always the same. 

If we use a square gride we can either have four or eight neighbour nodes, if we choose eight we need to watch out how we create our wall because of the diagonal. If we are having an enemy traverse the path, an enemy cannot pass through a dot in most game scenarios.

We do however have a problem, since we don't have a direct left or right node going from left to right in a direct manner vs an angled one is exactly the same.

This is why use the distance to goal as well as the nodes until goal.

Javascript Specific implementation:

   I originally created this for a iOS game and then ported it to javascript/html/css.
Well how was this acheived? using JQuery and a unique way of naming our html components. We give our main HexMap class a getId function, that returns a unique id. We also add a getPos function that returns the actual x,y position used to place the html. Finally we add a htmlElement variable to our class, and assign it to the reference JQuery wrapped object of the html div. The div contains a svg hexagon, and its css properties are modified to change its color. 

function HexMap(x,y){
    this.x = x;
    this.y = y;
    ...
    this.htmlElement = null;
    this.getId =  function(){
       return "hex"+this.x+"-"+this.y;};
    this.getPos =  function(){
       ...
       return [actualX,actualY]};
}
function buildMap(){
    ...
    var node = new HexMapNode(x,y);
    hexMap[x][y] = node;
    var htmlNode = '<div id="' + node.getId() +
           '"style="left:'+ node.getPos()[0] + ';top:'+
           node.getPos()[1] +';'"> ...</div>';
    $('#mainDiv').append(htmlNode);
    node.htmlElement = $('#'+ node.getId() );
    ...
}

Note the actual implementation is slightly different
  Our array is y then x first, since its html our arrays 0,0 is top left and extends down and right.
  This also mean building the map is slightly different.
ViewSource by simple right-clicking and viewing source.


Refferences:  http://www-cs-students.stanford.edu/~amitp/game-programming/grids/