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

Add path finding for Directed Acyclic Graphs #18

Closed
roy-t opened this issue Aug 1, 2018 · 2 comments
Closed

Add path finding for Directed Acyclic Graphs #18

roy-t opened this issue Aug 1, 2018 · 2 comments

Comments

@roy-t
Copy link
Owner

roy-t commented Aug 1, 2018

If we add path finding for Directed Acyclic Graphs, and also add an option to convert a grid to such a graph. We can make path finding a lot more flexible as this gives more control over what tiles are reachable from another tiles.

This could fix #16 by removing links between tiles that would cause cutting a corner.
This could fix #17 by giving links between tiles a direction.

Its still unclear what the performance impact would be. Do we need both algorithms or is path finding equally fast on a DAG?

@bradzoob
Copy link

Hadn't seen you'd posted this 2 weeks ago! This would be awesome :)

@roy-t
Copy link
Owner Author

roy-t commented Dec 27, 2018

So this turned out to be a complex problem. Graphs are usually faster because you can use a less dense representation, but performance optimizations for graphs and grids are very different. I've decided not to implement this feature.

@roy-t roy-t closed this as completed Dec 27, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants