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.
It looks like the string pulling algorithm but reversed. Instead the angle of the cone can only be reduced, in your case it can only be increased.