This is a project aimed at implementing different path finding algorithms between two points. Any number of walls may be added and path may can be found between these two points. Also, passable walls may also be added, with an increased cost to cross them.
Bidirectional search, search without diagonal neighbours and search with 4 different heuristics (for informed search) are supported.
The total time taken for the search is also displayed at the end of every search.
The different algorithms supported -
A* search-- using Chebyshev Heuristics, allowing diaognals mono directional and bidirectional, and not allowing diagonal neighbours, respectively-
The Iterative Deepening Search works with the help of heuristics. A threshold of path length is set for every iteration and all nodes from the start position with maximum path length as threshold are explored. If endPos is not found within that threshold, the threshold is increased to the minimum path length required from the previous iteration. Thus, the search continues, increasing the threshold each time all nodes for a given threshold are explored until endPos is reached.
As this algorithm may visit the same node via different paths, it may be possible that the time taken for the search explodes. Here, the search stops when the prescribed time limit for search is crossed.
If the visualise recursion option is chosen, nodes are colored according to the order in which they are visited. Moreover, if a node is currently on different paths, it is colored proportionately with a darker shade. As the node is removed from the recursive stack, it is uncolored to white. This helps us visualise the recursion, depicting the nodes visited and unvistited, in that particular order. In case the time limit is exceeded, only the recursive visulisation is seen, if the option is selected.
IDA* search-- using Chebyshev Heuristics, allowing and not allowing diagonal neighbours, respectively-
Breadth First search--mono directional and bidirectional respectively-
Best First Search-- using Chebyshev Heuristics, allowing diaognals mono directional and bidirectional, and not allowing diagonal neighbours, respectively-
Djikstra search--allowing diagonals and not allowing diagonals respectively-
