Click here to Skip to main content
15,867,453 members
Articles / Game Development

FirstWins Pathfinding Algorithm

Rate me:
Please Sign up or sign in to vote.
4.95/5 (16 votes)
7 Feb 2017CPOL4 min read 40.3K   1.5K   44   12
Pathfinding algorithm based on a direction priority

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:

Image 1

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:

Image 2

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:

Image 3

'FirstWins' pathfinding block diagram:

Image 4

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:

Image 5

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:

Image 6

 

License

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


Written By
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 Pin
entilete18-Mar-13 17:13
entilete18-Mar-13 17:13 
QuestionMy vote of 5 Pin
Jonathan C Dickinson17-Mar-13 22:20
Jonathan C Dickinson17-Mar-13 22:20 
QuestionDiaganol length vs straight Pin
DaveAuld17-Mar-13 4:04
professionalDaveAuld17-Mar-13 4:04 
AnswerRe: Diaganol length vs straight Pin
O.G.I.18-Mar-13 7:38
O.G.I.18-Mar-13 7:38 
AnswerRe: Diaganol length vs straight Pin
Kenneth Haugland4-Feb-15 23:04
mvaKenneth Haugland4-Feb-15 23:04 
GeneralRe: Diaganol length vs straight Pin
DaveAuld4-Feb-15 23:27
professionalDaveAuld4-Feb-15 23:27 
GeneralRe: Diaganol length vs straight Pin
Kenneth Haugland4-Feb-15 23:28
mvaKenneth Haugland4-Feb-15 23:28 
GeneralRe: Diaganol length vs straight Pin
DaveAuld4-Feb-15 23:49
professionalDaveAuld4-Feb-15 23:49 
QuestionDoes this saves over regular Astar ? Pin
Roland_Y14-Mar-13 22:39
Roland_Y14-Mar-13 22:39 
AnswerRe: Does this saves over regular Astar ? Pin
O.G.I.17-Mar-13 0:09
O.G.I.17-Mar-13 0:09 
GeneralMy vote of 5 Pin
Alex Essilfie11-Mar-13 23:00
Alex Essilfie11-Mar-13 23:00 
GeneralMy vote of 5 Pin
Hoangitk9-Mar-13 17:14
professionalHoangitk9-Mar-13 17:14 

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

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