Click here to Skip to main content
Click here to Skip to main content

FirstWins Pathfinding Algorithm

, 17 Mar 2013
Rate this:
Please Sign up or sign in to vote.
Pathfinding algorithm based on a direction priority

Introduction

I came up with this idea while I was working on my game engine long time ago. At the beginning, I didn't expect that it will work and for several months the algorithm was only one sketch lying on my desk. However, several days ago, I decided to write a program that implements this logic and it turns out that it works just like it was on the sketch. There is a 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 axes 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 to the destination point in case that branch reaches the end.

Optional Step 3: Priority Switch

In case 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 just to show that the algorithm 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:

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

O.G.I.

Bulgaria Bulgaria
Name: Ognian Gantchev Ivanov
 
Current Age: 27
 
Country: Bulgaria
 
City: Stara Zagora
 
Professional skills: fine arts, sculpture
 
Hobbies: Programming();
 
Computer Languages: VB, C#, C++
 
Human Languages: Bulgarian, English
 
About me:
I'm an enthusiast game developer. I love computers, art and science.

Comments and Discussions

 
GeneralMy vote of 4 Pinmemberentilete18-Mar-13 17:13 
QuestionMy vote of 5 PinmemberJonathan C Dickinson17-Mar-13 22:20 
QuestionDiaganol length vs straight PinprotectorDaveAuld17-Mar-13 4:04 
AnswerRe: Diaganol length vs straight PinmemberO.G.I.18-Mar-13 7:38 
QuestionDoes this saves over regular Astar ? PinmemberRoland_Y14-Mar-13 22:39 
AnswerRe: Does this saves over regular Astar ? PinmemberO.G.I.17-Mar-13 0:09 
GeneralMy vote of 5 PinmemberAlex Essilfie11-Mar-13 23:00 
GeneralMy vote of 5 PinmemberHoangitk9-Mar-13 17:14 
Greate demo. Thanks!

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140709.1 | Last Updated 17 Mar 2013
Article Copyright 2012 by O.G.I.
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid