New Path-Finding Sub-system

[jonathan]

The built-in Vanilla path-finding algorithm is not optimized (at all) and makes the game almost unplayable when more than one player is logged-on a server at a time. This is because some mobs (Nightmare Creatures mobs in-particular) make very deep path-finding requests and these requests are issued once per tick, which is very inefficient (and unnecessary).

This will likely inspire a new companion mod that solely improves the built-in path-finding.

[jonathan]

Implementation is almost completed. Some outstanding sub-tasks include (may be promoted to separate tickets later):

• Fire-based mobs to avoid water (may not be necessary, I think Lava Monsters has its own AI)
• Revisit diagonal graph-edge computation, current implementation is too simple
• Account for ladders and vines
• Clear A* graph memory periodically (based on random time period)
• Introduce random entropy so that paths are non-deterministic
• Allow a timid setting for animals and bold setting for mobs, this influences whether risky / dangerous paths are considered impassible or not
• Entities stall path-finding every now and then for some reason

Sub-tasks that are complete but require further testing:

• A* graph cache window, verify that it culls properly
• Normal mobs to properly avoid lava / fire, they're still strafing too close to it and dying

[jonathan]

All of the above are now completed except for the following remaining sub-tasks:

• Clear A* graph memory periodically (based on random time period)
• Introduce random entropy so that paths are non-deterministic
• A* graph cache window, verify that it culls properly

There are some new sub-tasks I've found since working

• Fences, mobs think they can jump over them and jump endlessly at them
• Cache the path-point graph since we're going to be refreshing it periodically anyway
• Mobs tend to "break-dance" near edges
• Spiders don't really move, they just sit there unless you get very close to them
• Zombies (and other mobs) seem to give-up path-finding altogether and even lose complete interest in you until you aggravate them

[jonathan]

Again, the above are now completed except for the following remaining sub-tasks:

• Introduce random entropy so that paths are non-deterministic
• A* graph cache window, verify that it culls properly
• Fences, mobs think they can jump over them and jump endlessly at them

Improved, but still needs work:

• Mobs still tend to "break-dance" near edges

[jonathan]

Again and again, the above are now completed except for the following remaining sub-tasks:

• Introduce random entropy so that paths are non-deterministic
• Mobs "break-dance" near narrow holes, the block-highlighter indicates that these are larger mobs that are trying to path-find into them. They give-up after a little while though so I might leave this as is.

Additionally, I still need to:

• Prohibit animal-like mobs from climbing ladders

I also did some performance profiling, once again none of the path-finding methods shows-up as hot spots, even with a hundred mobs running around in the immediate vicinity. These performance gains are simply unreal, we're talking between x100 and x1000 performance boost over the Vanilla implementation. Minecraft multi-player will be playable again at last.

[jonathan]

Only remaining sub-task is the break-dancing phenomenon, which is a bit more common than I had thought.

I decided against a random entry feature, this would significantly increase the computational and storage complexity of the algorithm, and the resultant behavior may not even be desirable.

[jonathan]

Released as version 1.0 under MMM 8.6.8-Blackberry