Introduction
I came up with this idea while I was working on my game engine few years ago. There is huge resources in the web about pathfinding, especially for A* , but I wanted to create something myself, so here it is. I hope you'll find it useful.
The Demo Program
The applied demo program and code are written on VB 2010, however, the logic of 'FirstWins' pathfinding is not program-specific. You should be able to adapt what's here to any computer language.
Here's a short description about the demo program interface:
Set or Remove Walls
When this option is enabled, you can "draw" or "erase" walls
- left mouse button = create walls
- right mouse button = erase walls
Set Start or End
When this option is enabled, you can place the start point(A) and the end point(B) on the playground
- left mouse button = set point A
- right mouse button = set point B
Sorted Branch
This means that all active branches will be sorted by their distance to the end point and the searching will start from the branch that is closest to the end point.
Full Priority
This means that path finding will start from the branch that meets the full priority of the branching.
Description
In order to reach the end point 'FirstWins' pathfinding relies on 2 simple rules - 'Priority Set' and 'Priority Switch'. Here are all the steps to perform in order to find the path:
Step 1: Priority Set is simple movement direction instruction:
Let’s set 2 points; a start and an end:
If start.x > end.x then the priority for x is X- because in order to get to end.x, we will have to decrease the value in start.x. Vice versa if start.x < end.x, then the priority for x is X+. If start.x = end.x, then the priority is 0, we don’t need to change the value in start.x in order to reach the end. The same rule applies for the Y axis.
Examples:
- start.x = 4, end.x = 10, priority for x is X+
- start.y = 3, end.y = 1, priority for y is Y-
The priority of branching is: X+,Y-
Step 2: Check for free positions
If our priority is X+,Y- then the branching will be headed North-East, let’s find all positions that fit this priority:
As you can see, in order to be a suitable position for the next branching, the square doesn’t need to meet the same directions as the priority. It’s enough that only one of the axis has the same direction.
The next sub-step is to check if the priority points are free, e.g., there are no walls, other objects or if these points haven’t been examined by other path-searching branches from the same family.
Next, we branch to the free positions. Each new branch remembers its parent position. This is important because this data will help us trace the path back to the destination point, when that branch reaches the end.
Optional Step 3: Priority Switch
If none of the priority positions are free, then the branch will switch its priority. The ‘+’ will become ‘-’ and ‘-’ will become ‘+’ , then we perform step 2 again, but this time using the new priority.
Final Step - Deactivating
Inactive branch is a branch that doesn't have suitable positions to reach, or its branches are already spread into the suitable positions and there are no more actions for it to perform. If the branch has reached the destination point, it will also deactivate all other branches and will retrieve the path to the destination.
Examples
Graphics example of how 'FirstWins' is searching for a path:
'FirstWins' pathfinding block diagram:
Conclusion
According to the algorithm's logic, the first branch to reach the end point is the relatively shortest path. However, the solution might not always coincide with the mathematically shortest path. The ‘branching priority’ is the mechanics that make the pathfinding process more controlled and less branched out.
The implementation of the algorithm in the applied demo program (PathfindingDemo) is very basic and sometimes buggy and inaccurate, its primary intent is to show that the algorithm just works, nothing more. Most of the problems with pathfinding in the demo program are related to the coding, not to ‘FirstWins’ algorithm. I believe that due to its simplicity, 'FirstWins' could be enhanced and optimized in many ways. Any suggestions and ideas from you are more than welcome.
Whats new in this release
15 Dec 2012:
- first release
Latest release - 17 Mar 2013:
- added path optimization function that reduces the 'jumps' and 'drops' in the discovered path.
- 'trace object' added for testing the path
Interface and system changes:
the new set of menus are located near the right bottom corner of the graphics interface:
timespan:
the speed of the moving path-trace object: the lower the value is the faster the object is.
Test Path:
click this button to test the generated path using the trace object that moves through the destination nodes
optimize path:
'optimize path' function is reducing the fluctuations in the destination path, ie it straightens the path line:
