- check_circle Functions
Published Apr 12th, 2020, 4/12/20 4:16 pm
- 5,705 views, 5 today
- 117 downloads, 0 today
5
Why did the chicken cross the road....?
...to follow the optimal path!
This datapack implements two-dimensional pathfinding algorithms in Minecraft.
How to install:
1) Click the download button and download the .zip file
2) Head to your ".minecraft" folder and open it
3) Open the "saves" folder and choose the world you want to install in
4) Drag the downloaded .zip file into the "datapack" folder
5) You're done!
How to make it work:
When opening the world you will see a welcome message which tells you how to open the menu
In the menu there are 4 options:
1) Run: This starts the pathfinding process
2) Spawn Eggs: This gives you the spawn eggs for:
-) The start marker to set the start point of the path
-) The end marker to set the destination of the path
-) The pathfinding chicken, which will follow the path
3) Clear Path: This deletes the last path
4) Options: This opens an option menu, with various settings.
Options:
There are 6 settings available:
1) Visual: Decide if you want to see the path (Both, while generating and as "final product")
If you turn this off, the process will be faster since it will use area effect clouds instead of armor stands. Note that you can press F3 + B to see the hitboxes of the effect clouds to get faster processing speed while still being able to see the path.
2) Algorithm: Here you can choose the algorithm you want to use to caculate the path.
There are currently 4 options available:
-) A Star Manhattan: This is the default option and a balanced algorithm
-) A Star Euclidean: Use this if you want to always get the perfect path
Calculating will take longer than with the default option though.
-) Best First: Usually the fastest algorithm but will often return non-ideal paths
-) Dijkstra: This algorithm will, just like A Star Euclidean, always return the perfect path.
It will take longer to calculate, so the only reason to select this is if you want to see how it works
If you want to experiment with the algorithms, I recommend this site.
3) Diagonal: Decide if you want to allow diagonal movement
Note, that even if this is true diagonal movement is only possible if both of the blocks you cross are free as well.
4) Max Steps: Set the number of steps the calculation will do before it "gives up"
If the maximum number of steps is reached the process will stop.
WARNING: Setting this to "no limit" can lead to severe lag and potentially freeze your game!
5) Steps per tick: Define how many steps of calculation will be done each tick.
The default value is "all", which means all the processing will be done in one tick.
If you don't want to freeze your world while processing, you can set this to lower values.
The lower the value the longer the process might take
6) Welcome message: This setting lets you turn off the welcome message when entering your world
If you want to modify this datapack, use it for your own project or if you're just curious look no further.
If you want to know anything else leave a comment and I will expand this area.
Known Issues:
-) The pathfinding chicken is invulnerable, so you can't kill it without commands/creative
-) There is no option to cancel the process once you hit run.
Credits to yosho27 for his mathematical functions datapack!
If you find a bug/issue feel free to leave a comment below.
...to follow the optimal path!
This datapack implements two-dimensional pathfinding algorithms in Minecraft.
How to install:
1) Click the download button and download the .zip file
2) Head to your ".minecraft" folder and open it
3) Open the "saves" folder and choose the world you want to install in
4) Drag the downloaded .zip file into the "datapack" folder
5) You're done!
How to make it work:
When opening the world you will see a welcome message which tells you how to open the menu
In the menu there are 4 options:
1) Run: This starts the pathfinding process
2) Spawn Eggs: This gives you the spawn eggs for:
-) The start marker to set the start point of the path
-) The end marker to set the destination of the path
-) The pathfinding chicken, which will follow the path
3) Clear Path: This deletes the last path
4) Options: This opens an option menu, with various settings.
Options:
There are 6 settings available:
1) Visual: Decide if you want to see the path (Both, while generating and as "final product")
If you turn this off, the process will be faster since it will use area effect clouds instead of armor stands. Note that you can press F3 + B to see the hitboxes of the effect clouds to get faster processing speed while still being able to see the path.
2) Algorithm: Here you can choose the algorithm you want to use to caculate the path.
There are currently 4 options available:
-) A Star Manhattan: This is the default option and a balanced algorithm
-) A Star Euclidean: Use this if you want to always get the perfect path
Calculating will take longer than with the default option though.
-) Best First: Usually the fastest algorithm but will often return non-ideal paths
-) Dijkstra: This algorithm will, just like A Star Euclidean, always return the perfect path.
It will take longer to calculate, so the only reason to select this is if you want to see how it works
If you want to experiment with the algorithms, I recommend this site.
3) Diagonal: Decide if you want to allow diagonal movement
Note, that even if this is true diagonal movement is only possible if both of the blocks you cross are free as well.
4) Max Steps: Set the number of steps the calculation will do before it "gives up"
If the maximum number of steps is reached the process will stop.
WARNING: Setting this to "no limit" can lead to severe lag and potentially freeze your game!
5) Steps per tick: Define how many steps of calculation will be done each tick.
The default value is "all", which means all the processing will be done in one tick.
If you don't want to freeze your world while processing, you can set this to lower values.
The lower the value the longer the process might take
6) Welcome message: This setting lets you turn off the welcome message when entering your world
If you want to modify this datapack, use it for your own project or if you're just curious look no further.
Technical Stuff
So first of all I want to start this by saying the files are partly in a really messy state. It was all nice and clean until I decided to publish this datapack and added the "steps per tick" option and the command line interface. There are a few things that should be re-organised and put in separate files, so: sorry if you want to touch the "code".
Running functions without the menu
All functions can also be run outside of the "User Interface" (obviously) for my functions I used 3 different namespaces: "pathfinding", "_pathfinding" and "_math_pathfinding".
Basically the "pathfinding" namespace (so everything that does not start with an underscore) are the functions you normally call by navigating in the menu.
Everything that does have a leading underscore is a function that normally gets called by the "pathfinding" functions.
Changing options without the menu
You can change all options not only via the menu or by running the "pathfinding:options" functions, but also by modifying the storage object named "pathfinding:options" . This allows you to use custom values for the options, yay. If you do this you will break the option menu tough, because I'm lazy :((
Behind the scenes
The start and end markers can be any entity with the tags "pathfinding" and "start" (or "end).
The follower needs the tags "pathfinding" and "follower" in order to walk along the path.
Algorithms:
I will not explain the algorithms in detail, there is more than enough material to find online, I'm just adding a few things.
For "A Star Manhattan" I used the manhattan distance as heuristic. This means that the the function will "overestimate" the cost most of the time, which results in the algortihm to not find the optimal path in some situations.
"A Star Euclidean" uses euclidean distance instead and should always find the optimal path. I'm saying should because calculating the square root in Mincecraft is kinda weird and there are also most likely a lot of rounding errors.
For the best-first search I used manhattan distance, because I couldn't find a noteable difference to euclidean.
I decided to set A* with Manhattan distance as default, because it is a lot faster and still returns a decent path most of the time.
Scores I use
If you're planning on using this datapack alongside some other code you might face issues if the code is using any of the following names for scores (sry for missing prefix)
x_value, z_value, cost, new_cost, h_cost, f_cost, left_side, right_side, multi, max_steps, total_steps, steps_per_tick, tick_steps, finder, math_in, math_in_w, math_exp, math_out, math_k1, math_k2, math_k3, math_k4, -1, x
gamerule maxCommandChainLength
I set this to max value :3
Running functions without the menu
All functions can also be run outside of the "User Interface" (obviously) for my functions I used 3 different namespaces: "pathfinding", "_pathfinding" and "_math_pathfinding".
Basically the "pathfinding" namespace (so everything that does not start with an underscore) are the functions you normally call by navigating in the menu.
Everything that does have a leading underscore is a function that normally gets called by the "pathfinding" functions.
Changing options without the menu
You can change all options not only via the menu or by running the "pathfinding:options" functions, but also by modifying the storage object named "pathfinding:options" . This allows you to use custom values for the options, yay. If you do this you will break the option menu tough, because I'm lazy :((
Behind the scenes
The start and end markers can be any entity with the tags "pathfinding" and "start" (or "end).
The follower needs the tags "pathfinding" and "follower" in order to walk along the path.
Algorithms:
I will not explain the algorithms in detail, there is more than enough material to find online, I'm just adding a few things.
For "A Star Manhattan" I used the manhattan distance as heuristic. This means that the the function will "overestimate" the cost most of the time, which results in the algortihm to not find the optimal path in some situations.
"A Star Euclidean" uses euclidean distance instead and should always find the optimal path. I'm saying should because calculating the square root in Mincecraft is kinda weird and there are also most likely a lot of rounding errors.
For the best-first search I used manhattan distance, because I couldn't find a noteable difference to euclidean.
I decided to set A* with Manhattan distance as default, because it is a lot faster and still returns a decent path most of the time.
Scores I use
If you're planning on using this datapack alongside some other code you might face issues if the code is using any of the following names for scores (sry for missing prefix)
x_value, z_value, cost, new_cost, h_cost, f_cost, left_side, right_side, multi, max_steps, total_steps, steps_per_tick, tick_steps, finder, math_in, math_in_w, math_exp, math_out, math_k1, math_k2, math_k3, math_k4, -1, x
gamerule maxCommandChainLength
I set this to max value :3
If you want to know anything else leave a comment and I will expand this area.
Known Issues:
-) The pathfinding chicken is invulnerable, so you can't kill it without commands/creative
-) There is no option to cancel the process once you hit run.
Credits to yosho27 for his mathematical functions datapack!
If you find a bug/issue feel free to leave a comment below.
| Compatibility | Minecraft 1.13 |
| to | Minecraft 1.15 |
| Tags |
tools/tracking
4547841
119
pathfinding-4547841
_Blanc__
TravisaInc
Danesto
CrystalRuby
User5098101G
EarthUser
Team UNNAMED
User5115289G
MindOfSocial
slavoj_zizek
EnderCraft
VoidCrawler9
Zatimy
opeepo
Create an account or sign in to comment.
Also great pack!
Currently i teleport the follower by 0.25 blocks every step.
Changing this values will slow it down, but could potentially also get it stuck somewhere.
Cheers!