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. Click Here To Register...]
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. Click Here To Register...]), 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. Click Here To Register...] who pointed out on Discord how it worked)
- Add tests for object interactions ("exit strategies")
Credits
- @[Only registered and activated users can see links. Click Here To Register...]: 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. Click Here To Register...]: 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. Click Here To Register...]: 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
}
