Skip to content

Instantly share code, notes, and snippets.

@Jire
Created January 8, 2021 01:28
Show Gist options
  • Save Jire/d3993cbaec9649596d99b17fe41285e9 to your computer and use it in GitHub Desktop.
Save Jire/d3993cbaec9649596d99b17fe41285e9 to your computer and use it in GitHub Desktop.
package ps.eden.server
import java.util.*
import kotlin.random.Random
import kotlin.system.measureNanoTime
import sun.misc.Unsafe
import java.lang.reflect.Field
object BFS {
const val columns = 64
const val rows = 64
const val colbyrows = columns * rows
const val percent = 0.3F
const val fill = -1
const val fillF = -1F
object distances {
const val bytes = colbyrows * 4L * 2
val address = unsafe.allocateMemory(bytes)
fun index(x: Int, y: Int) = ((x shl 6) or y) * 4
operator fun set(x: Int, y: Int, value: Float) {
unsafe.putFloat(address + index(x, y), value)
}
operator fun get(x: Int, y: Int): Float {
return unsafe.getFloat(address + index(x, y))
}
val fillAddress = unsafe.allocateMemory(bytes)
init {
for (x in 0..columns-1) for (y in 0..rows-1) unsafe.putFloat(fillAddress + index(x, y), fillF)
fill()
}
fun fill() = unsafe.copyMemory(fillAddress, address, bytes)
}
object collision {
fun index(x: Int, y: Int) = ((x + 1) shl 6) or (y + 1)
val bitset = BitSet(colbyrows)
operator fun set(x: Int, y: Int, value: Boolean) = bitset.set(index(x, y), value)
operator fun get(x: Int, y: Int) = bitset.get(index(x, y))
}
const val startX = 0
const val startY = 0
const val start = 0
val unsafe: Unsafe
init {
val f: Field = Unsafe::class.java.getDeclaredField("theUnsafe")
f.isAccessible = true
unsafe = f.get(null) as Unsafe
collision[startX, startY] = false
}
object queue {
const val bytes = colbyrows * 8L
val address = unsafe.allocateMemory(bytes)
fun index(i: Int) = i shl 2
operator fun set(i: Int, x: Int, y: Int) = unsafe.putLong(address + index(i), xy(x, y))
operator fun get(i: Int) = unsafe.getLong(address + index(i))
fun xy(x: Int, y: Int) = ((x.toLong() and 0xFFFFFFFF) shl 32) or (y.toLong() and 0xFFFFFFFF)
fun x(value: Long) = ((value ushr 32) and 0xFFFFFFFF).toInt()
fun y(value: Long) = (value and 0xFFFFFFFF).toInt()
val fillAddress = unsafe.allocateMemory(bytes)
init {
val negative1 = xy(-1, -1)
for (i in 0..colbyrows-1) {
unsafe.putLong(fillAddress + index(i), negative1)
}
}
fun fill() = unsafe.copyMemory(fillAddress, address, bytes)
}
var writeIndex = 0
var readIndex = 0
fun randomise() {
for (x in 0..columns-1) {
for (y in 0..rows-1) {
collision[x, y] = Random.nextFloat() < percent
}
}
}
fun reset() {
distances.fill()
writeIndex = 0
readIndex = 0
queue.fill()
queue[writeIndex, writeIndex++] = start
distances[startX, startY] = 0.0F
}
fun check(parentX: Int, parentY: Int, x: Int, y: Int) {
val px = parentX + x
val py = parentY + y
if (!collision[px, py] && distances[px, py] == -1.0F) {
distances[px, py] = distances[parentX, parentY] + 1.0F
queue[writeIndex++, px] = py
}
}
fun bfs(): Long {
return measureNanoTime {
while (readIndex < writeIndex) {
val parent = queue[readIndex++]
val parentX = queue.x(parent)
val parentY = queue.y(parent)
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)
}
}
}
@JvmStatic
fun main(args: Array<String>) {
// Warm-up
setup()
val times = 2000
var total = 0L
repeat(times) {
randomiseReset()
total += bfs()
}
println("BFS took $total avg ${total / times}")
}
@JvmStatic
fun setup() {
reset()
bfs()
}
@JvmStatic
fun randomiseReset() {
randomise()
reset()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment