Some points:
1. From the Wikipedia article, it seems that a good heuristic would be max{|dx|, |dy|}.
This represents the distance in the absence of obstacles, and has therefore the nice properties of being admissible and monotonic. Apparently, admissibility is essential for always finding an optimal path.
Have you tried that? It would be interesting to know how this would compare to the euclidean distance in your particular application, with respect to both functionality and performance.
2. Do you think your application would benefit from reusing the buffers for predecessor map and distance map between calls to findPath?
In this case, findPath could be a function object, with each instance holding the buffers as members. Current behaviour would be equivalent to instantiating one temporary object per call, while, depending on the application, it might be interesting to give the object a longer lifetime, reusing it across several calls.
I am very much interested in this series of articles, yes!
Two points:
1. Why the use of isValid() in iterator increments?
Isn't it better to have that be a precondition rather than force the cost of a branch in what could otherwise be a trivial operation? If the possibility of misusing the iterator is feared, a debug mode assertion could be used to detect it, instead of trying to compensate for it.
2. Edge iterator increment could use a simple iteration, instead of a call to a recursive function.
I think this would simplify the code (from an imperative language perspective), besides being possibly more efficient.
Thanks for the article! It is a great demonstration of the power of generic interfaces, and of the Boost Graph Library in particular. It also serves as a nice tutorial.
Log In
or
Sign in with Github
Sign in with Twitter
or
Sign in with Github
Sign in with Twitter
Sign Up
or
Sign in with Github
Sign in with Twitter
Reset Password
Enter the email address associated with your account, and we'll email you a link to reset your password.
Some points:
1. From the Wikipedia article, it seems that a good heuristic would be max{|dx|, |dy|}.
This represents the distance in the absence of obstacles, and has therefore the nice properties of being admissible and monotonic. Apparently, admissibility is essential for always finding an optimal path.
Have you tried that? It would be interesting to know how this would compare to the euclidean distance in your particular application, with respect to both functionality and performance.
2. Do you think your application would benefit from reusing the buffers for predecessor map and distance map between calls to findPath?
In this case, findPath could be a function object, with each instance holding the buffers as members. Current behaviour would be equivalent to instantiating one temporary object per call, while, depending on the application, it might be interesting to give the object a longer lifetime, reusing it across several calls.
Two points:
1. Why the use of isValid() in iterator increments?
Isn't it better to have that be a precondition rather than force the cost of a branch in what could otherwise be a trivial operation? If the possibility of misusing the iterator is feared, a debug mode assertion could be used to detect it, instead of trying to compensate for it.
2. Edge iterator increment could use a simple iteration, instead of a call to a recursive function.
I think this would simplify the code (from an imperative language perspective), besides being possibly more efficient.
Thanks for the article! It is a great demonstration of the power of generic interfaces, and of the Boost Graph Library in particular. It also serves as a nice tutorial.