Breadth first search

bfs.scratch.kts

import kotlin.random.Random
import kotlin.system.measureNanoTime

val columns = 64
val rows = 64
val percent = 0.3
val distances = Array(columns) { Array(rows) { -1.0 } }
val collision = Array(columns) { Array(rows) { Random.nextDouble() < percent } }

val startX = 0
val startY = 0

collision[startX][startY] = false

val queueX = IntArray(columns * rows) { -1 }
val queueY = IntArray(columns * rows) { -1 }

var writeIndex = 0
var readIndex = 0

fun randomise() {
    for (x in 0 until columns) {
        for (y in 0 until rows) {
            collision[x][y] = Random.nextDouble() < percent
        }
    }
}

fun reset() {
    distances.forEach {
        it.fill(-1.0)
    }
    writeIndex = 0
    readIndex = 0
    queueX.fill(-1)
    queueY.fill(-1)

    queueX[writeIndex] = startX
    queueY[writeIndex++] = startY
    distances[startX][startY] = 0.0
}

fun check(parentX: Int, parentY: Int, x: Int, y: Int) {
    if (collision.getOrNull(parentX + x)?.getOrNull(parentY + y) == false && distances[parentX + x][parentY + y] == -1.0) {
        distances[parentX + x][parentY + y] = distances[parentX][parentY] + 1.0
        queueX[writeIndex] = parentX + x
        queueY[writeIndex++] = parentY + y
    }
}

fun bfs(): Long {
    return measureNanoTime {
        while (readIndex < writeIndex) {
            val parentX = queueX[readIndex]
            val parentY = queueY[readIndex++]
            check(parentX, parentY, -1, 0)
            check(parentX, parentY, 1, 0)
            check(parentX, parentY, 0, -1)
            check(parentX, parentY, 0, 1)
            check(parentX, parentY, -1, -1)
            check(parentX, parentY, 1, -1)
            check(parentX, parentY, -1, 1)
            check(parentX, parentY, 1, 1)
        }
    }
}

// Warm-up
reset()
bfs()


val times = 2000
var total = 0L
repeat(times) {
    randomise()
    reset()
    total += bfs()
}
println("BFS took $total avg ${total / times}")