I'm working on creating a digital version of the game Hex and I've hit a major obstacle when it comes to detecting if a player has won. I want to avoid a basic O(n^2) approach for performance reasons. How can I effectively determine if one of the players has created a continuous connection between their sides? I'm okay with explanations in plain English rather than precise code snippets.
4 Answers
You might want to think about creating a graph where each hexagon is a vertex and edges connect hexes of the same color. Don't rebuild it every turn; just update when needed. You can also add four extra vertices representing the sides and link edge vertices to their respective side. Using A* search on this setup could work well.
Check out this resource on hexagonal grids and pathfinding: www.redblobgames.com/grids/hexagons/. It has some great insights that might help you out!
Consider using a flood fill algorithm starting from the edge nodes to check for connections. This can help efficiently trace paths across the board.
Try a neighbor connection model: when creating a node, ask its neighbors which sides they're connected to, and spread that info back through the nodes. This way, you're incrementally updating the graph as the game progresses.
This is smart! Just keep in mind how often pieces change because it might mean needing to update a lot of nodes each time.