sampsaoinonen
commented
2 weeks ago -
Adding more comments to both of the algorithms is a good observation and I will do that!
-
Understanding Fringe search: You're right that the Fringe Search algorithm is quite challenging to understand just by looking at the code, especially with just standard docstring-style comments(or at least was for me). Unlike algorithms like Dijkstra's, Fringe Search isn't as widely taught or documented and reading the study is slow. Without turning commenting into teaching material itself, it's probably not going to easily open up. But again it’s a good point to make more clear comments and I’m also planning to write a brief description about both Fringe and A* in the documentation before the end of this course.
-
A_star vs Fringe: You've pointed out the biggest challenge and perhaps the main point of this topic. I've asked about this and according to Hannu Kärnä "Fringe search is very hard to make faster than A". Additionally, all the previous works in this course(or internet) I’ve found on this subject have also lost the speed comparison to A. I’m beginning to think Fringe is quite academic and not that much used in real life. I’m not even sure if it’s possible to optimize Fringe faster than A* in this environment. Note that the original Fringe Search study was focused on grid-based game pathfinding not real maps.
-
A_star priority Queue: This is being implemented using Python's heapq-module. I'll add comments to clarify this.
Thanks for the feedback!
The project was downloaded on October 2nd at ~11PM. The project runs and all the tests pass.
The code is well structured and mostly clear and well commented. I would have wished the code implementing the algorithms to be a bit more commented — I am still not sure if I understand how the fringe search algorithm is supposed to work. From what is reported by the interface, the fringe search takes about 8 times longer than A*. I am under the impression that it should be faster, but can’t see anything wrong about the code in the immediate.
Also from what I could gather, the A* is supposed to be slower because it is costly to keep the list sorted. I don’t see which part of the code represents the list being kept in order. It might be included, but the code is quite heavy to read, could use more comments and more descriptive naming.
One thing that could be interesting to see, although probably out of scope for this project, is some kind of illustration on the map of the nodes visited by each search algorithm.
Tests look tidy and extensive. Is the purpose of this project to demonstrate the differences of the chosen algorithms, and could such comparison be included in the tests?
Great work overall! I can also see that you’ve put a lot of work into the the UI :)