The goal in my clone of the game "Hex" is to occupy a contiguous chain of hex spaces in your color from one side of the board to the opposing side before your opponent does the same (see board below).

My problem is that I am not sure how to detect end of game without using brute force. I'm storing the state of all the hex spaces in both a single and two dimensional array (where each array position is an integer and 0=unoccupied, 1=player 1, 2=player 2). The only algorithm I can think of to check if the game is ended is to go through each hex on the left side of the board, check all adjacent hexes to the right and see if they are occupied in the same color...if so move one hex to the right and repeat until either I am out of adjacent hex spaces with the same color or the board ends. Then do the same for the other player's color. Is there a better way to do this?

You can always go with a standard depth-first or A* search (for which the distance to the other edge -width - x- is the heuristic and the goal state is x = width - 1).

Your approach of only moving right would most likely fail as soon as the path needs to loop around opposing players cells and actually has to move left.

Yeah I thought about it last night and it would fail. I suppose the first step is building a tree (or graph) for each occupied red hex on the furthest left of the board one at a time (for red at least). Then walk the tree for each instance and see if it ever reaches opposing side of the board. Any reason why that would not work?

It works, but you have some unnecessary logic in your method. Just building the tree is enough; if you even add an end-node to the tree, you have reached the other side. Since you don't have to store the tree for later traversal, you can effectively build and traverse it at the same time, without explicitly storing it, using recursion. It should be easy enough to start at any one hex and to recursively check all its unvisited neighbors; if you ever reach an end hex, you have a complete path from the starting side to the end side.

It is important to keep track of visited and unvisited nodes when recursing to not get stuck in loops. If the game allows multiple starting points, you have to check all of them in case they are not connected.

Pseudo code:

bool check(currentHex) {
if(isEndHex(currentHex)) {
return true;
}

for neighbor=each neighbor of currentHex {
setVisited(neighbor);
bool res = check(neighbor)
resetVisited(neighbor);

if(res == true) {
return true;
}
}

return false;
}

I hope I got the logic correct. You should call check() for all starting hexes and it should return true if the hex has a path to an end hex.

Since the only way a game can be ended is when placing a marker at a position, so each time a hex is marked, do a breadth first search until there are no more connected positions of the same color, or two different end positions are found.

I'm at a lecture, writing on my phone, so sorry if I'm terse. Anyone see anything wrong with my approach?

The above is o(n) with n = nodes in connected graph.

At each placement, you could instead cache the connected end nodes to that position. You could then just check if the neighbours have any elements connected to end nodes. Constant time end-game check at each placement.

I think A* is a good place to start, but since you don't really care what the shortest way across is (only that there is a complete path across) it could be somewhat simplified (you don't need any heuristic values, parents, distances, or anything like that.) Have each hex have a list of hexes called neighbors. Then, when a hex is set to a player, have it check the six hexes around it to see if they are set to the same player, and if so, add that hex to its neighbor list, and add itself to that hex's neighbor list. Then, for the check win condition, have it add the most recently added hex to an open list. Then take the first hex in your open list, move it to the closed list, and have it add all of its neighbors not already in the open or closed list to the open list, and repeat. When it is done, it will have a list (closed) of everything in the chain connected to the most recently placed tile. You can then quickly search that chain to see if it has a tile at the x=0 and a tile at the x=10 (or whatever your coordinates are) and if it finds both in that list, it knows it's a win. If not, it clears the lists, and passes the turn.

Based on the responses I think I have an algorithm worked out.

Let there be one master list for each player. Each of these master lists contains one or more lists of contiguous hex spaces.

Each hex space will store array positions for all possible adjacent hexes (<=6).

So when a hex for a player is added...
1. If this is the first ever hex to be added for a player, add a new list to the master list and put that hex in it.
2. Walk through the array of possible adjacent hexes for the newly added hex. Check those array positions to see if it is occupied by the same player. If there is a match, assume it is contiguous and add the matched adjacent hex to the list of contiguous hexes the newly added hex is on. If a newly added hex has no adjacent matches, add a new list to the master list and put it in there.
3. Loop through all of the lists in the master list, check for adjacencies and collapse the two lists being compared if a match is found.
4. Check each list of contiguous hexes in the master list to see if there are two hexes from opposite sides of the board. If they are found, the game is over.

So in this example there would be two master lists, one for red and one for blue. Red has one list of contiguous hex spaces and blue has four.



I know this algorithm isn't very elegant...that aside, can anyone find a case where it would not work? I'm very new to this path logic stuff and this the best I could wrap my head around.

I appreciate all the help so far with this! I'll post code somewhere when it is done.