Pathfinding

Overwatch Script To Workshop supports pathfinding players and dummy bots.

Some features include:

• Take advantage of hero abilities using the attributes system.
• Can be customized to prefer speed or performance.
• Paths can be precalculated so the path to take from anywhere in the map to a certain destination will instantly be known.
• Pathfinding can be adjusted according to the state of the game.

If you don't have OSTW already, see getting started.

Table of contents

• Creating Pathmaps
  • The editor
  • Adding attributes
  • Compiling
  • Editing pathmap files
• Using Pathmaps
  • ★ Common functionality
  • ★ Attributes
  • ★ Bakemaps (new!)
  • Resolving paths
  • Server load VS algorithm speed
  • Hooks
  • Dynamically changing pathmaps
  • Smoothing paths (new!)
• Examples

Creating Pathmaps

The first step to pathfinding is to create a pathmap.

Copy the pathmap editor code by running the Overwatch Script To Workshop: Copy pathmap editor code command in Visual Studio Code. This will copy workshop rules used to create pathmaps to the clipboard. Paste the rules into Overwatch then enable the map you want to create a pathmap for.

The editor

There are 3 modes in the pathfinding editor: Free-Walk, Place Nodes + Segments, and Add Attributes. Press interact to cycle between them.

---

Pathmaps contain an array of nodes that will be navigated between. While in the Place Nodes + Segments mode, press primary fire to create a node (as shown by blue spheres). Pressing crouch + primary fire will delete the closest nodes and any segments connected to them.

After creating nodes, press secondary fire to select them. Selected nodes will be green. Press ability 2 to connect the selected nodes with segments (as shown by grapple beams). Pressing crouch + secondary fire will deselect all nodes. Pressing crouch + ability 2 will delete all segments in-between the selected nodes.

With the nodes now connected, pathfinding can move between them.

---

At the top of the editor, you can see the Connect Mode text. This determines how all the selected nodes are connected with segments. There are 3 ways they can be connected: Connect All, Connect As Path, and Connect As Star. You can cycle through these by pressing reload while in the Place Nodes + Segments mode.

In this example, the nodes are selected in the order 3, 4, 5, 2, 6.

Connect All: Connects selected all nodes to each other.

Connect As Path: Creates a segment between all the selected nodes in the order they were selected.

Connect As Star: Creates a segment from the first selected node to all other selected nodes.

Adding Attributes

Attributes can allow you to take advantage of hero abilities and block paths. For more information, view the attributes section.

Attributes can be added in the 'Add Attributes' mode. To add an attribute, select 2 nodes you want to add an attribute in-between, press reload and crouch + reload to set the attribute value, then press primary fire to toggle the current attribute value.

In the image below, CurrentSegmentAttribute will return [3] if the player is travelling from node 68 to 99, and will return [2] when traveling from node 99 to 68. To change the attribute when traveling from 68 to 99, select 68 first. Otherwise, to change the attribute when traveling from 99 to 68, select 99 then 68.

Compiling

When you are done creating your pathmap, execute the 'Acknowledge' communication to compile. (Default key is G.) You will see the messages Compiling... followed by Compiling Finished!. Open the inspector and click copy to clipboard current variables as CSV text. on the GLOBAL variable target.

With the CSV values copied to the clipboard, open vscode, press ctrl+shift+p then run the Overwatch Script To Workshop: Create pathmap from CSV clipboard command. This will reveal a prompt to save the exported pathmap file.

Editing pathmap files

To open pathmap files in the ingame editor, run the Overwatch Script To Workshop: Copy pathmap editor code command with a pathmap file opened. Then paste the rules into Overwatch.

To save the edited file, follow the compiling steps again.

Using Pathmaps

The bulk of pathfinding functions found in OSTW are within the Pathmap class.

Pathmaps can be imported to your code like so:

globalvar Pathmap map = new Pathmap("path-to-file.pathmap");

Since OSTW supports object oriented programming, you can do something like this instead and it will work as expected:

globalvar Pathmap map;

rule: "Get map"
{
    // Get the Hanamura pathmap.
    if (CurrentMap() == Map.Hanamura)
        map = new Pathmap("hanamura.pathmap");

    // Get the Horizon Lunar Colony pathmap.
    else if (CurrentMap() == Map.Horizon_Lunar_Colony)
        map = new Pathmap("horizon.pathmap");

    // Get the Dorado pathmap.
    else if (CurrentMap() == Map.Dorado)
        map = new Pathmap("dorado.pathmap");

    // Current map not supported.
    else
        SmallMessage(AllPLayers(), <"The map '<0>' is not supported.", CurrentMap()>);
}

Or:

globalvar Pathmap[] maps = [new Pathmap("hanamura.pathmap"), new Pathmap("horizon.pathmap"), new Pathmap("dorado.pathmap")];

With your pathmap imported, you can run functions such as Pathfind, PathfindAll, or Resolve.

Common functionality

Static functions are called using the class itself, and object functions are called using an object reference. Parameters surrounded by [] are optional parameters.

Pathmap class

Pathmap map = new Pathmap(...);

// Object pathmap functions
map.Pathfind(player, destination, [attributes], [onLoopStart], [onNeighborLoopStart]); // Pathfinds a player to the specified destination.
map.PathfindAll(players, destination, [attributes], [onLoopStart], [onNeighborLoopStart]); // Pathfinds an array of players to the specified destination. Unlike the Pathfind function, this does not support moving players. If you are to pathfind an array of moving players, use the Resolve function instead.
map.PathfindEither(player, destinations, [attributes], [onLoopStart], [onNeighborLoopStart]); // Pathfinds a player to the closest position in the 'destinations' array.
PathResolve resolve = map.Resolve(destination); // Resolves a destination. This can be used to cache the path required to reach a destination and reduce server load usage.

// Static pathmap functions
define isPathfinding = Pathmap.IsPathfinding(player); // Determines if a player is pathfinding.
define isStuck = Pathmap.IsPathfindingStuck(player, [speed_scalar]); // Determines if a player takes longer than expected to reach the next node.
Pathmap.StopPathfind(player); // Stops the specified player from pathfinding.
define attribute == Pathmap.CurrentSegmentAttribute(player); // The current segment attribues of a pathfinding player.

PathResolve class

PathResolve resolve = map.Resolve(destination);

// Object PathResolve functions
resolve.Pathfind(players); // Pathfinds the array of players to the PathResolve's destination.

---

Not all of the pathfinding functions are listed here! Use the auto-completion to list all the pathfinding functions.

Attributes

Segments can be tagged with an array of attributes. Attributes can be used for many things, including:

• Jumping over obstacles.
• Taking advantage of hero abilities to navigate cliffs or terrain.
• Blocking a path if a hero does not have the capabilites to transverse a route.
• Blocking a segment if a payload gate is closed or opened.

You can assign different attributes to different hero abilties. For example, you can have an attribute 1 mean that pharahs will use their jump jets, or an attribute of 2 will have mei's create a wall underneath them. You can then program these actions in your code to activate when an attribute of 1 or 2 is reached.

If a segment is marked with an attribute, it will not be transversed unless the pathfinder function's attribute parameter is given the specified attribute.

Pathmap map;

// The player will pathfind through segments that have an attribute of 1 or 3, but not any segments that have any other attribute.
map.Pathfind(player: eventPlayer, destination: walkTo, attributes: [1,3]);

The Pathmap.CurrentSegmentAttribute function can be used to get an array of the current segment's attribute.

Example:

define eventPlayer: EventPlayer();

// This rule will cause the player to jump when an attribute of 1 is reached.
rule: "Pathfinder: Jump when an attribute of 1 is reached."
Event.OngoingPlayer
if (Pathmap.CurrentSegmentAttribute(eventPlayer).Contains(1))
{
    PressButton(eventPlayer, Button.Jump);
}

// Genji wall climb when an attribute of 2 is reached.
playervar define climbing;

rule: "Nav: Gengi: Climb Start"
Event.OngoingPlayer
Player.Genji
if (Pathmap.CurrentSegmentAttribute(eventPlayer).Contains(2))
{
    MinWait();
    StartHoldingButton(eventPlayer, Button.Jump);
    climbing = true;
}

rule: "Nav: Gengi: Climb End"
Event.OngoingPlayer
Player.Genji
if (climbing)
if (Pathmap.CurrentSegmentAttribute(eventPlayer).Contains(2) == false)
{
    StopHoldingButton(eventPlayer, Button.Jump);
    climbing = false;
}

Bakemaps

Bakemaps is a very fast pathfinding system. You can pathfind 12 players across the entire map and the shortest path will be found in a single tick (without waits!) and without crashing the server.

To create a bakemap:

// Live bakemap (slower to bake, pathmap and attributes can be set at runtime)
Bakemap bake = map.Bake(attributes:[0,1], printProgress: p => {
    // Show baking progress as a HUD text
    CreateHudText(AllPlayers(), <'Baking: <0>%', Min(100, p * 100)>, Location: Location.Top, SortOrder: 2);
});

// Compressed bakemap (*much* faster to bake, pathmap and attributes must be known at compilation)
Number i = 0;
Bakemap bake = map.BakeCompressed('original.pathmap', attributes:[0,1], printProgress: p => {
    // Show baking progress as a HUD text
    CreateHudText(AllPlayers(), <'Baking: <0>%', Min(100, p * 100)>, Location: Location.Top, SortOrder: 2);
}, onLoopStart: () => { // Override onLoopStart so baking is x5 faster
    i++;
    if (!(i % 5))
        MinWait();
});

Then pathfind with the bakemap:

bake.Pathfind(players, destination);

Resolving paths

Paths can be precalculated and reused using the Pathmap.Resolve() function. After a destination is resolved, pathfinding will instantly know the path to take from anywhere on the map with almost no affect on the server load.

Pathmap map = new Pathmap("my_pathmap.pathmap");
PathResolve obj = map.Resolve(ObjectivePosition(0));

...

obj.Pathfind(eventPlayer);

Server load VS algorithm speed

You can customize the pathfinding functions depending on if server load or speed is more important.

Some pathfinding functions contain optional parameters that can be used to determine where and when waits will occur while pathfinding. There are 2 main loops that make up pathfinding, where one is nested in the other. By default, Wait(0.016) will occur at the start of each of these loops.

In the example below, a wait will occur every 4 iterations of the nested loop.

define waitIterate = 0;

hanamuraMap.Pathfind(lastDummyBot, LookingAtSpot, onLoopStart: () => {}, onNeighborLoopStart: () => {
    waitIterate++;
    if (waitIterate % 4 == 0) MinWait();
});

Hooks

Hooks can be used to modify how pathfinding-generated rules are created. More information on hooks is provided in their completion. Hooks are set by assigning them in the rule-level, like so:

globalvar define myVariable;

Pathmap.OnPathStartHook = () => {
    // Specify additonal code to run when the 'Pathfinder: Resolve Current' rule runs.
};

rule: "My rule" { ... }

Currently, there are 5 hooks.

• Pathmap.OnPathStartHook: The code to run when a path starts.
• Pathmap.OnNodeReachedHook: The code to run when a player reaches a node.
• Pathmap.OnPathCompleted: The code to run when a player reaches their destination.
• Pathmap.IsNodeReachedDeterminer: The condition used to determine wether or not a player reached a node.
• Pathmap.ApplicableNodeDeterminer: The code used to get a node from a position.

When pathfinding occurs, the starting node is chosen by the closest node to the player. This means in the image above, if a player were to start pathfinding while on top of the arch, the chosen node will be the one underneith. This will cause the pathfinder to run in place, futily trying to get to the node. Overriding the Pathmap.ApplicableNodeDeterminer hook to consider line-of-sight will fix this:

// Set the 'ApplicableNodeDeterminer' hook to consider line-of-sight.
Pathmap.ApplicableNodeDeterminer = (Vector[] nodes, Vector position) => {
    // Return the index of the closest node that is in line-of-sight.
    return nodes.IndexOf(nodes.FilteredArray(Vector node => node.IsInLineOfSight(position)).SortedArray(Vector node => node.DistanceTo(position))[0]);
};

Dynamically changing pathmaps

You can change pathmaps at runtime using functions like AddNode, AddSegment, AddAttribute, etc.

In the jump pad example, jump pads predict the landing location and connect segments as needed. I recommend checking out the source code for more information on dynamically changing pathmaps.

Smoothing Paths

These Pathmap functions can be used to smooth out the path of pathfinding players and make it look more natural. Try adding this to your script:

rule: 'Pathfinder: skip if visible'
Event.OngoingPlayer
if (Pathmap.IsPathfinding(EventPlayer())) // Make sure the player is pathfinding.
if (Pathmap.CurrentNode(EventPlayer()) != -1) // This ensures that we do not skip when the player is walking towards their destination.
if (Pathmap.CurrentPosition(EventPlayer()).Y - Pathmap.NextPosition(EventPlayer()).Y~Abs() < 1) // Height of position and skipped node must be < 1 meters.
if (IsInLineOfSight( // Make sure the player's position and the next node is in LOS.
    StartPos: PositionOf() + Up() * .25,
    EndPos: Pathmap.NextPosition(EventPlayer()) + Up() * .25
))
{
    Wait(0.1); // A small wait so the player has a chance to walk past the corner (so they do not bump)
    Pathmap.SkipNode(EventPlayer());
    Wait(0.1);
    LoopIfConditionIsTrue();
}

The reason why this isn't implemented natively is because there may be some cases with pathmaps where this will skip nodes unintentionally, but it will be fine in most cases.

Examples

Jump-pads

This example allows you to create jump pads. The jump pads will dynamically create paths so dummy bots can use them.

The entire map except the last point is mapped out, I recommend mapping the last point yourself by editing the pathmap file with the pathmap editor.

Source code

Import code: AFAAX

• Press crouch to summon a dummy bot.
• Communicate hello to pathfind the dummy bot to the position you are looking at.
• Press interact to create a jump pad. Pathfinding dummy bots will use the jump pad if it will be faster to take to reach the destination.