RSMod 2 Pathfinding 5.0 Implementation

[HarleyGilpin]

What has been done?

• Implemented Pathfinding 5.0 from RSMod v2
• Added collision flags for missing chunks using allocateIfAbsent method.

What needs to be done?

• Fix water tiles so NPCs can swim on water. (Ex. Ducks)
• Fix interaction distance with NPCs and Objects.
• Add back Sheep shearing.

Example

class PathFinderExample(collisionFlags: CollisionFlagMap) {

    private val pathFinder = PathFinder(collisionFlags)

    fun findPath(level: Int, srcX: Int, srcZ: Int, destX: Int, destZ: Int): Route {
        return pathFinder.findPath(
            level = level,
            srcX = srcX,
            srcZ = srcZ,
            destX = destX,
            destZ = destZ
        )
    }
}

CollisionFlagMap is responsible for storing collision flag data for the game map. When loading map data on the game-server, each object - and special tiles, such as roofs and bridges - should call the helper functions: fun CollisionFlagMap.add(x: Int, z: Int, level: Int, mask: Int) and fun CollisionFlagMap.remove(x: Int, z: Int, level: Int, mask: Int) in order to add or remove, respectively, the mask flag data.

Performance

Benchmark sources: [gg/rsmod/game/pathfinder/benchmarks/][benchmark]

Machine Specs

• OS: Windows 10 Pro (64-bit)
• CPU: Intel Core i7-7700k @ 4.20GHz (4 cores)
• RAM: 4 x 16GB DDR4-2132 (1066 MHz)
• JMH: 1.36
• VM: JDK 11.0.6, Java HotSpot(TM) 64-Bit Server VM, 11.0.6+8-LTS

PathFinder (BFS)

Benchmark                                 Mode  Cnt    Score   Error  Units
GameClickAltPath.sequentialPathFinder     avgt       733.039          ms/op
GameClickLongPath.sequentialPathFinder    avgt       367.350          ms/op
GameClickMedPath.sequentialPathFinder     avgt       310.479          ms/op
GameClickShortPath.sequentialPathFinder   avgt         7.429          ms/op

GameClickAltPath.threadLocalPathFinder    avgt       168.779          ms/op
GameClickLongPath.threadLocalPathFinder   avgt        85.639          ms/op
GameClickMedPath.threadLocalPathFinder    avgt        80.181          ms/op
GameClickShortPath.threadLocalPathFinder  avgt        19.010          ms/op

Glossary

• sequentialPathFinder: calculates 2000 paths sequentially using the same PathFinder instance.
• threadLocalPathFinder: similar to sequentialPathFinder, but uses ThreadLocal<PathFinder> to find paths asynchronously.
• GameClickAltPath: destination outside valid search distance (pathfinder forced to iterate the whole search area) (~72 tiles).
• GameClickLongPath: destination near upper limit of PathFinder::searchMapSize radius (~63 tiles).
• GameClickMedPath: destination about half of PathFinder::searchMapSize radius (~32 tiles).
• GameClickShortPath: destination near lower limit of PathFinder::searchMapSize radius (~8 tiles).

Credits

• @Tomm0017
• Kris#1337 Discord ID: 202342920106409984:
• Special thanks to @MatthewBishop for assisting me with debugging and implementation.
• Thank you @DesecratedTree for implementing Pathfinding 4.2.