Pathfinding doesn't use h(n)

[andretchen0]

Meta: Not a bug, per se. Not a feature request. Should this go in "Discussions"?

I'm looking at HexGrid and Hex. Hex carries around a lot of state. One part of the state is f, g, h, pathparent used by pathfinding.

The path finding algo setup is similar to A*. It's got a a small twist for Creature size. The benefit of using A* over another algo (e.g., Djikstra) comes from the use of the heuristic h. From Wikipedia:

A* achieves better performance by using heuristics to guide its search.

But pathfinding.js doesn't actually use h, except to set it to 0. Here's an example for a very brief game (2 rounds, summoning 2 creatures and moving each creature):

~6,000 assignments setting h to 0.

Ultimately, 6,000 unused assignments don't matter unless performance is affected.

But the keeping f, g, h on Hex leads to tightly coupled modules, and extra operations in pathfinding, Hex, and HexGrid to keep those attributes "clean".

On top of that, forcing callers to provide concrete Hexs, a concrete HexGrid, and a creature id isn't ultimately necessary and makes the algo resistant to testing.

So ...

So, I'm going to go ahead and work on a full rewrite here, unless there are objections.

[andretchen0]

Documenting things here:

HexGrid calls search in pathfinding.ts, but always with coordinates that don't exist in-game – (-2,-2). This essentially runs a shortest path tree algorithm. The algorithm is used to set the value of Hex.g, the cost of the path to get to a particular Hex. Hexs with a g below a certain threshold are then collected into an array and returned.

[DreadKnight]

Sounds like a good rewrite, nice find! I've converted this to discussion more for the sake of testing the GitHub feature tbh. 🐻
This could have remained an issue just fine; actually wanted to close conversation and reopen the existing issue, but not possible.