Basic of Pathfinding algorithm

Definition:
Pathfinding is an algorithm that defines the ideal “pathway” for a certain entity to move.

As you can see inside the image above, the “A” object is defining the possible shortest pathway to the “B” object. By using an artificial deep neural system and BFS to evaluate and eliminate every possible path. It calculates the shortest path out of those paths.

In Minecraft:
Pathfinding is slightly different in Minecraft. Namely because of how coordinates work.

■ Up/Down: Pitch.
■ Forward/Left/Right/Backward: Yaw.

Permutation:
Every possible pattern for the AI can use to move is called a permutation. Specifically, there are 12 possible permutations for the obstruction to generate at.

Pattern#1:(“x+1”)
Pattern#2:(“x+1”,“z+1”)
Pattern#3:(“z+1”)
Pattern#4:(“x-1”,"z+1)
Pattern#5:(“x-1”,“z-1”)
Pattern#6:(“x+1”,“z-1”)
Pattern#7:(“x-1”)
Pattern#8:(“z-1”)
Pattern#9:(“x+1”,“x-1”,“z+1”)
Pattern#10:(“x+1”,“x-1”,“z-1”)
Pattern#11:(“z+1”,“z-1”,“x+1”)
Pattern#12:(“z+1”,“z-1”,“x-1”)

If we counted pitch then there will be a total of 20 possible patterns. But I will be explaining yaw patterns only in this thread.

Permutations basically check which coordinates the entity can move to. Example:

If pattern#1 >> There will be 3 possible paths the entity can use to move (7 if counts diagonal).
If pattern#4 >> There will be 2 possible paths the entity can use to move (3 if counts diagonal).
If pattern#9 >> There will be only 1 possible path the entity can use to move (1 if counts diagonal).

RNG:
RNG (Random Number Generator) is a system used to generate random values that follow a range. For instance:

RNG has a range from 0 - 100 will try to choose a value (n) within that range. It can’t go outside the max(100) boundary nor go outside the min(0) boundary.

For easier understanding:

x1 x2… x100; the x value can be either x2 or x45, it doesn’t matter if it is still in the range.

So what does rng do here?
Well, it basically chooses the ideal pathway the entity can move to. Because like I said above, there is a total of 12 random patterns that obstructions can generate within each of them. And each pattern has at least 1 to 3 paths the generate can choose to move to (7 if counts diagonal). So the RNG will decide which path the entity can move to:

The algorithm:

If pattern#1
Call function(a) {
Set variable random number values %RNG% (1 - 3)
Call function(b) {
If variable RNG = 1 >> Set location value (x-1)
If variable RNG = 2 >> Set location value (z+1)
If variable RNG = 3 >> Set location value (z-1)
}
}

Basically, if it is pattern#1 then it gonna set up a function named “a”. This function consists of an RNG that has boundaries from 1 - 3 values. If the variable RNG’s value = 1 then it gonna uses the set location value to change the x coordinate and subtract it by 1. Example:

The default x coordinate of the entity is 288. When I utilize the set location value I will subtract the 288 by 1 and it gonna become 287. So the entity will move to 287 x coordinate path.

Same to if variable RNG’s value = 2 and 3, either subtract or add 1 to the current entity’s z coordinate value.

Now to pattern#4 and pattern#9 which there will be 2 and 3 obstacles obstructing the entity’s path. The code will look like this:

If pattern#4
Call function(a) {
Set variable random number values %RNG% (1 - 2)
Call function(b) {
If variable RNG = 1 >> Set location value (x+1)
If variable RNG = 2 >> Set location value (z-1)
}
}

So the trick here is just if |x| and |z| = + or = - then change it to the opposite. Like

If x’s value is negative then change it to positive.
If z’s value is positive change it to negative.

Facing:
You can change the entity’s facing direction by simply creating a variable that checks the coordinates/yaws it is going and from there change the corresponding yaw value to match the entity’s moving direction.

Extra Info:
There is pattern#13 as well but it is used to define 4 obstacles and I barely see that happen. This is just the basic concept of the Path Finder AI algorithm, there is even more but I’m lazy to explain :sweat_smile:. Hope this helped and you guys can even create a custom AI with this.

3 Likes