PathFinder version1.0 now on AssetStore

​

PathFinder is a simple and easy to use A* path-finding package. The package required almost no additional work to work with other project and can be apply on almost any kind of terrain.

• Relatively good performance suitable for any game.
• Able to search thousands of nodes in miliseconds.
• Auto GridGraph Generator applicable in just about any terrain.
• Line-Graph Generator based on user hand-place waypoint.
• Configurable parameters to fine-tune the graph.
• Queue based search call so no lag spike.
• Support various option for Path-smoothing.
• Source code in both C# and JS.
• Well commented and documented exacmple code

Here's two demo scene showcase the PathFinder in action in a custom build environment and a smooth terrain with varried height. Feel free to take a look at the documentation, it should provide an idea of just how accessible it is. For more information please visit my development blog.

Finally here's a link to the AssetStore link.

Thanks for reading.

​

PathFinder version1.1 is now released. The update includes:

• Added a new graph type which is more memory and performance friendly
• Added binary heap based sorting to the search algorithm, make the search faster
• Path-smoothing has been reworked entirely
• Reorganise structure of the code
• All Example scripts has been rewritten
• C# counter part of the source and examples are now included

Here's a video just to show the path-finding in action

The scene is setup with a square grid with grid size of 0.5 over an area of 100x100. Effectively 40k nodes. A few agents in the scene is simultaneously searching for path to the point where the mouse cursor is pointing at every 0.1seconds. The colored line indicate the path determined for each agents.

 

Awesome.
I guess this is the same system in the TDTKit Right ?

 

Yes.

At it's core, it's pretty much the same system. However the one in the TDTK is a simplified version which only works in the context of the grid system in TDTK.

 

Hey just purchased this. Went to do a build on iOS to test performance. Got these errors. I understand you never said it was built for iOS devices but is there any chance these could get fixed? Really wanted to see what kinda performance the little device could get out of it . Thanks bro!


Assets/ExampleScripts/Patrol.js(58,96): BCE0051: Operator '-' cannot be used with a left hand side of type 'Object' and a right hand side of type 'UnityEngine.Vector3'.

Assets/ExampleScripts/RTSUnit.js(36,33): BCE0004: Ambiguous reference 'LookAt': UnityEngine.Transform.LookAt(UnityEngine.Vector3), UnityEngine.Transform.LookAt(UnityEngine.Transform).

 

I guess that looks nice, but why the agents in the demo get a bit jittering sometimes? (I am not refering to the physics collision between them)
Can we see the API (= functionality) somewhere?
Thanks

 

To fix, author needs to add '#pragma strict' at the top of all his code in every file, then he will find the undeclared variable types which unity is tying to assist with, a common problem. Looks as though it's a very easy thing to fix.

 

Sorry for the much delayed respond. Thank so much hippocoder for clarifying the issue. Indeed I apologize for my short-sighted code which doesn't work at all for iOS. Like what hippocoder said, it shouldn't be a big problem to fix. However I'm currently away from home for the weekend. I'll have a look at it as soon as I can.

The link to full documentation is there in the first post. I dont see any jittering when running the demo on my machine except when two agents collide. I suppose it's partly due to the over-simplified example code for the agent which doesn't take account into obstacle avoidance, and the fact that it constantly update the path without movement smoothing, if this explanation make sense to you.

 

Yes that makes sense. I have 2 questions if you don't mind.

1) How fast and easy is it to rescan the grid?
2) Is there a funtion to return the path length?

I am currently using SimplePath but for some things I want its rather not Simple since I am using JS.

 

Of course I dont mind, I'm happy to answer any question I can.

It's very much subject to the map size and the grid size, which are configurable. The scanning is done automatically during loading of the scene, specifically in Start(). For something like the demo, the scanning time is almost unnoticeable, 1 or 2 second max I recon. Fyi I'm using an i3 processor with 2g of ram.

I'm not sure what are you referring to in term of length. How many way points or actual distance in unit? At any rate, the path returned is a series of Vector3 points which makeup the path. You can easily acquire both information from that.

Hope this helps

 

Thanks for answers. Sure they helped

 

Thanks for getting back so quickly on the subject. Much appreciated!

 

Even if I use other pathfinding system, I purchased this to support it and because source is in JS. Hope I also use it in a game later on

 

@nuverian, Thanks very much for your support!

@Burletech, I've pm you regarding the fix you needed yesterday. Not sure if you have got it.

 

Hey man, I couldnt DM you anymore, says your inbox is full.
send me a DM when you removed some messages and can send a reply back

Great system, I am happy with my purchase!

-D

 

A new update (v1.0f) which fixes several bugs has been released. Please update your package!

The fixes are as follow:

• fixed bug where clustering error occur when the area specified doesnt have similar width and length
• fixed bug where agent would not go to reach the final waypoint
• fixed bug where node generation would encounter error when negative x or z value is specified in the area.
• example scripts (chase.js, patrol.js and RTSUnit.js) is now compatible with iOS compilation.

​

 

It has just come to my attention that v1.0f has contain a rather serious bug. A hot fix has been uploaded to AssetStore pending approval. My Aplologies for any inconvenience cause. Please email me if you need the fix urgently.

 

The hotfix, version 1.0f2 has just gone live at AssetStore. Please update your existing copy if you haven't already done so. Sorry again for all the trouble.

 

To fix that, I just did this:
//look at the next waypoint
var thing:Vector3 = path[0];
transform.LookAt(thing);

And

//rotate towards the next waypoint
var thing:Vector3 = path[currentPathID][wpID];
var wantedRotation:Quaternion=Quaternion.LookRotation(thing-transform.position);

 

Thanks Stradagee1.

I believe I have fixed that error in version 1.0f2.

 

I'm pleased to annouce that PathFinder version1.1 is released and now live on AssetStore. The update are as follow:

• Added a new graph type which is more memory and performance friendly
• Added binary heap based sorting to the search algorithm, make the search faster
• Path-smoothing has been reworked entirely
• Reorganise structure of the code
• All Example scripts has been rewritten
• C# counter part of the source and examples are now included

Here's a video just to show the path-finding in action

The scene is setup with a square grid with grid size of 0.5 over an area of 100x100. Effectively 40k nodes. A few agents in the scene is simultaneously searching for path to the point where the mouse cursor is pointing at every 0.1seconds. The colored line indicate the path determined for each agents.

for more information, please visit the development blog

 

great package, but could u show us how to set up a line graph type, i tried simple one with 4 nodes following your documentation but i'm getting a very dense grid when i click generate preview.

 

Hi there, thanks for using the package.

I have to say since from the upgrading from 1.0 to 1.1, lineGrid is very much being overlooked. I've just gave it a go and indeed there is some problem when it comes to the path-finding part. But there is no problem with the graph generation part. I'll get to the problem asap. As for now, I would recommend you to use Grid or AGrid.

Since the generation bit should have no problem so let's get to that. I have to ask how "dense" is the grid? You should know the each node will try to connect to every other node that has clear LOS. It should look something like this.



Please note that in the unmodified script, you will only get to see the node but not the connection. If you have anything other than this, you have probably missed something in the configuration. Those are included in the image so you can check against it with your own setting.

 

the grid was a bunch of waypoint generated all over the scene, it seems like it's not recognizing the waypoint gameobject i'm feeding it it's using a grid to generate waypoints,
it's less dense because i increased the grid size

 

Ops terribly sorry, I just did a check and you are absolutely right. Preview LineGraph doesnt work. I have been doing runtime test only that I haven't realize this.

Anyway, I've send a package to your inbox. It should contains all the fix for LineGraph. So upon import it you should be able to use LineGraph without issue. Please let me know if you have further issue. Sorry for the trouble.

 

thanks , it works perfectly now

 

A quick note, the fix for faulty lineGraph had been submitted and is now live on AssetStore. Sorry for any inconveniences.

 

Hello,

So i have a basic proof of concept working based on the sample environment - no problem.

trying to replicate this in one of my real scenes fails - it generates 26832 nodes, does the erode to optimize which basically removes all of the nodes, and I get

IndexOutOfRangeException: Array index is out of range.
NodeGeneratorC.GenerateNode () (at Assets/PathFinder/Scripts/C#/PathFinding/NodeGeneratorC.cs:199)
NodeGeneratorC.GenerateGraph () (at Assets/PathFinder/Scripts/C#/PathFinding/NodeGeneratorC.cs:63)
NodeGeneratorC.Start () (at Assets/PathFinder/Scripts/C#/PathFinding/NodeGeneratorC.cs:56)

I am using an identical layout as the demo level - a big plane as the base 'ground', with unity cubes placed to create the overall navmesh structure.

Any ideas what I might be doing wrong?

 

Here's the full log of the fail

http://gekidoslair.com/wp-content/uploads/2012/11/erode.jpg

here's the pathfinder settings
http://gekidoslair.com/wp-content/uploads/2012/11/pathfinder.jpg

and here's the scene setup - all of the objects under navmesh are in the 'pathfinding' layer
http://gekidoslair.com/wp-content/uploads/2012/11/editor.jpg

Thanx alot. This is a perfect addition to the TD kit - looking forward to showing you how these are being used ;}

 

ok even more strangeness. instead of making the pathfinding objects fresh in my new scene (they are just a default unity plane for the ground and cubes for the blocking areas), I copied pasted them from the example scene into my new scene instead.

this now works for generating the pathfinding, but when i try to get my objects moving, the 'GetNearestNodeFromNeighbourANode' function fails:

When it does the comparison to from the source.neighboursList array against the target ANode, the entry in the array that it thinks is the valid neighbour is only null entries.

I am not sure what / where I've gone wrong here.

The big strangeness is that the exact same scripts are working fine in the other scene, just something is going wierd with the pathfinding generation.

Ideas?

 

ok fixed it, but still not sure what the problem was.

instead of trying to rebuild the pathfinding in my existing scene, i decided to copy the environment setup from my old scene into the test scene and modify the pathfinding from there - and now it works.

very strange.

 

Hi gekidoslair,

Thanks for using the package and sorry for the delay. I've been on travel and will continue to do so, so my respond speed is going to be a bit slow. Very sorry for that.

The first thing that I notice from the 'setting' image you sent me is that you have left the walkableLayer unassigned on NodeGenerator. It should have been assigned with the layer you set for the ground and whatever environmental object in the scene. If you look at the example scene carefully, all the objects has been set to layer8 and layer8 has been assigned to NodeGenerator as the walkable layer. The failure of doing so result in the NodeGenerator failed to locate any walkable surface and thus none of the node generated is walkable, which in turn leads to the error you are getting, none of the node generated are walkable. Simply named layer8 to something and you'll see.

I know by default the import of the package doesn't include the layer or tag information so it is a bit easy to be overlooked. Sorry if I didn't make this clear enough in the documentation.

Hope this solve the problem.

 

Hey Songtan,

So I've been doing some additional experimentation with the kit - does the kit only work with default unity cubes / terrains or is it possible to use a custom mesh ? In my experiments so far, the pathgeneration seems to just ignore the custom navmesh that i've built (but it generates navigation chunks fine for the cubes that i'm using for building / blocking areas.

Thanx,
Mike

 

Does the custom mesh have any collider on it? The nav-graph generation is based on collider on gameObjects with the specific walkable layer. As long as the mesh have a collider, it should work. So I suspect the problem is there isn't any collider on the mesh you are using.

 

doh - you're right - that's exactly it. knew it was something simple ;}

thanx again - the pathfinding system is awesome, so nice and simple to integrate (compared to any of the other options).

 

Thanks for your kind words. Glad it helps!

 

Hello songtan,

I just purchased this. I am using your block JS example and I would like the "chase" agent to chase a First Person Controller with the name "Player" instead of the mouse cursor. How do I do this?

 

Hehe I just bought this package and came on here to see if someone had asked that exact thing.

 

I know SongTan is away for sometime so I hope he can help me out once he has returned.

My goal:
I want an agent to patrol between his waypoints, but once he sees the player he has to stop patrolling and chase the player instead. Once the player is out of sight, the agent has to return to his patrol.

What I tried:
1) In the Patrol.js I have added the following variables:

Code (csharp):

1.  
2. var player:Transform;
3. var MoveSpeed = 4;
4. var MaxDist = 10;
5. var MinDist = 5;
6. var canPatrol : boolean = true;
7.  

2) I have dragged the first person controller (named Player) onto the "player" variable.

3) In the Update() function I have written a check whether the agent sees the player or not:

Code (csharp):

1.  
2. //can enemy see the player?
3. var hit : RaycastHit;
4. var rayDirection = player.position - transform.position;
5.    
6. if (Physics.Raycast (transform.position, rayDirection, hit)) {
7.    
8.      if (hit.transform == player) {
9.          //enemy can see the player!
10.          canPatrol = false;
11.      } else {
12.          //there is something obstructing the view
13.          canPatrol = true;
14.     }
15.  
16. }
17.  

4) In the Update() function you already have an if statement "if(path.Count>0){". What I did is use my check there:

Code (csharp):

1.  
2. if(canPatrol == false) {
3.     //chase player
4.     transform.LookAt(player);
5.  
6.     if(Vector3.Distance(transform.position,player.position) >= MinDist){
7.          transform.position += transform.forward*MoveSpeed*Time.deltaTime;
8.     }
9.            
10.     if(Vector3.Distance(transform.position,player.position) <= MaxDist){
11.          //Here call any function like shoot or something
12.     }
13. }else{
14.     //execute SongTan's code
15.     if(path.Count>0){
16.     ...
17. }
18.  

Now when you play this, the agent will do his regular patrol, until he sees the player. Once he sees the player, the agent stops patrolling and goes directly to the player. However, my problem is that I do not know how to tweak my code so he also uses the pathfinding system, as my code doesn't.

Please help!

 

Look at the RTS example for trying to figure out a path to your player once they are spotted. Basically find the destination (the player's position) and then call 'SearchPath' to find a path.

Then in your update routine, you cycle through the pathpoints and translate the agent along his way.

 

Hi, I don't have any RTS example. I only got:

linegrid
block JS and C#
terrain JS and C#

I will give what you said a try, although it really ain't easy for me.

Right now I have the position (Vector3) of the player and my next step is to get the agent to move towards me using the pathfinding system. At the moment it's already drawing a line from the agent towards the player and chasing it. However, once I run away around a corner, things like this happen:



I kind of copied a few lines of the waypoints part and defined their own variables. Code:

Code (csharp):

1.  
2. //find and chase player
3. transform.LookAt(player);
4. var playerObject = GameObject.Find("Player");
5. var playerPos:Vector3 = playerObject.transform.position;
6.    
7. //rotate towards target, make sure it faces the destination before reaching it.
8. var dir2:Vector3=playerPos-transform.position;
9. //make sure the vector is not zero so we dont get the look vector error from LookRotation
10. if(dir2!=Vector3.zero){
11.     var wantedRotation2:Quaternion=Quaternion.LookRotation(dir2);
12.     transform.rotation=Quaternion.Slerp(transform.rotation, wantedRotation2, Time.deltaTime*15);
13. }
14.            
15. //calculate the distance between current position and next waypoint
16. var dist2:float=Vector3.Distance(transform.position, playerPos);
17.  
18. //move towards the waypoint,
19. //take the distance into consideration and limiter to how far the agent can move so it  wont overshoot it's destination
20. var direction2:Vector3=(playerPos-transform.position).normalized;
21. transform.Translate(direction2 * Mathf.Min(dist2, moveSpeed * Time.deltaTime), Space.World);
22. SearchPath(playerPos);
23.  

 

Hello all,

Sorry for being away.

I would modify the example script itself for the purpose requested by derrtyones. Instead of tracking the position pointed by the mouse cursor, the agent should track the target directly. To do that, simply change the function CustomUpdate in the example script to following:

Code (csharp):

1.  
2.  
3.     //the target transform, assign in inspector
4.     public Transform target;
5.    
6.     // Update is called once per frame
7.     IEnumerator CustomUpdate () {
8.         yield return new WaitForSeconds(0.1f);
9.         gridSize=NodeGeneratorC.GetGridSize();
10.         while(true){
11.             //only search if the target has moved
12.             if(Vector3.Distance(target.position, currentDestination)>gridSize*1){
13.                 //if we havent call for a search
14.                 if(!searching) SearchPath(hit.point+new Vector3(0, agentHeight/2, 0));
15.             }
16.            
17.             //wait 0.1s instead of every frame, it's more efficient but the delay should be un-noticeable
18.             yield return new WaitForSeconds(0.1f);
19.         }
20.     }
21.  

notice I also added a public variable target, that should be assigned in Inspector.

Please note that I havent test this out. Please let me know if there's any problem.


Song

 

Hi Song,

Really appreciate the help! Your code does not work (or I am doing something wrong!).

I get errors on the following lines:

Code (csharp):

1. public Transform target;

Assets/PathFinder/Scripts/JS/Examples/Chase.js(6,16): BCE0043: Unexpected token: Transform.

Code (csharp):

1. yield return new WaitForSeconds(0.1f);

Assets/PathFinder/Scripts/JS/Examples/Chase.js(47,18): UCE0001: ';' expected. Insert a semicolon at the end.

Error above is shown twice.

I have used the chase.js file.

Is it possible if we could work towards what I requested earlier? So that the patrol agent does his patrol, but if he sees the player he stops patrolling and chases the player instead until the player is out of sight, causing the agent to go back on patrol? That would be a dream!

 

oh, silly me. I forgot that you are using js, not C#.

please change the line in question to:

public var target:Transform;

and

yield WaitForSeconds(0.1);

respectively.

Please give me sometime. I'll work on that as soon as I'm back to my work place and got some time. Should be sometime around next week.

 

Hey no problem at all, I can wait. Just post here once you got time somewhere next week and we can work on it.

 

@derrtyones, I've just send a download link contain the new scripts which should work as you describe. Please check it out.

 

Christmas/New Year sales! Currently at $25 down from $35. Limited duration only! Get it while it last!

Sorry in advance for the shameless plugging.

Have a great holiday season!

 

Hi, I just purchased your product which looks very impressive so far. I am designing a game which allows characters to walk as well as ships to fly around the terrain. Obviously, your product will work great for the walkers but in looking through the code, I'm not sure about the flying characters. Have you given this any thought or do you have any suggestions?

-Tim

 

Hi Tim, thanks for your purchase! The question would be how do your flying character works? Do they have to avoid any obstacle? at all? If that's the case, you dont need to search for a path at all. simply go straight to the point. If not, how are they differ from ordinary walking character?

 

Hi and thanks for the quick reply! My flying characters need to navigate around a variety of terrain and static structures. I guess it would be kind of like a helicopter having to fly through a city filled with high rise buildings. Not all of my buildings are super tall, but one for example is about 300m scale height. My terrains vary from flat to very mountainous (max ~600m scale height peaks) so using my current home grown steering AI, my ships detect all of the obstacles, and mostly avoid them but the result is sometimes erratic, unnatural movement and changes in velocity and direction.

I guess you can think of my flying characters as like bees, as they are primarily ships that hover which will come and go from a central building, carrying supplies, patrolling for enemies, building new structures and repairing damaged structures. Because I can't control what structures the player puts where, a "straight to the point" approach will not always work.

One way I can fudge it for now is to increase altitude to like 700m at take off, and then fly to a waypoint above my actual destination point and then descended nearly straight down to my destination point. This will work but I just thought it would be more visually pleasing/realistic to see the ships navigating smoothly around and over the structures at a narrower altitude margin. I'm sure you have seen a helicopter land, it usually doesn't just hover over something and then drop 700m straight down.

-Tim

 

The easiest solution that I can think of is using path-smoothing algorithm that take accounts of the path height(altitude). By default, the path-smoothing algorithm assume the agents will be traveling just above the surface so all obstacle will always in the way. What I can do is write a similar path-smoothing algorithm, only the altitude value will can be passed and used as an height offset to all the waypoints. This way, higher building will continue to block the path but lower building can be by-passed.

The problem I can see now is that you mention in your game, player will build new structure which will impact the map in runtime. But the path-finding component doesnt support changes of navigational graph in runtime. That means you can add new obstacle n run time and expect that will be taken acount into the path-finding automatically. It cant do that, at least not at the moment. I've been thinking adding the feature but frankly, it's not a straight-forward task and it might take some time.

Anyhow, I can at least work on the altitude dependant path-smoothing, that should be pretty straight-forward. But please understand that I have some other commitment that I must full-fill first before I can tend to this. So please give me some time to do that.