In der Pfadfindung geht es darum möglichst effizent zwischen zwei punkten zu navigieren. Um dies zu tun werden gebiete oftmals in einzelne Punkte unterteilt, allerdings ist dies in Minecraft schwierig, da man für jeden Punkt eine Entity benötigt, was schnell zu problemen führt.
In diesem artikel wird alles auf zwei dimensionale Pfadfindung vereinfacht, die Konzepte sind allerdings die gleichen, zusätzlich werden alle operationen Cross-Tick ausgeführt das führt zu eienr schönen Visualisierung, allerdings ist es auch langsam. Die methoden können leicht auf Drei Dimensionale probleme und/oder auf einen Tick umgestellt werden. Fangen wir also an
Flood-Fill funktioniert indem einfach alle Wege gleichzeitig ausgefüllt werden bis das Ziel gefunden ist.
Nehmen wir zum beispiel diesen Simplen Irrgarten. <Bild_Leerer_Irrgarten>
Wir setzen oben rechts den start, und unten links das Ende, zur visualisierung verwenden wir hier kleine Armorstands die wolle auf dem kopf haben, bzw. der start hat einen stein block auf dem Kopf, und das Ziel einen Gold block. Als erstes müssen alle Wege durchsucht werden, das sieht dann so aus: <Bild_Voller_Irrgarten>
Wenn wir dann noch die Logik zum Kalkulieren des weges hinzufügen, und alle Armorstands die nicht zu diesem gehören töten sieht das ganze so aus: <Bild_Kalkulierter_Irrgarten>
Es ist garantiert das dieser weg der kürzeste weg ist.
# X+
execute as @e[tag=nextGen] at @s align xyz positioned ~1.5 ~ ~.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "setup"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# Z+
execute as @e[tag=nextGen] at @s align xyz positioned ~.5 ~ ~1.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "setup"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# X-
execute as @e[tag=nextGen] at @s align xyz positioned ~-0.5 ~ ~.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "setup"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# Z-
execute as @e[tag=nextGen] at @s align xyz positioned ~.5 ~ ~-0.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["nextGen", "nextGen"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
Diese neuen nextGen Armor Stands sind die die im nächsten tick die Commands oberhalb wieder ausführen, dadurch breiten sie sich aus. Nachdem diese die commands oberhalb ausgeführt haben verlieren sie den nextGen tag, damit sie nicht unnötig Commands ausführen
Damit später der weg berechnet werden kann wird jedem ArmorStand ein "index" zugewiesen, der identifizieren kann wie viele schritte es von diesem ArmorStand noch zum anfang sind.
Dies wird erzielt indem einfach der score vom zuvorigen Tick plus eins gerechnet wird.
der Fake-Player #tmp hat bereits einen score von 1 im searcher_value scoreboard.
# Increment Index
scoreboard players operation #searcherIndex searcher_value += #tmp searcher_value
# Set Index
execute as @e[tag=nextGen] run scoreboard players operation @s searcher_value = #searcherIndex searcher_value
Zuletzt wird noch getestet ob einer der nextGen ArmorStands bereits auf dem ziel ist, falls ja wird der ArmorStand markiert, was auch dazu führt das diese Funktion nicht nochmal ausgeführt wird, sondern im nächsten tick der Weg berechnet wird.
execute as @e[tag=nextGen] at @s if entity @e[tag=finder.end, distance=0..0.5] run tag @s add found
Die Wegberechnung funktioniert vom Ende aus zum start.
Es wird mithilfe der solvepath funktion rekursiv immer zum ArmorStand der einen Score der kleiner ist als der eigene durch den Irrgarten navigiert, bis der start erreicht ist.
Alle dabei getroffenen ArmorStands werden mit einem tag path.part markiert.
tag @e[tag=path.parent] remove path.parent
tag @s add path.part
tag @s add path.parent
execute align xyz positioned ~.5 ~ ~.5 as @e[tag=searcher, distance=0..1.1] at @s if score @s searcher_value < @e[tag=path.parent, limit=1] searcher_value run function simple_indexed_pathfinding:solvepath
Nachdem diese funktion ausgeführt wurde werden dann einfach alle ArmorStands die den tag searcher aber nicht den Tag path.part haben, getötet.
Man spricht man von einer O(n) operation. d.h. im schlechtesten fall benötigt man gleichviele Operationen wie es datenpunkte gibt. In diesem simplen Fall gibt es gleichviele Datenpunkte wie Blöcke, und jeder Datenpunkt ist ein Entity. Dieser Algorythmus ist daher nicht besonders schnell.
Funktionen:
load.mcfunction
Die lade funktion.
function simple_indexed_pathfinding:reset
scoreboard objectives add searcher_value dummy
scoreboard players set #tmp searcher_value 1
reset.mcfunction
Setzt alles zurück
kill @e[tag=finder.start, type=!minecraft:player]
kill @e[tag=finder.end, type=!minecraft:player]
kill @e[tag=searcher, type=!minecraft:player]
scoreboard players set #searcherIndex searcher_value 0
step.mcfunction
Jedesmal wenn diese Funktion ausgeführt wird macht die wegfindung einen Schritt.
Man will diese funktion vermutlich an eine Clock, oder das Tick event anschliessen.
execute unless entity @e[tag=found] run function simple_indexed_pathfinding:real_step
execute as @e[tag=found, tag=!found.processed] at @s run function simple_indexed_pathfinding:found
real_step.mcfunction
# X+
execute as @e[tag=nextGen] at @s align xyz positioned ~1.5 ~ ~.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "nextGen"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# Z+
execute as @e[tag=nextGen] at @s align xyz positioned ~.5 ~ ~1.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "nextGen"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# X-
execute as @e[tag=nextGen] at @s align xyz positioned ~-0.5 ~ ~.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "nextGen"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# Z-
execute as @e[tag=nextGen] at @s align xyz positioned ~.5 ~ ~-0.5 if block ~ ~ ~ air unless entity @e[tag=searcher, distance=0..0.5] run summon armor_stand ~ ~ ~ {NoGravity:1b,Marker:1b,Invisible:1b,Tags:["searcher", "nextGen"],ArmorItems:[{},{},{},{id:"minecraft:green_wool",Count:1b}],Small:1b}
# Increment Index
scoreboard players operation #searcherIndex searcher_value += #tmp searcher_value
# Set Index
execute as @e[tag=nextGen] run scoreboard players operation @s searcher_value = #searcherIndex searcher_value
execute as @e[tag=nextGen] at @s if entity @e[tag=finder.end, distance=0..0.5] run tag @s add found
found.mcfunction
tag @s add found.processed
function simple_indexed_pathfinding:solvepath
kill @e[tag=!path.part, tag=searcher]
solvepath.mcfunction
tag @e[tag=path.parent] remove path.parent
tag @s add path.part
tag @s add path.parent
particle minecraft:flame ~ ~2 ~ 0 0 0 .001 5 normal
execute align xyz positioned ~.5 ~ ~.5 as @e[tag=searcher, distance=0..1.1] at @s if score @s searcher_value < @e[tag=path.parent, limit=1] searcher_value run function simple_indexed_pathfinding:solvepath
zusätzlich kann mit dem befehl
execute align xyz positioned ~.5 ~ ~.5 run summon armor_stand ~ ~ ~ {NoGravity:1b,Small:1b,Marker:1b,Invisible:1b,Tags:["finder.start", "searcher", "nextGen"],ArmorItems:[{},{},{},{id:"minecraft:stone",Count:1b}]}
der start gesetzt werden.
und mit
execute align xyz positioned ~.5 ~ ~.5 run summon armor_stand ~ ~ ~ {NoGravity:1b,Small:1b,Marker:1b,Invisible:1b,Tags:["finder.end"],ArmorItems:[{},{},{},{id:"minecraft:gold_block",Count:1b}]}
das ende gesetzt werden.