dart-a-star icon indicating copy to clipboard operation
dart-a-star copied to clipboard

Add the more general `AStarState`

Open Levi-Lesches opened this issue 1 year ago • 0 comments

Broadly, this alternate API gets rid of any assumptions about a finite or enumerable grid, and thus allows users to plan a path across an infinite grid or theoretical grid, such as those representing player moves in a game.

The API is a tad clunky due to one thing: It is often very convenient to implement getNeighbors by simply coping the parent state and making small changes to it for each neighbor. But since the heuristic and hash are cached, I chose to expose a finalize function to let the user decide when to cache. This means we avoid hard-to-diagnose bugs where, say, a state's has is printed during debugging, thus possibly caching the hash before the vital change was made. The only problem is the user must manually call state.finalize() on all states they wish to use with aStar(). In practice, it isn't so bad because that's only two places: the start state, and in getNeighbors.

I've battle-tested the logic and API by using it in two of my projects before opening this PR, but I'd appreciate a second look at the actual aStar function for good measure.

Levi-Lesches avatar Jan 23 '24 10:01 Levi-Lesches