Hello GameDev,

During my efforts to accomplish the last robust challenge of mine

I discovered a new way, *for me*, to speed up the processing time to achieve much faster path-finding results.

About the technique:

I created continues node loops,

Every node has information about the loop it's a member of. Each Node has the following object:

{ id: 4, loop: 10, loopSize: 8, loopStart: 0, loopEnd: 7 }

and the following functions:

left( x ){ if( this.id - x < this.loopStart ){ return ( this.id - x + this.loopSize ); } else { return ( this.id - x ); } } right( x ){ if( this.id + x > this.loopEnd ){ return ( this.id + x - this.loopSize ); } else { return ( this.id + x ); } } getDirection( n , M ){ var m = M || this.id; if( n - m > 0 ){ if( Math.abs( n - m - this.loopSize ) < ( n - m ) ){ return true; // to IDa } else { return false; // to IDb } } else { if( ( n - m + this.loopSize ) < Math.abs( n - m ) ){ return false; // to IDb } else { return true; // to IDa } } } getNodesBetween( n , M ){ var m = M || this.id; if( n - m > 0 ){ if( Math.abs( n - m - this.loopSize ) < ( n - m ) ){ return Math.abs( n - m - this.loopSize ); // to IDa } else { return ( n - m ); // to IDb } } else { if( ( n - m + this.loopSize ) < Math.abs( n - m ) ){ return ( n - m + this.loopSize ); // to IDb } else { return Math.abs( n - m ); // to IDa } } }

With information about its parent loop accessible to each node, informed choices are possible about the nodes that should be tested for each subsequent iteration.

The following animated .gif visually demonstrates the logic.

1: Select Origin and Destination points

2: Check for collisions between them and determine node pairs ( Node pairs are nodes that are apart of the same loop )

3: Determine the smallest number of nodes between the node pairs, ( Are there fewer nodes if we travel left? or right? )

4: Check for collisions between Origin node and each incremental node apart of the loop. ( stop once collision is found )

5: Use last successful node tested as the new Origin point.

6: Check for collisions between Destination node and each incremental node apart of the loop. ( stop once collision i found )

7: Use last successful node tested as the new Destination point.

7. Repeat.

The **Good**,

It is much faster than using the blind search method I was using before, especially if both directions are searched when an obstacle is encountered. If only one node loop is encountered it will return the shortest path with the addition of a refinement function.

The **Bad**,

It doesn't return the shortest path. For that it has to be used in combination with other techniques and two new '*branches*' of the function would be required for each unique node loop encountered.

## 1 Comment

## Recommended Comments

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now