Skip to content

Instantly share code, notes, and snippets.

@Jire
Created January 8, 2021 00:36
Show Gist options
  • Save Jire/82dce0ca7cb1344b5ae18a930158baa6 to your computer and use it in GitHub Desktop.
Save Jire/82dce0ca7cb1344b5ae18a930158baa6 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.3
const val fill = -1
//val distances = Array(columns) { Array(rows) { -1.0 } }
object distances {
const val bytes = colbyrows * 8L
val address = unsafe.allocateMemory(bytes)
operator fun set(x: Int, y: Int, value: Double) = unsafe.putDouble(address + (x * y), value)
operator fun get(x: Int, y: Int) = unsafe.getDouble(address + (x * y))
val fillAddress = unsafe.allocateMemory(bytes)
init {
for (x in 0..columns) {
for (y in 0..rows) {
unsafe.putDouble(fillAddress + (x * y), -1.0)
}
}
}
fun fill() = unsafe.copyMemory(fillAddress, address, bytes)
}
//val collision = Array(columns) { Array(rows) { Random.nextDouble() < percent } }
object collision {
val bitset = BitSet(colbyrows)
operator fun set(x: Int, y: Int, value: Boolean) = bitset.set((x + 1) * (y + 1), value)
operator fun get(x: Int, y: Int) = bitset.get((x + 1) * (y + 1))
}
val startX = 0
val startY = 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
collision[startX, startY] = false
}
object queueX {
const val bytes = colbyrows * 4L
val address = unsafe.allocateMemory(bytes)
operator fun set(i: Int, value: Int) {
//unsafe.putInt(queueAddress + (x * 4), ((x and 0xFFFF) shl 16) or (y and 0xFFFF))
unsafe.putInt(address + (i * 4), value)
}
operator fun get(i: Int) = unsafe.getInt(address + (i * 4))
val fillAddress = unsafe.allocateMemory(bytes)
init {
for (i in 0..columns) {
unsafe.putInt(fillAddress + (i * 4), -1)
}
}
fun fill() = unsafe.copyMemory(fillAddress, address, bytes)
}
object queueY {
const val bytes = colbyrows * 4L
val address = unsafe.allocateMemory(bytes)
operator fun set(i: Int, value: Int) {
unsafe.putInt(address + (i * 4), value)
}
operator fun get(i: Int) = unsafe.getInt(address + (i * 4))
val fillAddress = unsafe.allocateMemory(bytes)
init {
for (i in 0..columns) {
unsafe.putInt(fillAddress + (i * 4), -1)
}
}
fun fill() = unsafe.copyMemory(fillAddress, address, bytes)
}
/* 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
collision[x, y] = Random.nextDouble() < percent
}
}
}
fun reset() {
/*distances.forEach {
it.fill(-1.0)
}*/
distances.fill()
writeIndex = 0
readIndex = 0
/* queueX.fill(-1)
queueY.fill(-1)*/
queueX.fill()
queueY.fill()
/* queueX[writeIndex] = startX
queueY[writeIndex++] = startY*/
queueX[writeIndex] = startX
queueY[writeIndex++] = startY
//distances[startX][startY] = 0.0
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
}*/
val px = parentX + x
val py = parentY + y
if (!collision[px, py] && distances[px, py] == -1.0) {
distances[px, py] = distances[parentX, parentY] + 1.0
queueX[writeIndex] = px
queueY[writeIndex++] = py
}
}
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)
}
}
}
@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