Performant Pathfinder - A* Algorithm

[civic tartan]

The Minecraft scripting API currently doesn't expose any pathfinding methods or algorithms to us. Hopefully, one day; but for now, we need to create our scalable and efficient pathfinding algorithms. Here is my take on it with a customizable A* algorithm.

It can be customized to:

• Jump over gaps (such as a bridge missing some pieces)
• Dodge lava
• Dodge or traverse into water
• Not jump over fences/walls (it can still get on them like a normal player, if there is a block next to them shown in Video 1)
• Customize corner-cutting (shown in the videos below)
• Walk/jump over blocks
• Safely fall down a ledge if there is 1 block below
• Works with different entity heights (some entities are taller or shorter) and the BlockSafetyChecker this pathfinder uses can be customized to fit smaller or larger entities
• And, in general, pathfind to locations

To be efficient, it utilizes the new (beta) system.runJob() to process the algorithm en-masse on different hardwares of devices. This allows you to not worry about performance - and for good PCs, have it pathfind almost instantly in reasonable distances. You can see this efficiency in video 2 as I enable the woodcutter. Not only is he finding the nearest wood block, but then he is pathfinding to it. All of this is calculated almost instantly - as he begins moving towards the tree within milliseconds.

Code and usage: https://github.com/nox7/mc-bedrock-script-utilities/tree/main/Pathfinder

Video examples attached

[civic tartan]

To reinforce why I choose to mention "performant" and discuss efficiency: here is an example of using multiple NPCs all utilizing flood-fill and A* pathfinding algorithms every tick with no lag and no watchdog complaints via all calculations.

[final dirge]

thats really impresive

[eternal geyser]

Age of empire feel having them chop trees for you lol love it

[civic tartan]

Yessir. I started my journey on MC Add-Ons entirely because I really had grown tired of doing the mundane labor in survival - so I thought I'd code up some "helpers." Age of Empires, Stronghold, and Total War have all been inspirations.

[eternal geyser]

Your using gametest right? To control them, I haven't done much gametest but I need to get into it more.

[civic tartan]

Not at all - everything is through the main server module.

[eternal geyser]

Wow that's neat

I'll have to see how you've done it!

[idle solar]

Hello
I am trying to use it but i get error that the coordinates are invalid

but theyre okay

[civic tartan]

Definitely make an individual post in #1067535382285135923 with a description of the issue. I use this implementation to this day with no issues.

[idle solar]

Ok

[idle solar]

are there any problems with floats?

[civic tartan]

I'm not sure what you're implying. Without an actual error and the code you're using - I have 0 clue how I could help you.

[idle solar]

i've written a wrapper

async goToLocation(location: mc.Vector3, speed: number): Promise<void> {
    console.warn(
      `${this.entity.location.x} ${this.entity.location.y} ${this.entity.location.z}`
    );
    let pathFindOptions = new AStarOptions(
      this.entity.location,
      location,
      this.entity.dimension
    );

    let astar = new AStar(pathFindOptions);
    pathFindOptions.TypeIdsToConsiderPassable = ["minecraft:air"];

    let path = await astar.Pathfind();

    let idx = 0;
    while (Vec3.floor(this.entity.location) != Vec3.floor(location)) {
      let currMove = Vec3.subtract(path[idx], this.entity.location);
      this.entity.applyImpulse(currMove);
      idx++;
    }

    return;
  }```

{ x: 205, y: 63, z: 295 } this is the coord

[civic tartan]

What is the actual error you get - a screenshot or copy-paste

Because it sounds like you're getting an unloaded chunk error

[idle solar]

э

[civic tartan]

Your locations are out of bounds and in unloaded chunks (one or both of them are). This isn't an error with the pathfinder.

[idle solar]

let me check

[idle solar]

ah

1 minus problem

anyway
thx for your script
its amazing

[civic tartan]

Welcome. Glad to hear it.

[idle solar]

could you help me with moving entity with that?
this is my current not working solution

async goToLocation(location: mc.Vector3, speed: number): Promise<void> {
    console.warn(
      `${this.entity.location.x} ${this.entity.location.y} ${this.entity.location.z}`
    );
    let pathFindOptions = new AStarOptions(
      this.entity.location,
      location,
      this.entity.dimension
    );

    let astar = new AStar(pathFindOptions);
    pathFindOptions.TypeIdsToConsiderPassable = ["minecraft:air"];

    let path = await astar.Pathfind();

    let idx = 0;
    let finalpath = [];

    for (let point of path) {
      for (let i = 0; i < 1 / speed; i++) {
        finalpath.push(Vec3.multiply(point, speed));
      }
    }

    let run = mc.system.runInterval(() => {
      if (idx == finalpath.length) {
        mc.system.clearRun(run);
      }
      this.entity.applyImpulse(finalpath[idx]);
      idx++;
    });

    return;
  }

nvm i found the problem

[gleaming hollow]

whats going on in this ?

[civic tartan]

It's an example showing the use of a lot of NPCs that are using pathfinding, movement, and flood fill algorithms (to find the nearest tree) all on the same ticks and not causing watchdog warnings.

If that's what you mean

[gleaming hollow]

wat if trees arw very far away

[civic tartan]

The flood fill algorithm has a limit you can define. In my example, right clicking the woodcutter block let's you choose the max distance

It takes them longer to find further trees, but still doesn't lag as it uses runJob

[gleaming hollow]

flood fill uses lot of memory

how you mannage to keep up with that

[civic tartan]

Not in this case, no. My implementation only stores hashes of data, which you can store hundreds of thousands of blocks per run

Using a proper data structure alleviates memory issues

My BDS currently has players using 1-2 of them and maybe 20 running at a time and hasn't had any issues so far.

[gleaming hollow]

have u tried 64x64x64 area

[civic tartan]

A full chunk? No, but I'll try it in a few moments to see

[gleaming hollow]

yea

[civic tartan]

12 seconds to search 64^3 blocks (1 chunk)

I did it with no oak logs in the chunk, because it's a benchmark on how quick it can search the entire chunk. If there was an oak log, it would have stopped early because it found it.

Much shorter if there is one close by, of course

[worthy oak]

A chunk is 16x384x16 no?

[gleaming hollow]

can u add a particle and record vid so i can see visual

[civic tartan]

You're right, I did way more blocks than a chunk it seems

[worthy oak]

Yea, tbh 64^3 is probably a better to find anything since it's unlikely you'd want an entity to move up/down 200 bloks

[gleaming hollow]

its about algo testing tho

[civic tartan]

Adding particle spawns will slow it down, but sure one second - as the engine has to call internal things outside of the standard process.

[gleaming hollow]

i seem to have issues with larger areas even tho i dont see anything diff in ur code

u have 4 pointer scan right?

[civic tartan]

No idea what you mean by that

[gleaming hollow]

we can have 4 point or 8 point one in 2d

6 or 14 in 3d

[civic tartan]

Sorry, it looks like I forgot to enable AllowYAxisFlood on my initial test. The real 64^3 (which is 262,144 blocks) looks like it takes upwards of 6.5 minutes. Initially I used a "climbing flood-fill" test which only moves along blocks NPCs can reach (jumps up blocks, goes into caves, etc). A Y-axis flood-fill goes into the air in places people can't get to and checks every single block - all air blocks.

However, still no memory issues

[gleaming hollow]

try 256💀

[civic tartan]

"Flood-fill" in this situation is only places NPCs can reach. So I'll continue with that assumption

Checking now

Ignore the 64^3 console log, I forgot to change it. But that's 256 at 18seconds with y-axis flooding at false.

They go pretty far - 256 is off-screen for my RTX rendering

Climbs up and over stone/crevices etc.

Here's two visualizations at 20 block distances

Finally, here's one at ~50 blocks away (due to the height it has to walk up)

[gleaming hollow]

no point testing it if no y

[civic tartan]

I have 0 clue why you would think that. It uses Y - just not randomly shooting into the air for no reasons. That's terrible optimization.

You can test y if you want to, but the logical time (in O(n) format) increases when you add a third axis. You can also use octadrahedron-iteration to optimize y-axis flood-filling (which is what mine does).

Your complete dismissal of the tests, however, is disappointing and misplaced.

Additionally, as I mentioned above - I did a Y-axis test and it takes around 6.5 minutes to flood-fill 256K blocks. Your problem with memory is a your-code issue.

Video showing the 256K block iteration steps: https://youtu.be/yGGozc9uJlU
Video is 2x for brevity.

You can optimize the Y-axis flood fill by using internal raycasting to pass by tens to hundreds of air blocks at once in a single tick.

If you're trying to use the base BFS (also called flood-fill in 3D) for large-scale cuboids with no heuristic algorithm changes (such as short-cuts with long stretches of air) - then you're approaching this problem wrong. BFS is a base algorithm, not one you just implement and use.

[gleaming hollow]

sure but i am talking in general, if u have to find x thing then u have to go all the way on all axis

[gleaming hollow]

dont think so as i am on phone

[civic tartan]

Fair enough

[gleaming hollow]

wym by heuristic, when we are scanning for blocks

[civic tartan]

Heuristic is just a general term for "a piece of an algorithm that develops over time" to make your algorithm more and more accurate as it runs

E.g., raycasting instead of checking all air blocks

[gleaming hollow]

ik but my point througout was about scanning said x blocks in range even with heuristic it doesnt create any big diff

[civic tartan]

If the blocks aren't uniform, yes, it will take a while. I just assumed you were talking about running out of memory. If you mean speed, yes large ranges will take a long time without an exposed MC API to do it on the C-side.

Roblox actually does this with "Region3": https://create.roblox.com/docs/reference/engine/classes/WorldRoot#GetPartBoundsInBox

We would need something like that

[gleaming hollow]

how are those entity moving ? and doing actions ?

[gleaming hollow]

made one with less memory usage , anim is not very cool xd

covers 1k with just 120 in variable

[worthy oak]

Now make it minecraft

[civic tartan]

You might find the .80 preview methods coming into the API useful

They added the ability to search an entire 3D volume for blocks now. So flood-fill and BFS algorithms will no longer be needed soon for finding blocks.

[gleaming hollow]

ye

[gleaming hollow]

btw this^

[civic tartan]

Uses my EntityWalker class - teleportation -> https://github.com/nox7/mc-bedrock-villager-system/blob/main/scripts/Walker/EntityWalker.ts

The "actions" are animations that are controlled by state enums.

Which is slightly similar to what my mining NPCs do

[gleaming hollow]

tps arent smooth thp

[civic tartan]

What? They're perfectly fine, as you can see

The MC docs on Microsoft themselves say they use TPs on NPCs

[gleaming hollow]

can show video

closely

[eternal geyser]

Lower back and neck problems after they retire

[rugged python]

This is really cool! How did you find a block in volume without lag? Despite the many blocks sensed within the volume, there seems to be no issues at all.

[civic tartan]

Hey, thanks for the compliment. Prior to the beta function runJob, I implemented a "finder queue" using asynchronous awaiting on runInterval - the queue stacked a max of two "finds" running at any given tick.

Now, runJob allows us to register a generator (a yielding function) to the MC JS engine and Minecraft's engine determines how often to run the function based on the capabilities of the PC running it. It will space out the generator function's calls on different ticks for us to avoid any lag.

So, either method works. You just have to make sure to be granular with how often to space your out of over game ticks.

[rugged python]

That makes a lot of sense! So my best bet is runJob. Has it been released out of beta/preview?

[civic tartan]

It hasn't, but an alternative is just to use asynchronous awaiting of a runInterval. E.g.

await new Promise(resolve => {
  let runId = system.runInterval(() => {
    // Whenever, you're done with the interval, do these two calls
    system.clearRun(runId);
    return resolve();
  }, 1);
});

[rugged python]

Thank you! Free code! This will help me considerably.

Though, how did you make the entity move to where you want it to? moveTo? Or another way? Cuz this is one of the most frustrating things to work out.

[civic tartan]

The original post is a link to my A* pathfinding implementation. It asynchronously generates a list of Vector3 locations that lead to a goal location. Then, every tick, I teleport the entity at a fraction of a value (usually 1/8) in the direction of the next location.

Although, to use it you'd need to use the beta APIs. For stable, you'd have to somewhat recreate it unfortunately. The code is fair-use licensed so you can copy it and do whatever you want with it.

It's performant. Many people in this server over-optimize or are a bit paranoid about "what it may do", but if you understand how to implement proper game-engine loops you can almost always get by doing any operation. I run about ~20 NPCs all doing pathfinding in simulated chunks using the code I linked. No issues (no watchdog)

[rugged python]

Very interesting. That is a cool way to make an entity move.

[rugged python]

I believe ya. But just one more question: if I were to use your code (since you said it was okay) is there a place to say which entity I want to move? And if so, do I have to give them dummy components so they won't wander around?

[civic tartan]

If it's a custom entity, they shouldn't be randomly wandering around unless you add components to them that cause movemet. If it's existing ones, I don't have an answer for you - I've never modified existing entities.

For your first question, the examples in the code links show how to use the code to generate locations. Moving the entities to them is where you have to write your own code. It just provides the Vector3 to move them to on a path.

[rugged python]

That makes sense. I'm focusing on custom entities, so I'll make sure to remove components that lead them to move randomly. As for the location, that also makes sense. It might take some time, but I am willing to write my own code on that part.

[civic tartan]

I just haven't released a stand-alone portion of my code-base that does the walking. Right now, it's built into other systems I have for my own add-on, so it would take a lot of decoupling for someone to take it apart to be stand alone.

[rain zephyr]

what are your pc specs?

[civic tartan]

Nothing crazy. I currently run an i9-14900K, 32GB RAM, NVMe SSD, and 2 4090 RTX cards SLI'd

[rain zephyr]

"nothing crazy" 😭

[civic tartan]

Sorry, I was just messing with you. i7-7700K - same RAM and SSD - with an RTX 3080

[rain zephyr]

still not bad at all

[rain zephyr]

do you think an i5 13600K and 4070 would be good? or should i do 30 series card

[civic tartan]

I'm not really good with hardware specs. But GPU benchmark says the 4000 series cards are 5-7% better

[rain zephyr]

yeah, im not sure why people say 40 series is so bad

[civic tartan]

It's because 5-7% increase compared to the 3000 series was a weird "small gain" to release a whole new card series for instead of just waiting until they could get higher gains

[rain zephyr]

thats true i suppose

[gleaming hollow]

30 cards have raw perf thats why

[rugged python]

Quick questions. The path is generated in one tick right? Despite the functions, for loops, and while loops, right?

[civic tartan]

Not at all

That would be insane if that was true

[rugged python]

Oh wait. Guess I misunderstood the process. How does it generate a block path so fast then?

[civic tartan]

That's the might of system.runJob on line 47 in the AStar.ts file. It runs it as many times as the hardware running the code can handle before causing Watchdog. Then it goes to the next tick if needed.

[rugged python]

Oh I see. And that code you gave me. The await new Promise. That does something similar right?

[civic tartan]

Sort of, yeah. That runs at minimum once per-tick. system.runJob can run multiple times per tick.

[rugged python]

Oh WOW. That's pretty powerful.

[rugged python]

Hope runJob is released out of preview soon. That would be very useful.

[civic tartan]

There are a few things coming out of preview, then beta, then stable soon that would increase the efficiency of all things. Including a built-in block finder for 3D spaces.

[rugged python]

Oh yeah, the getBlocks method right?

[civic tartan]

Yeah, that's right.

[cursive moon]

What does getblock method do ?

[rain zephyr]

gets the block!

getBlock "GET BLOCK"

[shy urchin]

Sorry for bothering, i am using the latest stable, and works perfectly fine pathfinding in land, but in water even if water is included in the TypeIdsToConsiderPassable, it still not finding the EndBlock or EndNode, I remodified it to reconsider with isLava and isInWater to check also if it's included in the TypeIdsToConsiderPassable as it should be imo. Although i was just testing it below 10 blocks to my coordinate, and i'm in sea area of my world. The surroundingBlocks returns 9 as length with my remodified version of this script, and that's correct, but when being iterated it as surroundingBlock doesn't even go to that location.

So, i think this is a bug in terms of liquid blocks to be passable. Thank you for this Pathfinding resource btw, it's really cool!

[shy urchin]

nvm, i think i'll use the FloodFill for this option, thanks for this script again

[rose oak]

Im just seeing this post and it’s a pretty cool algorithm as I’ve used the same one with particles to solve mazes which were made using another algorithm but I hit a bottleneck when it tried to find paths between long distances

Or with too many “steps”

[uneven copper]

Watched the videos above. Pretty neat lol.

[dense hawk]

wait what

You dont exist in this server

@nox7

it does not show you, when trying to ping

[shy urchin]

Nvm im dumdum, just watched how A* works

[uneven copper]

They left.

[dense hawk]

why

[uneven copper]

Based on what I found looking up their previous conversation, probably related to certain disagreements.

[shy urchin]

I used this script Nox's made, and modified a bit of the code and created this Bidirectional A*, if someone wants it.

A* Star Pathfinding (Nox's with visuals)

Bidirectional A* Pathfinding (with visuals)

and learned that A* is great on average, but bidirectional ones makes it great for early exiting any path that is not possible to move with.

Also, I added AllowYAxisFlood to have a functionality, since based on his current script (upon reading his entire utility scripts), it didn't have one. Since this is what i needed also in my project.

[gleaming hollow]

how does bi works

[shy urchin]

its just two A*, one from start, and one from goal. If the safe nodes from the start reaches to the another safe nodes from end, then return that node starting from safe nodes from start towards the safe node from end.

it's taking long like 300 ticks due to creating DebugBlocks or Structure Void for visualizing the nodes, if i disable the debugMode then it's just raw pathfinding.

[gleaming hollow]

do you have any source for it

[shy urchin]

imma send it here after I commit it to my forked repo from Nox's Utils

but here's the class of it, i will re-edit it when i finished submitting my commit.

sorry for messing Nox's wrote xd

[gleaming hollow]

nah like tutorial video or something

[shy urchin]

https://youtu.be/jEyOlGn5xm4?si=yDM-Bg15fLtCL_ye

I was trying to use another method to iterate this two nodes from start and the end, but i haven't find other way to yield and return it using the runJob so i put another two loops instead of just creating a method for that.

[gleaming hollow]

thanks

[rugged python]

Are you going to release this, cuz this would be extremely helpful.

[shy urchin]

latest update with Bi-directional A*: https://github.com/nox7/mc-bedrock-script-utilities

[rugged python]

YES! Thank you!

[random jay]

Hey man, how did you get them to detect and chop trees?

[novel berry]

They aren’t in the server anymore

[vapid oar]

this is cool

[vivid elm]

i guess we dont have a better way of smoothing out the teleporting?

[shy urchin]

Wdym? Like how Nox's villager walks?

[vivid elm]

Well their villager kinda just 'slides'

i meant like make it move more like a real entity

my question is, would there be a way to help trigger a 'jump' effect whenever it needs to 'jump'

maybe apply impulse or knockback at the base of the entity before going up a y level

[shy urchin]

I think, it's possible, haven't messed with land creatures yet. (Idk it's just in my head)

[vivid elm]

i was reviewing the algorithm. Kind of a headache trying to read everything. xD

[shy urchin]

There's catmull for smoothing points or list of vectors (but i think i messed with it a few weeks ago)

[vivid elm]

Also if the world closes, will the path/entity still continue its goal?

once it is loaded back up

[shy urchin]

I had those when i first reviewed the algorithm, but after watching some short in-depth visualizer for A*, it made sense.

[vivid elm]

yeah i need to do some research...im struggling with a custom behavior for my entity

[shy urchin]

I think, nah (my brain not braining rn). I am going to use this pathfind script to create my custom entity also (but haven't really figured how do i make it consistent).

[vivid elm]

yeah the consistency is my issue currently

[shy urchin]

Without a clue, my guess for this kind of problem (I'm going to also encounter soon) is to store the entity's rotation, and end goal, and just run the script for that entity (as long as there's player online). Then if this entity is visible to any player then just load that rotation, and continue pathfinding. So it's pathfinding in the background, if the entity should be visible to the player, then just load the rotation looking like it's still continuing moving towards its path,then just load the rotation.

Can't really figure my head atm (haven't sleep yet ☠️)

[vivid elm]

but how do you check if the entity is rendered?

[shy urchin]

The important thing to store is probably the rotation (view direction) and the end goal. So you don't have to store the whole vectors or points this entity is going to pathfind

No clue yet (idk if molang can solve this). Assigning a certain distance to "re-render" this entity is not ideal.

Idk if there's a molang or client thing to detect if this entity is rendered in the player's screen.

[vivid elm]

hmmm 🤔

[shy urchin]

Oh yeah, i remembered i did this with a fish (catmull + A*) it was smooth

[upper jolt]

Store the locations to dynamic property and play it via onEntityLoad event if i remember it correctly that event runs when an entity gets loaded

[vivid elm]

thanks i was able to do it

[earnest bobcat]

how to use it?

[shy urchin]

you just copy nox's utils folder, and import it in your project just like in the README:

https://github.com/nox7/mc-bedrock-script-utilities

[earnest bobcat]

what folder is that?

[shy urchin]

all of it, like create a new folder in your project's script folder, after creating, copy all the folders this project repo has since all is needed, although you can just skip the Iterators/FloodFill I guess, then move it to that newly created folder.

[blissful pollen]

this is so cool. How did you get Y direction to be working for A*? never seen any yt tutorial talk about 3D y* specifically vec3 coords.

[blissful pollen]

what happens if the entity is hit, does this cancel the pathfind?

[shy urchin]

Probably not, cuz it only returns the actual paths (vector) based on start and end and doesn't really use ".teleport" Or somekind inside the actual class. You have to implement that yourself.

[blissful pollen]

yeah got it, I talked to nox and his implementations. made my own custom one but this one is an inspiration