Pathfinding in a Hexagon Grid

Hexagons are popular in board and video games as the six sided tile provides versatility and opportunity for a wide range of strategy. We will be using an adjacency list esque implementation for our hexagon graph.

Consider a single tile:

Picture1

Each hexagon has six sides or edges. Each edge connects to exactly one hexagon or is null/empty. A strict number ordering of the sides, that is starting with the same side as the first entry in the list results in a well defined set of reciprocal edges. Edge 0 of a tile will always point to edge 3 of another tile.

0,3
3,0
1,4
4,1
2,5
5,2

Similarly for any given edge, there are left and right edges, taking into account wraparound. This mapping is important for tile insertion; if there exist other tiles, their edges must be updated accordingly:

n -> (n-1)(n+1)
0 -> 5,1
1 -> 0,2
2 -> 1,3
3 -> 2,3
4 -> 3,4
5 -> 0,4

The definition of our Hex object has its name, a list of edges, and a boolean indicating whether or not we have visited it during a search. A tile could also be ‘blocked’. This means it exists and is a valid object for each edge, but we cannot traverse it (see example below). We also define a static reciprocal edge list for simplicity during insertion:

public class Hex {

  private static final Map<Integer, Integer> flipEdges = new HashMap<>();
  static {
    flipEdges.put(0,3);
    flipEdges.put(3,0);
    flipEdges.put(1,4);
    flipEdges.put(4,1);
    flipEdges.put(2,5);
    flipEdges.put(5,2);
  }

  private String id;
  private Hex[] edges;
  private boolean visited;
  private boolean blocked;

  public Hex(String id){
    this.id = id;
    this.edges = new Hex[6];
    this.visited = false;
    this.blocked = false;
  }

  private static int indent = 0;
  public void assignEdge(int edge, final Hex hex) throws Exception {
    if (edge < 0 || edge > 5) throw new IllegalArgumentException("Invalid edge value, must be between 0-5");
    for(int i = 0 ; i < indent; i++) System.out.print("\t");
    System.out.println("e: " + edge + " " + hex.toString());
    ++indent;
    edges[edge] = hex;
    edges[edge].getEdges()[flipEdges.get(edge)] = this;
    int left = edge-1;
    if (left < 0) left = 5;
    int right = edge+1;
    if (right > 5) right = 0;
    if(edges[left] != null){
      for(int i = 0 ; i < indent; i++) System.out.print("\t");
      System.out.println("[LEFT] assigning hex " + hex.toString() + " to edges[" + left + "] on its edge " + right);
      edges[left].getEdges()[right] = hex;
      hex.getEdges()[flipEdges.get(right)] = edges[left];
    }

    if(edges[right] != null){
      for(int i = 0 ; i < indent; i++) System.out.print("\t");
      System.out.println("[RIGHT] assigning hex " + hex.toString() + " to edges[" + right + "] on its edge " + left);
      edges[right].getEdges()[left] = hex;
      hex.getEdges()[flipEdges.get(left)] = edges[right];
    }
    --indent;
  }

  public void setBlocked(boolean blocked)   {this.blocked = blocked;}
  public void setVisited(boolean visited)   {this.visited = visited;}
  public Hex[] getEdges()                   {return edges;}
  public boolean isBlocked()                {return blocked;}
  public boolean isVisited()                {return visited;}
  public String getId()                     {return id;}

  public void visit(){
    this.visited = true;
  }

  public boolean equals(final Hex rhs){
    return id.equals(rhs.getId());
  }

  public String toString(){
    StringBuilder sb = new StringBuilder();
    sb.append(id);
    //edges?
    return sb.toString();
  }
}

Building a graph requires a ‘root’ tile that we will assign edges to. We will look at a single level full graph, that is a middle tile with full edges: a total of 7 tiles. Building more intricate graphs is easy enough using this Hex model.

picture2hexagon

We will be using a breadth first search on the graph. This will give us the shortest path between two tiles with the path length being to total number of edges. Note that other search algorithms are certainly viable and relatively plug and play with our Hex model.

    //Breadth First Search
  public static void findPath(final Hex start, final Hex end){
    System.out.println("Searching from " + start.toString() + " to " + end.toString());  
    LinkedList<Hex> ll = new LinkedList<>();
    HashMap<String, String> path = new HashMap<>();
    ll.add(start);
    boolean pathFound = false;
    while(!ll.isEmpty()){
      final Hex tmp = ll.removeFirst();
      if(tmp.equals(end)){
        System.out.println("Reached goal, path:");
        //print out path
        ArrayList<String> output = new ArrayList<>();
        output.add(tmp.toString());
        String run = tmp.toString();
        while (path.get(run) != null){
          output.add(path.get(run));
          run = path.get(run);
        }
        Collections.reverse(output);
        for(int i = 0; i < output.size(); i++){
          System.out.print(output.get(i));
          if(i < (output.size() -1)) System.out.print(" -> ");
        }
        System.out.println();
        pathFound = true;
      }
      for(Hex edge : tmp.getEdges()){
        if (edge == null || edge.isVisited() || edge.isBlocked()) continue;
        if(!ll.contains(edge)){
          ll.add(edge);
          path.put(edge.toString(), tmp.toString());
        }
      }
      tmp.setVisited(true);
    }
    if(!pathFound){
      System.out.println("No path possible.");
    }
  }

Starting with the root node, we visit each edge tile, enqueuing it into a list for further search if it has not already been visited. We mark the current tile as visited and continue to the next tile. When we hit the target end tile, we build the path by backtracking through the tiles from start to end. For pretty printing purposes, we then reverse this list and display.

Examples:

Middle tile to middle edge 0:

picture3hexagon

Middle edge 0 to middle edge 3:

picture4hexagon

Middle edge 0 to middle edge 3, but the middle tile is blocked:

picture5hexagon

Example three illustrates how one would begin to create more interesting and intricate graphs. One option would be to simply not have a tile there, but setting a flag indicating the tile is not traversable provides for a better visual.

The driver that builds the above graphs and performs path finding on them is as follows:

  public static void main(String[] args) throws Exception{
    Hex middle = new Hex("middle tile");
    //build smallest full map
    for(int i = 0; i < 6; i++){
      middle.assignEdge(i, new Hex("me: " + i));
    }
    //example 1
    findPath(middle, middle.getEdges()[0]);
    resetGraph(middle);
    //example 2
    findPath(middle.getEdges()[0], middle.getEdges()[3]);
    resetGraph(middle);
    //example 3
    middle.setBlocked(true);//force route around the outside
    findPath(middle.getEdges()[0], middle.getEdges()[3]);
    resetGraph(middle);
    //no path possible
    middle.setBlocked(true);//force route around the outside
    middle.getEdges()[1].setBlocked(true);
    middle.getEdges()[5].setBlocked(true);
    findPath(middle.getEdges()[0], middle.getEdges()[3]);
  }

Full code can be found here. Happy coding!

Written by: Knowles Atchison, Jr., Synergist Software Developer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Up ↑

%d bloggers like this: