🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Node Loops

posted in the game for project unirule
Published May 16, 2018
Advertisement

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,
NodeLoop.png.e7a4150f4cd7d8b3310b9270b325bd42.png

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.

animatedPathFind.thumb.gif.1d6e83e28bbc0cb999381f605181de8c.gif

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.
 

6 likes 1 comments

Comments

bdubreuil

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.

May 18, 2018 03:33 AM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Profile
Author
Advertisement
Advertisement