Somehow object gets mutated after list.add(object) during recursion. Explain?

Question

So the task I am currently tackling is fairly simple. I must find all exits from a given starting point within every given maze and print the path onto the screen. Multiple exits are possible. A maze can look like this:

    #####.###
    #.....#.#
    #.#####.#
    #.#.....#
    #.#.###.#
    #.#.#.#.#
    #.....#.#
    #########

A square is a Square. A point is a WhiteSquare and a hashtag is a BlackSquare, and they are both subclasses of Square. Opening is a subclass of WhiteSquare.

The idea is to call go() on every neighbour of the square I am currently in. The method go() in a black square doesn't do anything, so only white squares are functional in that regard. Every time go() is called, a copy of a list containing all the previous visited squares are sent as a parameter, so that it doesn't call go() on the previous neighbour. This is because I want the algorithm to work with cyclical mazes as well. As soon as I hit an opening, I will add the path onto the start square's list of possible exits (list of lists). Here is the code:

public void go(ArrayList<Rute> path, WhiteSquare startSquare) {
    ArrayList<Rute> pathCopy = path;
    pathCopy.add(this);
    if (this instanceof Opening) {
        startSquare.addPossibleExit(pathCopy);
        return;
    }
    for (Square neighbour : this.getNeighbours()) {
        if (!path.contains(neighbour)) {
            neighbour.go(pathCopy, startSquare);
        }
    }
}

System.out.println(startSquare.exits) after an opening is found will print the correct path. Everything works great. However, if there are more Squares to go through AFTER an opening is found, somehow the correct path in exits will start to grow within the list itself, even after it has been added. I dont get it. Example if startRoute is (3, 1) in the maze above (pseudocode):

System.out.println(Square.toString() + " go. " + Exits: " + startSquare.getExits())

if (this instanceof Opening) {print("Opening found!")}

Will print out:

(3, 1) go. Exits: []
(2, 1) go. Exits: []
(1, 1) go. Exits: []
(1, 2) go. Exits: []
(1, 3) go. Exits: []
(1, 4) go. Exits: []
(1, 5) go. Exits: []
(0, 5) go. Exits: []
Opening found!
(4, 1) go. Exits: [[(3, 1), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (0, 5)]]
(5, 1) go. Exits: [[(3, 1), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (0, 5), (4, 1)]]
(6, 1) go. Exits: [[(3, 1), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (0, 5), (4, 1), (5, 1)]]

I can't explain what is going on here. I do not want the path to grow after it has been added to exits.

score 0 · Answer 1 · answered Apr 13 '18 at 14:54

pathCopy is not a new ArrayList, it's a reference to path and when you add to pathCopy it actually adds to path.

You can create a new ArrayList and then use .addAll(path) to copy all the values to the new ArrayList.

Every variable in Java is a pointer, except basic types, like int, bool. When you assign a 'complex' type it assign the pointer not the value.

A explanation about reference and value can be found here

score 0 · Answer 2 · answered Apr 13 '18 at 14:58

0

As mentioned in the question about arraylist copying you're not really copying the array by the assignment. You should create a new array and copy the items.

ArrayList<Rute> pathCopy = new ArrayList<>(path);

answered Apr 13 '18 at 14:58

Hassan Pezeshk

343
5
16

Somehow object gets mutated after list.add(object) during recursion. Explain?

2 Answers2