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

...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))

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"
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"
}

}

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)]
}
}