# User:Dreww/Sandbox

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

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

### Reachability

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

• The south-west tile of an object destination must be within a 101x101 tile area around the starting location
• The possible path towards the destination must never leave the 128x128 tile area around the starting location
• Blockages must allow for traversing towards the destination without interruptions

First, in the case of an object destination, the target tile is set to the south-west tile if the object is larger than one tile. Then, in the cases of an NPC, player, or object destination, the target tile will be moved to the nearest of the free tiles surrounding the current target tile in the cardinal directions.

If the target tile is unreachable, the nearest free tile within a 21x21 square surrounding the current is picked as a new target tile. If no new destination can be found, pathfinding will be cancelled if the target was an object, tile, or dropped item. If the target was an NPC or player, a new pathfinding attempt will be started every tick, until a destination meets all the aforementioned requirements.

### Pathfinding for players

Pathfinding itself is executed via an algorithm called Breadth-first search and prioritizes the shortest full path.

It is important to note that the pathfinding process will try to calculate a path as close to the desired location as possible. This means the final target tile may not always be the desired target tile, and there can be multiple paths at any given time. In case of multiple paths with the same length, the one with the west-most target tile is chosen. If there are still multiple paths with the same length, the same thing is done with the south-most target tile.

An example of Breadth-First Search. The numbers represent the amount of steps required to reach each tile.

At this point, calculating possible paths is finished, and the options are walked through step-by-step. Beginning at the starting tile, a path towards the next tile is 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

This process is repeated alongside the calculated possible paths. When the target tile is reached, pathfinding is complete, and the path that was hypothetically travelled is chosen.

The full path is not stored on the server. Instead, a maximum of 25 'checkpoint tiles' are tracked, at which the direction of the path changes. These are essentially the corners of the chosen path. If more than 25 checkpoint tiles would be required to reach the target tile, the path ends at the 25th checkpoint tile. This happens even if you have not reached the target tile.

To summarize:

• The paths with least total tiles travelled are prioritized
• Paths will prioritize long, straight lines
• Paths will prioritize lines in the cardinal directions
• Paths can have a maximum of 25 corners before they end

Additionally, when there is only one checkpoint tile left in the path and the target has moved, the path is recalculated starting from the current tile. Since this does not happen every tick, it may cause players to run past their target if it has moved significantly before the re-calculation.

Finally, if the player chose the 'Follow' option on another player and there is only 1 checkpoint tile left in the path, they will enter 'Follow mode'. In this state, each path only consists of a single checkpoint tile: The last tile the followed player walked over. This often causes players to get stuck behind obstacles when following at large distances. Follow mode continues until the player cancels it by triggering a new round of pathfinding.