Hexgame is a simple two-player CLI game with one goal: connect two sides of the board! If the red player connects the top and bottom, they win; if the blue player connects the left and right, they win. Any n x n size board (greater than 2) is allowed. Hexgame is fully open-source: the repo can be found here.
In the HexGame struct, there are two main fields that deal
with data: game, a Vec<Color> that keeps
track of the pieces placed, and logic, a
DisjointSet containing every piece as well as symbolic
pieces for the edges. As the name suggests, the logic set
controls the logic of the game: once the top and bottom or left and right
edges are part of the same set, a player has won, and the game is over.
The point of the exercise was to implement a disjoint set data structure,
and use it to create a product (originally in Java, see
why). The struct itself is surprisingly simple: it
contains a field nodes: Vec<isize> in which all values
are initialized to -1. Each node represents either the
(negative) size of its set if it is the root, or its parent node.
The algorithm to find the root of a set uses path compression: whenever a node is touched, its parent is changed to the root of the set. This causes much shorter traversals on average. The algorithm itself is as follows:
Let's look at this chunk-by-chunk:
Negative values represent the size of a set and are only held by roots. So, if the given node is negative, it is already the root of the set and is returned.
This is the traversal of the set. The first few lines store the current
node and the data held by that node, and creates a Vec to keep
track of nodes that have been visited. Any positive value represents a
parent, so, while data is positive, we can set current to the
node's parent and repeat the cycle. Once it reaches a negative value, it
has found the root, and the loop exits. Each node touched is also pushed to
the to_compress list.
Each node that was visited is then made a direct child of the parent. This compresses the set and allows for much faster traversal in the future for frequently checked nodes.
The root node stored in current is then returned.
The algorithm to join two sets is as follows:
Again, let's look at this chunk-by-chunk:
The provided nodes aren't guaranteed to be roots, so the roots of each node are found and stored.
If self.find() returns the same root for both nodes, they are
already part of the same set, so no joining is necessary.
The algorithm uses smart-union by size: when the two sets are
joined, the root of larger of the two becomes the root of the new set. The
size of a set is stored as a negative value, so if root.0 is
less than root.1, it becomes the new root (and vice versa).
The size of the nodes are then added, and the smaller root's parent is set
to the larger root.
The HexGame struct is defined as
Color is an enum containing Blank, Red,
or Blue. On initialization, the logic board and game board are
created with the provided size squared, plus 4 for the edges.
All elements in the game board start with Blank. The
top, bottom, left, and right
elements are calculated and represented as the last four elements.
To play a piece, either HexGame::play_red() or HexGame::play_blue
(nearly identical) is called:
The function returns true only if the win condition is met. Chunk-by-chunk:
HexGame::get_neighbors() calculates the immediate neighbors on
the hexagonal board given a position. It calls for a bool is_red
that simply controls whether the top/bottom or left/right edges are
considered.
If the given position is already taken, no action should be taken, and the
function should return false. Otherwise, set the position to
Color::Red or Color::Blue, depending on who's
turn it is.
If any of the neighbors are red or edges, they should be joined with the current position.
The win condition is that the top/bottom edges are connected for red, or the left/right edges are connected for blue. If the win condition is met, the function returns true.
This was originally given as an assignment in the course Algorithms and Data Structures which was taught in Java (barf). We were given a plain text file of moves to parse, the goal being to detect when either player had won. In order to better learn Rust, I've been re-implementing (almost) all of assignments in it. For this one, parsing a static file and detecting the win condition seemed boring, so I made it interactive as an exercise.