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 Code

Here is a basic Example


1	2	3
		4
		5	6	7

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 Priority

Large-Scaling Map

Basically the program is build for large-scaling map. The time to take a decision is constant no matter how huge is the map.

Artificial Intelligence

The program is not using any complex algorithms. It move one steep at the time and make decision when it cannot continue forward.

Precision

The Path Finding Engine ensure that is a single path exist from point A to B it will be found!

Fast

The 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

Optimization

When a path is found, two basic optimizations are done to reduce the path length.

Local Optimisation

1	2	3	4
		6	5
		7			12
		8	9	10	11

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.

1	2	3
		4
		5			10
		6	7	8	9

Example #2 (Local optimization)

Bi-directional 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 Bi-directional is useful.


			Will spend a lots of time here
1	2	3	Will spend a lots of time here						1
15									2
14									3
13	12	11	10	9	8	7	6	5	4

Example #3 (Bi-Directional optimization)

In example #3 we can see that starting from the end is MUCH easier! This situation do happen on large-scale map and a bi-directional optimization in this situation will save process time. Because End-Start will finish probably twice faster that Start-End


1	2	3	4					21
			5					20
	8	7	6				18	19
	9						17
	10	11	12	13	14	15	16

Example #4-1 Start-End


					5	4	3	2	1
21	20				6
	19				7	8	9
	18						10
	17	16	15	14	13	12	11

Example #4-2 End-Start

In example #4-1 and #4-2 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 Bi-Directional optimization that do optimized the path length but not the process time.


1								17
2	3							16
	4						14	15
	5						13
	6	7	8	9	10	11	12

Example #6 (Bi-Directional optimization) Start-End

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.