Formula that describes the movement of a bishop in chess

Question

I'm programming a chess game and I'm trying to validate the movements every player tries to make. Obviously, every piece can move differently and I've had no trouble validating their moves up until now.

The first thing I do in order to validate the pieces is to check for collisions. In order to achieve that, I calculate the squares that are in between the original position of the piece and the final destination and check if there are any pieces in those squares.

Each position in the board has two values: x and y. So if I wanted to move the following bishop from (1,4) to (4,1) the squares in between would be (3,2),(2,3),(1,4).

According to a regression tool I've used, the formula would be y = 5 − 1⋅x. However that doesn't apply in other cases that follow the same pattern (where the bishop moves down-right) and it also doesn't apply in cases that don't follow the same pattern (for instance when the biship moves down-left).

So my question is, how can I mathematically (or programmatically) obtain positions a bishop will have to go through in order to reach a certain destination?

Answer 1

If a bishop is traveling from $(x_1,y_1)$ to $(x_2,y_2)$. This move is legal on an empty board if you have that:

$$|x_2-x_1|=|y_2-y_1|>0$$

Call this value $n$. and let $x_d=\frac{x_2-x_1}{n},y_d=\frac{y_2-y_1}{n}$. You have $x_d=\pm 1,y_d=\pm 1$, and together $(x_d,y_d)$ represents the "direction" of a single step in the move.

Then you have to check if $(x_1+kx_d,y_1+ky_d)$ is occupied for $1\leq k<n$.

This is essentially a "vector" formula: $(x_1,y_1)+k(x_d,y_d)$.

In your case, $x_1=1,y_1=4,x_2=4,y_2=1$ and $n=|x_2-x_1|=|y_2-y_1|=3$.

So $x_d=\frac{4-1}{3}=1, y_d=\frac{1-4}{3}=-1$ and your in-between squares are:

$$(1,4)+1\cdot(1,-1)=(2,3)\\ (1,4)+2\cdot(1,-1)=(3,2) $$

You can just skip the fraction calculation, if you know the move is legal, and just define $x_d=\mathrm{sgn}(x_2-x_1), y_d=\mathrm{sgn}(y_2-y_1)$, where:

$$\mathrm{sgn}(z)=\begin{cases}1&z>0\\-1&z<0\\0&z=0\end{cases}$$

This is because, when $z\neq 0$, $\mathrm{sgn}(z)=\frac{z}{|z|}$.

If you must have a line formula, rather than a vector formula, define $m=\frac{y_2-y_1}{x_2-x_1}$. By the above argument, we know $m=\pm 1$. Then $y = m(x-x_1)+y_1$ is the line, and you want to check the squares $(x,y)$ for $x$ strictly between $x_1$ and $x_2$.

Answer 2

Look at your two downward cases, compared to the upward cases. The upward cases -- which, you say, work -- start from the piece's location and move towards the target location.

In this case, there is no reason to deviate from listing your positions starting nearest the start position PrePosition and moving towards the target position PostPosition.