factorio bot pathing

import kotlin.math.sqrt

val roboports = """
0,0
0,100
0,200
0,300
0,400
0,500
0,600
0,700
0,800
0,900
0,1000
100,0
100,100
100,200
100,300
100,400
100,500
100,600
100,700
100,800
100,900
100,1000
200,0
200,100
200,900
200,1000
300,0
300,100
300,900
300,1000
400,0
400,100
500,0
500,100
600,0
600,100
700,0
700,100
800,0
800,100
900,0
900,100
1000,0
1000,100
1100,0
1100,100
1200,0
1200,100
1300,0
1300,100
1400,0
1400,100
1500,0
1500,100
1600,0
1600,100
1700,0
1700,100
1800,0
1800,100
1800,900
1800,1000
1900,0
1900,100
1900,900
1900,1000
2000,0
2000,100
2000,200
2000,300
2000,400
2000,500
2000,600
2000,700
2000,800
2000,900
2000,1000
2100,0
2100,100
2100,200
2100,300
2100,400
2100,500
2100,600
2100,700
2100,800
2100,900
2100,1000
""".trimIndent().lines().mapNotNull { if (it.isBlank()) null else it.split(',').map { it.toInt() } }

val inRangeMap = Array<BooleanArray>(roboports.size) { a ->
    BooleanArray(roboports.size) { b ->
        isInRange(roboports[a], roboports[b])
    }
}

const val tech = 0 // assumes you have the 5 starter levels
const val speed = 3.0 * (3.4 + 0.65 * tech)
const val range = 1500.0 / (3.0 / speed + 5)

fun getDistSq(start: List<Int>, end: List<Int>): Int {
    val dx = start[0] - end[0]
    val dy = start[1] - end[1]
    return dx * dx + dy * dy
}

fun isInRange(start: List<Int>, end: List<Int>): Boolean {
    return getDistSq(start, end) <= range * range
}

fun getInRange(pos: Int): List<Int> {
    val list = mutableListOf<Int>()
    inRangeMap[pos].forEachIndexed { index, b ->
        if (b) list.add(index)
    }
    return list
}

data class PathInfo(val here: Int, val history: MutableList<Int>, val distSq: Int, val curDist: Double) {
    fun makeNext(next: Int, target: Int): PathInfo {
        val newHist = history.toMutableList()
        newHist.add(next)
        return PathInfo(next, newHist, getDistSq(roboports[next], roboports[target]), curDist + sqrt(getDistSq(roboports[here], roboports[next]).toDouble()))
    }

    fun getNext(target: Int, seen: List<Int>): List<PathInfo> {
        if (distSq < range * range) return listOf(makeNext(target, target))
        val list = mutableListOf<PathInfo>()
        getInRange(here).forEach { next ->
            if (!seen.contains(next)) list.add(makeNext(next, target))
        }
        return list
    }
}
data class ResultInfo(val list: List<Int>, val dist: Double) {
    companion object {
        fun makeResult(path: PathInfo): ResultInfo {
            return ResultInfo(path.history, path.curDist)
        }
    }
}
fun pathSmart(start: List<Int>, end: List<Int>): ResultInfo {
    // return a list of positions to use before going to the target, INCLUDING start and end
    val endIdx = roboports.indexOf(end)
    val list = mutableListOf(PathInfo(roboports.indexOf(start), mutableListOf(roboports.indexOf(start)), getDistSq(start, end), 0.0))
    var best: ResultInfo? = null
    val seen = mutableListOf(roboports.indexOf(start))
    while (list.isNotEmpty()) {
        val next = list.removeLast()
        if (best != null && next.curDist + sqrt(next.distSq.toDouble()) >= best.dist) continue

        val opts = next.getNext(endIdx, seen)
        if (opts.size == 1 && opts[0].distSq == 0) {
            val res = ResultInfo.makeResult(opts[0])
            if (best == null || best.dist > res.dist) {
                best = res
                list.removeIf { sqrt(it.distSq.toDouble()) + it.curDist >= best.dist }
            }
        }
        else {
            list.addAll(opts)
            list.sortByDescending { it.distSq }
        }

        seen.addAll(opts.map { it.here })
    }
    return best!!
}

fun main() {
    var timeDumb = 0L
    var timeSmart = 0L
    var distDumb = 0.0
    var distSmart = 0.0
    var numSearched = 0
    var numSkipped = 0
    println("Speed: $speed")
    println("Range: $range")
    for (a in 0 until roboports.size) {
        for (b in a+1 until roboports.size) {
            val start = System.nanoTime()
            numSearched++
            if (inRangeMap[a][b]) {
                numSkipped++
                continue
            }

            // dumb: go as far as possible then just go there slowly (not quite how it works)
            val startA = System.nanoTime()
            val dist = sqrt(getDistSq(roboports[a], roboports[b]).toDouble())
            val slowRem = dist - range
            val effectiveDist = range + slowRem * 5 // 20% speed when empty
            distDumb += effectiveDist
            val endA = System.nanoTime()

            // smart: pathfind to in-range ports
            val res = pathSmart(roboports[a], roboports[b])
            distSmart += res.dist
            val endB = System.nanoTime()
            timeDumb += endA - start
            timeSmart += endB - start - (endA - startA)
        }
    }
    println("In range: $numSkipped/$numSearched")
    println()
    println("Dumb method: Just continue at 20% speed")
    println("Total time: ${timeDumb}ns")
    println("Total dist: $distDumb")
    println()
    println("Smart method: Pathfind to avoid 20% speed")
    println("Total time: ${timeSmart}ns")
    println("Total dist: $distSmart")
    println()
    println("Extra time: ${(timeSmart-timeDumb).toDouble()/timeDumb*100.0}%")
    println("Saved dist: ${(distDumb-distSmart)/distDumb*100.0}%")
}