bracket-lib
bracket-lib copied to clipboard
amethyst
Optimize astar
This is a series of small discrete changes which improves the performance of astar:
| Lower bound | Estimate | Upper bound |
|---|---|---|
| -38.047% | -35.871% | -33.599% |
I have a second PR for getting the bench running due to some sign issue making usizes which is needed to be able to reproduce these results. I have a third PR which adds some minimal unit tests
*Note: This was updated to reflect latest updates and to use the fixed benchmark master: 3072985
Err the first commit is the commit is the other PR so I guess only merging this PR would fix the other open PR as well.
I just realized this benchmark is making a mistake on the last point of get_available_exits. This ends up causing a lot more searching but it this is ok since it is now properly determining all possible valid exits. Technically, this commit should have been another PR...
I just realized that I made an error in a294e8c. Using parents obviously works but way over allocates. I will think about this for a little bit and revert that change if I do not come up with something more reasonable.
As author of this PR I am willing to resolve merge conflicts but another idea would be to just use pathfinding crate for astar (and pretty much any algo for searching). In my own project which has a similar map (this was a long time ago so my memory is fuzzy) but I think using an iterator for proposed moves (get_available_exits) and pathfinding was like 20x faster than this. It might be better to open a newer PR which makes those changes...or not.
I just remembered this is a public repo: https://github.com/enebo/mappy/blob/main/src/map.rs#L244 . This just gives an idea and mappy is not exactly the same as bracket-lib but the benchmark itself is the same so it can be compared.