What is the significance of initializing direction arrays below with given values when developing chess program?

C++CChess

C++ Problem Overview


I am new to competitive programming, and I noticed frequently, many of the great coders have these four lines in their code (particularly in those involving arrays):

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

What does this really signify and what is technique used for?

C++ Solutions


Solution 1 - C++

This is a technique to encode all directions as arrays - every pair of di[i],dj[i] is a different direction.

If we imagine we have a piece at a location x,y, and we want to add onto its x and its y value to move it to a nearby location, 1,0 is east, -1,0 is west, 0,1 is south, 0,-1 is north and so on.

(Here I have said top left is 0,0 and bottom right is 4,4 and shown what move each index of the arrays will make from the central point, X, at 2,2.)

.....
.536.
.1X0.
.724.
.....

The way it is set up, if you do ^1 (^ being bitwise XOR) on the index you get the opposite direction - 0 and 1 are opposites, 2 and 3 are opposites and so on. (Another way to set it up is to go clockwise starting at north - then ^4 gets you the opposite direction.)

Now you can test all directions from a given point by looping over your di and dj arrays, instead of needing to write out each direction on its own line (for eight in total!) (Just don't forget to do bounds checking :) )

diK and djK form all knights directions instead of all adjacent directions. Here, ^1 will flip along one axis, ^4 will give the opposite knight leap.

.7.6.
0...5
..K..
1...4
.2.3.

Solution 2 - C++

For those finding Patashu's explanation difficult to follow, I'll attempt to clarify.

Imagine you are trying to consider every possible move from a given point on a chess board.

If you loop over the di and dj arrays, interpreting the di values as x offsets and the dj values as y offsets, you cover each of the possible 8 directions.

Assuming positive x is east and positive y is south (as in Patashu's answer), you get the following;

| di/x | dj/y | Direction
--+------+------+-----------
0 |   1  |   0  | east
1 |  -1  |   0  | west
2 |   0  |   1  | south
3 |   0  |  -1  | north
4 |   1  |   1  | south-east
5 |  -1  |  -1  | north-west
6 |   1  |  -1  | north-east
7 |  -1  |   1  | south-west

The diK and djK arrays can be interpreted the same way to establish the possible moves for the Knight piece. If you're not familiar with chess, the Knight moves in an L pattern - two squares in one direction, and then one square at right angles to that (or vice versa).

| diK/x | djK/y | Direction
--+-------+-------+----------------
0 |  -2   |  -1   | 2 west, 1 north
1 |  -2   |   1   | 2 west, 1 south
2 |  -1   |   2   | 1 west, 2 south
3 |   1   |   2   | 1 east, 2 south
4 |   2   |   1   | 2 east, 1 south
5 |   2   |  -1   | 2 east, 1 north
6 |   1   |  -2   | 1 east, 2 north
7 |  -1   |  -2   | 1 west, 2 north

Solution 3 - C++

A small snippet of code to check the amount of moves possible in all directions, which uses the defined arrays.

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int movesPossible[8];
int move = 0;
int posx, posy; // position of the figure we are checking

for (int d=0; d<8; d++) {
  for (move = 1; board.getElt(posx+di[d]*move, posy+dj[d]*move)==EMPTY; move++) ;
  movesPossible[d] = move-1;
}

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionejjyrexView Question on Stackoverflow
Solution 1 - C++PatashuView Answer on Stackoverflow
Solution 2 - C++James HoldernessView Answer on Stackoverflow
Solution 3 - C++DariuszView Answer on Stackoverflow