Skip to content
Advertisement

Is there any other more efficient approach for getting the possible moves in a Matrix and for iterating over them?

I am creating an algorithm in Java for playing the isolation game (1vs1) board game: https://en.wikipedia.org/wiki/Isolation_(board_game) Basically my problem concerns moving a pawn following several rules (later specified). I have created this solution (it works) to get the moves(only the ones that are possible) of the pawn and to iterate over them to create news states of the problem and I wanted to know if there is a more efficient way to solve this. Basically, the roles of the movements are:

  1. The pawn can move in the 8 possibles directions(up, down, left, right, diagonals).
  2. The pawn can only move 1 step each move.
  3. The pawn can not move to a tile if the other pawn is there, or if the tile is markdown.
  4. After each move the player can markdown a tile of the board ( one which does not have a pawn and one which is not markdown already).

Here is my solution:

Getting the possible moves

    public List<Integer> moves(int f, int c) {
    List<Integer> moves= new ArrayList<Integer>();
    int nuevaX,nuevaY;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if (!(i == 1 && j == 1)) {
                nuevaX = f + (i - 1);
                nuevaY = c + (j - 1);
                if (disponible(nuevaX,nuevaY) && !ocupada(nuevaX, nuevaY)) {
                    moves.add(nuevaX);
                    moves.add(nuevaY);
                }
            }
        }
    }
    return moves;

Iterating

List<Integer> moves = moves(f, c);
    for (int i = 0; i < moves.size(); i+=2) { 
        x = moves.get(i);
        y = moves.get(i+1);
        //Do some stuff
        }

Advertisement

Answer

The code you have shown is already very fast.

It performs a constant (doesn’t change with the size of the board) and very small number (8) of operations.

You may be able to optimize disponible() and ocupada() methods, but although you haven’t shown those, I suspect they are also simple and therefore already fast.


As a style note, I suggest that rather than pushing x and y into a List<Integer>, you instead create a Move class (or record if you’re using Java 15), that has x and y fields and creating a list of List<Move> instead, which will make your code easier to read and understand.

6 People found this is helpful
Advertisement