[Resource] Graph-based Pathfinding Algorithm for Dummy Bots

This is a pathfinding/navigation algorithm for dummy bots that works on a map specific graph. I originally made it for one of my own modes, but I want to share it as an easily integratable resource.
By using this resource you can make dummy bots walk from any position to any other position of the map, if you have the corresponding graph.

Share code: MF6V4 - Version 1.0

What is a graph? A graph can be imagined as a network. It consists of a set of nodes, wich are connected by edges.
For an Overwatch-navigation-graph this would mean nodes are positions on the map a bot can walk to and edges are connections between them, if a bot can walk from one position to another. If a bot can't walk between 2 positions, they are not connected by an egde.

How is the graph type implemented in workshop? The nodes are an array of position vectors.
The edges are an array of vectors in this structure: vector(node1, weight, node2)
- node1: This is the index of the node in the nodes array the bot is coming from.
- node2: This is the index of the node in the nodes array the bot can walk towards.
- weight: This number represents how long the way from one node to the other is. If it's 0 it doesn't mean that the way is free, but that it's an unweighted (= undefined weight) edge.

Weighted, directed, what does it mean? An edge has the structure vector(node1, weight, node2).
If the edge is interpreted as directed, it means that the bot can walk from node1 to node2, but not from node2 to node1.
If the edge is interpreted as undirected, it means that the bot can walk in both directions.
If the edge has weight > 0, it is a weighted edge. The weight represents the length of the way between the nodes, so the bot can find the shortest path.
If the edge has weight = 0, it is an unweighted edge. This will break the "weighted" versions of the "compute path" rule, so you have to use the "unweighted" versions of the rule.

And wich graph type should I choose? The best type to choose is the undirected and weighted.
If you are lazy (like me) you can create an undirected and unweighted graph and enable the "auto weighting module" rule. Use the "compute path (weighted undirected)" rule in this case.
If you want the bots to be able to drop down certain ledges they can't climb back up, you need to use the directed graph types. But keep in mind that this will potentially double the amount of edges you need in your graph.

Usage:

  • Copy a graph for the map you need or create a new one using my graph-creation-tool: [Tool] Graph Creation Tool
  • Add the “nodes” and “edges” arrays to your mode, into an initialisation rule (e.g. a rule without condition).
  • Copy the rules with an initial “P” in the name from this resource and add them to your mode.
  • If you are using a graph with no unweighted edges and the edges can be passed in one direction, you use the rule “P compute path (weighted directed graph)”.
  • If you are using a graph with one or more unweighted edges and the edges can be passed in one direction, you use the rule “P compute path (unweighted directed graph)”.
  • If you are using a graph with no unweighted edges and the edges can be passed in both directions, you use the rule “P compute path (weighted undirected graph)”.
  • If you are using a graph with one or more unweighted edges and the edges can be passed in both directions, you use the rule “P compute path (unweighted undirected graph)”.
  • Make sure that no variables that are used in this resource are already used by your script. Rename them to what you need.
  • Copy all the actions of the rule “initiate pathfinding” into the rule where you want to start the pathfinding algorithm.
  • If you have an unweighted graph, you can use the rule “Auto Weighting Module” to transform it into a weighted graph. Make sure to use the “weighted” version of the rule “compute path” in this case.

Change-Log:

  • Version 1.0
  • Added support for a new graph type using undirected edges.
  • Cleaned up the code wich removed a few rules.
  • Added a second example graph that covers whole hollywood (no interiors) using undirected edges.
  • Added an auto-weighting module, wich adds the weight to unweighted edges during runtime when enabled

I hope you will find this resource useful. I would be happy to read your feedback, suggestions and bug reports. And if you have a graph for a map, feel free to share it here, so we dont have to recreate them over and over.

7 Likes

Thanks for your awesome tool. In your Graph-based Pathfinding game mode with this code: 3NB76, you defined an example graph in Hollywood map. But I couldn’t start the pathfinding algortihm and sometime it gave me this error: Can’t access target position. I tried everything like your codes in the condition rule like pressing crouch button and not being in the spawn room. but the ana dummy bots didn’t move at all.

By the way I used your Graph Creation tool and it worked well and I manged to create my own graph.

1 Like

Thank you for your kind feedback :heart:

Yes, this error gets thrown if there is no node that has LOS to the target location. You will see this error a lot with my example graph, because the example graph is kind of small and only covers the area around the defenders spawn.
Im sorry for that. Maybe I should add a graph that covers most of the map too.

Also, when you dont put nodes into interiors and small rooms and only put the nodes in the exteriors the graph will be significantly smaller.
Of course, it does work when you put the nodes in the interiors too. The graph will just be bigger.

1 Like

This is a pretty nice tool. I made a similar graph-based algorithm for my gamemode so I converted my graph to your algorithm. Maybe you will find this useful.

Code: VDC26

It works nicely, but the bot has some problems to path to the platform around the pylon. Maybe it’s because I didn’t use your tool to create to graph.

1 Like

This seems to be the case because when the bot is standing on the lower level sometimes a node on the highground is still in LOS. When this node is closer than any other node, the bot will chose it as starting node and will walk straight to it.

I can think of 3 ways to solve this:

  1. Adding the condition that the hight difference between the bot and the starting node is lower than a specific x. The problem is, what if there are stairs higher than x, but the bot can still walk them upwards? And what if there is a plateau lower than x but the bot still gets stuck when trying to get on it? This solution is to inconsistent.
  2. If the bot gets stuck, the entire calculation restarts. In this case the chances are high that the bot will choose a different starting node and will success. But this is actually a workaround and not an actual solution, because the next times the bot will get stuck again when in a similar situation.
  3. The best solution would be to add a new node close to the position where the bot was when he chose the wrong starting node.

This kind of confuses me, I work on workshop a lot and have Ai’s that are fully functional, but just run around randomly. I’m reading the description and I don’t understand what “nodes” “edges” and “unweighted edges” are. If you may can you please explain more on what they are. I have not used it yet however so if it explains itself in the Gamemode then please tell me. Thank You!

Edit: never mind, I’m reading your other post, but I will keep this here anyways just in case :slightly_smiling_face:

1 Like

A node in a graph is similar to a hub in a network. Multiple nodes are connected by edges, wich are similar to connections between hubs in a network.

In the case of Overwatch, the nodes are certain positions on the map. They are connected by the edges, wich can be imagined as walkable roads between these positions.

Edges can have a weight or not. If they don’t have a weight, all edges are considered equally valuable. If they have a weight, some edges might be considered longer or shorter (more difficult to pass/ less difficult to pass).

If the graph consists of unweighted (weight = 0) only, the bot doesnt know if he is about to walk a very long way to the next node or not. He might prefer a longer way with less nodes inbetween over a shorter way with more nodes. This way the bot will find a short path to the target position, but not necessarily the shortest.

If all the edges in a graph have a weight (in Overwatch the weight equals their length / the distance between the nodes the are connecting) the bot can differentiate between long and short edges and will always find the shortest path towards the target position.

Of course, it is way more work to create a graph with weighted edges, than a graph with just 0 weight on each edge. This is why I’m planning to add a rule that automatically applies the weight to all edges when the match starts.

Thank You! This helps me understand them a lot better now!

1 Like

Hey there. I just updated my Pathfinding Algorithm to version 1.0. I also updated the OP with a detailed description.

Additions:

  • A second example graph that covers the whole map Hollywood without the interiors. It is also added to the Graph Creation Tool.
  • An auto-weighting rule, wich transforms an unweighted graph into a weighted one (for lazy people like me who don’t want to bother with adding all the weights by hand).
  • A new graph type (with weighted and unweighted subversions) using undirected edges. Notice that the undirected graph is significantly smaller and requires less work to create, so it is kind of the main-type. It has just a slight disadvantage, wich is that bots can’t drop down ledges.

I also updated my Graph Creation Tool to version 1.2, wich is essential for working on bigger graphs. Somehow I can’t post the notification in the other thread, so I’m doing it here. (Detailed description in the OP of the other thread.)

Additions:

  • Top-down camera option that provides a better overview and area selection.
  • Option to select a specific area of the map. Only nodes wich are inside this area will be shown.
1 Like