13,045,564 members (68,651 online)
alternative version

#### Stats

19.9K views
41 bookmarked
Posted 15 Dec 2012

# FirstWins Pathfinding Algorithm

, 7 Feb 2017
 Rate this:
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:

### 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-

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.

## 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:

## Share

 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

I'm an enthusiast game developer. I love computers, art and science.

## You may also be interested in...

 First Prev Next
 My vote of 4 entilete18-Mar-13 17:13 entilete 18-Mar-13 17:13
 My vote of 5 Jonathan C Dickinson17-Mar-13 22:20 Jonathan C Dickinson 17-Mar-13 22:20
 Diaganol length vs straight DaveAuld17-Mar-13 4:04 DaveAuld 17-Mar-13 4:04
 Re: Diaganol length vs straight O.G.I.18-Mar-13 7:38 O.G.I. 18-Mar-13 7:38
 Re: Diaganol length vs straight Kenneth Haugland4-Feb-15 23:04 Kenneth Haugland 4-Feb-15 23:04
 Re: Diaganol length vs straight DaveAuld4-Feb-15 23:27 DaveAuld 4-Feb-15 23:27
 Re: Diaganol length vs straight Kenneth Haugland4-Feb-15 23:28 Kenneth Haugland 4-Feb-15 23:28
 Re: Diaganol length vs straight DaveAuld4-Feb-15 23:49 DaveAuld 4-Feb-15 23:49
 Does this saves over regular Astar ? Roland_Y14-Mar-13 22:39 Roland_Y 14-Mar-13 22:39
 Re: Does this saves over regular Astar ? O.G.I.17-Mar-13 0:09 O.G.I. 17-Mar-13 0:09
 I'm very busy working on two jobs and I didn't have the time to write A* implementation to make a comparison, but I think it have the potential to be faster because it relies on much more simple logic and the calculations needed for the 'FirstWins' are also more simple - basically it only compares two integer values and then add or subtract again from integer. Thank you guys for the votes and for the interest, I hope someone will find a spare time to make some benchmarks between other pathfinders.
 My vote of 5 Alex Essilfie11-Mar-13 23:00 Alex Essilfie 11-Mar-13 23:00
 My vote of 5 Hoangitk9-Mar-13 17:14 Hoangitk 9-Mar-13 17:14
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jul-17 15:53 Refresh 1