BFS.kt

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