Pathfinding

From Old School RuneScape Wiki
Jump to: navigation, search

Pathfinding is the process of calculating which path of game squares (after this point referred to as 'tile') a player or NPC should move to get to its desired destination. This process happens whenever a player or NPC attempts to walk, run, or interact with a different player, different NPC, or an object in the world.

Blockage and valid movement[edit | edit source]

Whether a tile can be reached from another depends on the blockage properties of both the tiles. These blockages can occur in a number of combinations, but there are four main types.

  • Non-blocking tile: A non-blocking, or free, tile is a tile that allows free movement from all directions, given that the adjacent tiles do not have any blockage that prevents this. It is a tile that does not have any objects, walls or pillars and can be stood on.
  • Full-blocking tile: A full-blocking tile is one that completely disallows movement from all directions. These tiles are usually occupied by an object and cannot be reached by normal means.
  • Walls: Walls occupy the borders of a tile. They block movement from the same direction as their location on the tile. Despite blocking movement, walls do not fully occupy the tile. It is possible to stand on a tile that has one or more walls on its borders.
  • Pillars: Pillars occupy the corners of a tile. They normally block movement from the diagonal direction just like walls do for cardinal directions. However, pillars are rarely added on all four adjacent tiles, often making it possible to walk through them in one or more directions, typically south-west to north-east and vice-versa. It is possible to stand on a tile that has one or more pillars on its corners.



Calculation[edit | edit source]

The pathfinding algorithm is determined largely by three steps. First, it's determined whether the requested location based on the player's click is a valid candidate for pathing and the requested tiles are selected. Second, a nuanced algorithm is used to determine the target tile and the possible paths. Third, the ultimate destination tile is chosen.

The second step to find the target tile roughly operates according to the following principles:

  • Paths must never leave the 128x128 tile area centred at the player's starting location,
  • The paths with least total tiles traveled are prioritized, and
  • Paths will prioritize lines in the cardinal directions and generally long, straight lines.

Determining whether pathing will be attempted and the requested tiles[edit | edit source]

In order to start pathfinding towards a destination, the destination must be considered reachable. Being reachable may sound straightforward, but a condition has to be met:

  • the south-west tile of an object destination must be within a 101x101 tile area around the starting location.

When clicking on a tile, the requested tile will be the tile that was clicked on. When clicking on an npc, object, or player, the requested tiles will be all tiles within melee range of the npc, object, or player.

Determining the target tile[edit | edit source]

Pathfinding itself is executed via an algorithm called Breadth-first search which prioritizes the shortest path that arrives to the requested tiles. It is important to note that the pathfinding process will try to calculate a path to a requested tile; however, this isn't always possible, so the final target tile may not always be among the requested tiles.

Beginning at the starting tile, neighboring tiles are iteratively checked in the following order to determine which way to continue:

  1. West
  2. East
  3. South
  4. North
  5. South-west
  6. South-east
  7. North-west
  8. North-east
The Breadth-First Search process and pathfinding calculations visualized. The numbers represent the amount of steps required to reach each tile.

Each time a new tile is seen by the algorithm, the path distance from the starting location is stored (as one higher than the previous tile) and the previous tile is (indirectly) stored. This process with the path distances included is visualized in the figure to the right. Instead of checking all neighboring tiles, there are further constraints that:

  • a considered tile needs to be within a 128x128 tile grid with the player's starting location at the north-east corner of the centre and
  • obstructions can block some tiles from considered as neighbors of other tiles.

The breadth-first search algorithm terminates when all reachable tiles within the 128x128 tile grid are considered or a requested tile is discovered.

In the case that the algorithm discovered a requested tile, set that requested tile as the target tile. Otherwise, in the case that there is not a path within the 128x128 tile grid to a requested tile, a second search is started. All tiles are considered within a 21x21 grid which is centred at the south-west tile of the clicked npc, object, or player or the clicked tile. The tiles are considered in order with western priority then southern priority. The target tile is set as the first tile found for which there exists a previously found path which

  • has path length lass than 100,
  • has the shortest path distance, and
  • has target tile as close as possible in Euclidean distance to the clicked tile or the clicked npc, object, or player.

In case that the no such tile was found, store no target tile.

The checkpoint tiles and destination tile[edit | edit source]

The target tile previously located is not always the destination tile at which the player will arrive when finishing pathing. Instead, the calculated path is post-processed by extracting only the first 25 corners of the path, called "checkpoint tiles". The last checkpoint tile is intended to be the ultimate destination of the pathing. As an example, if more than 25 checkpoint tiles would be required to reach the target tile, the destination tile is set at the 25th checkpoint tile of the path to the target tile. This can cause the path to appear to "stop early".

While pathing to each checkpoint tile, the player uses "follow mode" pathing identical to the pathing of NPCs. This pathing mode naively paths diagonally to the end tile and then straight if there's no diagonals left. In standard situations, the path from one checkpoint tile to the next is a straight line so the pathing appears straightforward. However, sometimes a player will be moved by external factors (such as firemaking) or the obstruction landscape can change (such as by opening a gate).

Path recalculation[edit | edit source]

If no target tile was found, pathfinding will have been permanently cancelled if the target was an object, tile, or dropped item. However, if the clicked entity is an NPC or player, a new pathfinding attempt will be started every tick, until a target tile can be found that meets all the aforementioned requirements.

Additionally, when there is only one checkpoint tile left in the path and the target has moved, the path is recalculated every tick starting from the current tile. Despite this, since players can traverse two checkpoint tiles in one tick, players may run past their target if it has moved towards them.

Changes[edit | edit source]

Date Changes
17 December 2013
(update)

When you are following a player in walk-mode, you should no longer find that you randomly lag behind them by an extra tile, forcing you to consume your run energy to catch up.