This page explains how the Runescape Pathfinder works.

An arry of nodes, created with the tool at the end of this page, is stored in the file nodedata.js. It is assumed that when two nodes are connected, one can walk between them without hitting any obstacles. This assumption is not as strong as it sounds: in Runescape, stepping to an adjacent square takes the same amount of time as stepping diagonally, so the length of the shortest path between two points is given by the Chebychev distance. Unlike the usual metric (in which the only shortest path between two points is a straight line), there are many shortest paths between two points, and it may be possible to find one even if some obstacles are present.

The node array also contains information on teleport destinations and links between nodes (such as taking a boat from Port Sarim to Entrana). For simplicity the algorithm assumes that all teleports and links are instant. When many nodes are interlinked (such as the fairy rings), they are put on a network rather than each being linked to the other. Data about teleports and links is also stored in the file teledata.js

When the user has entered start and end points, the A* algorithm is used to find a path from the end to the start or any teleport destination (taking into account links). The heuristic function used is the length the shortest such path would have if all nodes were connected. This function is itself complicated to compute, and is found using Dijkstra's algorithm.

The implementation of the Runescape map in the google API was taken from here. For this, the world map was cut into tiles using ImageMagick and this perl file.

Create(1) Connect(2) Link to selected(3) Link from selected(4)
Free Web Hosting