CODEWITHSUNDEEP
javaalgorithmmaze
Michael Doyle
Michael Doyle

Reputation: 147

Wall follow maze solver

I'm having some trouble with my maze solving algorithm. I'm trying to implement the left hand rule.

public Direction move(View v) {
    if (!wallExistsToLeft(v)) {
        turnLeft();
    } else if (v.mayMove(direction)) {
        return direction;
    } else if (!wallExistsToRight(v)){
        turnRight();
    } else {
        turnAround();
    }
    return direction;
}

direction is always set to the current direction the maze solver is facing.

turnX changes the direction based on the direction you're currently facing

The move function returns a direction in which the maze solver moves 1 space in that direction.

Can anyone point me in the right direction? I'm sure there is some simple recursive way that this can be implemented but I can't seem to work it out.

Currently I'm failing on these two tests:

enter image description here

Any help would be greatly appreciated.

Upvotes: 2

Views: 3039

Answers (2)

example
example

Reputation: 3419

the left-hand-rule is only applicable if start and goal are next to wall segments of the same connected component of walls. If there is a pillar in the middle of a room and you start next to it you will always walk around it. the second problem comes from open spaces. If there is no wall to cling to, then the algorithm will always walk in circles. Usually one thinks if narrow corridors when suggesting this algorithm. So regardless of whether your implementation is correct, the testcases cannot be passed by a simple left-hand-rule.

Upvotes: 0

mbeckish
mbeckish

Reputation: 10579

From your pictures, it looks like you always turn right.

Which, from your code, would indicate that wallExistsToLeft(v) always returns true, and v.mayMove(direction) always returns false.

Upvotes: 2

Related Questions