Jump to content

unirule

  • entries
    20
  • comments
    39
  • views
    18653

More Adventures in Robust Coding

Awoken

2280 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 CommanderLake
      I've been experimenting with my own n-body simulation for some time and I recently discovered how to optimize it for efficient multithreading and vectorization with the Intel compiler. It did exactly the same thing after making it multithreaded and scaled very well on my ancient i7 3820 (4.3GHz). Then I changed the interleaved xy coordinates to separate arrays for x and y to eliminate the strided loads to improve AVX scaling and copy the coordinates to an interleaved array for OpenTK to render as points. Now the physics is all wrong, the points form clumps that interact with each other but they are unusually dense and accelerate faster than they decelerate causing the clumps to randomly fly off into the distance and after several seconds I get a NaN where 2 points somehow occupy exactly the same x and y float coordinates. This is the C++ DLL:
      #include "PPC.h" #include <thread> static const float G = 0.0000001F; const int count = 4096; __declspec(align(64)) float pointsx[count]; __declspec(align(64)) float pointsy[count]; void SetData(float* x, float* y){ memcpy(pointsx, x, count * sizeof(float)); memcpy(pointsy, y, count * sizeof(float)); } void Compute(float* points, float* velx, float* vely, long pcount, float aspect, float zoom) { #pragma omp parallel for for (auto i = 0; i < count; ++i) { auto forcex = 0.0F; auto forcey = 0.0F; for (auto j = 0; j < count; ++j) { if(j == i)continue; const auto distx = pointsx[i] - pointsx[j]; const auto disty = pointsy[i] - pointsy[j]; //if(px != px) continue; //most efficient way to avoid a NaN failure const auto force = G / (distx * distx + disty * disty); forcex += distx * force; forcey += disty * force; } pointsx[i] += velx[i] -= forcex; pointsy[i] += vely[i] -= forcey; if (zoom != 1) { points[i * 2] = pointsx[i] * zoom / aspect; points[i * 2 + 1] = pointsy[i] * zoom; } else { points[i * 2] = pointsx[i] / aspect; points[i * 2 + 1] = pointsy[i]; } /*points[i * 2] = pointsx[i]; points[i * 2 + 1] = pointsy[i];*/ } } This is the relevant part of the C# OpenTK GameWindow:
      private void PhysicsLoop(){ while(true){ if(stop){ for(var i = 0; i < pcount; ++i) { velx[i] = vely[i] = 0F; } } if(reset){ reset = false; var r = new Random(); for(var i = 0; i < Startcount; ++i){ do{ pointsx[i] = (float)(r.NextDouble()*2.0F - 1.0F); pointsy[i] = (float)(r.NextDouble()*2.0F - 1.0F); } while(pointsx[i]*pointsx[i] + pointsy[i]*pointsy[i] > 1.0F); velx[i] = vely[i] = 0.0F; } NativeMethods.SetData(pointsx, pointsy); pcount = Startcount; buffersize = (IntPtr)(pcount*8); } are.WaitOne(); NativeMethods.Compute(points0, velx, vely, pcount, aspect, zoom); var pointstemp = points0; points0 = points1; points1 = pointstemp; are1.Set(); } } protected override void OnRenderFrame(FrameEventArgs e){ GL.Clear(ClearBufferMask.ColorBufferBit); GL.EnableVertexAttribArray(0); GL.BindBuffer(BufferTarget.ArrayBuffer, vbo); mre1.Wait(); are1.WaitOne(); GL.BufferData(BufferTarget.ArrayBuffer, buffersize, points1, BufferUsageHint.StaticDraw); are.Set(); GL.VertexAttribPointer(0, 2, VertexAttribPointerType.Float, false, 0, 0); GL.DrawArrays(PrimitiveType.Points, 0, pcount); GL.DisableVertexAttribArray(0); SwapBuffers(); } These are the array declarations:
      private const int Startcount = 4096; private readonly float[] pointsx = new float[Startcount]; private readonly float[] pointsy = new float[Startcount]; private float[] points0 = new float[Startcount*2]; private float[] points1 = new float[Startcount*2]; private readonly float[] velx = new float[Startcount]; private readonly float[] vely = new float[Startcount];  
      Edit 0: It seems that adding 3 zeros to G increases the accuracy of the simulation but I'm at a loss as to why its different without interleaved coordinates. Edit 1: I somehow achieved an 8.3x performance increase with AVX over scalar with the new code above!
    • By MakeIndieGreatAgain
      Game developers will be able to become pioneers in the development of decentralized games for the gambling industry using DAO.Casino protocol.
      On September 17, 2018, DAO.Casino is opening Sandbox for developers, independent teams and game development studios that choose to harness the power of the rapidly developing DApp industry.
      Starting today everyone may submit their application for Sandbox on the official Sandbox page.
      The Sandbox project is designed by DAO.Casino developers. Participants of Sandbox will learn the basics of decentralized applications development on DAO.Casino protocol. Developers participating in Sandbox will learn to create, design and deploy decentralized games and applications on Ethereum blockchain.
      DAO.Casino is planning to reward most active developers for their constructive feedback on the improvement and optimization of the SDK and related documentation. The company will separately announce the details of the rewards program later this fall.
      “We are confident that the Sandbox project will play an important role in our collaboration with studios and independent game developers. We cannot wait to see our product helping developers unleash their creative and entrepreneurial talents and apply those to one of the most groundbreaking technologies of the XXI century. — states Ilya Tarutov, CEO, DAO.Casino. – I am sure that the products we’re developing will transform the online gambling into a fair and transparent industry for all of the involved parties: casino operators, developers, and affiliate marketers. “
      “We are launching the Sandbox with the goal of enabling as many developers as possible to learn to create decentralized games. We have achieved an important milestone by starting to accept applications from developers all around the world who share our idea to make online gambling fair and transparent. With our technology, developers can take the whole gambling industry to the next level” – says Alexandra Fetisova from DAO.Casino.
      DAO.Casino is disrupting the online gambling industry by developing the protocol based on Ethereum blockchain technology. The protocol ensures the automation of transactions and facilitates interactions between all the industry participants: casino operators, game developers, and affiliate marketers. DAO.Casino team is fully dedicated to developing the best products and making the gambling industry a better place.

      View full story
    • By MakeIndieGreatAgain
      Game developers will be able to become pioneers in the development of decentralized games for the gambling industry using DAO.Casino protocol.
      On September 17, 2018, DAO.Casino is opening Sandbox for developers, independent teams and game development studios that choose to harness the power of the rapidly developing DApp industry.
      Starting today everyone may submit their application for Sandbox on the official Sandbox page.
      The Sandbox project is designed by DAO.Casino developers. Participants of Sandbox will learn the basics of decentralized applications development on DAO.Casino protocol. Developers participating in Sandbox will learn to create, design and deploy decentralized games and applications on Ethereum blockchain.
      DAO.Casino is planning to reward most active developers for their constructive feedback on the improvement and optimization of the SDK and related documentation. The company will separately announce the details of the rewards program later this fall.
      “We are confident that the Sandbox project will play an important role in our collaboration with studios and independent game developers. We cannot wait to see our product helping developers unleash their creative and entrepreneurial talents and apply those to one of the most groundbreaking technologies of the XXI century. — states Ilya Tarutov, CEO, DAO.Casino. – I am sure that the products we’re developing will transform the online gambling into a fair and transparent industry for all of the involved parties: casino operators, developers, and affiliate marketers. “
      “We are launching the Sandbox with the goal of enabling as many developers as possible to learn to create decentralized games. We have achieved an important milestone by starting to accept applications from developers all around the world who share our idea to make online gambling fair and transparent. With our technology, developers can take the whole gambling industry to the next level” – says Alexandra Fetisova from DAO.Casino.
      DAO.Casino is disrupting the online gambling industry by developing the protocol based on Ethereum blockchain technology. The protocol ensures the automation of transactions and facilitates interactions between all the industry participants: casino operators, game developers, and affiliate marketers. DAO.Casino team is fully dedicated to developing the best products and making the gambling industry a better place.
    • By 3dmodelerguy
      For reference I am use Unity as my game engine and the A* Pathfinding Project for path finding as there is no chance I would be able to create anything close to as performant as that in any reasonable amount of time.
      So I am looking to build a game that is going to have a very similar style as Prison Architect / Rim World / SimAirport / etc. One of the things that I assume is going to effect performance is path finding. Decisions about the game I have already made that I think relate to this are:
      1. While I am going to be using Colliders, all of them will be trigger colliders so everything can pass through each other and I will not be use physics for anything else as it has no relevance for my game
      2. I am going to want to have a soft cap at the map size being 300x300 (90,000 tiles), I might allow bigger sizes but do something like Rim World does in warning the player about possible side effect (whether it be performance or gameplay)
      3. The map will be somewhat dynamic in that the user will be able to build / gather stuff from the map but outside of that, it should not change very much
      Now I am going to build my game around the idea that users would be in control of no more than 50 pawns at any given time (which is something I can probably enforce through the game play) but I am also going to want to have number other pawns that are AI controlled on the map (NPCs, animals, etc.) that would also need path finding enabled. Now I did a basic test in which I have X number of pawns pick a random location in the 300 x 300 map. move towards it, and then change the location every 3-5 seconds. My initial test was pretty slow (not surprising as I was calculating the path every frame for each pawn) so I decided to cache the calculated path results and only update it ever 2 seconds which got me:
      100 pawns: 250 - 450 FPS
      150 pawns: 160 - 300 FPS
      200 pawns: 90 - 150 FPS
      250 pawns: 50 - 100 FPS
      There is very little extra happening in the game outside of rendering the tilemap.
      I would imagine the most pawns on the map at a given time that need path finding might be a 1000 (and I would probably be able to make due with like 500 - 600). Now obviously I would not need all the pawn to be calculation paths every 2 seconds nor would they need to be calculating paths that are so long but even at a 5 second path refresh rate and paths that are up to 10 tiles long, I am still only able to get to about 400 pawns before I start to see some big performance issues. The issue with reducing the refresh rate is that there are going to be cases where maybe a wall is built before the pawns path is refreshed having them walk through the wall but not sure if there is a clean way to update the path only when needed.
      I am sure when I don't run the game in the Unity editor I will see increase performance but I am just trying to figure out what things I could be doing to make sure path finding is as smaller of a performance hit as possible as there is a lot of other simulation stuff I am going to want to run on top of the path finding.
    • By Gerhart
      Hi,
      I want to learn to program games for PC and maybe Android. Sorry in advance if i don't know the correct terms.
       
      The game i have in mind will be relative simple (at least that's what i hope). It should be turn based with a map and different locations the player can switch in between. At the different locations there will be simple minigames, sometimes withwith simple animations. There is a storyline, the player sometimes can chose between different outcomes. I would like to include character progression in form of attributes and an inventory and i also would like to include a battle system (turn based).
      I've seen that there are some flash games out there who have similiar elements as i have planned for my game. The thing is, i don't know anything about flash and read, that it's not worth it to learn it anymore.
      Since i have some basic skills in html and css, i thought it would be better to give html5 and javascript a try (i have to learn javascript though).
      But iam not sure if it's really a good choice, since all html5 games i've seen so far are either actionshooters and/or have a really crappy graphics compared to flash games. In addition to that, i have no clue if the game i want to create is possible with either flash or html5/javascript. Another issue is, that flash needs adope flash and that's about 900 $ a year, money i don't have at the moment. It's a while ago, since i have made something with html and css, but i remember that there where a lot of problems with compatibility and the different browsers. I assume the same problems still exist and are true for games too?
      I would be really happy if someone could enlighten me, what would be the best possibilities for me to get in the gaming buisiness. What would be the best way, and what do i have to learn?
×

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!