[Resource] Graph-based Pathfinding Algorithm for Dummy Bots

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

Sometimes the dummy bot will get stuck on one nodes, How do i fix this?

(P compute path (unweighted directed graph))

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?

That’s probably what’s happening. if you want to take a look anyways F7X9Z it got stuck on node 0.

I fixed the issue that I mentioned.

1 Like

Been using this for one of my modes, so I felt like bumping it to the top for others to see!

2 Likes

So glad to read :heart:

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.

1 Like

Hey, it makes me happy to read that you want to use my mode :slight_smile:

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.

2 Likes

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 :frowning: ) 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.

1 Like

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 :slight_smile:

I have taken a look into your gamemode. Unfortunately, your graph has a few issues, wich breaks the algorithm.
First, nodes[0] is 0 and not a vector, wich breaks the algorithm, since the number 0 has always distance 0 to everything, no matter what. I could add a condition for my algorithm wich filters the zeros from the array, but it’s not yet fixed. As a workaround, you could put a vector wich is below the ground as nodes[0]. Later you might be able to put an actual valid node into that index.
Second, there are some connections (edges) going through walls, wich you can see when you put your graph into my graph creation tool. Those shouldn’t exist, since it will tell the bots that they can walk through these walls, when they actually can’t.

You need to rework your graph.
When you do so you can make your life a little easier by only adding one edge between to nodes to connect them. You only need 2 edges (both directions) if you are using the directed version of my algorithm, wich you didn’t.

For the testing in your gamemode you should temporarily disable the other rules that make the dummy bots walk or add a condition event player.mode == 1 to them, so you can toggle between pathfinding movement (event player.mode == 2) and your custom movement.

Also, you need to fix the last 4 actions of the dummy spawn rule:

Variablen
{
	player:
		27: pathTarget
}

aktionen
{
	Players In Slot(0, Team 2).pathTarget = Position Of(Players In Slot(0, Team 1));
}

The “pathTarget” variable of the dummy bot (mercy on slot 0 team 2 in this case) needs to be set to the position the bot will move to (the position of the player in this case).

aktionen
{
	Start Camera(Players In Slot(0, Team 1), Ray Cast Hit Position(Eye Position(Players In Slot(0, Team 2)), Eye Position(
		Players In Slot(0, Team 2)) + Facing Direction Of(Players In Slot(0, Team 1)) * -2, Null, All Players(All Teams), False),
		Eye Position(Players In Slot(0, Team 2)) + Facing Direction Of(Players In Slot(0, Team 1)), 50);
}

This is a debug action to see what the bot is doing while pathfinding (I replaced “event player” with the mercy bot here). Feel free to remove it.

Variablen
{
	player:
		26: mode
		28: pathPhase
}

aktionen
{
	Players In Slot(0, Team 2).pathPhase = 0;
	Players In Slot(0, Team 2).mode = 2;
}

These 2 player variables need to be set for the dummy bot (the mercy bot in this case) to start the pathfinding algorithm for this bot.

I hope this will help you fixing your gamemode :slight_smile:

Note: If you experience high server load and crashes when multiple bots pathfind at the same time, add a short wait action to the rule “P compute path (unweighted undirected graph)” as the second last action (before the End; and after the Event Player.pathNodesVisited[Event Player.pathCurrentNode] = 1;)

1 Like

Thank you so much :slight_smile: 1.i assumed the first one was ment to be was empty for some reason (honestly don’t know why) 2.i will definitely redo the graph 3.i didn’t realise I need to disable the walk rule once again my bad 4.thanks for the corrections to the camera and mercy as I had no idea what was going wrong as I mentioned thank you so much for this :slight_smile:

1 Like