How can I make a more efficient node-based AI pathfinding system?

How do I...?
1

What I’m trying to do
I want to make a top-down shooter that pits one player against one enemy. This enemy will travel by pathfinding to nodes. The purpose of this node system is to:

  1. Have better pathfinding than the default GDevelop pathfind behavior by itself.

  2. Allow for special actions related to nodes. Such as “If player is at X and unarmed, move to X. If player is at X and armed, move to Y and take cover.”

What I have so far
I have built a node system made of numbers. It is functional and works by pathfinding the enemy to a number. For example, if the enemy needs to move to 1 and is at node 5, he heads to node 4. Then from 4, he moves to 3. And so on.

PathEvent1
PathEvent11076×771 82.2 KB

This is how my node system functions. If the enemy needs to go to node 1 like in the event example above, every other node in existence has a response. If the enemy is touching node 40, I will have made a set path on how he can get from 40 to 1. Every path will take every other node into consideration.

“The boolean value of scene variable Moving” tells the enemy to move.

“GoHereEnemy is in collision with _1” tells the enemy what path will be considered. In this case, move to node 1 (by moving to related nodes).

“RifleEnemy distance to X is below 50 pixels” tells the enemy which node he is at right now.

These three are combined to determine which node should be moved to next. If the enemy is told that the path is for 1 but he is touching node 9, then he moves to node 7. Then he moves to node 5. Then 3, 2, and finally 1.

The issue I am having
The issue is a workload/efficiency one.

If I have 40 nodes, each node will take 39 events. This way the enemy can always reach every node from anywhere.

40 multiplied by 39 is 1,560. That is 1,560 events to the basic act of pathfinding for a small map.

I estimate that most of my maps need to be even larger than merely 40 nodes.

What should I do in order to cut down on the amount of events I’ll need to make node pathfinding? Please explain the solution to me in layman’s terms as I am pretty new to GDevelop… especially if mathematics are required.

2

Instead of using different objects for each node, you could use the same object but have a variable with a different value (like a node number) to differentiate them all. Its possible to generalize the code to apply to all of the nodes using the “For each object…” event type (can find it in the right click menu in the event sheet). Take care to avoid running it every frame or it could cause performance problems.

It can be quite tricky to work with multiple instances of the same object since event conditions will filter down the instances as you add conditions, making it impossible to compare one object matching a filter to another object not matching a filter. There are ways around it using extra objects or scene variables. It’s kind of hard to explain and would probably be best to find an example.

I’ll point you towards an extension called Linked Object tools. It has the ability to do node based pathfinding like you described and if you check the wiki page linked there i believe there are examples there to study to learn about how it works. I remember one trick about it is you need to place the origin of your sprites in their center or else it won’t detect which node the object is on.

This is definitely something you can achieve, but isn’t the simplest type of game to create. If you are new to GDevelop you might want to create an easier type of game first just to get familiar with it. But, if you are good at studying an example like in that wiki, don’t let me stop you.