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: 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;
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. 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());
HashMap<String, String> path = new HashMap<>();
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<>();
String run = tmp.toString();
while (path.get(run) != null){
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)){
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: Middle edge 0 to middle edge 3: Middle edge 0 to middle edge 3, but the middle tile is blocked: 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());
resetGraph(middle);
//example 2
findPath(middle.getEdges(), middle.getEdges());
resetGraph(middle);
//example 3
middle.setBlocked(true);//force route around the outside
findPath(middle.getEdges(), middle.getEdges());
resetGraph(middle);
//no path possible
middle.setBlocked(true);//force route around the outside
middle.getEdges().setBlocked(true);
middle.getEdges().setBlocked(true);
findPath(middle.getEdges(), middle.getEdges());
}```

Full code can be found here. Happy coding!

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