Basic algorithms

Here I try to describe three algorithms, so that everyone can understand it. Maybe it's not the most efficient way to implement something, but it's easy and of course, it's only one possibility you can make it in many other ways too.

How to check if a peg connects to another?
Basic algorithms - Twixt
First look at the picture on the right side. The yellow peg (say placed at row, col) is the peg you want to test if there is any connection to another one. The red pegs show all positions where the distance (not diagonal) to the yellow peg is 3 (line with comment 1 at the code). The green area is the rectangle with top left (row-2, col-2) and bottom right corner (row+2, col+2). The points who match both criterias and where's a peg with same color as the test peg (//2) are the points we're looking for. In java this could look like this:
Warning: this is not the complete method, just the main parts, of course you got to make sure that you don't have an index out of bounds and if the connection you get is not crossed by one of the opponent. For this problem see next chapter.

public void connect(
int[] point, // point[0] = row of peg to test, point[1] = column (both 0 to 23)
int[][] board) // board[row][col] = 0 --> no peg, 1 --> peg up-down, 2--> peg left-right
{
for (int i = -2; i < 3; ++i)
for (int j = -2; j < 3; ++j)
if (Math.abs(i) + Math.abs(j) == 3 && //1
board[point[0]][point[1]] == board[point[0] + i][point[1] + j]) //2
{
// We can connect from (point[0], point[1]) to (point[0] + i, point[1] + j)
// ATTENTION: not tested if a link is crossing
}
}

How to check if a link crosses another one?
There are two ways to do that. You can calculate the connections who would cross your connection and then look if this connection exists or you can check for every connection if it is crossing your one. Second way is explained here because it can be done with simple mathematics, but the other way would probably be faster.
In words: A connection is crossing another one if the start and end point of both connections are on different sides of the line going through the other connection.
In mathematics:
Basic algorithms - Twixt
Legend:
(x1, y1) = startpoint of connection 1
(x2, y2) = endpoint of connection 1
(x1', y1') = startpoint of connection 2
(x2', y2') = endpoint of connection 2
g = straight line through connection 1
h = straight line through connection 2
y(x) = the formula for g
red = the test we need to test if the points of connection 2 are on different sides of g.

So the drawing only shows one test, youve got to do the same for h. You get this test if you replace every 1 by a 2 and every 2 by a 1 in the formulas. This works for all connection, doesnt matter if they stored from left to right, up-down or whatever...

This can be implemented by some for loops. With the given information above, I think a code example wouldn't be necessary and just ballast for this site...

How to check if your move is a winning move?
Lets say you played your last peg at (row, col). You can calculate all reachable positions from there and see if there is one reachable position at each side of the board. This can be done recursive, here a java code example:

// more about Connections in 'Do it yourself'
private boolean[][] reachable;

public boolean isWinningMove(int row, int col, Connections myConnections) {
reachable = new boolean[24][24];
calcReachablePos(row, col, myConnections);
// now you can test with a for loop if you have
// on both of your sides a reachable position,
// for example if you playing left right
// At least one of reachable[1 to 22][0] and
// at least one of reachable[1 to 22][23] has to be true.
}

private void calcReachablePos(int row, int col, Connections myConnections) {
if (!reachable[row][col]) {
reachable[row][col] = true;
for (int i = 0; i < myConnections.getSize(); ++i) {
int[] c = myConnections.get(i);
if (c[0] == row && c[1] == col)
calcReachablePos(c[2], c[3], myConnections);
else if (c[2] == row && c[3] == col)
calcReachablePos(c[0], c[1], myConnections);
}
}
}

Conclusion
I hope this text gives a small insight in the computer thinking of Twixt. Comments and contributions welcome ;-)


--- Update Jul 18 2008 ---

I developed a new way to store a twixt board. For the advantages see below. Maybe someone has any use for it. That's how it works:

You store all in a 48x48 integer array instead of a 24x24 array (in the whole text it is assumed that the first index is 0). This means one "cell" contains of a 2x2 array which I use like this:

numbers:
even
odd
even
pegconnection
odd
connectionfree for use

Pegs: The pegs are stored on their normal position multiplied by two. 0 means no peg. -1 is the player from left to right and 1 the player from top to bottom.

Connections: The middle point of every connection is stored. 0 means no connection. The sign gives the color. For the two possible directions you can use 2 constant values.

Free for use: Here you can attach some information to a peg coded as an integer or use it as index for another data structure where peg-relevant information is stored.


The advantages of using this way instead of the common way:

  • All information is on the board, you don't have to search in a list of connections, means better performance.

  • There are 9 connections that can cross another one. On this board there are stored on only 7 spots and they can be found very easy:
    * \ * X P
    \ . \ . \
    P X * \ *
    Explanation: 'P' means peg, so the connection goes from bottom left to top right. Stars '*' are Positions where pegs could stand. The 'X' are the spots where connections in both directions cross the other one and the '\' are positions where only a connection from top left to bottom right intersects. So you see all the 7 possibilities to cross a connection are stored within the rectangle given by the connection itself.

  • All possible connections to or from a peg are stored in the square surrounding the peg (the characters mean the same as above):
    * \ * / *
    \ . . . /
    * . P . *
    / . . . \
    * / * \ *

  • Because the color of a player is represented by the sign and the direction by a constant value. You can work good with absolute values if you just want a direction or with signs if you just want the color. The -1 and +1 values of the pegs are practical for multiplication too (if you want to paint something a specific color ;-), because they don't change the absolute value.

The advantages in short words: The board is more "human" (easier to get a picture what's really going on with a scan of the board) and the performance is better.

I would like to hear your opinion, does this make any sence to you or is it just useless?

More pages