4
\$\begingroup\$

I'm making a traditional roll-the-dice-and-move style board game. Players move along the white squares on the board (see image) and may move in any available direction from a junction. Players must move the full distance of their roll.

Other than a brute force calculation, how can I efficiently calculate the destination squares of all legal moves?

Example diagram of game board

\$\endgroup\$
5
\$\begingroup\$

One solution is to use a recursive function (Video explaining recursion). So for example the player is on the red square and he can do 5 moves :

enter image description here

The function should see that the square on the right is white so it calls the same function but with the square on the right (it does the same to the left but we will just look at the right to simplify). Except that this time, it tells the function that the player can only do 4 moves and not to the left.(the pink square represents the place the player can't go anymore)

enter image description here

The function sees that the square on the right is white. Again, it calls itself but now there is only 3 moves left.

enter image description here

Now the function calls itself again but with 2 moves left for the square on the right and the square on the bottom (it calls the function 2 times).

enter image description hereenter image description here

and again and again... Until there is no move left! When the function is called with no move left, it writes its position in an array.

At the end the array contains all the possible position for the player to go.

I don't know what language you use, so I will writte an example in C. So we will need a structure to contain the position of the legal moves :

struct Rect
{
    unsigned short x;
    unsigned short y;
};

Let's say you have these variables, to simplify we'll say they are global but you could just send their pointers to the function.

Rect legalDest[20];                     // This array contains the legal destinations
unsigned short numberOfSolution = 0;        //number of solution in the array
bool map[30][30];                       //2d array containing your map, 1 = white, 0 = black

Let's also say that you have a variable named commingFrom, if commingFrom egal 1 the previous square is on the right, 2 the previous square is on the top, 3 the previous square is on the left and 4 on the bottom. 0 means no previous square.

void get_legal_dest(Rect currentPosition//The square that is being analysed
unsigned short numberOfMoveLeft,        //the number of move left
unsigned short commingFrom)             //position of the previous step 
{
    Rect nextPosition;

    if (numberOfMoveLeft == 0) // if we can't move anymore, we reached a legal destination location
    {
        legalDest[numberOfSolution].x = currentPosition.x
        legalDest[numberOfSolution].y = currentPosition.y // we write the current position inside the array containing the solutions.
            numberOfSolution ++;//One more solution !
    }
    else
    {
        numberOfMoveLeft --;//we did a move

        if (commingFrom != 1 && map[currentPosition.x+1][currentPosition.y])//if not comming from the right and the square on the right is white
        {
            nextPosition.x = currentPosition.x+1;
            nextPosition.y = currentPosition.y;//the next position is on the right
            get_legal_dest(nextPosition,numberOfMoveLeft,3);//3 = next time we are comming from the left
        }
        if (commingFrom != 2 && map[currentPosition.x][currentPosition.y-1])//if not comming from the top and the square on the top is white
        {
            nextPosition.x = currentPosition.x;
            nextPosition.y = currentPosition.y-1;//the next position is on the top
            get_legal_dest(nextPosition,numberOfMoveLeft,4);//4 = next time we are comming from the bottom
        }

        //same for left and bottom

    }
}

Utilisation of the function, for example the player in on position 10, 10 and can move 6 squares :

Rect currentPosition = {10,10};
void get_legal_dest(currentPosition, 6, 0); //0 = comming from nowhere : first test.

I really hope that makes sense, I will edit it if it doesn't. It is a lot harder to explain than I thought.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

I'd actually move away from the square/grid representation and use loose nodes instead:

Nodes rather than squares.

Each valid position is one node and nodes are linked with each other (using connections) to form valid moves or directions:

Nodes connections.

Based on your game design, those connections could have additional properties like costs, directions etc. This allows you to do all kind of interesting things, such as one-way shortcuts, shorter but more expensive to pass ways, etc. (see the dashed arrows in the center ):

Nodes with one way connections.

When the user tries to move, you're using a pathfinding algorithm such as A* to look for a route between his current position and the target position. You'd have to explore all possible paths till you're running out of options (impossible move) or you've found a valid distance (the move is valid). Whether you'd like to allow "too short" paths is a different story.

While this is more complicated to implement (and setup), you'll have to clear advantage that your board doesn't have to be aligned to a grid. You don't even have to use uniform positions (e.g. some could be square, others round etc.). For presentation, you'll just need coordinates assigned to each node (they're not game logic related).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.