Jump to content
  • Advertisement

unirule

  • entries
    20
  • comments
    38
  • views
    19091

More Adventures in Robust Coding

Awoken

2409 views

Hello GameDev, 

This entry is going to be a big one for me, and it's going to cover a lot.  What I plan to cover on my recent development journey is the following:

1 - Goal of this Blog entry.

2 - Lessons learned using Node.js for development and testing as opposed to Chrome console.

3 - Linear Path algorithm for any surface.

4 - Dynamic Path Finding using Nodes for any surface, incorporating user created, dynamic assets.

5 - short term goals for the game.

-- - -- - -- - -- - -- - -- - Goal of this Blog entry - -- - -- - -- - -- - -- - --

My goal for this adventure is to create a dynamic path-finding algorithm so that:
- any AI that is to be moved will be able to compute the shortest path from any two points on the surface of the globe.
- the AI will navigate around bodies of water, vegetation, dynamic user assets such as buildings and walls.
- will compute path in less then 250 milliseconds.

5a737586448c5_Screenshotfrom2017-12-2021-28-04.thumb.png.ce24aed24ba92ae43cede325f984f5ff.png

There are a few restrictions the AI will have to follow, in the image above you can see land masses that are cut off from one another via rivers and bodies of water are uniquely colored.  If an AI is on a land mass of one color, for now, it will only be able to move to a location on the same colored land mass.  However; there are some land masses that take up around 50% of the globe and have very intricate river systems.  So the intended goal is be able to have an AI be on one end of the larger land mass and find the shortest path to the opposite end within 250 milliseconds.
Currently my path finding algorithm can find the shortest path in anywhere from 10 ms and up, and when I say up, I mean upwards of 30 seconds, and that's because of the way I built the algorithm, which is in the process of being optimised.

-- - -- - -- - -- - -- - -- - Lessons learned using Node.js for development and testing - -- - -- - -- - -- - -- - --

As of this writing I am using Node.js to test the efficiency of my algorithms.  This has slowed down my development.  I am not a programmer by trade, I've taught myself the bulk-work of what I know, and I often spend my time re-inventing the wheel and learning things the hard way.  Last year I made the decision to move my project over to Node.js for continued development, eventually it all had to be ported over to Node.js anyways.  In hind sight I would have done things differently.  I would have continued to use Chrome console for testing and development, small scale, then after the code was proven to be robust would I then port it over to Node.js.  If there is one lesson I'd like to pass on to aspiring and new programmers, it's this, use a language and development environment that allows you, the programmer, to jump into the code while it's running and follow each iteration, line by line, of code as it's be executed, basically debugging.  It is so easy to catch errors in logic that way. Right now I'm throwing darts at a dart board, guesses what I should be sending to the console for feedback to help me learn more about logical errors using Node.js, see learning the hard way.

-- - -- - -- - -- - -- - -- - Linear Path algorithm for any surface. - -- - -- - -- - -- - -- - --

In the blog entry above I go into detail explaining how I create a world. The important thing to take away from it is that every face of the world has information about all surrounding faces sharing vertices pairs.  In addition, all vertices have information regarding those faces that use it for their draw order, and all vertices have information regarding all vertices that are adjacent to them.

An example vertices and face object would look like the following:

Vertices[ 566 ] = { 
  ID: 566,
  x: -9.101827364,
  y: 6.112948791,
  z: 0.192387718,
  connectedFaceIDs: [ 90 , 93 , 94 , 1014 , 1015 , 1016 ], // clockwise order
  adjacentVertices: [ 64 , 65 , 567 , 568 , 299 , 298 ] // clockwise order
} 

Face[ 0 ] = {
  ID: 0,
  a: 0,
  b: 14150,
  c: 14149,
  sharedEdgeVertices: [ { a:14150 , b: 14149 } , { a:0 , b: 14150 } , { a:14149 , b:0 } ], // named 'cv' in previous blog post
  sharedEdgeFaceIDs: [ 1 , 645 , 646 ], // named 's' in previous blog post
  drawOrder: [ 1 , 0 , 2 ], // named 'l' in previous blog post
}

Turns out the algorithm is speedy for generating shapes of large sizes. :) My buddy who is a Solutions Architect told me I'm a one trick pony, HA!

5a738051dc4c1_Screenshotfrom2018-02-0115-00-08.thumb.png.b2adf356b6506f7d284a54c1b24abe8f.png

Anyways, this algorithm comes in handy because now if I want to identify a linear path along all faces of a surface, marked as a white line in the picture above, you can reduce the number of faces to be tested, during raycasting, to the number of faces the path travels across * 2.

To illustrate, imagine taking a triangular pizza slice which is made of two faces, back to back.  the tip of the pizza slice is touching the center of the shape you want to find a linear path along, the two outer points of the slice are protruding out from the surface of the shape some distance so as to entirely clear the shape.  When I select my starting and ending points for the linear path I also retrieve the face information those points fall on, respectively.  Then I raycaste between the sharedEdgeVertices, targeting the pizza slice.  If say a hit happens along the sharedEdgeVertices[ 2 ], then I know the next face to test for the subsequent raycaste is face ID 646, I also know that since the pizza slice comes in at sharedEdgeVertice[ 2 ], that is it's most likely going out at sharedEdgeVertices[ 1 ] or [ 0 ].  If not [ 1 ] then I know it's 99% likely going to be [ 0 ] and visa-versa.  Being able to identify a linear path along any surface was the subject of my first Adventure in Robust Coding.  Of course there are exceptions that need to be accounted for.  Such as, when the pizza slice straddles the edge of a face, or when the pizza slice exits a face at a vertices.

Sometimes though when I'm dealing with distances along the surface of a given shape where the pizza slice needs to be made up of more than one set of back to back faces, another problem can arise: I learned about the limitations of floating point numbers too, or at least that's what it appear to be to me.  I'm sure most of you are familiar with some variation of the infinite chocolate bar puzzle

chocolatePuzzle.jpg.d663364ab230157cc0927a12a849b168.jpg

So with floating point numbers I learned that you can have two faces share two vertices along one edge, raycaste at a point that is directly between the edges of two connecting faces, and occasionally, the raycaste will miss hitting either of the two faces.  I attribute this in large part because floating point numbers only capture an approximation of a point, not the exact point.  Much like in the infinite chocolate bar puzzle there exists a tiny gap along the slice equal in size to the removed piece, like wise, that tiny gap sometimes causes a miss for the raycaste.  If someone else understands this better please correct me.

-- - -- - -- - -- - -- - -- - Dynamic Path Finding using Nodes for any surface - -- - -- - -- - -- - -- - --

Now that I've got the linear path algorithm working in tip top shape, I use it in conjunction with Nodes to create the pathfinding algorithm.

Firstly I identify the locations for all nodes. I do this using a Class I created called Orientation Vector, I mention them in the blog post above.  When they're created, they have a position vector, a pointTo vector, and an axis vector.  The beauty of this class is that I can merge them, which averages their position, pointTo, and axis vectors, and it allows me to rotate them along any axis, and it allows me to move them any distance along the axis of their pointTo vector.

5a7389dbe00a6_Screenshotfrom2018-02-0114-58-57.thumb.png.b2e1647b01019680901b46c2f490eade.png

5a7389e66c2e2_Screenshotfrom2018-02-0114-58-18.thumb.png.1a68cd884e56cda9937bc6b7b156aac0.png

To create shoreline collision geometry, and node collision geometry, illustrated above, and node locations along shorelines, illustrated below, I utilise the Orientation Vector Class.

5a738d1a2479c_Screenshotfrom2018-02-0115-35-27.thumb.png.33c5aa6db67508c5be5782c0b2820183.png

Firstly, the water table for the world is set to an arbitrary value, right now it's 1.08, so if a vector for a given face falls below the table and one or two vertors are above the table then I know the face is a shoreline face.  Then I use simple Math to determine at what two points the face meets the water and create two OVectors, each pointing at each-other.  Then I rotate them along their y axis 90 and -90 degrees respectively so that they are now facing inland.  Since each face, which are shoreline faces, touch one another, there will be duplicate OVectors a each point along the shore.  However, each Ovector will have a pointTo vector relative to it's sister Ovector during creation.  I merge the paired Ovectors at each point along the shore, this averages their position, pointTo and axis.  I then move them inland a small distance.  The result is the blue arrows above. The blue arrows are the locations of three of the thousands of nodes created for a given world.  Each Node has information about the shoreline collision geometry, the node collision geometry ( the geometry connecting nodes ), and the Node to its left and the Node to its right.  Each face of collision geometry is given a Node ID to refer to.

So to create the path-finding algorithm. I first identify the linear path between the starting and ending points.  I then test each segment of the linear path for collision geometry. If I get a hit, I retrieve the Node ID.  This gives me the location for the Node associated for a given face of collision geometry.  I then travel left and right along connecting Nodes checking to see if a new Linear path to the end point is possible, if no immediate collision geometry is encountered, the process continues and is repeated as needed.  Subsequently, a list of points is established, marking the beginning, encountered Nodes and end of the line of travel.  The List is then trimmed by testing linear paths between every third point, if a valid path is found, the middle point is spliced.  Then all possible paths that have been trimmed are calculated for distance.  the shortest one wins.

Below is the code for the algorithm I currently use.  its my first attempt at using classes to create an algorithm.  Previously I just relied on elaborate arrays.

Spoiler

function PATHFINDER_findPath( TGm , Pt , nodes , o , e , testAssets ){

	e.currentProcesses ++;

	var sN , eN , Br=[] , pIdx=[];

	sN = new oNode( o.point1.clone() );
	sN.fID = o.id1;
	sN.pID = o.p1;
	sN.gID = o.g1;
	sN.ID = o.ID1;

	eN = new oNode( o.point2.clone() );
	eN.fID = o.id2;
	eN.pID = o.p2;
	eN.gID = o.g2;
	eN.ID = o.ID2;

	Br.push( new oBranch( sN , eN ) );
	Br[0].setDirection( true );

	var br , p , p1 , i , d , d2 , d3;
	var info = [], ID , IN, seQ = false;

	

	//// rewrite ////
	// Cycle through all branches
	for( var a=0; a<Br.length; a++ ){

		br = Br[ a ];

		// first do one raycaste to see if the starting nodes parent is in the way.

		// second check if path between branchTestStart and branchTestEnd
		nodeTOobject( br.start() , br.end() , o );

		//console.dir( o );
		// determine if path exists in pathIndex
		// possibly entertain idea of storing path information perminently.
		p = pathINDEX.getPath( br.startID() , br.endID() );

		if( p == false ){

			ID = PATHFINDER_firstCheck( br.start() , br.end() , Pt[ br.getParent( br.branchTestStart ) ] , o );
		 	if( ID > -1 ){
		 		IN = false;
		 	} else {
				p = new oPath( definePathLocal( TGm , o , false ) );
				info = PATHFINDER_checkPathValidity( p , Pt );
				ID = info[0];
				IN = info[1];
			}

		} else {
			ID = -1;
			IN = false;
		}	


		if( e.pathReadout ){ 
			if( ID > -1 ){
				console.log( 'BRANCH == startID: ' + br.startID() + ' endID: ' + br.endID() );
				console.log( 'BRANCH == A: ' + a + ' ID: ' + ID + ' IDa: ' + nodes[ ID ].IDa + ' IDb: ' + nodes[ ID ].IDb + ' IN: ' + IN );
			} else {
				console.log( 'BRANCH == startID: ' + br.startID() + ' endID: ' + br.endID() );
				console.log( 'BRANCH == A: ' + a + ' ID: ' + ID + ' IDa: -1 IDb: -1 IN: ' + IN );
			}
			
		}

		if( ID > -1 ){
			if( br.endID() == nodes[ ID ].IDb && br.getDirection() ){
				if( p != false ){
					if( e.pathReadout ){  console.log( 'over-riding to IDa' ); }
					ID = -1;
				}
			} else if( br.endID() == ID && !br.getDirection() ){
				if( p != false ){
					if( e.pathReadout ){  console.log( 'over-riding to IDb' ); }
					ID = nodes[ ID ].IDb;
					ID = -1;
				}
			}
		}

		if( ID == -1){
			if( e.pathReadout ){ console.log( 'valid path' ); }
			br.setPath( pIdx.length , br.branchTestStart );
			pIdx.push( p.clone() );
			br.setDistance( p.getDistance() , br.branchTestStart );
			br.setDirlog( br.getDirection() , br.branchTestStart );
		}

		if( e.pathReadout ){ console.log( ' ' ); }

		if( ID > -1 ){

			if( br.getNodeEncountered( ID ) && br.getNodeEncountered( nodes[ ID ].IDb ) ){

				// check to see if the next node in this direction is already apart of this nodes listing
				if( br.getDirection() ){
					if( br.getNodeEncountered( nodes[ ID ].IDa ) ){
						
						// continue this path in the true direction according to br.startID();
						if( br.startID() == -1 ){
							if( e.pathReadout ){ console.log( 'REMOVING BRANCH' ); }
							br.destroy();
							Br.splice( a , 1 );
						} else if( br.getNodeEncountered( nodes[ br.startID() ].IDa ) ){

							if( e.pathReadout ){ console.log( 'REMOVING BRANCH' ); }
							br.destroy();
							Br.splice( a , 1 );
						} else {

							br.insertNode( nodes[ nodes[ br.startID() ].IDa ].clone() , br.branchTestEnd );
							br.setNodeEncountered( nodes[ br.startID() ].IDa );

						}
						

					} else {
						// add IDa node to branch.
						br.insertNode( nodes[ nodes[ ID ].IDa ].clone() , br.branchTestEnd );
						br.setNodeEncountered( nodes[ ID ].IDa );
					}
				} else {

					if( br.getNodeEncountered( nodes[ nodes[ ID ].IDb ].IDb ) ){
						// destroy this path
						if( br.startID() == -1 ){
							if( e.pathReadout ){ console.log( 'REMOVING BRANCH' ); }
							br.destroy();
							Br.splice( a , 1 );
						} else if( br.getNodeEncountered( nodes[ nodes[ br.startID() ].IDb ].IDb ) ){
							if( e.pathReadout ){ console.log( 'REMOVING BRANCH' ); }
							br.destroy();
							Br.splice( a , 1 );
						} else {
							br.insertNode( nodes[ nodes[ nodes[ br.startID() ].IDb ].IDb ].clone() , br.branchTestEnd );
							br.setNodeEncountered( nodes[ nodes[ br.startID() ].IDb ].IDb );
						}						
						
					} else {
						// add IDb of IDb node to branch.
						br.insertNode( nodes[ nodes[ nodes[ ID ].IDb ].IDb ].clone() , br.branchTestEnd );
						br.setNodeEncountered( nodes[ nodes[ ID ].IDb ].IDb );
					}

				}

			} else if( br.getNodeEncountered( ID ) && !br.getNodeEncountered( nodes[ ID ].IDb ) ){

				if( br.getDirection() ){
					
					if( br.getNodeEncountered( nodes[ ID ].IDa ) ){
						// switch direction
						// add IDb node to branch
						br.setDirection( false );
						br.insertNode( nodes[ nodes[ ID ].IDb ].clone() , br.branchTestEnd );
						br.setNodeEncountered( nodes[ ID ].IDb );
					} else {
						// create new branch:
						// add IDa node to branch.
						// add IDb to another branch
						br.insertNode( nodes[ nodes[ ID ].IDa ].clone() , br.branchTestEnd );
						br.setNodeEncountered( nodes[ ID ].IDa );

						if( a < e.maxBranchSize /* arbitrary number used, will have to come up with idea */ ) { 
							i = Br.length;
							Br[ i ] = br.clone();
							Br[ i ].insertNode( nodes[ nodes[ ID ].IDb ].clone() , br.branchTestEnd );
							Br[ i ].setNodeEncountered( nodes[ ID ].IDb );
							Br[ i ].setDirection( false );
						}
					}

				} else {
					// add IDb node to branch
					br.insertNode( nodes[ nodes[ ID ].IDb ].clone() , br.branchTestEnd );
					br.setNodeEncountered( nodes[ ID ].IDb );
				}

			} else if( !br.getNodeEncountered( ID ) && br.getNodeEncountered( nodes[ ID ].IDb ) ){

				if( br.getDirection() ){
					// add ID node to branch
					br.insertNode( nodes[ ID ].clone() , br.branchTestEnd );
					br.setNodeEncountered( ID );
				} else {
						
					if( br.getNodeEncountered( nodes[ nodes[ ID ].IDb ].IDb ) ){
						// switch direction
						// add ID node to branch
						br.setDirection( true );
						br.insertNode( nodes[ ID ].clone() , br.branchTestEnd );
						br.setNodeEncountered( ID );
					} else {
						// create new branch:
						// add ID node to branch.
						// add IDb of IDb to another branch
						br.insertNode( nodes[ nodes[ nodes[ ID ].IDb ].IDb ].clone() , br.branchTestEnd );
						br.setNodeEncountered( nodes[ nodes[ ID ].IDb ].IDb );

						if( a < e.maxBranchSize /* arbitrary number used, will have to come up with idea */ ) { 
							i = Br.length;
							Br[ i ] = br.clone();
							Br[ i ].insertNode( nodes[ ID ].clone() , br.branchTestEnd );
							Br[ i ].setNodeEncountered( ID );
							Br[ i ].setDirection( true );
						}
					}
				}

			} else {
				// create new branch:
				// add ID node to branch.
				// add IDb to another branch
				br.setDirection( true );
				br.insertNode( nodes[ ID ].clone() , br.branchTestEnd );
				br.setNodeEncountered( ID );

				if( a < e.maxBranchSize /* arbitrary number used, will have to come up with idea */ ) { 
					i = Br.length;
					Br[ i ] = br.clone();
					Br[ i ].insertNode( nodes[ nodes[ ID ].IDb ].clone() , br.branchTestEnd );
					Br[ i ].setNodeEncountered( ID );
					Br[ i ].setDirection( false );
				}
			}

			a--;

		} else {

			// set the distance
			// increment both start and end
			if( p.getDistance() < 0 ){
				console.log( '--------------------------------------' );
				console.log( "--  something's up with p" );
				console.log( '--------------------------------------' );
				console.log( p );
			}
			br.setDistance( p.getDistance() , br.branchTestStart );
			br.branchTestStart ++;
			br.branchTestEnd ++;

			if( br.branchTestEnd <= br.getTreeLength()-1 ){
				//if( e.pathReadout ){ console.log( 'true, less then' ); }
				a--;
			} else {
				if( e.pathReadout ){ console.log( 'BRANCH COMPLETE' ); }
				br.pathFound = true;
				// Branch is complete.
			}
		}
	}
	//// rewrite ////


	if( e.pathReadout ){ console.log( 'STARTING TRIM' );}

	if( br.getTreeLength() > 2 ){

		// resets start and end.
		for( var a=0; a<Br.length; a++ ){
			Br[ a ].branchTestStart = 0;
			Br[ a ].branchTestEnd = 2;
			if( !Br[ a ].pathFound && e.pathReadout ){
				for( var ii = 0; ii<100; ii++ ){
					console.log( 'BRANCH NOT COMPLETE!!' );
				}
			}	
		}

		// trim branches
		for( var aa=0, A; aa<Br.length; aa++ ){
			br = Br[ aa ];
			br.setOldIndex();
			A=1;
		for( var a=0; a<A; a++ ){
			// 
			
			// first check if path between branchTestStart and branchTestEnd

			//if( br.getTreeLength() < 30 ){

				nodeTOobject( br.start() , br.end() , o );

				// determine if path exists in pathIndex
				// possibly entertain idea of storing path information perminently.
				p = pathINDEX.getPath( br.startID() , br.endID() );
				if( p == false ){

					ID = PATHFINDER_firstCheck( br.start() , br.end() , Pt[ br.getParent( br.branchTestStart ) ] , o );
				 	if( ID > -1 ){
				 		IN = false;
				 	} else {
						p = new oPath( definePathLocal( TGm , o , false ) );
						info = PATHFINDER_checkPathValidity( p , Pt );
						ID = info[0];
						IN = info[1];
					}

				} else {
					ID = -1;
				}

				if( e.pathReadout ){
					console.log( ' ' );
					if( ID > -1 ){
						console.log( 'TRIM == startID: ' + br.startID() + ' endID: ' + br.endID() );
						console.log( 'TRIM == A: ' + aa + ' ID: ' + ID + ' IDa: ' + nodes[ ID ].IDa + ' IDb: ' + nodes[ ID ].IDb + ' IN: ' + IN );
					} else {
						console.log( 'TRIM == startID: ' + br.startID() + ' endID: ' + br.endID() );
						console.log( 'TRIM == A: ' + aa + ' ID: ' + ID + ' IDa: -1 IDb: -1 IN: ' + IN );
					}
				}


				if( ID > -1 ){
					if( br.endID() == nodes[ ID ].IDb && br.getDirlog( br.branchTestStart ) && IN ){
						if( p != false ){
							if( e.pathReadout ){  console.log( 'over-riding to IDa' ); }
							ID = -1;
						}
					} else if( br.endID() == ID && !br.getDirlog( br.branchTestStart ) && IN ){
						if( p != false ){
							if( e.pathReadout ){  console.log( 'over-riding to IDb' ); }
							ID = -1;
						}
					}
				}

				if( ID == -1){
					// path is valid
					// splice previous node if distance is shorter
					d = p.getDistance();
					d2 = br.getDistanceBetweenTwoIndexes( br.branchTestStart , br.branchTestEnd-1 );

					if( e.pathReadout ){ console.log( 'TRIM == D: ' + d + ' D2: ' + d2 ); }

					if( d <= d2){
						// newly tested valid path is shorter
						if( br.branchTestEnd - br.branchTestStart > 2 ){
							br.spliceBetween( br.branchTestStart+1 , br.branchTestEnd-1 );
							//br.branchTestEnd = br.branchTestStart + 2;
						} else {
							br.splice( br.branchTestStart+1 );
						}
						br.setPath( pIdx.length , br.branchTestStart );
						br.setDistance( p.getDistance() , br.branchTestStart );
						pIdx.push( p.clone() );

					} else {
						// newly tested valid path is longer 
						if( e.pathReadout ){ console.log( 'IMPOSSIBLE ++' ); }
						//br.branchTestEnd ++;
					}
					
					br.branchTestStart ++;
					br.branchTestEnd = br.branchTestStart+2;

					if( br.branchTestEnd >= br.getTreeLength()-1 ){

						if( br.compareIndexes() ){
							// this cycle is done
							// allow a to incriment.
							if( e.pathReadout ){ console.log( '::: BRANCH FINISHED :::' ); }
							br.finished();
							seQ = true;

						} else {

							br.branchTestStart = 0;
							br.branchTestEnd = br.branchTestStart+2;
							aa--;
						}

					} else {
						A++;
					}

				} else {
					
					// obsticle encountered. create new path cycle only if nodes are unknown
					// otherwise increment.

					if( !br.getNodeEncountered( ID ) && !br.getNodeEncountered( nodes[ ID ].IDa ) && !br.getNodeEncountered( nodes[ ID ].IDb ) ){

						//nodeTOobject( br.start() , nodes[ ID ] , o );
						nodeTOobject( br.start() , br.end() , o );
						
						if( e.currentProcesses < e.maxDeepProcesses ){
							if( e.pathReadout ){ console.log( 'GOING DEEP ' + e.currentProcesses ); }
							if( e.pathReadout ){ console.log( 'TRIM == start: ' + br.startID() + ' end: ' +  ID ); }
							p = PATHFINDER_findPath( TGm , Pt , nodes , o , e , false );
						} else {
							p = false;
						}

						// may need to check on condition of p;
						if( p == false ){

							// next cycle

						} else {

							d = p.getDistance();
							d2 = br.getDistanceBetweenTwoIndexes( br.branchTestStart , br.branchTestEnd-1 );
							if( e.pathReadout ){ console.log( 'TRIM == D: ' + d + ' D2: ' + d2 ); }

							if( d <= d2){
								// newly tested valid path is shorter
								if( br.branchTestEnd - br.branchTestStart > 2 ){
									br.spliceBetween( br.branchTestStart+1 , br.branchTestEnd-1 );
									//br.branchTestEnd = br.branchTestStart + 1;
								} else {
									br.splice( br.branchTestStart+1 );
								}
								br.setPath( pIdx.length , br.branchTestStart );
								br.setDistance( p.getDistance() , br.branchTestStart );
								pIdx.push( p.clone() );

							} else {
								// newly tested valid path is longer
								if( e.pathReadout ){ console.log( 'IMPOSSIBLE' ); }
							}
						}
					} 
					
					br.branchTestStart ++;
					br.branchTestEnd = br.branchTestStart+2;

					if( br.branchTestEnd >= br.getTreeLength()-1 ){

						if( br.compareIndexes() ){
							// this cycle is done
							// allow a to incriment.
							if( e.pathReadout ){ console.log( '::: BRANCH FINISHED :::' ); }
							br.finished();
							seQ = true;

						} else {

							br.branchTestStart = 0;
							br.branchTestEnd = br.branchTestStart+2;
							aa--;
						}

					} else {
						A++;
					}
				}
			//}
		}
		}
	}

	if( e.pathReadout ){ console.log( Br.length ); }
	

	for( var a=0; a<Br.length; a++ ){
		if( Br[ a ].complete == false ){
			Br[ a ].finished();
		}
	}

	if( e.pathReadout ){ console.log( 'PATH COMPLETE' ); }
	
	// calculate all distances for branches
	if( Br.length > 0 ){

		d = 100000;
		d1 = 0;

		for( var a=0; a<Br.length; a++ ){
			if( Br[ a ].totalDistance < d ){
				d = Br[ a ].totalDistance;
				d1 = a;
			}
		}

		p = new oPath( [] );
		for( var a=0, aa=Br[ d1 ].path.length; a<aa; a++ ){
			d = Br[ d1 ].path[ a ];
			p.concat( pIdx[ d ] );
		}

		if( e.pathReadout ){ console.dir( 'BRANCH ID:: ' + d1 ); }
		if( e.pathReadout ){ console.dir( Br[ d1 ].index ); }
		if( e.pathReadout ){ console.dir( p ); }
		if( e.pathReadout ){ console.dir( p.path.length ); }

		e.currentProcesses --;
		return p;

	} else {

		e.currentProcesses --;
		return false;
	}
}

 

I plan on improving the the process mentioned above by keeping track of distance as each path spreads out from it's starting location.  Only the path which is shortest in distance will go through its next iteration.  With this method, once a path to the end is found, I can bet it will be shortest, so I won't need to compute all possible paths like I am now.

5a7391df0b55f_Screenshotfrom2018-02-0116-16-30.thumb.png.93d104534482f95ccfcb0dc39c2fb1bf.png

The challenge I've been facing for the past two months is sometimes the Nodes end up in the water, The picture above shows a shoreline where the distance the OVectors travel would place them in the water.  Once a node is in the water, it allows the AI to move to it, then there is no shoreline collision geometry for it to encounter, which would keep it on land, and so the AI just walks into the ocean.  Big Booo!  I've been writing variations of the same function to correct the location of the geometry shown below in Red and Yellow below.

5a7393533ae6b_Screenshotfrom2018-02-0116-22-49.thumb.png.7c2af2aae94984708b3bdae2e36ce644.png

But what a long process.  I've rewritten this function time and time again.  I want it to be, well as the title of this Blog states, Robust, but it's slow going.  As of today's date, it's not Robust, and the optimised path-finding algorithm hasn't been written either. 

I'll be posting updates in this blog entry as I make progress towards my goal.  I'll also make mention what I achieve for shortest, long time for pathfinding.  Hopefully it'll be below 250 ms.

-- - -- - -- - -- - -- - -- - short term goals for the game - -- - -- - -- - -- - -- - --

Badly... SO BADLY I want to be focusing on game content, that's all I've been thinking about.  Argh, But this all has to get wrapped up before I can.  I got ahead of myself, I'm guilty of being too eager.  But there is no sense building game content on top of an engine which is prone to errors. 
My immediate goals for the engine are as follows:

// TO DO's //
// Dec 26th 2017 //
/*
*	<< IN PROGRESS >>	-update path node geometry so no errors occur 
*				-improve path finding alg with new technique
*				-improve client AI display -only one geometry for high detail, and one for tetrahedron.
*				-create ability to select many AI at the same time by drawing a rectangle by holding mouse button.
*				-create animation server to recieve a path and process animation, and test out in client with updates.
*				-re-write geometry merging function so that the client vertices and faces have a connected Target ID
*				-incorporate dynamic asset functionality into client.
*				-create a farm and begin writing AI.
*				-program model clusters
* 				-sychronize server and client AI.  Test how many AI and how quickly AI can be updated.  Determine rough estimate of number of players the server can support.
*
*/

see the third last one!  That's the one, oh what a special day that'll be.

I've created a Project page,

please check it out.  It gives my best description to date of what the game is going to be about.  Originally I was going to name it 'Seed', a family member made the logo I use as my avatar and came up with the name back in 2014. The project is no longer going to be called Seed, it's instead going to be called Unirule.

[ edit: 02/02/18 
 Some new screen shots to show off.  All the new models were created by Brandross. 
5a753c793e094_Screenshotfrom2018-02-0222-30-55.thumb.png.dec7e089b56972d37f46234dde73783b.png

5a753cc02f7b4_Screenshotfrom2018-02-0222-30-24.thumb.png.5d94565aad026dd8f0bb157e7b00b073.png

There are now three earth materials, clay, stone and marble.  There are also many types of animals and more tree types. ]

Thanks for reading and if you've got anything to comment on I welcome it all.

Awoken



11 Comments


Recommended Comments

Sounds quite ambitious, but should still be achievable! Looking forward to seeing your progress, this sounds like it will be fun to play!

 

Hopefully it can still stand out from Seed! :)

Share this comment


Link to comment

Thanks jbadams

If there is one advantage this project has right now it's that it doesn't have to meet any deadlines.  Over the years there have been many times that I'll be out for a walk or whatever, and I'll have novel insights on how to approach a problem, or ideas on how the game should be played.  The idea for this game is getting better with age, like a fine wine, it's being refined.  I think if I had had the ability to produce this game years ago it would not be the same game it is today, it wouldn't have been as good.

Share this comment


Link to comment

Sounds good, take your time with it and make sure it's something you're happy with. Hopefully it will turn out well as something you're proud of. :)

Share this comment


Link to comment

Just put the finishing touches on updating the path node geometry so no errors occur.
There was a lot more than just logical errors.  In fact, once I took the time to go through the code step by step with drawings I discovered that I had used the wrong variable during the class deceleration, and I used very confusing labelling.  the draw order and therefor raycaste order is counter clockwise going from a to b to c, the adjoining Node order is clockwise going form a to b, a to b.  And I used two variables within the code named a and b for the node positions.  :S, no wonder I was confusing myself.  But spent the past couple nights really pouring through it and it's all good now.

Here are some pics:
5a84b5ad605b1_Screenshotfrom2018-02-1416-17-53.thumb.png.46d092198346f65e6b9370bc33f63b21.png
5a84b18c0d371_Screenshotfrom2018-02-1415-32-45.thumb.png.d41fcce50800b79be6d6f91c4e4b9bf8.png

The yellow face and red face are examples of where the inverse collision geometry intersected one another.  So I just clipped them, added a node at their intersection and then updated surrounding node geometry.  The shorter faces are shoreline geometry.  The major accomplishment is having situations where a portion of land will cut itself off from the major continent. So the nodes need to loop-out independent of the main node loops.

5a84b1a4e8c0b_Screenshotfrom2018-02-1415-29-53.thumb.png.ca5b322777837ff47fcfb618852a213b.png

5a84b1b081e07_Screenshotfrom2018-02-1415-30-19.thumb.png.09f391d6825df725ba658818c9f75556.png

In the two photos above you can see what I mean, if you look very carefully. In the top photo it's the very bottom yellow face,  On the lower right portion of the bottom photo you'll see a yellow face end, then a bit to it's right a yellow face and red face joined.  All faces are on the same portion of land, so I needed to modify the geometry so no inverse geometry ends up in the water.  I don't know if any of that makes sense, but I'm sure you get the gist of what I'm trying to do.  Both photos are of the same area on the globe, just different angle.

Anyways, Collision geometry DONE!
Now I can rewrite the path-finding alg.  Wa-Woooo!

I'm also going to re-order the list a bit.  Some of items are enjoyable to code and seeing progress is incredibly fast and impressive for me.  Other bits of code are labour intensive and require major attention to detail ( like this collision geometry, 3 months, ARGH! ).  I want to get Simulin simulated as fast a possible and focus on gaming elements.  I can then add some of the To-Do's as time goes on and when there is really a need.  I am a perfectionist and what things pristine, But I also really want to program the economic simulation and gaming portion of this project.  After all this is what all my efforts over the past 4 years have been all about.  

New To Do list order

// TO DO's //
// Dec 26th 2017 //
/*
*	<<  COMPLETE  >>	-update path node geometry so no errors occur 
*	<< IN PROGRESS >>	-improve path finding alg with new technique
*
*				-re-write geometry merging function so that the client vertices and faces have a connected Target ID
*				-incorporate dynamic assets functionality	
*				-create a farm and begin writing AI.
*
*				-improve client AI display -only one geometry for high detail, and one for tetrahedron.
*				-create ability to select many AI at the same time by drawing a rectangle by holding mouse button.
*				-create animation server to recieve a path and process animation, and test out in client with updates.
* 				-sycronize server and client AI.  Test how many AI and how quickly AI can be updated.  Determine rough estimate of number of players the server can support.
*				-program model clusters
*
*/

Thanks for reading, more updates on the next 4 To-Do's to come!

Edited by Awoken

Share this comment


Link to comment
Awoken

Posted (edited)

The other week I completely changed the path finding algorithm and I'm pleased to say it is running much more efficiently and way faster.  I've also added a new camera rotation feature which I think looks good.  But only at two distances from the planet, otherwise it is off.  If anyone can help me out with the camera problem it would be much appreciated.

I've linked a video demonstrating the path finding in real-time.  The camera movement is a little jerky, apologies. The world is colored to make it easier for me to identify homogeneous land masses. 

It is still buggy.  Problem is the bugs are unique and only pop up once and awhile.  So sorting through them all is going to be tough.

In the video, the longest processed path was 500ms.  As stated before the goal is to get to 250ms anywhere on the planet.

Here is a screenshot of the world in the video
5a9abc0ae0631_Screenshotfrom2018-03-0308-30-48.thumb.png.949b87089f9abd1dadf8f34272ac52ee.png

The small blue island in the middle is where the video takes place. 
5a9abc311788b_Screenshotfrom2018-03-0308-18-20.thumb.png.8530914b0b37c954d42338e8ea6e69fa.png

I've got my work cut out for me if I want to get to 250ms on a land mass as complicated and intricate as the one above.

That being said though.  I've already begun thinking about how I can 'trim' the algorithm to make it faster yet.  I've also come up with some other approaches to path-finding.  the problem now is, I have come up with ways I can find a path in a very short amount of time, but it may not necessary be the shortest path.  

Much work to do...
Thanks for reading.
 

Edited by Awoken

Share this comment


Link to comment

@Awoken you mentioned missing Chrome as a dev environment due to lack of debugging in node.js in your first entry. Not sure if you are aware but you can do real-time debugging of node.js from VS Code.

Share this comment


Link to comment
7 hours ago, y2kiah said:

@Awoken you mentioned missing Chrome as a dev environment due to lack of debugging in node.js in your first entry. Not sure if you are aware but you can do real-time debugging of node.js from VS Code.

Much appreciated! I'm going to be looking into this one for sure.

Share this comment


Link to comment
Awoken

Posted (edited)

@y2kiah Visual Code is my go to!  Thank you.

More about pathfinding progress.
Consolidated the code and now all simulin that are added to the world are given a path that is dynamic, as in the AI will stick to the land now.  So no more AI walking into the oceans or rivers.  :D  That being said though there are still many types of errors that are popping up.  Some are node related, some are time related.  If a path leads an AI into the water it's trimmed and a new path is generated.  If the time to process a path exceeds a certain limit it is also trimmed and a new one processed.  So now I can start to determine the number of error paths per 1000 paths generated and work on reducing the ratio until it's almost ziltch.  

Here's a screen shot showing the AI not walking into the water.
5a9f1a0364ec6_Screenshotfrom2018-03-0616-39-29.thumb.png.bdc0ddbf15f96401a39097a4b386928a.png To be continued!

[ edit: 03/10/18, just did a time and error report.  Starting stats are:
Successful Paths: 1000,
into Water Paths: 14,
Time Outs: 118, @ over 500 milliseconds.
Time Per Path : 79.31 milliseconds. 

That means my error ratio is 1.32 for every 10 paths.  1.32:10. ]
 

Edited by Awoken

Share this comment


Link to comment
Awoken

Posted (edited)

Lastest build results:

successes:1000
intoWater:2
timeOuts:39
noPath:0
time:33206
timePerPath:33.206
total:1041

So not bad.  
I had a realisation of how I'm going to approach player movement anyways.  The player will only see a portion of the world that they have discovered, and the game will only allow them to move so far from their current position anyways.  Plus most of the time the simulated people will be walking in straight lines along the worlds surface, not always weaving in and around rivers.

Final note: In the future I'm going to incorporate the ability for players to create roads, or stone trails, and these too will be a connection of nodes that the player can define.  Once I incorporate these I think I'll be able to get much closer to my intended objective, especially since the player will be doing all the path-finding.

Now I'm going to focus my attention on incorporating dynamic assets into this build.  Something I hatched out in a previous build and am looking forward to it, should be swift, nothing new.  Then the final pieces de resistance will be having the simulated people interact within the dynamic assets.   I'm so excited, almost there!

Thanks for reading.

[ edit: April 17th,
geometry:1
noPath:0
success:1000
time:28947
timeOut:26
timePerPath:28.947
total:1027 ]

[ edit: April 18th,
geometry:0
noPath:0
success:1000
time:23024
timeOut:24
timePerPath:23.024
total:1024

-- I just flushed out a bug that has been creeping in my code since the first robust challenge back two years ago.  It didn't show it's ugly little self until just recently.  Another variant of the missing chocolate piece analogy mentioned above.  Again it has to do with floating point numbers. But alas it's been discovered and with two short lines of code so much headache is gone.
-- I think my new goal will be to achieve under 20 milliseconds on average, so 23 is pretty darn close.  I've been thinking of even better ways to improve my path finding alg, and the latest times are a testament to my latest modifications.  I think this weekend I'm going to rip out some new code for the path finding.  I'm thinking it's going to be way faster. 
-- I've been spending all this time cleaning my code and logic.  As a result I've flushed out a lot of little problems  that individual don't cause noticeable performance issues, but when taken all together are a major bothersome.]

[ edit: April 28th,
geometry:0
noPath:0
success:2000
time:41480
timeOut:56
timePerPath:20.74
total:2056 ]

Edited by Awoken

Share this comment


Link to comment
Awoken

Posted (edited)

The other day I had a eureka moment.  I kind of stumbled into it.  I only starred at the beginnings of what it could have been for so long, then finally saw it for complete potential.  

Latest build times

geometry:6
longPath:335
noPath:2
success:1000
time:3524
timeOut:0
timePerPath: 3.524
total:1008

I've dropped the time to 3.524 milliseconds per path and those figures are consistent.  The distances that can be covered are long too.  Extremely long.  In fact with a few tweaks I can do any two points on the planet so long as the land mass is homogeneous. 
I expect the total time-per-path to increase slightly, perhaps to around 5 or 6 milliseconds as I clean up the output of the algorithm so that the path is indeed the shortest possible.  Right now the algorithm spits out a short short path, sometimes shortest path.  But not always. 

The new Algorithm and technique I'm using is extremely simple, short and fast.  I'll be dedicating a future blog post explaining the technique I used.

I may just in fact meet my goal for this Robust Challenge.  Which would be incredible since I thought for the longest time it was just not possible.  That would mean updating the paths of ~200 AI per second!  

[ edit: Oh one more thing, I've ironed out ALL build errors that had built up and caused me troubles.  So clean, I love it. ]

Edited by Awoken

Share this comment


Link to comment

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
  • Advertisement
  • Blog Entries

  • Similar Content

    • By slayemin
      What exactly is an Octree? If you're completely unfamiliar with them, I recommend reading the Wikipedia article (read time: ~5 minutes). This is a sufficient description of what it is but is barely enough to give any ideas on what it's used for and how to actually implement one. In this article, I will do my best to take you through the steps necessary to create an octree data structure through conceptual explanations, pictures, and code, and show you the considerations to be made at each step along the way. I don't expect this article to be the authoritative way to do octrees, but it should give you a really good start and act as a good reference.
       
      Assumptions
      Before we dive in, I'm going to be making a few assumptions about you as a reader:
      You are very comfortable with programming in a C-syntax-style language (I will be using C# with XNA). You have programmed some sort of tree-like data structure in the past, such as a binary search tree and are familiar with recursion and its strengths and pitfalls. You know how to do collision detection with bounding rectangles, bounding spheres, and bounding frustums. You have a good grasp of common data structures (arrays, lists, etc) and understand Big-O notation (you can also learn about Big-O in this GDnet article). You have a development environment project which contains spatial objects which need collision tests.  
      Setting the stage
      Let's suppose that we are building a very large game world which can contain thousands of physical objects of various types, shapes and sizes, some of which must collide with each other. Each frame we need to find out which objects are intersecting with each other and have some way to handle that intersection. How do we do it without killing performance?
       
      Brute force collision detection
      The simplest method is to just compare each object against every other object in the world. Typically, you can do this with two for loops. The code would look something like this:
      foreach(gameObject myObject in ObjList) { foreach(gameObject otherObject in ObjList) { if(myObject == otherObject) continue; //avoid self collision check if(myObject.CollidesWith(otherObject)) { //code to handle the collision } } }  
      Conceptually, this is what we're doing in our picture:
      Each red line is an expensive CPU test for intersection. Naturally, you should feel horrified by this code because it is going to run in O(N^2) time. If you have 10,000 objects, then you're going to be doing 100,000,000 collision checks (hundred million). I don't care how fast your CPU is or how well you've tuned your math code, this code would reduce your computer to a sluggish crawl. If you're running your game at 60 frames per second, you're looking at 60 * 100 million calculations per second! It's nuts. It's insane. It's crazy. Let's not do this if we can avoid it, at least not with a large set of objects. This would only be acceptable if we're only checking, say, 10 items against each other (100 checks is palatable). If you know in advance that your game is only going to have a very small number of objects (i.e., Asteroids), you can probably get away with using this brute force method for collision detection and ignore octrees altogether. If/when you start noticing performance problems due to too many collision checks per frame, consider some simple targeted optimizations:
      How much computation does your current collision routine take? Do you have a square root hidden away in there (ie, a distance check)? Are you doing a granular collision check (pixel vs pixel, triangle vs triangle, etc)? One common technique is to perform a rough, coarse check for collision before testing for a granular collision check. You can give your objects an enclosing bounding rectangle or bounding sphere and test for intersection with these before testing against a granular check which may involve a lot more math and computation time. Can you get away with calculating fewer collision checks? If your game runs at 60 frames per second, could you skip a few frames? If you know certain objects behave deterministically, can you "solve" for when they will collide ahead of time (ie, pool ball vs. side of pool table). Can you reduce the number of objects which need to be checked for collisions? A technique for this would be to separate objects into several lists. One list could be your "stationary" objects list. They never have to test for collision against each other. The other list could be your "moving" objects, which need to be tested against all other moving objects and against all stationary objects. This could reduce the number of necessary collision tests to reach an acceptable performance level. Can you get away with removing some object collision tests when performance becomes an issue? For example, a smoke particle could interact with a surface object and follow its contours to create a nice aesthetic effect, but it wouldn't break gameplay if you hit a predefined limit for collision checks and decided to stop ignoring smoke particles for collision. Ignoring essential game object movement would certainly break gameplay though (i.e., player bullets stop intersecting with monsters). So, perhaps maintaining a priority list of collision checks to compute would help. First, you handle the high priority collision tests, and if you're not at your threshold, you can handle lower priority collision tests. When the threshold is reached, you dump the rest of the items in the priority list or defer them for testing at a later time.  Can you use a faster but still simplistic method for collision detection to get away from an O(N^2) runtime? If you eliminate the objects you've already checked for collisions against, you can reduce the runtime to O(N(N+1)/2), which is much faster and still easy to implement. (technically, it's still O(N^2)) In terms of software engineering, you may end up spending more time than it's worth fine-tuning a bad algorithm & data structure choice to squeeze out a few more ounces of performance. The cost vs. benefit ratio becomes increasingly unfavourable and it becomes time to choose a better data structure to handle collision detection. Spatial partitioning algorithms are the proverbial nuke to solving the runtime problem for collision detection. At a small upfront cost to performance, they'll reduce your collision detection tests to logarithmic runtime. The upfront costs of development time and CPU overhead are easily outweighed by the scalability benefits and performance gains.  
      Conceptual background on spatial partitioning
      Let's take a step back and look at spatial partitioning and trees in general before diving into Octrees. If we don't understand the conceptual idea, we have no hope of implementing it by sweating over the code. Looking at the brute force implementation above, we're essentially taking every object in the game and comparing their positions against all other objects in the game to see if any are touching. All of these objects are contained spatially within our game world. Well, if we create an enclosing box around our game world and figure out which objects are contained within this enclosing box, then we've got a region of space with a list of contained objects within it. In this case, it would contain every object in the game.
      We can notice that if we have an object on one corner of the world and another object way on the other side, we don't really need to, or want to, calculate a collision check against them every frame. It'd be a waste of precious CPU time.
      So, let's try something interesting! If we divide our world exactly in half, we can create three separate lists of objects. The first list of objects, List A, contains all objects on the left half of the world. The second list, List B, contains objects on the right half of the world. Some objects may touch the dividing line such that they're on each side of the line, so we'll create a third list, List C, for these objects.
      We can notice that with each subdivision, we're spatially reducing the world in half and collecting a list of objects in that resulting half. We can elegantly create a binary search tree to contain these lists. Conceptually, this tree should look something like so:
      In terms of pseudo code, the tree data structure would look something like this:
       
      public class BinaryTree { //This is a list of all of the objects contained within this node of the tree private List m_objectList; //These are pointers to the left and right child nodes in the tree private BinaryTree m_left, m_right; //This is a pointer to the parent object (for upward tree traversal). private BinaryTree m_parent; } We know that all objects in List A will never intersect with any objects in List B, so we can almost eliminate half of the number of collision checks. We've still got the objects in List C which could touch objects in either list A or B, so we'll have to check all objects in List C against all objects in Lists A, B & C. If we continue to sub-divide the world into smaller and smaller parts, we can further reduce the number of necessary collision checks by half each time. This is the general idea behind spatial partitioning. There are many ways to subdivide a world into a tree-like data structure (BSP trees, Quad Trees, K-D trees, OctTrees, etc).
      Now, by default, we're just assuming that the best division is a cut in half, right down the middle, since we're assuming that all of our objects will be somewhat uniformly distributed throughout the world. It's not a bad assumption to make, but some spatial division algorithms may decide to make a cut such that each side has an equal amount of objects (a weighted cut) so that the resulting tree is more balanced. However, what happens if all of these objects move around? In order to maintain a nearly even division, you'd have to either shift the splitting plane or completely rebuild the tree each frame. It'd be a bit of a mess with a lot of complexity. So, for my implementation of a spatial partitioning tree, I decided to cut right down the middle every time. As a result, some trees may end up being a bit more sparse than others, but that's okay -- it doesn't cost much.
       
      To subdivide or not to subdivide? That is the question.
      Let's assume that we have a somewhat sparse region with only a few objects. We could continue subdividing our space until we've found the smallest possible enclosing area for that object. But is that really necessary? Let's remember that the whole reason we're creating a tree is to reduce the number of collision checks we need to perform each frame -- not to create a perfectly enclosing region of space for every object. Here are the rules I use for deciding whether to subdivide or not:
      If we create a subdivision which only contains one object, we can stop subdividing even though we could keep dividing further. This rule will become an important part of the criteria for what defines a "leaf node" in our octree. The other important criteria is to set a minimum size for a region. If you have an extremely small object which is nanometers in size (or, god forbid, you have a bug and forgot to initialize an object size!), you're going to keep subdividing to the point where you potentially overflow your call stack. For my own implementation, I defined the smallest containing region to be a 1x1x1 cube. Any objects in this teeny cube will just have to be run with the O(N^2) brute force collision test (I don't anticipate many objects anyways!). If a containing region doesn't contain any objects, we shouldn't try to include it in the tree. We can take our subdivision by half one step further and divide the 2D world space into quadrants. The logic is essentially the same, but now we're testing for collision with four squares instead of two rectangles. We can continue subdividing each square until our rules for termination are met. The representation of the world space and corresponding data structure for a quadtree would look something like this:
      If the quadtree subdivision and data structure makes sense, then an octree should be pretty straightforward as well. We're just adding a third dimension, using bounding cubes instead of bounding squares, and have eight possible child nodes instead of four. Some of you might wonder what should happen if you have a game world with non-cubic dimensions, say 200x300x400. You can still use an octree with cubic dimensions -- some child nodes will just end up empty if the game world doesn't have anything there. Obviously, you'll want to set the dimensions of your octree to at least the largest dimension of your game world.
      Octree Construction
      So, as you've read, an octree is a special type of subdividing tree commonly used for objects in 3D space (or anything with 3 dimensions). Our enclosing region is going to be a three dimensional rectangle (commonly a cube). We will then apply our subdivision logic above, and cut our enclosing region into eight smaller rectangles. If a game object completely fits within one of these subdivided regions, we'll push it down the tree into that node's containing region. We'll then recursively continue subdividing each resulting region until one of our breaking conditions is met. In the end, we should expect to have a nice tree-like data structure.
      My implementation of the octree can contain objects which have either a bounding sphere and/or a bounding rectangle. You'll see a lot of code I use to determine which is being used.
      In terms of our Octree class data structure, I decided to do the following for each tree:
      Each node has a bounding region which defines the enclosing region Each node has a reference to the parent node Contains an array of eight child nodes (use arrays for code simplicity and cache performance) Contains a list of objects contained within the current enclosing region I use a byte-sized bitmask for figuring out which child nodes are actively being used (the optimization benefits at the cost of additional complexity is somewhat debatable) I use a few static variables to indicate the state of the tree Here is the code for my Octree class outline:
      public class OctTree { BoundingBox m_region; List m_objects; /// /// These are items which we're waiting to insert into the data structure. /// We want to accrue as many objects in here as possible before we inject them into the tree. This is slightly more cache friendly. /// static Queue m_pendingInsertion = new Queue(); /// /// These are all of the possible child octants for this node in the tree. /// OctTree[] m_childNode = new OctTree[8]; /// /// This is a bitmask indicating which child nodes are actively being used. /// It adds slightly more complexity, but is faster for performance since there is only one comparison instead of 8. /// byte m_activeNodes = 0; /// /// The minumum size for enclosing region is a 1x1x1 cube. /// const int MIN_SIZE = 1; /// /// this is how many frames we'll wait before deleting an empty tree branch. Note that this is not a constant. The maximum lifespan doubles /// every time a node is reused, until it hits a hard coded constant of 64 /// int m_maxLifespan = 8; // int m_curLife = -1; //this is a countdown time showing how much time we have left to live /// /// A reference to the parent node is nice to have when we're trying to do a tree update. /// OctTree _parent; static bool m_treeReady = false; //the tree has a few objects which need to be inserted before it is complete static bool m_treeBuilt = false; //there is no pre-existing tree yet. }  
      Initializing the enclosing region
      The first step in building an octree is to define the enclosing region for the entire tree. This will be the bounding box for the root node of the tree which initially contains all objects in the game world. Before we go about initializing this bounding volume, we have a few design decisions we need to make:
      What should happen if an object moves outside of the bounding volume of the root node? Do we want to resize the entire octree so that all objects are enclosed? If we do, we'll have to completely rebuild the octree from scratch. If we don't, we'll need to have some way to either handle out of bounds objects or ensure that objects never go out of bounds. How do we want to create the enclosing region for our octree? Do we want to use a preset dimension, such as a 200x400x200 (X,Y,Z) rectangle? Or do we want to use a cubic dimension which is a power of 2? What should be the smallest allowable enclosing region which cannot be subdivided? Personally, I decided that I would use a cubic enclosing region with dimensions which are a power of 2, and sufficiently large to completely enclose my world. The smallest allowable cube is a 1x1x1 unit region. With this, I know that I can always cleanly subdivide my world and get integer numbers (even though the Vector3 uses floats). I also decided that my enclosing region would enclose the entire game world, so if an object leaves this region, it should be quietly destroyed. At the smallest octant, I will have to run a brute force collision check against all other objects, but I don't realistically expect more than 3 objects to occupy that small of an area at a time, so the performance costs of O(N^2) are completely acceptable. So, I normally just initialize my octree with a constructor which takes a region size and a list of items to insert into the tree. I feel it's barely worth showing this part of the code since it's so elementary, but I'll include it for completeness. Here are my constructors:
      /*Note: we want to avoid allocating memory for as long as possible since there can be lots of nodes.*/ /// /// Creates an oct tree which encloses the given region and contains the provided objects. /// ///The bounding region for the oct tree. ///The list of objects contained within the bounding region private OctTree(BoundingBox region, List objList) { m_region = region; m_objects = objList; m_curLife = -1; } public OctTree() { m_objects = new List(); m_region = new BoundingBox(Vector3.Zero, Vector3.Zero); m_curLife = -1; } /// /// Creates an octTree with a suggestion for the bounding region containing the items. /// ///The suggested dimensions for the bounding region. ///Note: if items are outside this region, the region will be automatically resized. public OctTree(BoundingBox region) { m_region = region; m_objects = new List(); m_curLife = -1; }  
      Building an initial octree
      I'm a big fan of lazy initialization. I try to avoid allocating memory or doing work until I absolutely have to. In the case of my octree, I avoid building the data structure as long as possible. We'll accept a user's request to insert an object into the data structure, but we don't actually have to build the tree until someone runs a query against it.
      What does this do for us? Well, let's assume that the process of constructing and traversing our tree is somewhat computationally expensive. If a user wants to give us 1,000 objects to insert into the tree, does it make sense to recompute every subsequent enclosing area a thousand times? Or, can we save some time and do a bulk blast? I created a "pending" queue of items and a few flags to indicate the build state of the tree. All of the inserted items get put into the pending queue and when a query is made, those pending requests get flushed and injected into the tree. This is especially handy during a game loading sequence since you'll most likely be inserting thousands of objects at once. After the game world has been loaded, the number of objects injected into the tree is orders of magnitude fewer. My lazy initialization routine is contained within my UpdateTree() method. It checks to see if the tree has been built, and builds the data structure if it doesn't exist and has pending objects.
      /// /// Processes all pending insertions by inserting them into the tree. /// /// Consider deprecating this? private void UpdateTree() //complete & tested { if (!m_treeBuilt) { while (m_pendingInsertion.Count != 0) m_objects.Add(m_pendingInsertion.Dequeue()); BuildTree(); } else { while (m_pendingInsertion.Count != 0) Insert(m_pendingInsertion.Dequeue()); } m_treeReady = true; } As for building the tree itself, this can be done recursively. So for each recursive iteration, I start off with a list of objects contained within the bounding region. I check my termination rules, and if we pass, we create eight subdivided bounding areas which are perfectly contained within our enclosed region. Then, I go through every object in my given list and test to see if any of them will fit perfectly within any of my octants. If they do fit, I insert them into a corresponding list for that octant. At the very end, I check the counts on my corresponding octant lists and create new octrees and attach them to our current node, and mark my bitmask to indicate that those child octants are actively being used. All of the leftover objects have been pushed down to us from our parent, but can't be pushed down to any children, so logically, this must be the smallest octant which can contain the object.
      /// /// Naively builds an oct tree from scratch. /// private void BuildTree() //complete & tested { //terminate the recursion if we're a leaf node if (m_objects.Count <= 1) return; Vector3 dimensions = m_region.Max - m_region.Min; if (dimensions == Vector3.Zero) { FindEnclosingCube(); dimensions = m_region.Max - m_region.Min; } //Check to see if the dimensions of the box are greater than the minimum dimensions if (dimensions.X <= MIN_SIZE && dimensions.Y <= MIN_SIZE && dimensions.Z <= MIN_SIZE) { return; } Vector3 half = dimensions / 2.0f; Vector3 center = m_region.Min + half; //Create subdivided regions for each octant BoundingBox[] octant = new BoundingBox[8]; octant[0] = new BoundingBox(m_region.Min, center); octant[1] = new BoundingBox(new Vector3(center.X, m_region.Min.Y, m_region.Min.Z), new Vector3(m_region.Max.X, center.Y, center.Z)); octant[2] = new BoundingBox(new Vector3(center.X, m_region.Min.Y, center.Z), new Vector3(m_region.Max.X, center.Y, m_region.Max.Z)); octant[3] = new BoundingBox(new Vector3(m_region.Min.X, m_region.Min.Y, center.Z), new Vector3(center.X, center.Y, m_region.Max.Z)); octant[4] = new BoundingBox(new Vector3(m_region.Min.X, center.Y, m_region.Min.Z), new Vector3(center.X, m_region.Max.Y, center.Z)); octant[5] = new BoundingBox(new Vector3(center.X, center.Y, m_region.Min.Z), new Vector3(m_region.Max.X, m_region.Max.Y, center.Z)); octant[6] = new BoundingBox(center, m_region.Max); octant[7] = new BoundingBox(new Vector3(m_region.Min.X, center.Y, center.Z), new Vector3(center.X, m_region.Max.Y, m_region.Max.Z)); //This will contain all of our objects which fit within each respective octant. List[] octList = new List[8]; for (int i = 0; i < 8; i++) octList = new List(); //this list contains all of the objects which got moved down the tree and can be delisted from this node. List delist = new List(); foreach (Physical obj in m_objects) { if (obj.BoundingBox.Min != obj.BoundingBox.Max) { for (int a = 0; a < 8; a++) { if (octant[a].Contains(obj.BoundingBox) == ContainmentType.Contains) { octList[a].Add(obj); delist.Add(obj); break; } } } else if (obj.BoundingSphere.Radius != 0) { for (int a = 0; a < 8; a++) { if (octant[a].Contains(obj.BoundingSphere) == ContainmentType.Contains) { octList[a].Add(obj); delist.Add(obj); break; } } } } //delist every moved object from this node. foreach (Physical obj in delist) m_objects.Remove(obj); //Create child nodes where there are items contained in the bounding region for (int a = 0; a < 8; a++) { if (octList[a].Count != 0) { m_childNode[a] = CreateNode(octant[a], octList[a]); m_activeNodes |= (byte)(1 << a); m_childNode[a].BuildTree(); } } m_treeBuilt = true; m_treeReady = true; } private OctTree CreateNode(BoundingBox region, List objList) //complete & tested { if (objList.Count == 0) return null; OctTree ret = new OctTree(region, objList); ret._parent = this; return ret; } private OctTree CreateNode(BoundingBox region, Physical Item) { List objList = new List(1); //sacrifice potential CPU time for a smaller memory footprint objList.Add(Item); OctTree ret = new OctTree(region, objList); ret._parent = this; return ret; }  
      Updating a tree
      Let's imagine that our tree has a lot of moving objects in it. If any object moves, there is a good chance that the object has moved outside of its enclosing octant. How do we handle changes in object position while maintaining the integrity of our tree structure?
      Technique 1: Keep it super simple, trash & rebuild everything.
      Some implementations of an Octree will completely rebuild the entire tree every frame and discard the old one. This is super simple and it works, and if this is all you need, then prefer the simple technique. The general consensus is that the upfront CPU cost of rebuilding the tree every frame is much cheaper than running a brute force collision check, and programmer time is too valuable to be spent on an unnecessary optimization. For those of us who like challenges and to over-engineer things, the "trash & rebuild" technique comes with a few small problems:
      You're constantly allocating and deallocating memory each time you rebuild your tree. Allocating new memory comes at a small cost. If possible, you want to minimize the amount of memory being allocated and reallocated over time by reusing memory you've already got. Most of the tree is unchanging, so it's a waste of CPU time to rebuild the same branches over and over again. Technique 2: Keep the existing tree, update the changed branches
      I noticed that most branches of a tree don't need to be updated. They just contain stationary objects. Wouldn't it be nice if, instead of rebuilding the entire tree every frame, we just updated the parts of the tree which needed an update? This technique keeps the existing tree and updates only the branches which had an object which moved. It's a bit more complex to implement, but it's a lot more fun too, so let's really get into that!
      During my first attempt at this, I mistakenly thought that an object in a child node could only go up or down one traversal of the tree. This is wrong. If an object in a child node reaches the edge of that node, and that edge also happens to be an edge for the enclosing parent node, then that object needs to be inserted above its parent, and possibly up even further. So, the bottom line is that we don't know how far up an object needs to be pushed up the tree. Just as well, an object can move such that it can be neatly enclosed in a child node, or that child's child node. We don't know how far down the tree we can go.
      Fortunately, since we include a reference to each node's parent, we can easily solve this problem recursively with minimal computation! The general idea behind the update algorithm is to first let all objects in the tree update themselves. Some may move or change in size. We want to get a list of every object which moved, so the object update method should return to us a boolean value indicating if its bounding area changed. Once we've got a list of all of our moved objects, we want to start at our current node and try to traverse up the tree until we find a node which completely encloses the moved object (most of the time, the current node still encloses the object). If the object isn't completely enclosed by the current node, we keep moving it up to its next parent node. In the worst case, our root node will be guaranteed to contain the object.
      After we've moved our object as far up the tree as possible, we'll try to move it as far down the tree as we can. Most of the time, if we moved the object up, we won't be able to move it back down. But, if the object moved so that a child node of the current node could contain it, we have the chance to push it back down the tree. It's important to be able to move objects down the tree as well, or else all moving objects would eventually migrate to the top and we'd start getting some performance problems during collision detection routines.
      Branch Removal
      In some cases, an object will move out of a node and that node will no longer have any objects contained within it, nor have any children which contain objects. If this happens, we have an empty branch and we need to mark it as such and prune this dead branch off the tree.
      There is an interesting question hiding here: When do you want to prune the dead branches off a tree? Allocating new memory costs time, so if we're just going to reuse this same region in a few cycles, why not keep it around for a bit? How long can we keep it around before it becomes more expensive to maintain the dead branch? I decided to give each of my nodes a countdown timer which activates when the branch is dead. If an object moves into this nodes octant while the death timer is active, I double the lifespan and reset the death timer. This ensures that octants which are frequently used are hot and stick around, and nodes which are infrequently used are removed before they start to cost more than they're worth.
      A practical example of this usefulness would be apparent when you have a machine gun shooting a stream of bullets. Those bullets follow in close succession of each other, so it'd be a shame to immediately delete a node as soon as the first bullet leaves it, only to recreate it a fraction of a second later as the second bullet re-enters it. And if there's a lot of bullets, we can probably keep these octants around for a little while. If a child branch is empty and hasn't been used in a while, it's safe to prune it out of our tree.
      Anyways, let's look at the code which does all of this magic. First up, we have the Update() method. This is a method which is recursively called on all child trees. It moves all objects around, does some housekeeping work for the data structure, and then moves each moved object into its correct node (parent or child).
      public void Update(coreTime time) { if (m_treeBuilt == true && m_treeReady == true) { //Start a count down death timer for any leaf nodes which don't have objects or children. //when the timer reaches zero, we delete the leaf. If the node is reused before death, we double its lifespan. //this gives us a "frequency" usage score and lets us avoid allocating and deallocating memory unnecessarily if (m_objects.Count == 0) { if (HasChildren == false) { if (m_curLife == -1) m_curLife = m_maxLifespan; else if (m_curLife > 0) { m_curLife--; } } } else { if (m_curLife != -1) { if (m_maxLifespan <= 64) m_maxLifespan *= 2; m_curLife = -1; } } List<Physical> movedObjects = new List<Physical>(m_objects.Count); //go through and update every object in the current tree node foreach (Physical gameObj in m_objects) { //we should figure out if an object actually moved so that we know whether we need to update this node in the tree. if (gameObj.Update(time) == 1) { movedObjects.Add(gameObj); } } //prune any dead objects from the tree. int listSize = m_objects.Count; for (int a = 0; a < listSize; a++) { if (!m_objects[a].Alive) { if (movedObjects.Contains(m_objects[a])) movedObjects.Remove(m_objects[a]); m_objects.RemoveAt(a--); listSize--; } } //prune out any dead branches in the tree for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++) if ((flags & 1) == 1 && m_childNode[index].m_curLife == 0) { if (m_childNode[index].m_objects.Count > 0) { //throw new Exception("Tried to delete a used branch!"); m_childNode[index].m_curLife = -1; } else { m_childNode[index] = null; m_activeNodes ^= (byte)(1 << index); //remove the node from the active nodes flag list } } //recursively update any child nodes. for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++) { if ((flags & 1) == 1) { if(m_childNode!=null && m_childNode[index] != null) m_childNode[index].Update(time); } } //If an object moved, we can insert it into the parent and that will insert it into the correct tree node. //note that we have to do this last so that we don't accidentally update the same object more than once per frame. foreach (Physical movedObj in movedObjects) { OctTree current = this; //figure out how far up the tree we need to go to reinsert our moved object //we are either using a bounding rect or a bounding sphere //try to move the object into an enclosing parent node until we've got full containment if (movedObj.EnclosingBox.Max != movedObj.EnclosingBox.Min) { while (current.m_region.Contains(movedObj.EnclosingBox) != ContainmentType.Contains) if (current._parent != null) current = current._parent; else { break; //prevent infinite loops when we go out of bounds of the root node region } } else { ContainmentType ct = current.m_region.Contains(movedObj.EnclosingSphere); while (ct != ContainmentType.Contains)//we must be using a bounding sphere, so check for its containment. { if (current._parent != null) { current = current._parent; } else { //the root region cannot contain the object, so we need to completely rebuild the whole tree. //The rarity of this event is rare enough where we can afford to take all objects out of the existing tree and rebuild the entire thing. List<Physical> tmp = m_root.AllObjects(); m_root.UnloadContent(); Enqueue(tmp);//add to pending queue return; } ct = current.m_region.Contains(movedObj.EnclosingSphere); } } //now, remove the object from the current node and insert it into the current containing node. m_objects.Remove(movedObj); current.Insert(movedObj); //this will try to insert the object as deep into the tree as we can go. } //now that all objects have moved and they've been placed into their correct nodes in the octree, we can look for collisions. if (IsRoot == true) { //This will recursively gather up all collisions and create a list of them. //this is simply a matter of comparing all objects in the current root node with all objects in all child nodes. //note: we can assume that every collision will only be between objects which have moved. //note 2: An explosion can be centered on a point but grow in size over time. In this case, you'll have to override the update method for the explosion. List<IntersectionRecord> irList = GetIntersection(new List<Physical>()); foreach (IntersectionRecord ir in irList) { if (ir.PhysicalObject != null) ir.PhysicalObject.HandleIntersection(ir); if (ir.OtherPhysicalObject != null) ir.OtherPhysicalObject.HandleIntersection(ir); } } }//end if tree built else { if (m_pendingInsertion.Count > 0) { ProcessPendingItems(); Update(time); //try this again... } } } Note that we call an Insert() method for moved objects. The insertion of objects into the tree is very similar to the method used to build the initial tree. Insert() will try to push objects as far down the tree as possible. Notice that I also try to avoid creating new bounding areas if I can use an existing one from a child node.
      /// <summary> /// A tree has already been created, so we're going to try to insert an item into the tree without rebuilding the whole thing /// </summary> /// <typeparam name="T">A physical object</typeparam> /// <param name="Item">The physical object to insert into the tree</param> private bool Insert<T>(T Item) where T : Physical { /*if the current node is an empty leaf node, just insert and leave it.*/ //if (m_objects.Count == 0 && m_activeNodes == 0) if(AllTreeObjects.Count == 0) { m_objects.Add(Item); return true; } //Check to see if the dimensions of the box are greater than the minimum dimensions. //If we're at the smallest size, just insert the item here. We can't go any lower! Vector3 dimensions = m_region.Max - m_region.Min; if (dimensions.X <= MIN_SIZE && dimensions.Y <= MIN_SIZE && dimensions.Z <= MIN_SIZE) { m_objects.Add(Item); return true; } //The object won't fit into the current region, so it won't fit into any child regions. //therefore, try to push it up the tree. If we're at the root node, we need to resize the whole tree. if (m_region.Contains(Item.EnclosingSphere) != ContainmentType.Contains) { if (this._parent != null) return this._parent.Insert(Item); else return false; } //At this point, we at least know this region can contain the object but there are child nodes. Let's try to see if the object will fit //within a subregion of this region. Vector3 half = dimensions / 2.0f; Vector3 center = m_region.Min + half; //Find or create subdivided regions for each octant in the current region BoundingBox[] childOctant = new BoundingBox[8]; childOctant[0] = (m_childNode[0] != null) ? m_childNode[0].m_region : new BoundingBox(m_region.Min, center); childOctant[1] = (m_childNode[1] != null) ? m_childNode[1].m_region : new BoundingBox(new Vector3(center.X, m_region.Min.Y, m_region.Min.Z), new Vector3(m_region.Max.X, center.Y, center.Z)); childOctant[2] = (m_childNode[2] != null) ? m_childNode[2].m_region : new BoundingBox(new Vector3(center.X, m_region.Min.Y, center.Z), new Vector3(m_region.Max.X, center.Y, m_region.Max.Z)); childOctant[3] = (m_childNode[3] != null) ? m_childNode[3].m_region : new BoundingBox(new Vector3(m_region.Min.X, m_region.Min.Y, center.Z), new Vector3(center.X, center.Y, m_region.Max.Z)); childOctant[4] = (m_childNode[4] != null) ? m_childNode[4].m_region : new BoundingBox(new Vector3(m_region.Min.X, center.Y, m_region.Min.Z), new Vector3(center.X, m_region.Max.Y, center.Z)); childOctant[5] = (m_childNode[5] != null) ? m_childNode[5].m_region : new BoundingBox(new Vector3(center.X, center.Y, m_region.Min.Z), new Vector3(m_region.Max.X, m_region.Max.Y, center.Z)); childOctant[6] = (m_childNode[6] != null) ? m_childNode[6].m_region : new BoundingBox(center, m_region.Max); childOctant[7] = (m_childNode[7] != null) ? m_childNode[7].m_region : new BoundingBox(new Vector3(m_region.Min.X, center.Y, center.Z), new Vector3(center.X, m_region.Max.Y, m_region.Max.Z)); //First, is the item completely contained within the root bounding box? //note2: I shouldn't actually have to compensate for this. If an object is out of our predefined bounds, then we have a problem/error. // Wrong. Our initial bounding box for the terrain is constricting its height to the highest peak. Flying units will be above that. // Fix: I resized the enclosing box to 256x256x256. This should be sufficient. if (Item.EnclosingBox.Max != Item.EnclosingBox.Min && m_region.Contains(Item.EnclosingBox) == ContainmentType.Contains) { bool found = false; //we will try to place the object into a child node. If we can't fit it in a child node, then we insert it into the current node object list. for(int a=0;a<8;a++) { //is the object fully contained within a quadrant? if (childOctant[a].Contains(Item.EnclosingBox) == ContainmentType.Contains) { if (m_childNode[a] != null) { return m_childNode[a].Insert(Item); //Add the item into that tree and let the child tree figure out what to do with it } else { m_childNode[a] = CreateNode(childOctant[a], Item); //create a new tree node with the item m_activeNodes |= (byte)(1 << a); } found = true; } } //we couldn't fit the item into a smaller box, so we'll have to insert it in this region if (!found) { m_objects.Add(Item); return true; } } else if (Item.EnclosingSphere.Radius != 0 && m_region.Contains(Item.EnclosingSphere) == ContainmentType.Contains) { bool found = false; //we will try to place the object into a child node. If we can't fit it in a child node, then we insert it into the current node object list. for (int a = 0; a < 8; a++) { //is the object contained within a child quadrant? if (childOctant[a].Contains(Item.EnclosingSphere) == ContainmentType.Contains) { if (m_childNode[a] != null) { return m_childNode[a].Insert(Item); //Add the item into that tree and let the child tree figure out what to do with it } else { m_childNode[a] = CreateNode(childOctant[a], Item); //create a new tree node with the item m_activeNodes |= (byte)(1 << a); } found = true; } } //we couldn't fit the item into a smaller box, so we'll have to insert it in this region if (!found) { m_objects.Add(Item); return true; } } //either the item lies outside of the enclosed bounding box or it is intersecting it. Either way, we need to rebuild //the entire tree by enlarging the containing bounding box return false; }  
      Collision Detection
      Finally, our octree has been built and everything is as it should be. How do we perform collision detection against it? First, let's list out the different ways we want to look for collisions:
      Frustum intersections. We may have a frustum which intersects with a region of the world. We only want the objects which intersect with the given frustum. This is particularly useful for culling regions outside of the camera view space, and for figuring out what objects are within a mouse selection area. Ray intersections. We may want to shoot a directional ray from any given point and want to know either the nearest intersecting object or get a list of all objects which intersect that ray (like a rail gun). This is very useful for mouse picking. If the user clicks on the screen, we want to draw a ray into the world and figure out what they clicked on. Bounding Box intersections. We want to know which objects in the world are intersecting a given bounding box. This is most useful for "box" shaped game objects (houses, cars, etc). Bounding Sphere Intersections. We want to know which objects are intersecting with a given bounding sphere. Most objects will probably be using a bounding sphere for coarse collision detection since the mathematics is computationally the least expensive and somewhat easy. The main idea behind recursive collision detection processing for an octree is that you start at the root/current node and test for intersection with all objects in that node against the intersector. Then, you do a bounding box intersection test against all active child nodes with the intersector. If a child node fails this intersection test, you can completely ignore the rest of that child's tree. If a child node passes the intersection test, you recursively traverse down the tree and repeat. Each node should pass a list of intersection records up to its caller, which appends those intersections to its own list of intersections. When the recursion finishes, the original caller will get a list of every intersection for the given intersector. The beauty of this is that it takes very little code to implement and performance is very fast. In a lot of these collisions, we're probably going to be getting a lot of results. We're also going to want to have some way of responding to each collision, depending on what objects are colliding.
      For example, a player hero should pick up a floating bonus item (quad damage!), but a rocket shouldn't explode if it hits said bonus item. I created a new class to contain information about each intersection. This class contains references to the intersecting objects, the point of intersection, the normal at the point of intersection, etc. These intersection records become quite useful when you pass them to an object and tell them to handle it. For completeness and clarity, here is my intersection record class:
      public class IntersectionRecord { readonly Vector3 m_position, m_normal; readonly Ray m_ray; readonly Physical m_intersectedObject1, m_intersectedObject2; readonly double m_distance; public class Builder { public Vector3 Position, Normal; public Physical Object1, Object2; public Ray hitRay; public double Distance; public Builder() { Distance = double.MaxValue; } public Builder(IntersectionRecord copy) { Position = copy.m_position; Normal = copy.m_normal; Object1 = copy.m_intersectedObject1; Object2 = copy.m_intersectedObject2; hitRay = copy.m_ray; Distance = copy.m_distance; } public IntersectionRecord Build() { return new IntersectionRecord(Position, Normal, Object1, Object2, hitRay, Distance); } } #region Constructors IntersectionRecord(Vector3 pos, Vector3 normal, Physical obj1, Physical obj2, Ray r, double dist) { m_position = pos; m_normal = normal; m_intersectedObject1 = obj1; m_intersectedObject2 = obj2; m_ray = r; m_distance = dist; } #endregion #region Accessors /// <summary> /// This is the exact point in 3D space which has an intersection. /// </summary> public Vector3 Position { get { return m_position; } } /// <summary> /// This is the normal of the surface at the point of intersection /// </summary> public Vector3 Normal { get { return m_normal; } } /// <summary> /// This is the ray which caused the intersection /// </summary> public Ray Ray { get { return m_ray; } } /// <summary> /// This is the object which is being intersected /// </summary> public Physical PhysicalObject { get { return m_intersectedObject1; } } /// <summary> /// This is the other object being intersected (may be null, as in the case of a ray-object intersection) /// </summary> public Physical OtherPhysicalObject { get { return m_intersectedObject2; } } /// <summary> /// This is the distance from the ray to the intersection point. /// You'll usually want to use the nearest collision point if you get multiple intersections. /// </summary> public double Distance { get { return m_distance; } } #endregion #region Overrides public override string ToString() { return "Hit: " + m_intersectedObject1.ToString(); } public override int GetHashCode() { return base.GetHashCode(); } /// <summary> /// check the object identities between the two intersection records. If they match in either order, we have a duplicate. /// </summary> /// <param name="otherRecord">the other record to compare against</param> /// <returns>true if the records are an intersection for the same pair of objects, false otherwise.</returns> public override bool Equals(object otherRecord) { IntersectionRecord o = (IntersectionRecord)otherRecord; // //return (m_intersectedObject1 != null && m_intersectedObject2 != null && m_intersectedObject1.ID == m_intersectedObject2.ID); if (otherRecord == null) return false; if (o.m_intersectedObject1.ID == m_intersectedObject1.ID && o.m_intersectedObject2.ID == m_intersectedObject2.ID) return true; if (o.m_intersectedObject1.ID == m_intersectedObject2.ID && o.m_intersectedObject2.ID == m_intersectedObject1.ID) return true; return false; } #endregion }  
      Intersection with a Bounding Frustum
      /// <summary> /// Gives you a list of all intersection records which intersect or are contained within the given frustum area /// </summary> /// <param name="frustum">The containing frustum to check for intersection/containment with</param> /// <returns>A list of intersection records with collisions</returns> private List<IntersectionRecord> GetIntersection(BoundingFrustum frustum, PhysicalType type = PhysicalType.ALL) { if (!m_treeBuilt) return new List<IntersectionRecord>(); if (m_objects.Count == 0 && HasChildren == false) //terminator for any recursion return null; List<IntersectionRecord> ret = new List<IntersectionRecord>(); //test each object in the list for intersection foreach (Physical obj in m_objects) { //skip any objects which don't meet our type criteria if ((int)((int)type & (int)obj.Type) == 0) continue; //test for intersection IntersectionRecord ir = obj.Intersects(frustum); if (ir != null) ret.Add(ir); } //test each object in the list for intersection for (int a = 0; a < 8; a++) { if (m_childNode[a] != null && (frustum.Contains(m_childNode[a].m_region) == ContainmentType.Intersects || frustum.Contains(m_childNode[a].m_region) == ContainmentType.Contains)) { List<IntersectionRecord> hitList = m_childNode[a].GetIntersection(frustum, type); if (hitList != null) ret.AddRange(hitList); } } return ret; } The bounding frustum intersection list can be used to only render objects which are visible to the current camera view. I use a scene database to figure out how to render all objects in the game world. Here is a snippet of code from my rendering function which uses the bounding frustum of the active camera:
      /// /// This renders every active object in the scene database /// /// public int Render() { int triangles = 0; //Renders all visible objects by iterating through the oct tree recursively and testing for intersection //with the current camera view frustum foreach (IntersectionRecord ir in m_octTree.AllIntersections(m_cameras[m_activeCamera].Frustum)) { ir.PhysicalObject.SetDirectionalLight(m_globalLight[0].Direction, m_globalLight[0].Color); ir.PhysicalObject.View = m_cameras[m_activeCamera].View; ir.PhysicalObject.Projection = m_cameras[m_activeCamera].Projection; ir.PhysicalObject.UpdateLOD(m_cameras[m_activeCamera]); triangles += ir.PhysicalObject.Render(m_cameras[m_activeCamera]); } return triangles; }  
      Intersection with a Ray
      /// <summary> /// Gives you a list of intersection records for all objects which intersect with the given ray /// </summary> /// <param name="intersectRay">The ray to intersect objects against</param> /// <returns>A list of all intersections</returns> private List<IntersectionRecord> GetIntersection(Ray intersectRay, PhysicalType type = PhysicalType.ALL) { if (!m_treeBuilt) return new List<IntersectionRecord>(); if (m_objects.Count == 0 && HasChildren == false) //terminator for any recursion return null; List<IntersectionRecord> ret = new List<IntersectionRecord>(); //the ray is intersecting this region, so we have to check for intersection with all of our contained objects and child regions. //test each object in the list for intersection foreach (Physical obj in m_objects) { //skip any objects which don't meet our type criteria if ((int)((int)type & (int)obj.Type) == 0) continue; IntersectionRecord ir = obj.Intersects(intersectRay); if (ir != null) ret.Add(ir); } // test each child octant for intersection for (int a = 0; a < 8; a++) { if (m_childNode[a] != null && m_childNode[a].m_region.Intersects(intersectRay) != null) { m_lineColor = Color.Red; List<IntersectionRecord> hits = m_childNode[a].GetIntersection(intersectRay, type); if (hits != null && hits.Count > 0) { ret.AddRange(hits); } } } return ret; }  
      Intersection with a list of objects
      This is a particularly useful recursive method for determining if a list of objects in the current node intersects with any objects in any child nodes (See: Update() method for usage). It's the method which will be used most frequently, so it's good to get this right and efficient. What we want to do is start at the root node of the tree. We compare all objects in the current node against all other objects in the current node for collision. We gather up any of those collisions as intersection records and insert them into a list. We then pass our list of tested objects down to our child nodes. The child nodes will then test their objects against themselves, then against the objects we passed down to them. The child nodes will capture any collisions in a list, and return that list to its parent. The parent then takes the collision list received from its child nodes and appends it to its own list of collisions, finally returning it to its caller.
      If you count out the number of collision tests in the illustration above, you can see that we conducted 29 hit tests and received 4 hits. This is much better than [11*11 = 121] hit tests.
      private List<IntersectionRecord> GetIntersection(List<Physical> parentObjs, PhysicalType type = PhysicalType.ALL) { List<IntersectionRecord> intersections = new List<IntersectionRecord>(); //assume all parent objects have already been processed for collisions against each other. //check all parent objects against all objects in our local node foreach (Physical pObj in parentObjs) { foreach (Physical lObj in m_objects) { //We let the two objects check for collision against each other. They can figure out how to do the coarse and granular checks. //all we're concerned about is whether or not a collision actually happened. IntersectionRecord ir = pObj.Intersects(lObj); if (ir != null) { //ir.m_treeNode = this; intersections.Add(ir); } } } //now, check all our local objects against all other local objects in the node if (m_objects != null && m_objects.Count > 1) { #region self-congratulation /* * This is a rather brilliant section of code. Normally, you'd just have two foreach loops, like so: * foreach(Physical lObj1 in m_objects) * { * foreach(Physical lObj2 in m_objects) * { * //intersection check code * } * } * * The problem is that this runs in O(N*N) time and that we're checking for collisions with objects which have already been checked. * Imagine you have a set of four items: {1,2,3,4} * You'd first check: {1} vs {1,2,3,4} * Next, you'd check {2} vs {1,2,3,4} * but we already checked {1} vs {2}, so it's a waste to check {2} vs. {1}. What if we could skip this check by removing {1}? * We'd have a total of 4+3+2+1 collision checks, which equates to O(N(N+1)/2) time. If N is 10, we are already doing half as many collision checks as necessary. * Now, we can't just remove an item at the end of the 2nd for loop since that would break the iterator in the first foreach loop, so we'd have to use a * regular for(int i=0;i<size;i++) style loop for the first loop and reduce size each iteration. This works...but look at the for loop: we're allocating memory for * two additional variables: i and size. What if we could figure out some way to eliminate those variables? * So, who says that we have to start from the front of a list? We can start from the back end and still get the same end results. With this in mind, * we can completely get rid of a for loop and use a while loop which has a conditional on the capacity of a temporary list being greater than 0. * since we can poll the list capacity for free, we can use the capacity as an indexer into the list items. Now we don't have to increment an indexer either! * The result is below. */ #endregion List<Physical> tmp = new List<Physical>(m_objects.Count); tmp.AddRange(m_objects); while (tmp.Count > 0) { foreach (Physical lObj2 in tmp) { if (tmp[tmp.Count - 1] == lObj2 || (tmp[tmp.Count - 1].IsStationary && lObj2.IsStationary)) continue; IntersectionRecord ir = tmp[tmp.Count - 1].Intersects(lObj2); if (ir != null) { //ir.m_treeNode = this; intersections.Add(ir); } } //remove this object from the temp list so that we can run in O(N(N+1)/2) time instead of O(N*N) tmp.RemoveAt(tmp.Count-1); } } //now, merge our local objects list with the parent objects list, then pass it down to all children. foreach (Physical lObj in m_objects) if (lObj.IsStationary == false) parentObjs.Add(lObj); //parentObjs.AddRange(m_objects); //each child node will give us a list of intersection records, which we then merge with our own intersection records. for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++) { if ((flags & 1) == 1) { if(m_childNode != null && m_childNode[index] != null) intersections.AddRange(m_childNode[index].GetIntersection(parentObjs, type)); } } return intersections; }  
      Screenshot Demos
       
      This is a view of the game world from a distance showing the outlines for each bounding volume for the octree. This view shows a bunch of successive projectiles moving through the game world with the frequently-used nodes being preserved instead of deleted.  
      Complete Code Sample
      I've attached a complete code sample of the octree class, the intersection record class, and my generic physical object class. I don't guarantee that they're all bug-free since it's all a work in progress and hasn't been rigorously tested yet.
    • By therax1986
      Hi everyone. For the last few months I’ve been working on a simple HTML5 2D side scrolling action game called Theraxius. It's nothing new and revolutionary, it's more like an evolution of different technology (combination of HTML5, PHP, MySQL). The game also includes a level editor so you can create your own levels. The game and the level editor is written almost completely in JavaScript, no download is required. Just load and play. Here are a few screenshots and the link to the page.
      In the next weeks I’ll try to post some videos, try to add registration (for newsletter and later for public test).
      Release date: when it's done
      theraxius.com



    • By GameDev.net
      Does your code use one of the most popular graphics or compute APIs? Here is a map of Intel® processor series to each graphics generation to add to your dev docs.
      Developer Documents for Intel® Processor Graphics
      Intel® processor graphics provide the graphics, compute, media, and display for many of our processors including the 6th gen Intel® Core™ processors. Does your code use one of the popular graphics or compute APIs? Do you want a deeper understanding of our graphics hardware architecture? In the table, you’ll find the right documents to help you write and tune your software so it runs great on Intel processor graphics.
      If you’re developing compute applications, the compute architecture guides give foundational reading and the OpenCL™ optimization guides show you how to optimize. If your code uses the graphics APIs, read the graphics dev guides or programmers reference manuals.
      Read more
    • By GameDev.net
      Arizona Sunshine* found success in the VR space after following Intel® Guidelines for Immersive VR Experiences. See how they became the fastest-selling non-bundled virtual Reality title to date.

      With a dazzling launch in early 2017 that saw Arizona Sunshine* become the fastest-selling non-bundled virtual reality title to date, and instant recognition as the 2016 “Best Vive Game” according to UploadVR, the zombie-killer game is not just another VR shooter. Combining immersive game play with intriguing multi-player options, this game takes full advantage of VR capabilities to promote playability in both outdoor and underground environments.
      Through its association with Netherlands-based Vertigo Games and nearby indie developer Jaywalkers Interactive, Intel helped add sizzle to Arizona Sunshine by fine-tuning the CPU capabilities to provide end-to-end VR realism. The power of a strong CPU performance becomes apparent with every jaw-dropping zombie horde attack. From the resources available when a player chooses and loads a weapon, to the responsiveness of the surrounding eerie world, the immersive qualities of the VR interface make it easy to forget that it’s just a game.
      Read more
    • By GameDev.net
      Unity* 3.0 provides tools and settings that simplify game creation. This paper analyzes and troubleshoots performance with Unity* on Intel® graphics processors, and provides users with performance considerations for their games.
      Abstract
      Unity provides a number of tools and settings to help make games perform smoothly. For this project, we chose ones we thought could prove to be troublesome and analyzed how they affected game performance on Intel® graphics processors.
      We put ourselves in the shoes of a game developer learning how to use Unity. We wanted to stumble into performance pitfalls and then determine how to work through issues with Unity’s built-in performance mechanisms. One of Unity’s strengths is the ability to create content quickly, but when considering performance, especially on mobile and tablet devices, the developer needs to slow down and plan out how to utilize the built in performance mechanisms. This paper prepares new and existing Unity users with performance considerations when building your levels/games, and offers new ways to build.
      Read more
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!