Pathfinding

[iam4722202468]

[MelonHell]

Resolves #1987

[KrystilizeNevaDies]

I'm still not a big fan of having specific handling for certain types of pathfinding abilities. e.g. LAND, AQUATIC, FLYING, AMPHIBIOUS

I'd rather be supporting a generic api that could support any of these configurations. e.g.

interface PathfinderEntity {
  /**
   * Returns a set of next positions this entity can travel to from the given position.
   */
  Set<Pos> nextStep(Pos pos);
}

or

interface PathfinderEntity {
  /**
   * Returns a range of next positions this entity can travel to from the given position.
   */
  PosRange nextStep(Pos pos);
}

or

interface PathfinderEntity {
  /**
   * Returns a range of next velocities this entity can be applied from this given position.
   */
  VelRange nextStep(Pos pos);
}

e.t.c

There are many api ideas that could support this without need to hardcode specific arbitrary pathfinding types.

[DasBabyPixel]

Any updates here?

[iam4722202468]

Try the pr and see if there's issues. This hasn't been merged yet because we haven't had enough people test it

[RandomModderJDK]

I did some very limited testing, and found that this pathfinding is way better than the one from main.

I made a Zombie with me as a target and a follow-goal.

1. Testcase, let him try some parcour with blocks placed randomly by me:

• could walk diagonally, with just 2 blocks in a 2x2 square, which main algo failed at
• does not escalate completely (like turning his body rapidly), when he can not reach his target

2. just plain terrain, with running target:

• main branch algorithm leads to the zombie looking in a completely other direction, when changing targets position - this algorithm not so much
• more natural, doesnt walk "block for block", e.g. first ahead, then to the right, on a diagonal path. But I'm not quite sure about this - needs more testing

3. follow target on terrain generated by jnoise

• main branch algo wouldn't even work - they are freezed. Don't know why it shouldn't work
• just jumps and walks pretty-flawlessly to me

What I would consider to do test with:

• what if entities are in the way
• what about trapdoors and doors
• can a really distant target be reached( whats the maximum viable distance)

Performance comparison would be really nice too. I did not monitor it

[iam4722202468]

Thanks for taking a look. Currently doors, trapdoors, etc. are not handle, and are treated as full blocks. This algorithm allows for extending which blocks are walkable and how path are followed, so in the future there could be a node generator which implements features like climbing, doors, multi-block jumps, blocking entities, etc. The idea is this is the base which future pathfinding rules will be built on.

Performance has been worked on a decent amount and while the current pathfinder probably performs better this one will work properly and is multithreaded, meaning that even slow path generation wouldn't block the main thread. From testing i've seen most people can get 10k+ pathfinding entities without much lag.

if you're in the minestom discord this person tested it and found it performed well https://discord.com/channels/706185253441634317/706186227493109860/1214046960189837383

[RandomModderJDK]

What is needed to complete this pr then? My guess would be that we need to pass all tests, right?. (Or removing ones that became invalid now, if any)

[iam4722202468]

After a code review this will be merged with other large 1.20.5

[iam4722202468]

This will be merged in to 1_20_5 here https://github.com/Minestom/Minestom/pull/2153