Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Dijkstra map should set starting depths before iterating neighbors #370

Open
AdamStone opened this issue Jan 28, 2025 · 0 comments
Open

Comments

@AdamStone
Copy link

Thanks for the roguelike tutorial, it was a great way to get started with rust. I've been playing around with it and noticed the DijkstraMap is not quite working like I would expect.

In the DijkstraMap build function although the start tiles are assigned 0 depth in the open_list queue, the depth only gets written to dm.map when iterating exits. The effect is that a start tile's own value only gets set when iterating an adjacent tile's exits, at which point new_depth is 1. The start tiles then appear to have the same depth as their adjacent tiles. This is a problem for using find_lowest_exit to path all the way to a start tile, as the gradient disappears before actually reaching it.

For example in this image the grayscale tiles are starts and the green tiles show the distance to the gray tiles. Trying to path out of the green and into the gray tiles is unreliable because the gray exits have the same depth as some of the green exits:
Image

Looks like the other build variations have the same issue.

I think when you push the starts into open_list you should also set dm.map[*start] = 0.0; (or the provided depth for the weighted build). Trying that gives the result I'd expect:
Image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant