Jump to content
  • Advertisement

Node Loops

Sign in to follow this  
Awoken

513 views

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.
 

Sign in to follow this  


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
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!