Jump to content
  • Advertisement

Node Loops

Sign in to follow this  
Awoken

895 views

Hello GameDev,

During my efforts to accomplish the last robust challenge of mine 

I discovered a new way, for me, to speed up the processing time to achieve much faster path-finding results.  

About the technique:
I created continues node loops,
NodeLoop.png.e7a4150f4cd7d8b3310b9270b325bd42.png

Every node has information about the loop it's a member of.  Each Node has the following object:

{ 
	id: 4,
	loop: 10,
	loopSize: 8,
	loopStart: 0,
	loopEnd: 7
}

and the following functions:
 

	left( x ){

		if( this.id - x  < this.loopStart ){
			return ( this.id - x + this.loopSize );
		} else {
			return ( this.id - x );
		}

	}

	right( x ){

		if( this.id + x > this.loopEnd ){
			return ( this.id + x - this.loopSize );
		} else {
			return ( this.id + x );
		}

	}

	getDirection( n , M ){

		var m = M || this.id;

		if( n - m > 0 ){
			if( Math.abs( n - m - this.loopSize ) < ( n - m ) ){
				return true; // to IDa
			} else {
				return false; // to IDb 
			}
		} else {
			if( ( n - m + this.loopSize ) < Math.abs( n - m ) ){	
				return false; // to IDb
			} else {
				return true; // to IDa 
			}
		}
	}

	getNodesBetween( n , M ){

		var m = M || this.id;

		if( n - m > 0 ){
			if( Math.abs( n - m - this.loopSize ) < ( n - m ) ){	
				return Math.abs( n - m - this.loopSize ); // to IDa
			} else {	
				return ( n - m ); // to IDb 
			}
		} else {
			if( ( n - m + this.loopSize ) < Math.abs( n - m ) ){	
				return ( n - m + this.loopSize ); // to IDb
			} else {	
				return Math.abs( n - m ); // to IDa 
			}
		}
	}

With information about its parent loop accessible to each node, informed choices are possible about the nodes that should be tested for each subsequent iteration.
The following animated .gif visually demonstrates the logic.

animatedPathFind.thumb.gif.1d6e83e28bbc0cb999381f605181de8c.gif

1: Select Origin and Destination points
2: Check for collisions between them and determine node pairs ( Node pairs are nodes that are apart of the same loop )
3: Determine the smallest number of nodes between the node pairs, ( Are there fewer nodes if we travel left? or right? ) 
4: Check for collisions between Origin node and each incremental node apart of the loop. ( stop once collision is found )
5: Use last successful node tested as the new Origin point.
6: Check for collisions between Destination node and each incremental node apart of the loop. ( stop once collision i found )
7: Use last successful node tested as the new Destination point.
7. Repeat.


The Good,
It is much faster than using the blind search method I was using before, especially if both directions are searched when an obstacle is encountered.  If only one node loop is encountered it will return the shortest path with the addition of a refinement function.

The Bad,
It doesn't return the shortest path.  For that it has to be used in combination with other techniques and two new 'branches' of the function would be required for each unique node loop encountered.
 

Sign in to follow this  


1 Comment


Recommended Comments

It looks like the string pulling algorithm but reversed. Instead the angle of the cone can only be reduced, in your case it can only be increased.

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 Patson Luk
      Hi everyone! I have spent several months on my first hobby game project and decided to push it out to get some feedbacks.
      Would really appreciate it if you'd give it a try!
      It is live (and free of course) on http://www.airline-club.com ! The game is still in very early development stage, but I think it is quite playable
      My goal is to have a simulation good enough to generate data similar to real world's, while giving flexibility to simulate new outcome based on the dynamics of the conditions. For example one can start a really successful airline in a city that can actually alter demand distribution that is different from those observed in our current world (some part that I have not implemented yet but on the list for more end-game type - Airlines can make heavy investment in city/airport such as funding airport expansion, city projects to enhance a city's attributes etc)
      Several screenshots:


      Virtual passengers taking various routes using a flight going from San Francisco to Tokyo:

       
      The main highlights are:
        1. Real passengers that make decisions on what route to take based on various factors : Awareness of your airline, Loyalty to your airline, ticket pricing, seat class, service quality, # of connections, total travel time etc etc. This is different from several games that I played before which appeared to oversimplify flight demand with no connection flights. Having realistic simulation here provides many different strategic options
        2. Thousands of airports with basic data driven by real geographical information (surrounding city population, income, airport scale etc)
        3. Demand from airport to airport is calculated dynamically (not really based on real world data), which means various changes in game condition (not yet implemented, conditions are static for now) will affect demand accordingly
        4. Reactive UI - not a UI expert here. But at least I tried to make the code runs fast and the control flow reasonable
       
      A quick clip of the gameplay can be found here:
      https://uc50f3ae07e58d5abedb49ec99d6.dl.dropboxusercontent.com/cd/0/inline/AJusVsuSNgpWPKZsgBp7Eoo_WHboR0yZkArO4N4CewWG2580AOWDvIEbEruILjNmsgoLXaUqs3uJGMojsALOgz0B8StIMe2s0XTqvY85AyUzVMKS2EDyXq6ZGzhobshfTGFJm02puIcd5zkGg7IpsGYEfcP0WWK40o6UpReN67I1ok52wI11m04pZv4Zp9JAydQ/file
       
      Many thanks for your attention again and hope to see you in the game soon o/
       
       
    • By jb-dev
      I recently worked on a path-finding algorithm used to move an AI agent into an organically generated dungeon.
      It's not an easy task but because I've already worked on Team Fortress 2 cards in the past, I already knew navigation meshes (navmesh) and their capabilities.
      Why Not Waypoints?
      As described in this paper, waypoint networks were in the past used in video games to save valuable resources. It was an acceptable compromise : level designers already knew where NPCs could and could not go. However, as technology has evolved, computers got more memory that became faster and cheaper.
      In other words, there was a shift from efficiency to flexibility.
      In a way, navigation meshes are the evolution of waypoints networks because they fulfill the same need but in a different way.
      One of the advantages of using a navigation mesh is that an agent can go anywhere in a cell as long as it is convex because it is essentially the definition of convex. It also means that the agent is not limited to a specific waypoint network, so if the destination is out of the waypoint network, it can go directly to it instead of going to the nearest point in the network. A navigation mesh can also be used by many types of agents of different sizes, rather than having many waypoint networks for agents of different sizes.
      Using a navigation mesh also speeds up graph exploration because, technically, a navigation mesh has fewer nodes than an equivalent waypoint network (that is, a network that has enough points to cover a navigation mesh).
      The navigation mesh Graph
      To summarize, a navigation mesh is a mesh that represents where an NPC can walk. A navigation mesh contains convex polygonal nodes (called cells). Each cell can be connected to each other using connections defined by an edge shared between them (or portal edge). In a navigation mesh, each cell can contain information about itself. For example, a cell may be labeled as toxic, and therefore only those units capable of resisting this toxicity can move across it.
      Personally, because of my experience, I view navigation meshes like the ones found in most Source games.

      However, all cells in Source's navigation meshes are rectangular. Our implementation is more flexible because the cells can be irregular polygons (as long as they're convex).
      Navigation Meshes In practice
      A navigation mesh implementation is actually three algorithms :
      A graph navigation algorithm A string pulling algorithm And a steering/path-smoothing algorithm In our cases, we used A*, the simple stupid funnel algorithm and a traditional steering algorithm that is still in development.
      Finding our cells
      Before doing any graph searches, we need to find 2 things :
      Our starting cell Our destination cell For example, let's use this navigation mesh :

      In this navigation meshes, every edge that are shared between 2 cells are also portal edges, which will be used by the string pulling algorithm later on.
      Also, let's use these points as our starting and destination points:

      Where our buddy (let's name it Buddy) stands is our staring point, while the flag represents our destination.
      Because we already have our starting point and our destination point, we just need to check which cell is closest to each point using an octree. Once we know our nearest cells, we must project the starting and destination points onto their respective closest cells.
      In practice, we do a simple projection of both our starting and destination points onto the normal of their respective cells. 
      Before snapping a projected point, we must first know if the said projected point is outside its cell by finding the difference between the area of the cell and the sum of the areas of the triangles formed by that point and each edge of the cell. If the latter is remarkably larger than the first, the point is outside its cell.
      The snapping then simply consists of interpolating between the vertices of the edge of the cell closest to the projected point. In terms of code, we do this:
      Vector3f lineToPoint = pointToProject.subtract(start); Vector3f line = end.subtract(start); Vector3f returnedVector3f = new Vector3f().interpolateLocal(start, end, lineToPoint.dot(line) / line.dot(line)); In our example, the starting and destination cells are C1 and C8 respectively:

       
      Graph Search Algorithm
      A navigation mesh is actually a 2D grid of an unknown or infinite size. In a 3D game, it is common to represent a navigation mesh graph as a graph of flat polygons that aren't orthogonal to each other.
      There are games that use 3D navigation meshes, like games that use flying AI, but in our case it's a simple grid.
      For this reason, the use of the A* algorithm is probably the right solution.
      We chose A* because it's the most generic and flexible algorithm. Technically, we still do not know how our navigation mesh will be used, so going with something more generic can have its benefits...
      A* works by assigning a cost and a heuristic to a cell. The closer the cell is to our destination, the less expensive it is. The heuristic is calculated similarly but we also take into account the heuristics of the previous cell. This means that the longer a path is, the greater the resulting heuristic will be, and it becomes more likely that this path is not an optimal one.
      We begin the algorithm by traversing through the connections each of the neighboring cells of the current cell until we arrive at the end cell, doing a sort of exploration / filling. Each cell begins with an infinite heuristic but, as we explore the mesh, it's updated according to the information we learn. In the beginning, our starting cell gets a cost and a heuristic of 0 because the agent is already inside of it.
      We keep a queue in descending order of cells based on their heuristics. This means that the next cell to use as the current cell is the best candidate for an optimal path. When a cell is being processed, it is removed from that queue in another one that contains the closed cells.
      While continuing to explore, we also keep a reference of the connection used to move from the current cell to its neighbor. This will be useful later.
      We do it until we end up in the destination cell. Then, we "reel" up to our starting cell and save each cell we landed on, which gives an optimal path.
      A* is a very popular algorithm and the pseudocode can easily be found. Even Wikipedia has a pseudocode that is easy to understand.
      In our example, we find that this is our path:

      And here are highlighted (in pink) the traversed connections:

      The String Pulling Algorithm
      String pulling is the next step in the navigation mesh algorithm. Now that we have a queue of cells that describes an optimal path, we have to find a queue of points that an AI agent can travel to. This is where the sting pulling is needed.
      String pulling is in fact not linked to characters at all : it is rather a metaphor.
      Imagine a cross. Let's say that you wrap a silk thread around this cross and you put tension on it. You will find that the string does not follow the inner corner of it, but rather go from corner to corner of each point of the cross.

      This is precisely what we're doing but with a string that goes from one point to another.
      There are many different algorithms that lets us to do this. We chose the Simple Stupid Funnel algorithm because it's actually...
      ...stupidly simple.
      To put it simply (no puns intended), we create a funnel that checks each time if the next point is in the funnel or not. The funnel is composed of 3 points: a central apex, a left point (called left apex) and a right point (called right apex). At the beginning, the tested point is on the right side, then we alternate to the left and so on until we reach our point of destination. (as if we were walking)

      When a point is in the funnel, we continue the algorithm with the other side.
      If the point is outside the funnel, depending on which side the tested point belongs to, we take the apex from the other side of the funnel and add it to a list of final waypoints.
      The algorithm is working correctly most of the time. However, the algorithm had a bug that add the last point twice if none of the vertices of the last connection before the destination point were added to the list of final waypoints. We just added an if at the moment but we could come back later to optimize it.
      In our case, the funnel algorithm gives this path:

      The Steering Algoritm
      Now that we have a list of waypoints, we can finally just run our character at every point.
      But if there were walls in our geometry, then Buddy would run right into a corner wall. He won't be able to reach his destination because he isn't small enough to avoid the corner walls.
      That's the role of the steering algorithm.
      Our algorithm is still in heavy development, but its main gist is that we check if the next position of the agent is not in the navigation meshes. If that's the case, then we change its direction so that the agent doesn't hit the wall like an idiot. There is also a path curving algorithm, but it's still too early to know if we'll use that at all...
      We relied on this good document to program the steering algorithm. It's a 1999 document, but it's still interesting ...
      With the steering algoritm, we make sure that Buddy moves safely to his destination. (Look how proud he is!)

      So, this is the navigation mesh algorithm.
      I must say that, throughout my research, there weren't much pseudocode or code that described the algorithm as a whole. Only then did we realize that what people called "Navmesh" was actually a collage of algorithms rather than a single monolithic one.
      We also tried to have a cyclic grid with orthogonal cells (i.e. cells on the wall, ceiling) but it looked like that A* wasn't intended to be used in a 3D environment with flat orthogonal cells. My hypothesis is that we need 3D cells for this kind of navigation mesh, otherwise the heuristic value of each cell can change depending on the actual 3D length between the center of a flat cell and the destination point.
      So we reduced the scope of our navigation meshes and we were able to move an AI agent in our organic dungeon. Here's a picture :

      Each cyan cubes are the final waypoints found by the String pulling and blue lines represents collisions meshes. Our AI is currently still walking into walls, but the steering is still being implemented.
    • By lucky6969b
      Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
      thanks
      Jack
    • By ferreiradaselva
      There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
      Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (`uastar.c` and `uastar.h`) library: https://github.com/ferreiradaselva/uastar
      No memory dynamic allocation. Straight to the point (the README.md explains how to use).
      It's nothing biggie, but certainly useful.
      Path finder at work:

      I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).
    • By lucky6969b
      I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
      Any ideas?
      Jack
×

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!