- Version 0.10.771-RELEASE-universal
- File Size 0.00 KB
- Create Date March 19, 2020
Minecolonies Changelog
Version: 0.10.771-RELEASE
- Schematics115 (#4421)
- Fix hospital symbols * Update zh_cn.json (#4438)
- Chinese translation update * Updating the PathFinding Heuristics. (#4442)
- This PR updates the path finding heuristics to be more concise and much more efficient.
A* Background In A* (The path finding algorithm used by us) the next evaluated node is determined by its node-value, called the f-value. This f-value is composed out of two factors. The c-value, known as the cost. This is the cost it would take an entity to walk from the starting position of the path (usually the current position of the entity) to the node in question. And the second factor is the h-value, known as the heuristic. This value is an indication for the algorithm, and indicates how much it would cost an entity using the path to walk from the current node to a destination. Now if the h-value is not accurate a lot of nodes will have the same f-value and as such the algorithm has to consider a lot of them, if it wants to make progress. As such the correct heuristic is very important.