Performant Block Finder - Flood Fill Algorithm

[full umbra]

Currently, there is no API method to find an arbitrary block - and further, no way to do so with customizable restrictions (e.g., ignore certain Vector3s, safely dodge lava, don't jump fences, etc.). In short, there is no easy way to say "I want to find the nearest tree" or "I want to find the nearest Iron Ore vein".

With a proper flood-fill algorithm and the usage of (currently Beta) system.runJob, you can efficiently find a block with many search restrictions in an arbitrary search zone.

Source code + documentation: https://github.com/nox7/mc-bedrock-script-utilities/tree/main/Iterators/FloodFill

Code examples are provided in the link above.

See the attached videos for

1. Example of using Flood-Fill to find the closest tree
2. Visualization of how it searches and the speed.

It has two search algorithms:

• Gravity-based flood fill (what you see in the videos, an algorithm to use for entities to safely jump over blocks, safely fall down, jump over gaps, etc.)
• Y-axis flood support: This is a full 3D flood-fill that searches an entire spherical space from a starting location.

Finally, it is fully customizable in the FloodFillIteratorOptions.ts file. You can set a max search distance, Vector3s to ignore, Tags to include/ignore/consider air, TypeIds to include/ignore/consider air, and TypeIds that cannot be jumped over (fences, walls, etc.)

This is part of an ongoing effort to decouple a lot of my internal algorithms I use in my personal Add-On as free scripts/utilities for public use. The A* pathfinder shown in the videos below is soon to come.

[latent pewter]

for the first one you should spawn particles to help visualize where its searching

Also system.runJob crashes too much and cant properly be used or relyed on

[full umbra]

This has never been a case for me when used properly..

[full umbra]

This was just for an example. Not actually in production.

[latent pewter]

When you run it long enough

[full umbra]

You should come up with a reproduction and submit a bug report, otherwise it sounds like your code isn't yielding enough or properly - it's a generator runner and needs a bit more understanding of yielding in single-threaded applications. Long-running jobs make no difference if they are yielding at proper intervals - as described by the docs on runJob on Microsoft's documentation.

Never use runJob for long-running applications without granular yielding

[latent pewter]

I have told dark Navi. I have even put one between every line. The problem is it can’t do it for a lot of iterations that require reeding of memory

[full umbra]

If you say so, but just placing yields for no logical reason between every line isn't enough to solve the issue you're talking about. A proper code reproduction would answer this problem, though.

[keen hatch]

Btw, found what smelly was talking about
Source form Bedrock Scripting API server #1208535042029002782 message
(ik that your not in it, so the actual code)

  /**
   * Gets all claims
   * @returns
   */
  static *registerAllClaims() {
    yield;
    const keys = TABLES.claims.keys().entries();
    yield;
    for (const [i, claimId] of keys) {
      console.warn(`Loading Claim ${i}: ${claimId}`)
      yield;
      const model = new ClaimModel(claimId);
      yield;
      CACHED_CLAIMS[claimId] = model;
      yield;
    }
  }

ClaimModel constructor

  /**
   * A ids class
   * @param id the id of a player
   */
  constructor(id: string) {
    super("claims", id);
  }

super constructor

  /**
   * Constructs this Model Instance.
   * @param tableName
   */
  constructor(tableName: keyof typeof TABLES, key: string) {
    this.tableName = tableName;
    this.key = key;
    const table = TABLES[tableName];

    const data = table.get(key);
    if (!data) throw new Error(`Key: ${key}, not found on Table: ${tableName}`);
    this.data = data;
  }

table.get

  /**
   * Gets a value from this table
   * @param {Key} key - The key to retrieve the value for.
   * @returns the value associated with the given key in the database table.
   */
  get(key: string): T | undefined {
    if (!this.MEMORY)
      throw new Error(
        "Database not loaded! Consider using `getAsync` instead!"
      );
    return this.MEMORY[key];
  }

So even when using runJob for simple javascript object manipulations its still possible to have watchdog warnings

[latent pewter]

yup

I guess it would work well if your only using native functions. But when your using your own functions it breaks

[keen hatch]

Btw, how did you solved this problem? Did you actually used entities as storage as mrpatches suggested?

[latent pewter]

no, I just switched back to async

[keen hatch]

Oh okay

Just got scared because was using same landclain system and db as you, hah

[full umbra]

This is definitely a bug in it then, I assume it's been reported? Because if that's the full repo then it would appear it's not properly yielding back to the MC engine and allowing another tick to pass.

I haven't experienced this myself yet, and I run a ton of NPCs using system.runJob on a BDS - so something in that code may be triggering some strange things.

A 2s spike is insane, and I couldn't imagine what else is going on to cause that. I have a feeling there is something else in that codebase happening at the same time as that runJob that we're not seeing. Because if my implementations work without such a problem, and we consider the docs on how system.runJob specifies it won't starve the code and will still run all other code and async functions per tick - it leads us to believe that the rest of the code base is improperly written.

It's not as simple as you being able just to slap a generator on a few parts of a code base and it will perform well - your entire code base (just like how game engines are written) must be written as a large cohesive job or game loop.

[keen hatch]

was you able to reproduce it? Have you tried using script profiles?

[full umbra]

I'll have to try the code you sent when I get to my desk

If I can reproduce it I'll file a bug

[keen hatch]

I mean your code

when you get 2s spike

[full umbra]

In my code? I don't have watchdog complaints when I use system.runJob, and I have maybe 20 NPCs all pathfinding and using block finders happening at once

In one chunk

[keen hatch]

Oh so you was talking about that spike from screenshot

[full umbra]

Yes, that's right.

[keen hatch]

Thats from smelly's, not my code. However I was also struggling with the same and im trying to make my codebase support large loads but finding places where it spikes or hangs is so difficult even with script profiles

[full umbra]

Yeah, I understand. Bedrock's debugging platforms aren't very intuitive right now and it's hard to properly profile code.

It might even just be a bug with how Watchdog is monitoring a script and they haven't updated it to properly measure between yields that runJob is handling. Because I can see, in that screenshot, that there is small time differences happening which would imply maybe some yielding is really happening. The code may actually be performant and watchdog is just improperly reporting a spike that isn't there

[keen hatch]

Maybe thats it

[full umbra]

The only for sure way to tell would be to have other scripts outputting in between those console.warn calls, which would mean other code is running in between and watchdog is bugged

[latent pewter]

yeah I hope next update we can see a fix for it. If not we should be able to disable watch dog next update. Which would allow us to run anything

[keen hatch]

Isn't it better to just increase watchdog limits via server.properties?

[full umbra]

If Watchdog is correct, then you'd want it low; because if your script is hanging that means ticks aren't being processed at the correct 20TPS. This = lag for you and the players in the form of network lag (blocks don't break, chests/crafting UI opens slow)

[latent pewter]

Yes, but not available on worlds, or realms

[vast scaffold]

can u do skeleton move toward target like java?

[full umbra]

That's unrelated to this post. This post is just about a block finding algorithm. The movement is unrelated and just to show the example.