
The PathFinding Engine is a simple program that detect a path between a point A to a point B in a 2 dimensional map. The program has been written in using Visual C++ for personal fun and learning.
How it works. Color CodeHere is a basic Example
White: An empty cell Black: A barrier point, Cannot go on it. (you can change a barrier point to a empty cell by clicking on it) Green: is the current point, if you move one by one you will see the green cell moving. You can manually moving it by drag and drop. Yellow: is the path, The starting point is yellow. the path is always continuous. Red: The end of the path. This is the goal. You can manually changing it by drag and drop.
Dark Purple: This is a backup procedure, the user press undo button or the program got no other way to continue.
Bleu: This optimization. At the end, optimization is done depend on user option. Read more about optimisation 1,2,3,4,5... Number are use only in the help file to see the order of the path. They are not on the program.
Program PriorityLargeScaling MapBasically the program is build for largescaling map. The time to take a decision is constant no matter how huge is the map. Artificial IntelligenceThe program is not using any complex algorithms. It move one steep at the time and make decision when it cannot continue forward. PrecisionThe Path Finding Engine ensure that is a single path exist from point A to B it will be found! FastThe process is not the fastest way because it ensure that it will find it. But to accelerate the process 2 thread try to find the path OptimizationWhen a path is found, two basic optimizations are done to reduce the path length.
Example #1 (Local optimization) Example #1 is the classic example or local optimization possible. We can see here that #4 and #5 are useless. If local optimization is activate in the option. the path will be change at the end for example #2.
Example #2 (Local optimization)
This is an way to prevent huge derivation from a perfect path. Two paths are create simultaneously from start to end point and from end to start. At each move both path one cell at the time. If a path got a complete path the other will continue but not more than doing more than twice the number of move. At the end if both got a complete path, a smart merge of the two will be done. Here is some example of classic Bidirectional is useful.
Example #3 (BiDirectional optimization) In example #3 we can see that starting from the end is MUCH easier! This situation do happen on largescale map and a bidirectional optimization in this situation will save process time. Because EndStart will finish probably twice faster that StartEnd
Example #41 StartEnd
Example #42 EndStart
In example #41 and #42 we can see that both are in trouble. But if we merge, at the end, the 2 path are have a good result. Example #5 will show the result of a BiDirectional optimization that do optimized the path length but not the process time.
Example #6 (BiDirectional optimization) StartEnd
All optimization give a good result in a good process time. Of course this program does not guarantied the shortest path because a personally think that is we really want to find the shortest path is to do all the path and this is not possible since I want a large scaling algorithm. 