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.
- 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.
- 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.