-1
\$\begingroup\$

I am creating a Hashi Puzzle game (Islands and Bridges) I am generating a 2d grid with Islands that can be connected using bridges, I am also running a DFS algorithm to check if the map is solvable I am getting this error

java.lang.ArrayIndexOutOfBoundsException: length=4; index=-1

I am using a 2d array to generate the map,What could cause the error?

Land.java

public class Land {

    private int[][] BRIDGES_TO_BUILD;

    private boolean[][] IS_ISLAND;
    private Direction[][] BRIDGES_ALREADY_BUILT;

    public Land(int[][] bridgesToDo){
        BRIDGES_TO_BUILD = copy(bridgesToDo);

        int R = bridgesToDo.length;
        int C = bridgesToDo[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[R][C];
        IS_ISLAND = new boolean[R][C];
        for(int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = null;
                IS_ISLAND[i][j] = bridgesToDo[i][j] > 0;
            }
        }
    }

    public Land(Land other){
        BRIDGES_TO_BUILD = copy(other.BRIDGES_TO_BUILD);
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[R][C];
        IS_ISLAND = new boolean[R][C];
        for(int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = other.BRIDGES_ALREADY_BUILT[i][j];
                IS_ISLAND[i][j] = other.IS_ISLAND[i][j];
            }
        }
    }

    public int[] next(int r, int c, Direction dir){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;

        // out of bounds
        if(r < 0 || r >=R || c < 0 || c >= C)
            return null;


        // motion vectors
        int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
        int i = Arrays.asList(values()).indexOf(dir);

        // calculate next
        int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};

        r = out[0];
        c = out[1];

        // out of bounds
        if(r < 0 || r >=R || c < 0 || c >= C)
            return null;

        // return
        return out;
    }

    public int[] nextIsland(int r, int c, Direction dir){
        int[] tmp = next(r,c,dir);
        if(tmp == null)
            return null;
        while(!IS_ISLAND[tmp[0]][tmp[1]]){
            tmp = next(tmp[0], tmp[1], dir);
            if(tmp == null)
                return null;
        }
        return tmp;
    }

    public boolean canBuildBridge(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            return canBuildBridge(r0, c1, r1, c0);
        }
        if(c0 == c1 && r0 > r1){
            return canBuildBridge(r1, c0, r0, c1);
        }

            if (r0 == r1) {
                int[] tmp = nextIsland(r0, c0, Direction.EAST);
                if (tmp[0] != r1 || tmp[1] != c1)
                    return false;
                if (BRIDGES_TO_BUILD[r0][c0] == 0)
                    return false;
                if (BRIDGES_TO_BUILD[r1][c1] == 0)
                    return false;
                for (int i = c0; i <= c1; i++) {
                    if (IS_ISLAND[r0][i])
                        continue;
                    if (BRIDGES_ALREADY_BUILT[r0][i] == Direction.NORTH)
                        return false;
                }
            }
        if(c0 == c1){
            int[] tmp = nextIsland(r0, c0, Direction.SOUTH);
            if(tmp[0] != r1 || tmp[1] != c1)
                return false;
            if(BRIDGES_TO_BUILD[r0][c0] == 0 || BRIDGES_TO_BUILD[r1][c1] == 0)
                return false;
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                if(BRIDGES_ALREADY_BUILT[i][c0] == EAST) {
                    return false;
                }
            }
        }
        // default
        return true;
    }

    public int[] lowestTodo(){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;

        int[] out = {0, 0};
        for (int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                if(BRIDGES_TO_BUILD[i][j] == 0)
                    continue;
                if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0)
                    out = new int[]{i, j};
                if (BRIDGES_TO_BUILD[i][j] < BRIDGES_TO_BUILD[out[0]][out[1]])
                    out = new int[]{i, j};
            }
        }
        if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0) {
                return null;
        }
        return out;
    }

    @TargetApi(Build.VERSION_CODES.GINGERBREAD)
    private int[][] copy(int[][] other){
        int[][] out = new int[other.length][other.length == 0 ? 0 : other[0].length];
        for(int r=0;r<other.length;r++)
            out[r] = Arrays.copyOf(other[r], other[r].length);
        return out;
    }

    public void connect(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            connect(r0, c1, r1, c0);
            return;
        }
        if(c0 == c1 && r0 > r1){
            connect(r1, c0, r0, c1);
            return;
        }
        if(!canBuildBridge(r0, c0, r1, c1))
            return;

        BRIDGES_TO_BUILD[r0][c0]--;
        BRIDGES_TO_BUILD[r1][c1]--;

        if(r0 == r1){
            for (int i = c0; i <= c1 ; i++) {
                if(IS_ISLAND[r0][i])
                    continue;
                BRIDGES_ALREADY_BUILT[r0][i] = Direction.EAST;
            }
        }
        if(c0 == c1){
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                BRIDGES_ALREADY_BUILT[i][c0] = Direction.NORTH;
            }
        }
    }
}

Search function with Map Generation

 public int[][] debug_board_state_easy = new int[4][4];
 void search() {

        Map<Point, List<Direction>> remainingOptions = new HashMap<>();

        Stack<Land> gameTree = new Stack<>();
        gameTree.push(new Land(debug_board_state_easy));

        while (true) {

            Land state = gameTree.peek();
            int[] p = state.lowestTodo();
            if (p == null)
                System.out.println("solution found");

            // move to next game state
            int r = p[0];
            int c = p[1];
            System.out.println("expanding game state for node at (" + r + ", " + c + ")");

            List<Direction> ds;
            if (remainingOptions.containsKey(new Point(r, c)))
                ds = remainingOptions.get(new Point(r, c));
            else {
                ds = new ArrayList<>();
                for (Direction dir : Direction.values()) {
                    int[] tmp = state.nextIsland(r, c, dir);
                    if (tmp == null)
                        continue;
                    if (state.canBuildBridge(r, c, tmp[0], tmp[1]))
                        ds.add(dir);
                }
                remainingOptions.put(new Point(r, c), ds);
            }

            // if the node can no longer be expanded, and backtracking is not possible we quit
            if (ds.isEmpty() && gameTree.isEmpty()) {
                System.out.println("no valid configuration found");
                return;
            }

            // if the node can no longer be expanded, we need to backtrack
            if (ds.isEmpty()) {
                gameTree.pop();
                remainingOptions.remove(new Point(r, c));
                System.out.println("going back to previous decision");
                continue;
            }
            Log.e("gameTree", "WE ARE CRASHING HERE");
            Direction dir = ds.remove(0);
            System.out.println("connecting " + dir.name());
            remainingOptions.put(new Point(r, c), ds);
            Land nextState = new Land(state);
            int[] tmp = state.nextIsland(r, c, dir);
            nextState.connect(r, c, tmp[0], tmp[1]);
            gameTree.push(nextState);
        }
    }

  private void setCurrentState(State new_state) {
    this.current_state = new_state;
  }

  public State getCurrentState() {
    return current_state;
  }
}

    private void InitializeEasy() {
        Random rand = new Random();

        setCurrentState(new State(WIDTH_EASY));
        for (int row = 0; row < debug_board_state_easy.length; row++) {
            for (int column = 0; column < debug_board_state_easy[row].length; column++) {
                debug_board_state_easy[row][column] = Integer.valueOf(rand.nextInt(5));

            }

        }


        for (int row = 0; row < debug_board_state_easy.length; row++) {
            for (int column = 0; column < debug_board_state_easy[row].length; column++) {
                System.out.print(debug_board_state_easy[row][column] + " ");
            }
            System.out.println();

        }
        this.search();
        for (int row = 0; row < WIDTH_EASY; ++row) {
            for (int column = 0; column < WIDTH_EASY; ++column) {


                getCurrentState().board_elements[row][column] = new BoardElement();
                getCurrentState().board_elements[row][column].max_connecting_bridges = Integer.valueOf(debug_board_state_easy[row][column]);
                getCurrentState().board_elements[row][column].row = row;
                getCurrentState().board_elements[row][column].col = column;

                if (getCurrentState().board_elements[row][column].max_connecting_bridges > 0) {
                    getCurrentState().board_elements[row][column].is_island = true;
                }

            }
        }

    }
\$\endgroup\$
  • \$\begingroup\$ Not sure if you tried this yet, but maybe run a debugger, set a breakpoint at or near the failing line, look at the call stack, and trace through that way? \$\endgroup\$ – Ken Aug 21 '18 at 15:10
  • \$\begingroup\$ @Ken I have tried to debug this already, unfortunately it can't find the cause of this problem ;/ \$\endgroup\$ – Wojtek T Aug 21 '18 at 15:12
  • 1
    \$\begingroup\$ The problem appears to be that the index is -1. Which line specifically in the above code throws that exception? There's a ton of array accesses in the code snippet. If you can identify which line produces the exception you work backwards from there to determine how you ended up with an index of -1. \$\endgroup\$ – Josh Aug 21 '18 at 16:09
  • \$\begingroup\$ @JoshPetrie This line throws the exepction // calculate next int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]}; \$\endgroup\$ – Wojtek T Aug 21 '18 at 16:11
2
\$\begingroup\$

Since the line that throws the exception is

int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};

we can determine that motionVector is the array being indexed (it is the only index operation), and thus it is an array of length 4 that you are attempting to index with the value -1.

The only variable used to index motionVector is i, so i must be -1.

Just above, you have

int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
int i = Arrays.asList(values()).indexOf(dir);

indexOf returns -1 if the given object cannot be found in the list, so the root cause here is that you're not able to find dir in the list produced by values().

This is likely because dir is not one of the four direction values you put into the list, or because the equality operation for Direction is wrong or will not compare equal when you expect (note how indexOf performs its test).

\$\endgroup\$
  • \$\begingroup\$ I was missing Direction] in int i = Arrays.asList(Direction.values()).indexOf(dir); \$\endgroup\$ – Wojtek T Aug 22 '18 at 10:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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