My attempt at a drunkard walk algorithm seems to generate large groups instead of more linear paths

Question

...and I'm not sure if that's normal due to the random nature of the algorithm or am I doing something wrong. What I'm doing is:

• Set a random point within map boundaries (which I called a sandbox).
• Pick a random direction
• Check if a tile at that position is not outside of map boundaries or already occupied.
• If it is a valid tile to move to then move to it
• If it isn't then pick a new random direction
• If after 4 random direction picks it's still invalid then move back one step (to avoid boxing in and doing an infinite loop)

Here's the result and the code will be posted at the bottom:

initial point hr.mlovrekov.castlegame.util.Point(0, 4)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(1, 4)
moving BOTTOM
moved to point hr.mlovrekov.castlegame.util.Point(1, 5)
moving LEFT
moved to point hr.mlovrekov.castlegame.util.Point(0, 5)
moving BOTTOM
moved to point hr.mlovrekov.castlegame.util.Point(0, 6)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(1, 6)
moving BOTTOM
moved to point hr.mlovrekov.castlegame.util.Point(1, 7)
moving LEFT
moved to point hr.mlovrekov.castlegame.util.Point(0, 7)
attempts over 4 moving back
moved back to hr.mlovrekov.castlegame.util.Point(1, 7)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(2, 7)
moving TOP
moved to point hr.mlovrekov.castlegame.util.Point(2, 6)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(3, 6)
moving TOP
moved to point hr.mlovrekov.castlegame.util.Point(3, 5)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(4, 5)
moving BOTTOM
moved to point hr.mlovrekov.castlegame.util.Point(4, 6)
moving BOTTOM
moved to point hr.mlovrekov.castlegame.util.Point(4, 7)
moving LEFT
moved to point hr.mlovrekov.castlegame.util.Point(3, 7)
attempts over 4 moving back
moved back to hr.mlovrekov.castlegame.util.Point(4, 7)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(5, 7)
moving TOP
moved to point hr.mlovrekov.castlegame.util.Point(5, 6)
moving RIGHT
moved to point hr.mlovrekov.castlegame.util.Point(6, 6)
moving TOP
moved to point hr.mlovrekov.castlegame.util.Point(6, 5)
moving LEFT
moved to point hr.mlovrekov.castlegame.util.Point(5, 5)

Final result for a sandbox of size [8][8]

false   false   false   false   false   false   false   false
false   false   false   false   false   false   false   false
false   false   false   false   false   false   false   false
false   false   false   false   false   false   false   false
true    true    false   false   false   false   false   false
true    true    false   true    true    true    true    false
true    true    true    true    true    true    true    false
true    true    true    true    true    true    false   false

As you can see lower quadrants seems to be the most truthy while upper quadrants are not visited at all. Is there a way I could implement some sort of guided randomness wherein every quadrant would be visited at least twice but still have them all connected?

As promised, here's my code:

private void constructMapPath(Random random) {
    def point = new Point(random.nextInt(SANDBOX_WIDTH), random.nextInt(SANDBOX_HEIGHT))

    def stepsMade = new ArrayList<Point>(STEPS)

    println "initial point $point"
    sandbox[point.@y][point.@x] = true

    stepsMade << new Point(point)

    Direction direction

    //point used for checking if a new position is valid
    //initialized here so that a new point isn't initialized each time a validation is performed
    def validationPoint = new Point(point)

    int attempts
    for (int step = 0; step < STEPS; ++step) {
        attempts = 0
        while (!isValidDirection((direction = Direction.randomDirection(random)), point, validationPoint)) {
            if (attempts++ > MAX_ATTEMPTS) {
                println "attempts over $MAX_ATTEMPTS moving back"
                moveBack(stepsMade, point)
                println "moved back to $point"
                attempts = 0
            }
        }

        println "moving ${direction.name()}"
        move(direction, point)
        sandbox[point.@y][point.@x] = true
        println "moved to point $point"
        stepsMade << new Point(point)
    }

}

static void moveBack(List<Point> stepsMade, Point point, int steps = 1) {
    Point previousStep = stepsMade[-1 - steps]
    point.@x = previousStep.@x
    point.@y = previousStep.@y
}

private boolean isValidDirection(Direction direction, Point point, Point validationPoint, int steps = 1) {
    validationPoint.@x = point.@x
    validationPoint.@y = point.@y
    move(direction, validationPoint, steps)
    return validationPoint.@x >= 0 && validationPoint.@x <= SANDBOX_WIDTH - 1 && validationPoint.@y >= 0 && validationPoint.@y <= SANDBOX_HEIGHT - 1 && !sandbox[validationPoint.@y][validationPoint.@x]
}

static void move(Direction direction, Point point, int steps = 1) {
    switch (direction) {
        case Direction.TOP:
            point.y -= steps
            break
        case Direction.BOTTOM:
            point.y += steps
            break
        case Direction.LEFT:
            point.x -= steps
            break
        case Direction.RIGHT:
            point.x += steps
            break
    }
}

private static enum Direction {
    TOP,
    BOTTOM,
    RIGHT,
    LEFT

    private static final Direction[] VALUES = values()
    private static final int SIZE = VALUES.size()

    static Direction randomDirection(Random random) {
        return VALUES[random.nextInt(SIZE)]
    }
}

Answer 1

One common approach to generating more corridors than open spaces is to store the direction that you took in the last step and bias your random direction choice so that it's more likely to choose to continue on in that direction.

In your code, you could just have the randomDirection method generate a number up to SIZE + n and return a stored lastDirection member variable if the value >= SIZE.

Answer 2

The algorithm you stated sounds a lot more like that of a recursive back-tracker maze generator. For the drunkard walk algorithm I believe you can move to the next cell regardless of whether it is occupied or not. As for the generation of large groups, a way to go would be to bias the next direction by the previous direction as stated by 4026.

You can look here for more information:

• http://www.gridsagegames.com/blog/2014/06/procedural-map-generation/
• http://pcg.wikidot.com/pcg-algorithm:drunkard-walk