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.01
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.01
Fixed an issue when both the starting position and the target position had the same closest node
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.
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.
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.
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.
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:
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.
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.
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
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.
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.
Yea I have noticed this too while scripting some AI. It happens when the starting position and the ending position have the same closest node, so the path is “empty”. I will fix this soon.
If this isn’t the situation where you experienced the issue, can you post your graph and tell me wich map it is and between wich nodes the bot gets stuck?
Hey, im currently working on making a custom gamemode and i want to use your pathfinding, i need the bots to go from 1 points to the other, i did create nodes and all using your tool and ported to the gamemode, i don’t want them to pathfind to player, is there a way i can make them follow the path that i set and go from point A to point B? Its not a straight path, thats why i need the grid.
Hey, it makes me happy to read that you want to use my mode
To set the target (point B) of the pathfinding you just need to set the player variable “pathTarget” of the dummy bot to the position you want the bot to go to:
Set Player Variable(*Dummy Bot*, pathTarget, *point B*);
Then, to start the pathfinding, you need to set these 2 player variables of the bot:
Set Player Variable(*Dummy Bot*, pathPhase, 0);
Set Player Variable(*Dummy Bot*, mode, 2);
Though the “mode” variable was only meant to switch between multiple states the AI might be in, e.g. mode 0 = idle, mode 1 = fighting, mode 2 = pathfinding. So you can remove this variable from all my rules (since its in all of the conditions) if you want to.
The important variable is the “pathPhase”, with 0 being the indicator to start a new pathfinding.
Hi so I actually got around to using your tools (as the other you linked me to on my post requires a copy paste from ow to a website wich isn’t posable on console ) so I made it (obv) used the steps from this tool to import it to my game but it appears when I release my bots and start the pathfinding (I it set to ability 2 for testing reasons) I go Into 3rd person for some reason and they don’t follow the path at all and still ram into walls… Any idea as to why this may be happening? Like I said I’m pretty useless when it comes to the workshop so if it’s super obvious my bad
To be certain I would have to take a look at your code.
But I guess that the graph you created either has nodes connected wich shouldn’t be connected (so the bots “think” they can walk from one node to other - they can’t see walls or anything else around them) or it doesn’t cover enough of the maps space, since before the bots can follow the network of the graph, they need to directly move to the closest node the have in sight.
The code is “YKSRR” and for reference there are no nodes from the defenders spawn to the end of the area w/ the cherry blossom trees the rest of the map from attackers spawn to where I mentioned do have nodes though… (wich is intentional) thanks for being super helpful even though I’m stupid
) so I made it (obv) used the steps from this tool to import it to my game but it appears when I release my bots and start the pathfinding (I it set to ability 2 for testing reasons) I go Into 3rd person for some reason and they don’t follow the path at all and still ram into walls… Any idea as to why this may be happening? Like I said I’m pretty useless when it comes to the workshop so if it’s super obvious my bad