Thread: BFS Path Finder

Recently there's been a lot of talk about pathfinding, which I coincidentally had to start on for rsmod. Decided to make an open-source solution for anyone who might be wanting to use it in its entirety, or use it as reference.

Code can be found on GitHub: [Only registered and activated users can see links. ]

Installation, example usage, and benchmark can be found above. To make the thread not look as empty, will include the example usage code.


Why use this pathfinding implementation?

• One of the only (if not only) standalone pathfinding impl. on github, which means it can be a collaborative effort from the rsps community since we all want 100% rs pathing!!
• Performs faster than client (gains mainly from using 1d array vs 2d). Though the big gains would come from using something like coroutines (as demonstrated [Only registered and activated users can see links. ]), it outperforms the client most of the time.
• As far as I've been able to test and compare to OSRS, all paths have been 100% accurate.
• On maven central, so can be easily included into any project (org.rsmod:pathfinder:1.1.2)

What is left to do?

• DumbPathFinder has only been recently added and I've not had the chance to compare to OSRS for accuracy (credits to @[Only registered and activated users can see links. ] who pointed out on Discord how it worked)
• Add tests for object interactions ("exit strategies")

Credits

• @[Only registered and activated users can see links. ]: spoke a bunch about how path finding works on OSRS and came up with theories for certain interactions (player 'turn' limit, accepting destinations up to 74 tiles, etc)
  @[Only registered and activated users can see links. ]: I had previously asked for ways to contribute and scu suggested to write libraries instead of frameworks
  @[Only registered and activated users can see links. ]: as previously mentioned, DumbPathFinder logic came from something they explained on Discord a while back

Example usage

Code:

fun smartRoute(srcX: Int, srcY: Int, destX: Int, destY: Int, level: Int): Route {
    val pf = SmartPathFinder()
    val flags = clipFlags(srcX, srcY, level, pf.searchMapSize)
    return pf.findPath(flags, srcX, srcY, destX, destY)
}

fun clipFlags(centerX: Int, centerY: Int, level: Int, size: Int): IntArray {
    val half = size / 2
    val flags = IntArray(size * size)
    val rangeX = centerX - half until centerX + half
    val rangeY = centerY - half until centerY + half
    for (y in rangeY) {
        for (x in rangeX) {
            val coords = Coordinates(x, y, level)
            /*
             * collision map stores tile collision flags for all
             * tiles in the world.
             */
            val flag = collisionMap.get(coords)
            val lx = x - (centerX - half)
            val ly = y - (centerY - half)
            val index = (ly * size) + lx
            flags[index] = flag
        }
    }
    return flags
}