Calculating Valid Moves for Hexagonal Chess Pieces in Python

Question

Currently I'm experiencing dificulties with calculating the valid moves for pieces in my implementation of hexagonal chess in python. Let me first begin with describing how the movement of the knight is defined in Hexagonal chess.

Let me focus on 1 movement action of the knight. A knight move 4 rows up and 1 column to the left. This is described in the following lines of code:

target = (position_col - 1, position_row - 4)  
if on_board(target): 
    if empty_hexagon(target, board) or piece_color_on_position(target, board) != self.color: 
          move = Move(self, self.position, target) 
          self.moves.append(move)

Now this works for certain positions like here:

Now this does indeed work for this specific hexagon, but not for all. See for example this position:

This is happening because not all rows in my board contain the same amount of columns. My board is basically a 2 dimensional array filled with hexagon objects, which I don't think is particularly important in this example, but it has the following structure:

        self.board =  [
            [None],
            [None, None],
            [None, None, None],
            [None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None],
            [None, None, None, None],
            [None, None, None,],
            [None, None],
            [None]
        ]

I would like to create an offset function that looks at my current row and the target row and calculates an offset such that I can just use my 'normal' steps of movement and calculate the corresponding target column. Is there a way to do this, or perhaps another coordinate system which I can use to do this more easily?

Thanks in advance!

I've tried a couple of things which I either didn't implement correctly.

I used a function to calculate differences in columns per row. If a my starting row contained 3 columns, while my target row contained 5 columns, than I added this difference to my target column. This however did not have the desired effect.

Edit 1* The offset looked like the following:

offset = BOARD_LENGTH[position_row - 4] - BOARD_LENGTH[position_row]
        target = (position_col - 1 + offset, position_row - 4)
        if on_board(target):
            if empty_hexagon(target, board) or piece_color_on_position(target, board) != self.color:
                move = Move(self, self.position, target)
                self.moves.append(move)

where BOARD_LENGTH = [1,2,3,4,5,6,6,6,5,6,5,6,5,6,6,6,5,4,3,2,1](these are the amount of hexagons per row in my 2d board list.)

This implementation of an offset didn't have the desired effect, because calculating the valid moves of the pieces still gave me incorrect squares to move to for a lot of starting positions.

Edit 2* Since it from my original screenshots it looked like the knight was not moving 4 rows up and 1 column to the right. I'll add a screenshot here to show my coordinate system. Here we can see that we are in fact moving 4 rows up.Since we are using hexagons the hexagon directly on top of a hexagon is not 1 row up, but 2 rows up. Hopefully this screenshot will clarify this:

The coordinates of the board printed on each hexagon

Answer 1

Okey, I think I have found an answer here thanks to Joe. First of all thanks everyone for taking a look at this problem. I'll post my solution here if someone else needs to look for a solution to this (or a similar) problem in the future.

Looking at the coordinate system that I used the task of formulating a formula that works would be impossible for me. Therefore I've changed the coordinate system to the following:

Instead of starting each hexagon on our board at 0, we imagine that there are hexagons to the left and right of this hexagon. At position (0,3) we imagine there being 3 hexagons to the left of it, and 2 hexagons to the right of it. Our board therefore now looks like:

   self.board =  [
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None],
        [None, None, None, None, None, None]
    ]

Note* not all elements of this 2 dimensional list are populated with hexagons.

The problem is now more easy to understand. It looks like there is currently only a mismatch between even and uneven rows. If we go from an even row to an uneven row we see that the same column index is to the right of that same index in the even row. That is to say, if we have row 10, with column 3. If we were to move to row 9 column 3 we would move up one row and go to the right. This can be seen in the coordinate system shared in the screenshot above.

Now I currently only looked at the single movement action of the knight. For this I changed the code to:

    knight_offset = calculate_offset(position_row, position_row - 5)
    target = (position_col - knight_offset, position_row - 5)
    if on_board(target, board):
        if empty_hexagon(target, board) or piece_color_on_position(target, board) != self.color:
            move = Move(self, self.position, target)
            self.moves.append(move)

And I added the following helper function to deal with the offset:

def calculate_offset(start_row, target_row):
    ''' 
    This function calculates the offset that should be used to move from hex A, to hex B
    '''
    if start_row % 2 == 0 and target_row % 2 == 1:
        return 1
    return 0

And this seems to be working for this single knight movement. As can be seen from the following screenshot (I also tested this for other positions, but this seems to be working):

It could be that I will have to do some more tinkering with different movements and offsets for different pieces, especially moving to the left of the board and to the right of the board. However, according to me this issue has been resolved and I have a way forward again. Thanks for all the tips!

Answer 2

I would use different column indices for the columns than the posted answer - ones for which hexagons had the same column indices if and only if they were vertically aligned.

import math

import matplotlib.pyplot as plt
from matplotlib.patches import RegularPolygon
import numpy as np

a = np.sqrt(3)/2
colors = ['brown', 'darkkhaki', 'gold']

hexagons = {}
for i in range(21):
    for j in range(11):
        if (((i+j) % 2 == 1) and (5 <= i+j <= 25) and (-5 <= i-j <= 15)):
            hexagons[(i,j)] = {'center':(-7.5 + 1.5*j, (10-i)*a)}
        

fig, ax = plt.subplots(1, figsize=(10,10))
ax.set_aspect('equal')

for idx in hexagons:
    xy = hexagons[idx]['center']

    # add patch
    this_patch = RegularPolygon(xy, 
                                numVertices=6, 
                                radius=1, 
                                orientation=np.pi/6,
                                alpha=0.2, 
                                facecolor=colors[idx[0] % 3],
                                edgecolor='k',
                               )
    ax.add_patch(this_patch)
    plt.text(xy[0], xy[1], str(idx), ha='center', va='center')
plt.autoscale(enable = True)
plt.savefig("hex_chess.png")
plt.show()

Using these indices, the position of the center of a hexagon with indices (i,j) is given by:

a = np.sqrt(3)/2
(x,y) = (-7.5 + 1.5*j, (10-i)*a)

The rule for valid knight moves from position (i1, j1) to (i2, j2) is:

((abs(i1-i2)==1 and abs(j1-j2)==3) or 
 (abs(i1-i2)==5 and abs(j1-j2)==1) or 
 (abs(i1-i2)==4 and abs(j1-j2)==2))

Which is all of the hexagons with:

(x2-x1)**2 + (y2-y1)**2 == 21

A function to check whether a move is valid could be defined as:

def move_valid(start, end, piece):
    """Check whether a move from start to end is valid for piece.

    start : Tuple[int, int]
        The (row, column) of the starting position.
    end : Tuple[int, int]
        The (row, column) of the ending position.
    piece : str
        The type of piece, e.g. 'knight'.

    """
    (i1, j1) = start
    (i2, j2) = end
    
    # check if start and end are on the board
    if start not in hexagons or end not in hexagons:
        return False
    
    if piece == 'knight':
        valid = ((abs(i1-i2)==1 and abs(j1-j2)==3) or 
                 (abs(i1-i2)==5 and abs(j1-j2)==1) or 
                 (abs(i1-i2)==4 and abs(j1-j2)==2))
    else:
        raise NotImplementedError
        
    return valid

For example, the valid moves from the center hexagon are:

this_hexagon = (10,5)
this_center = hexagons[this_hexagon]['center']

for h in hexagons:
    if move_valid(this_hexagon, h, 'knight'):
        dist_sq = ((this_center[0] - hexagons[h]['center'][0])**2 + 
                   (this_center[1] - hexagons[h]['center'][1])**2)
        print(f"{h}: {dist_sq}")

with output:

(5, 4): 20.999999999999996
(5, 6): 20.999999999999996
(6, 3): 21.0
(6, 7): 21.0
(9, 2): 21.0
(9, 8): 21.0
(11, 2): 21.0
(11, 8): 21.0
(14, 3): 21.0
(14, 7): 21.0
(15, 4): 20.999999999999996
(15, 6): 20.999999999999996