[#396] Entities: Pathfinding [$50]

[gdude2002]

This issue is part of this story, Completing entities in Glowstone (#396). To make the work easier and bounties fairer, we've split it into multiple issues.

Anyone can participate in the completion of this issue, which will be a major turning point in the development and the possible use-cases for Glowstone as a Minecraft server alternative.

---

Before getting started! If you are unfamiliar with Glowstone, please remember that Glowstone is a complete rewrite of the Minecraft vanilla server, aimed to be a better alternative to other software like Spigot. You are by no means allowed to push code to this repository based on Mojang's own platform (whether it be Forge, MCP, decompiled binaries, etc.) Doing so will cause in the rejection of your Pull Request. You are allowed to use other resources like the numerous wikis that exist on the Internet (Minecraft Wiki, wiki.vg, etc.) as well as trial-and-error.

---

Pathfinding

Glowstone currently lacks a 3D pathfinding tool for entities to reach a specific target. Keep in mind that dozens of entities may be running pathfinding actions simultaneously, which may hinder the performance on the server. This pathfinding algorithm would need to be able to not affect performance too much, while being a rough equivalent to the Vanilla functionality.

• Decide on an appropriate pathing algorithm, which may be A* (currently used in Vanilla) or one of its many derivatives. Based on my personal work and research on this, A* seems much more efficient and appropriate for 2D environments, but less so with layered 3D environments. The decided algorithm would have to be implemented with the concept of a 3D voxel world in mind (not a closed environment!)

---

There is a $50 open bounty on this issue. Add to the bounty at Bountysource.

[Salil999]

Interested in working on this. If A* is used, what heuristic are we looking at? Manhattan distance is what I'm presuming...

[aramperes]

I would think that Euclidean distance heuristic would be used. Even though the world is just a set of cubes, mobs (entities subject to Pathfinding) don't have to follow the grid. They can go from A to B diagonally.

[smartboyathome]

One thing to check as you work on this is the affects of precision on whatever algorithm you use as you get close to the default Minecraft world border at 30,000,000 blocks. While in Vanilla this doesn't happen at 30,000,000 blocks, if you mod it to remove this limit, you'll see entities start to fall into loose lines. Youtuber AntVenom has done some good exploration around this: https://www.youtube.com/watch?v=uHWoB9GCSYk

[Salil999]

Got something in there: #799

Although I don't know how to remove all the odd formatting errors that are on CircleCI.

[mastercoms]

@creatorfromhell You can probably propose #924 as a resolution for this issue, for the bounty.