OP Plans and Path-finding Thoughts
Posted by Jeff Disher
OP Plans and Path-finding Thoughts
Split the loose grab-bag of ideas for OP 1.15 ("The Flavour Update") out so that now there is a plan for OP 1.16 ("The Weather Update").

This is because the list of items was generally unstructured and large. This new arrangement means that 1.15 is more about continuing to flesh out crafting requirements and missing content by adding new mobs and refining some work done in the previous release (plant growth stages, water flow distance, etc). OP 1.16, on the other hand, is more about animations, world-gen changes, and new mechanics related to friction (for ice) and weather.

So, this means that the only particularly big item for 1.15 is the rework of the AI path-finding and initiative to support how chickens and spiders will move, as well as adding general support for sub-block navigation. The problem is that I am not sure how I want to approach this, so some thinking is required.

As it stands, the path-finding algorithm is essentially just A-star with some tweaks in order to decay to walking in a straight line when there are no obstacles (so the creatures don't zig-zag around in an obvious grid). I don't know why people act like A-star is somehow "bad" when really it is just Dijkstra's Algorithm applied to a dense graph (so, the obvious first solution one would try). From my perspective, it is fine but heavier than I would like (since a dense graph is... dense).

Looking forward, there is an argument that I should just tweak the precision on the existing path-finder so that it works on the units of sub-blocks, not full blocks. This mostly worries me from a system resources perspective: It is taking a heavy algorithm and making it 64 times heavier.

But, I do also wonder if I should just be thinking in different, potentially less exhaustively correct terms. I am not sure how to approach that, though, so this is likely to be a slow start.

This question does explain why Minecraft mobs often behaved strangely when on something like stairs (like twirling around, etc).

Interacting with the world, on top of this, will be another level of complexity. Ideally, villagers could use doors and would go "in" at night and "out" during the day, just to show that they are doing something. Thinking about the definition of "inside" and "outside" also reminded me of how the old Minecraft villagers handled this problem.

I also wonder if there is some way I can solve this problem such that converting the movement plan to actions wasn't so ugly and manual.

Hopefully, I will have some idea to prototype soon,
Jeff.