This gist outlines the way of programatically representing a Ludo board and the algorithm for calculating the next position of a ludo piece after performing a move with any number of steps.
Although most important details are elaborated in this gist, a basic knowledge of Ludo is obviously required to understand unexplained trivial details.
To simplify further reading, the terms used frequently next are defined below:
- Board: the entire Ludo board including the playing and staging area
- Piece: a single pawn that moves on board after rolling the dice (also known as token or "goti" in Indian subcontinent)
- Quadrant: one of four rectangular playing areas on the board
- Yard: the staging area where the pieces (initially) are when they not part of play
- Square: a single box in a quadrant where a piece can stand
- Starting Square: the square where a piece enters the playing area (this square is typically coloured and adjacent to yard)
- Home: the finishing position of a piece
Some other common terms used throughout the gist are defined in Glossary of board games or Ludo's Wikipedia page.
For the sake of simplifying the calculations when calculating new position of a moved piece, I have used the following layout for representing a Ludo board programatically:
In this case, each square is identified by a certain position value (similar to chess). This position value has three characters:
- The first character is one of R, G, Y or B representing the color of quadrant the square is in.
- The color of quadrant is determined by the middle (colored) column or the starting square in leftmost column
- The second character represents the vertical columns
- The minimum value for this is 0 for the rightmost column, 1 for middle, coloured column (aka home column), or 2 (maximum value) for leftmost column with starting square.
- The third character represents the row.
- Minimum value is 0 representing the first row of that quadrant and maximum value is 5 for last row.
- The value row is 6, and that of column is 1, when a piece has reached the home.
Another point worth noting that both row and column number increase in the same order as piece movement. Since piece only moves forward and not backward, row and column increase with forward movement of piece. This means:
-
For columns (the second character in position value), the rightmost column is numbered 0 and leftmost is 2 because a piece only moves from right column to left one instead of the other way around.
-
The major difference is observed in the way row (third character in position value) increases in each column. In left (starting) and middle (home) columns, the row increases from down to top as piece only moves in this direction. In third (rightmost) column, however, the row increases top to down as this corresponds to piece's forward movement.
To represent this layout programatically, three-integer-array can be used. To simply calculations described in next section, each color (R, G, Y, B) is given a number. The order of these numbers is same as the order of colors on the board (e.g. red comes before green, yellow comes after green, blue comes after yellow)
P_RED = 0
P_GREEN = 1
P_YELLOW = 2
P_BLUE = 3To represent a position, a three-integer-array is used. For example, position R21 is represented as:
position = [P_RED, 2, 1]The first element represents the color of quadrant, second is for the column index, and third element is the row index.
The format described above allows usage of circular increment to calculate the next position of a piece after it moves a certain number of steps. Circular increment means that if a value reaches its maximum, the next increment should reset the value to its minimum. This is applicable for:
- Quadrant Color, when it reaches 3, reset it back to 0.
- Column, when it reaches 2, reset it back to 0.
- Row, when it reaches 5, reset it back to 0.
If we look at the layout again, circular increments lead to correct forward movements because a piece can move from column 0 to 1, 1 to 2, and then 2 to 0 and so on. The same goes for rows, moving forward from row 5 leads to row 0.
The following algorithm implemented in Python calculates the next position of a piece after moving steps number of steps from
initial position, currentpos:
def movepiece(steps, currentpos, piececolor):
quadcolor, col, row = currentpos
if (col, row) == (1, 6):
# If a piece is already in home, it
# cannot move any further
return currentpos
if (col, row) == (-1, -1):
# If a piece is in the yard, it can
# only move to starting square (pos. 21)
# when a six is rolled.
if steps == 6:
return [piececolor, 2, 1]
return currentpos
row += steps
if col == 1 and row == 6:
# Piece reached home, can't move any further
return [quadcolor, col, row]
if row > 5:
if col == 1 and row > 6:
# If the piece is in home column, it needs
# to roll an exact number to reach home.
# If rolled number exceeds this, movement
# is not possible.
return currentpos
# Modulo operator is used for circular increment.
# The expression, M = (M + 1) % N increments
# M until M != (N - 1). Further increment
# resets to value 0.
row = row - 6
col = (col + 1) % 3
if col == 0:
# If column has reset to 0 after increment,
# it means the piece has moved to next quadrant
# so change quadrant color to next one.
quadcolor = (quadcolor + 1) % 4
if col == 1 and row > 0 and quadcolor != piececolor:
# If piece has ended up in middle (home) column but
# piece's color is not same as quadrant color, it has
# to be moved to third column.
col = 2
row = row - 1
return [quadcolor, col, row]This algorithm is for single dice, that is steps must be between 1 to 6.