Assets K-PathFinder

Asset Store: https://www.assetstore.unity3d.com/en/#!/content/85181

Hello! For some time im working on my own implementation of navigation mesh.

I started it cause no other navmesh do what i want. And kinda cause i want to know how it work and how to write code. Now i have somewhat working prototype and wanna to share it, get some info, advices, etc.

So. My goal was to make global chunk grid like Unity does but retain ability to disconnect chunks and redo it if needed. All chunks must be computed in threads as much as it can so "redo" operation can be done while playing. Also i wanted to have different areas and some sort of jump connections.
And it kinda doesn't matter how much memory used while computing each chunk cause it imited by amount of processed chunks at same time. So i make temporary information storing kinda bad but rich as possible and it's became easy to add features.

Current features list:

• Different passability. Right now areas are optionaly divided to "walking" and "crouching" but it's not hard to add somthing like сlimbing or crawling or whatever.

• Different areas. It speaks for itself. Areas have different cost and it's cool stuff. I have global dictionary whith areas and gameobjects can generate own areas so potentialy have reference to navmesh through GO component to pass info back and forth. Also i add ability to associate areas dictionary to splat map on terrain so it can be just painted this way and it knida works very good.

• Multiple layers of navmesh. Navmesh can have multiple "floors" stack on top of each others.

• Jumping spots. Right now just up and down and it kinda suck but it works. I added concept of different type of "area". where one voxel can "capture" voxels around it and this type of areas can be passed to outline edges of navmesh if it have "captured" voxels in proximity. So i have lots of "jumping spots" and work around that. Right now jumping spots try to generate landing spots near them. Later on will expand this.

• Grid. It's kinda userful to have set of reachable points in proximity so these points can be tested to line of sight or distance to enemy or whatever.

• Covers. If just cover needed navmesh can generate cover planes in proximity to obstacles. It's actualy just reused Marching Squares and Ramer Douglas Peucker algorithm with different information. Right now there is low and high covers.

• Redo chunks. chunks can be disconnected and generated new one so navmesh can be partialy updated.

• Mupliple agents types support. Agent properties is key to graph dictionary inside chunks. So there can be multiple navmeshes for different agents. Also navmesh are can have different resolution.
  
• NavMesh Raycast. You can check visibility on navmesh for changing Area or just hole in graph.
• Local Avoidance. Agents move around and avoid each others. Cool stuff.

Questions:
Also is there some good way to get z-buffer as float array from camera? Right now i can only rasterize triangles of mesh wich plased on collider space. Much like Rain does. But it will be cool if i can use z-buffer from camera to do rasterization part.

Any advices or requests?

 

No discussion, just likes? Is fine too.

Last days working on fixing bugs and somewhat optimisation.


Also tried to create navMesh on bigger map and it's woking fine.

 

Finaly i can start working again. Last past days i spend on optimisation and bugfixing. Not much optimisation though in term of perfomance gain.
In prototype every voxel was object, now it's just lots of 2d arrays with some data so a lot less GC hiccups. Redone lots of code, also change how height stored. Prevoiusly it was int * voxel size, now it is just float. Expecting to release navmesh before end of this month.
Planing to spend time to up readability of code.

Some cool looking bug

 

Your AI movement looks very good. Especially turning and strafing. Does it use root motion?

 

So a nav mesh can be generated at run time with this?

 

sorry i a bit underestamate time to finish navmesh. I did not have time to finish it and finaly when i have it i caught a cold. But i done lots of work to make it more robust. Right now working on serialization.

Thank you. Yes it is. Actualy it is combination of root motion and some rails. Where red-blue-green lines there is stop sequence and it done by rails cause root motion are not good for precise movement and i want to tell where exactly i need to stop. Rest of movement actually fairly simple. I made array of values wich changes over time with linear speed and this values are responsible for XZ movement speed, rotation on movement, rotation animation while standing and aiming IK speed (yes i limit that). Actialy biggest challange was to sync AI ticks and animation timing so AI know when it can move or when it pick up somthing and movement are blocked or when some animation already active and it cant do other animation. I probably create thread to show this a bit later.

yup. pretty much it was main goal from the start.
in main thread are:

• chunk creation. it needed to tell where to find colliders, but it can be skipped if you tell it by creating chunks from start.
• creation of "template" to create navmesh. info gathering stuff. colliders, position, rotation, key components, tags, etc. fairly quick. a bit slower for terrain but i have idea how to improve this.
• connection of finished graph to whole navmesh and some last operations like jump spots checking.
  
• disconnection of graph inside chunk from navmesh.

rest are not in main thread.

 

Finaly. Today i submitter to asset store currents state of navmesh. "Expecting to release navmesh before end of this month." was WAY too optimistic. When i start implement sort of serialization i find out lots of odd things. In the end i scrap whole set of classes that store connection data and spend lots of time fixing it. Then when i start testing on large terrain using different resolution settings i find out another set of bugs. This time in triangulator class. Then i also scrap it. Redone lots of things. Think it was worth it.
Also add another method to gather voxel height on terrain and fix lots of things related to terrain. Now things really can be threded.



Also find out Unity have a strange method to deal with terrain from physics perspective. Before this i collect colliders using Physics.SphereCast and store collieds to hashset so only one collider allowed from all casts. Now unity have BoxCast. I thought "Yay! they finaly add this!" and use it and it was fine. Until i check it in playmode. Find out in editor mode it return only one collider as expected. But in playmode it also return Terrain collider for every tree it hit.



Hope now i can spend a bit more time with another project

 

Yay! Finaly this was published! Link are on top.

 

I made small update. now PathFinder is 0.33 version. I have very small feedback so i dont really know what people want. Currently work on some optimisation.



Changelog 0.3 => 0.33:
Whats new:
* Changlelog
in changelog.txt

* Navmesh Raycasting
There is now simple navmesh Raycasting. You can call it using PathFinder.Raycast() function. It's a static function and there is no stuff in thread.
It return RaycastHitNavMesh struct where contain point, and some flags about "if we fing navmesh below at all" and if it reach max iterations while searching. Intend to use it to test navmesh "if there is space to dodge" but will probably have lots of cool uses. A bit ugly inside.

* Agent now have threadsafe recieve info delegates:
It now have "AgentDelegateMode" and it can be threadsafe or not threadsafe. All current functions related to this now have this parameter.
Default are AgentDelegateMode.NotThreadSafe. So nothing will change if you dont want.
Threadsafe called in Update so it's can be a bit delayed (you can somewhat fix delay by changins scrip execution order)

* BattleGridPoint now contains field "passability" where it can be Crouchable or Walkable.
In case you want to take passability into account.

* Debugger are now Debuger_K
cause anyway all people write their own debuger and this word is too common. Namespaces dont help much to fix that.

* You can now disable NavMesh generation (lol)
If you just need covers or battle grid then here you go. Save up some processor time cause lots of code skipped in that case.

* "Debug Paths" checkbox in Debuger menu to enable or disable debuging of paths.
Cause there was not option to stop debuging it. And we end up with lots of stuff being debuged even if you dont see it

* PathFinderAgent.SetGoalGetBattleGrid now have (params Vector3[] positions) to request grid from multiple points at same time
Will request it's own position if you left it empty

*Bunch of internal changes. More important ones:
Point on graph search now alot faster.
New class dedicated to combine cells into graph. Cause lots of stuff in graph have no use after it was generated. This stuff moved into this class.
There is now no "Edge" is cells. It was replaced by struct witch represent two points.
There is no "Nodes" in cells and graphs.
Internaly jump points up and down stored in one class.


Whats Fixed:
* Battle grid now connect more properly on border if there multiple levels

* NodeCoverPoint.normalV3 now Vector3 (was Vector2)

* Covers wount generate on top of objects if there another cover nearby

* NodeCoverPoint now reference Cover it belongs as intended and dont throw exeptions

* Serialized data will no longer loaded twice

Whats Broken:
* You definatly can't load old serialized data with new version. So clean it and redo navmesh.



Brobably broke lot's of stuff cause internal changes was a bit big. And probably broke some parts of serialization.

 

hi nice work,
maybe jump through platform and multi level pathfinding ( i mean like generating patfinding in a building with more than one floor) will be great.

I'll try it later

(my english is bad also )

EDIT: Just forgot some idea, crowd control (like alternate route when someone blocking my main route) usable for ai in a crowd area

 

I have no clue what you mean! One solid object cannot go through another!

It's already are. I'ts split all into multiple 2d voxel maps but they still connected to each others so it's work just fine.

I planing to do this also but this will be tough. Think there is 2 ways to do this. Like A* does (or i think it does) split all into grid and check path also on grid. Or hard way: implement dynamic obstacles, make triangulation really fast, then just carve area around agent so only this agent can use this area and no one else. First one i dont really like but easy to implement and second will be painful.

Currently i spend some time with shaders and somewhat understand it now. Planing to reimplement rasterization on Compute Shaders to accelerate it a bit. Then probably try to reimplement triangulation on Compute Shaders and then will try to implement dynamic obstacles and suggested idea. Or as usual implement both easy and hard way and see which better.

 

Could you add cover agent for the next version like above video ? Thanks in advanced.

 

Wich one video?

Scene from showcase are already in project and you can see how it's implemented. I will put some code from it to default agent and add function like "get some points, find best point and get path there" to simplify it even further. With some cases like sampling points are only near covers or sample just cover nodes.

If "Unity AI strafing shooting and move to cover" there is nothing particulay intresting cause there is mostly same implementation of finding cover point.
Also couple people ask me to show implementation of strafing and i actualy did https://www.patreon.com/posts/example-of-8813692

 

Yes, its "Unity AI strafing shooting and move to cover" video. In the next update, could you make a example scene that have a agent like agent in this video ?

 

Sadly after new patch everything broken. Somtimes agent can find the path, sometimes he won't.

 

Spend some time with compute shaders and shaders overall. Get some cool experience.
Now debug are based on ComputeBuffer and fast. Rewrite rasterization on compute shaders and now it also can be somewhat fast but there is some place to improve. (how people even do it? there is like none debug tools and documentation is some kind of sacred knowledge) It now do this for lots of pixels and lots of triangles at same time. In like 0.5ms.

A bit burned out. Weather suck, feel sick. Found some strange bugs that i cant reproduce.

Actualy it's just two things i given glued together. But okay i spend some time to make example as seaprate project and will put link in this thread.

Oh. Okay. Probably it cant properly find nearest point to navmesh in some cases when multiple levels. I spend time to test it more and will fix it.

 

Now i also add Compute Shader version of terrain rasterization and also done some optimisations in that part.

Probably should now consider to retrive data from GPU in better way cause now bottleneck is moving data from GPU.

Now when i start using GPU more and start also profile it. I start getting something i did not expect.
Any idea why it is?

Oh silly me. I totaly forgot to test areas by distance at all and just grab first find. Cause i test it on 2D only. That embarrassing.

You can fix this if you go to PathFinder/Generation/Graph/Graph.cs find function GetClosestCell(Vector3 pos, out Cell cell, out bool outsideCell, out Vector3 closestPoint) and change it to that:

Spoiler: Code

Code (CSharp):

1.  
2.         public void GetClosestCell(Vector3 pos, out Cell cell, out bool outsideCell, out Vector3 closestPoint) {
3.             cell = null;
4.             closestPoint = Vector3.zero;
5.             outsideCell = true;
6.  
7.             //if true then no result
8.             if (empty || _map == null)
9.                 return;          
10.            
11.             float s = PathFinder.gridSize / PathFinder.cellGridSize;
12.             List<Cell> mapChunk = _map
13.                 [Mathf.Clamp((int)((pos.x - chunk.realX) / s), 0, PathFinder.cellGridSize - 1)]
14.                 [Mathf.Clamp((int)((pos.z - chunk.realZ) / s), 0, PathFinder.cellGridSize - 1)];
15.  
16.             float sqrDist = float.MaxValue;
17.  
18.             //search cell in chunk are inside chunk
19.             if (mapChunk.Count > 0) {
20.                 for (int i = 0; i < mapChunk.Count; i++) {
21.                     Vector3 curClosest;
22.                     if (mapChunk[i].GetPointInsideCell(pos, out curClosest)) {
23.                         float curSqrDist = SomeMath.SqrDistance(pos, curClosest);
24.                         if (curSqrDist < sqrDist) {
25.                             sqrDist = curSqrDist;
26.                             cell = mapChunk[i];
27.                             outsideCell = false;
28.                             closestPoint = curClosest;
29.                         }
30.                     }
31.                 }    
32.             }
33.  
34.             //if there was result then here it is
35.             if(cell != null)
36.                 return;
37.  
38.             //if there is no result then search it by checking all contours that represent hole in graph
39.             foreach (var pair in _contourLib) {
40.                 Vector3 curNearest = SomeMath.NearestPointOnSegment(pair.Key.a, pair.Key.b, pos);
41.                 float curSqrDist = SomeMath.SqrDistance(curNearest, pos);
42.  
43.                 if(curSqrDist < sqrDist) {
44.                     sqrDist = curSqrDist;
45.                     cell = pair.Value;
46.                     closestPoint = curNearest;
47.                 }
48.             }      
49.         }
50.  

 

It is possible to do 3D navigation? Like a 3d space fighter game where AI will move while avoiding astroid and other ships etc.

 

Changelog 0.33 => 0.37:

Whats new:
* ComputeShader rasterization
You can now get voxels using ComputeShaders. This GPU magic are fast and have some pros and cons.
Pros:
It's fast.
Cons:
It's can hit perfomance if you do it in big chunks.

Options to control it are in Menu. Just below threads options. It's separated for terrain and for other colliders. Also in that menu presented old options. "Precise" renamed to "UnityWay" and "Fast" renamed to "CPU". Also there is tooltips for this options.

* Minor optimisations here and there. Terrain CPU rasterization is now much faster.
Overal around 20% speed increase in navmesh generation

* Rewrited big chunk of Debuger.
Now it uses shaders and StructuredBuffer to debug point, lines and meshes. It's much-much faster.
Pros:
Speed.
Now you can see debuged stuff in scene.
Cons:
No more color picker.
Cant be updated to often.
You see debug in scene and game window and can't separate it. (but still can turn it off)
Require DX10 (i think)

Also since when new data debuged it need to recreate StructuredBuffers. There is now button to "Update" debuged things manualy and checkbox to auto update when new data coming in. If you debug voxels you might want to turn off auto update cause it's moving ALL voxels to GPU every time it get voxels.
There is now checkboxes to enable and disable some info groups like "Cells" or "Voxels"

* Agent Properties now have button to set target chunk resolution to make sure it at least have sellected amount of voxels per agent radius. Recomend 2-3.

* Debuging path are now also debug end point and cell
To make sure nearest point on navmesh are what you expect it to be.

Whats Fixed:
* Finding nearest point to mesh now return correct position on multiple layers of navmesh
* Saving data no longer cause exeption if there was no pathfinder helper yet in scene
* Loading non existed data no longer cause exeption
* You no longer need to rebuild project after you start using pathfinder in new scene
* VolumeContainer will no longer get error related to growt of obstacles when crouch enabled


Whats Broken:
* Probably triangulation was a bit broken. So can be new awesome errors in navmesh generation

Nope. Well at least with current state of this project.

If talk about navigation overall then yes it's possible to do 3D navigation and it's have lots of approaches. For 3d space fighter i recomend just avoid things at some safe distance. Recomend to read about Reciprocal Velocity Obstacles (RVO). It can be applied to 3D.

 

hi I have started using your pathfinding solution today so I downloaded it and went to the test scene you included and when the play mode is first the agent doesn't move 2nd I get this error: there was 100 iterations and still no graph. are you trying to find path in middle of nowhere? if u r so smart than increase up number

 

Well thats unexpected. Cause for sure i tested it on two different PC's in empty project. This error will occur if there was over 100 failed iterations of search nearest non empty chunk.
My best guess is: In agent properties there is option to include or exclude physics layers into navmesh generation. Unity probably fail to deserialize it for some reason. (Maybe adding or removing layer cause that?)
Try check agent properties asset.

Is Default are enabled in your case? Also check terrain. Is it also on Default layer?

Or maybe whole properties was failed to deserialize. Is numbers in your case look reasonable?
Rest will probably be fine if there is no other exeptions.

Also couple times unity fail to deserialize whole project and even fail to load settings. Is pathfinder main menu loaded without errors? Is there first two default areas in it?

 

This a great navigation mesh, keep it up. I was wondering if you could work on some documentation or a video on how to add this asset to a project? The example scene is very helpful, but still pretty hard to add to an existing project.
I also wanted to make sure if this asset would work fine on mobile as well.
Thanks.

 

Thank you. Sadly currently i dont have much time to work on my projects. Life if harsh for me right now. But i'm still working on this project so it will become better Currently working on PathFinder and my main project to test PathFinder in real environment cause whole project have big lack of testing. My current goal in PathFinder is make better triangulation cause it work for now but it still can fail when vertices aligned like that

It can be fixed if i firstly apply something like combination of ramer-douglas-peucker and funnel algorithm so all vertecies for sure will be connected sequentially but only on one side. Or find some kind of way to reliable test edges before add them to navmesh if they cause this trouble. But current approach are slow as hell right now (currently triangulation is 50-80% time of work) and will become slower if i do that and i don't see good way to optimise it. Also big problem is transfer it to compute shaders. But current method is kinda good cause after generation navmesh need very little cells merging and for sure navmesh have lowest number of cells to reduce path search time.
Currently i'm implementing sort of limited delaunay triangulation in my main project but i will try to apply it to PathFinder to fix that problem. Or at least have another option to triangulate navmesh if it fail first time.

But it will take some time to fix current approach or find another one.

Documentation and videos i need to expand. Yeah. PathFinder are actualy dont have much types of work but it have multiple approaches to do same work. I can imagine it can be very confussing. Will make vote pool to know what users want. Bug fixes or expand documentation or little of bouth.

I tested it on my phone right now. In my case compute shader rasterization seems dont work. But rest is fine. With CPU rasterization example scene work as expected.
So i guess it's work almost fine on mobile.

 

Great! Thanks for your detailed reply. Just one more thing, is it possible to use this asset in a 3d environment by giving it a position, instead of clicks? For example, a NPC is on point A, give the asset a position (x, y, z) to point B and it would work the same as a click (finds it's path to point B)? Sorry if this seems obvious, but I didn't have the time to test this asset outside of the example scene.

 

Sure you can PathFinder are just provide asked information when you ask it.
For path it is done by using PathFinderAgent.SetGoalMoveHere(Vector3 destination, bool snapToNavMesh) and return requested path to agent when it's done.
Or by using PathFinder.GetPath(PathFinderAgent agent, Vector3 target, bool snapToNavMesh, Action callBack) if you want to use it outside PathFinderAgent and provide some extra callBack.
Implementation of movement and when information should be generated is up to you. Cause for sure there is lots of approaches to do that.

Probably i should make another method which have starting point input. Currently it is PathFinderAgent.position and it is virtual so you can override it if you want to.

 

I tested the navigation mesh quite a bit using my existing project and I found some "bugs" (might not be bugs really).

1. The character will usually get stuck at the edges of trees and bushes (I noticed that you didn't add AreaGameObject to trees, so I did the same; can you please explain when it's needed exactly?). I can send you some of the trees and bushes I am using, if you want to try them.

2. The character wouldn't actually start walking for a bit of time (SetGoalMoveHere took 22-30 frames to start registering the nextPoint, in lower fps that's a problem).

3. The character wouldn't keep moving straight even if there is nothing in the way. (might have something to do with 2, since it reacts slower).

4. Line 430 in PFDebugger will give a NullReferenceException (PFDSettings not set) if none of the debugging classes were added to the project.

The code I am using (not including running and so on):

Code (CSharp):

1. //set goal of NPC to player
2. pathAgent.SetGoalMoveHere(player.position, true);
3.  
4.                         if (pathAgent.haveNextPoint && Vector3.Distance(transform.position, pathAgent.nextPoint.positionV3) < pathAgent.properties.radius)
5.                         {
6.                             pathAgent.RemoveNextPoint();
7.                         }
8.  
9.                         if (pathAgent.haveNextPoint)
10.                         {
11.                             moveDirection = new Vector3(pathAgent.nextPoint.x - transform.position.x, 0, pathAgent.nextPoint.z - transform.position.z).normalized;
12.                         }
13.  
14.                          animator.SetBool("walking", true);
15.                          rbody.velocity = moveDirection * 5;
16.  
17. if (pathAgent.haveNextPoint && moveDirection != Vector3.zero && direction.magnitude > 1.5f)
18.                 {
19.                     transform.rotation = Quaternion.Slerp(transform.rotation, Quaternion.LookRotation(moveDirection), 5 * Time.deltaTime);
20.                 }
21.                 else
22.                 {
23.                     transform.rotation = Quaternion.Slerp(transform.rotation, Quaternion.LookRotation(direction), 5 * Time.deltaTime);
24.                 }  

I also have PathFinderScene in the project. Is that needed?
If you want me to upload some gifs of the bugs let me know.

 

Character probably can stuck if tree are too large, will fix it in next version. Unity stores trees as instances inside terrainData and it can only have vertical capsule collider. Capsule are have a bit heavy geometry (550 verticies and 2496 triangles) also it have bottom half-sphere wich most time are just dont do anything or confuse cover generation.
So i cheat a bit. I replace capsule to octogon with 8 verticies and 6 triangles, place it to top part of tree and after rasterization i replace terrain voxels to tree voxels.

Result became far more reliable for cover generation and faster. Guess i need to test it with bigger trees and bouble check if it scales properly.

AreaGameObject are component for not-terrain gameobjects if you want them to have not default Area.
For example if you want to make some gameobjects non-walkable but still participate in navmesh generation. For example top part of gate definitely should not be accessible for AI so i make it not walkable. Or five cubes under rebuild example also serve only as obstacles.

Also cubes under gate are not just colored differently they also have different areas. Left are most acessable. Right 2 times less accessible than left. And middle are 20 times less acessable then left. So AI most time will go on left cube and maybe go on right cube and will avoid central.


TerrainNavmeshSettings are do same thing but for splat map.

That unexpected. Is navmesh exist before you use SetGoalMoveHere? Cause if not then it firstly build navmesh then find way on it and this take some time Some sort of video or scene or whatever are will be helpful to resolve this. Also you can check when Agent recive path with something like that agent.SetRecievePathDelegate((Path path) => { Debug.Log("i recive path " + path.count); }); maybe there is just some delay in AI so it dont know path already exist and it can use it.

Yeah i know that. Cause path are exist as graph where nodes are connected with "gate" line. So it tends to stuck on this line border if it too far from cell centers. This also was problem in older unity navmesh. It actualy can be fixed if i test visibility of node using navmesh raycasting but i firstly want to fix generation and then add navigation features.
For now if you really needed then you can fix it in some degree on you own if you use PathFinder.Raycast on next after next navigation point and ignore it if no obstacles were hitted.

Should say debuger are big part of this project You can add it, it won't exist in builded project anyway. There is lots of #if UNITY_EDITOR in this project. Also i think all files of debuger are in editor folder so they also will be excluded.
Finction for 430 line are update graphics of pathfinder. You probably can avoid this error if you disable all debug and close menu.

Yes this is important part. It automaticaly added when you use PathFinder. This class do two things:
1) execute Unity API in coroutines. Also it's gameobject where rasterization in compute shaders are executed.
2) hold reference to saved navmesh. there is no dictionary scene:navmesh, navmesh are simply goes to this object if it exist. You can swap or copy saved navmeshes in that object if you want.

For debuger are also separated object exist wich serve same functionality. You can actulay change name for it if you click on DebugerSettings.asset. For example you can change it to _pathFinderHelper and place it on already existed gameobject so it will stop create separated object to it's own.

It will be helpful. At least i can explain whats going on or troubleshoot issues.

 

I used the Debug line you gave above, PathFinderScene gets initialized then after around half a second or so the paths start showing.
Also waiting few seconds before calling SetGoalMoveHere, but it doesn't make a difference, so I assume it's not about building navmesh.

I took some gifs and uploaded them: https://drive.google.com/file/d/0B7v_WndMktZsUnlkVGYzYWtnWGM/view?usp=sharing

If the character is using walk animation but not moving, that means SetGoalMoveHere was called, but pathAgent.haveNextPoint is false (as shown in the code I sent before).

For additional testing you can use the code I gave above and direction is just player to character position:

Code (CSharp):

1.  
2. direction = player.position - transform.position;
3. direction.y = 0;
4.  

 

Actualy probably are. Navmesh are not builded automaticaly on start, there is only 2 cases when it build:
1) You tell Pathfinder where to build by using PathFinder.QueueGraph or buttons in menu.
2) You tell Agent to get some information around it. And then if no navmesh build it build and then get requested information.

Try enable debuger options to actualy see navmesh. Also try in start use something like PathFinder.QueueGraph(new Bounds(transform.position, Vector3.one * 50), myProperties); so pathfinder actualy build some navmesh arround it.

 

Calling QueueGraph in Start fixed the issue, thank you.

 

Oh silly me. I test out this part and figured out issue. Turns out that i forgot to apply tree prefab capsule collider offset to tree instance. So hole are generated on actual tree instance position and not it collider.
If it important you can fix it if you go to
ColliderCollectorTerrainAbstract.cs then go to
public List<Bounds> GenerateTreeBounds(Terrain terrain)

find place where bounds are generated and change it to that.

Spoiler: Code

Code (CSharp):

1.  
2.                 if (z < minZ || z > maxZ)
3.                     continue;
4.  
5.                 Vector3 size = prototypeBaseColiderSize[instance.prototypeIndex];
6.                 Vector3 center = prototypeBaseColiderCenter[instance.prototypeIndex];
7.                 float widthScale = instance.widthScale;
8.  
9.                 Bounds bounds = new Bounds(
10.                     new Vector3(
11.                         x + (center.x * widthScale),
12.                         instance.position.y * dataSizeY + terrainY + (center.y * instance.heightScale),
13.                         z + (center.z * widthScale)),
14.                     new Vector3(
15.                         size.x * widthScale,
16.                         size.y * instance.heightScale,
17.                         size.z * widthScale));
18.              
19.                 treeBounds.Add(bounds);
20.  

Also find out that hole are to small cause i use wrong parameter from bounds.

This can be fixed if you go to
protected Volume CollectTrees(TerrainColliderInfoAbstract terrain)
and change where matrix are generated from bound to

Code (CSharp):

1.  
2. Matrix4x4 m = Matrix4x4.TRS(bound.center, Quaternion.identity, new Vector3(bound.size.x, bound.size.y * 0.5f, bound.size.z));
3.  

It will fix this issue for now. In next update will made more elegant way to fix this.

Thanks for pointing to issue!

 

Trees now work great thank you.
There is another similar bug, Ai gets stuck in bushes and rocks that use Mesh Colliders and have a None walkable AreaGameObject (not created by terrain brush).

 

I also found a null reference exception (PathFinderMain line 846) when the Ai was passing into the second terrain, even though the other terrain had TerrainNavmeshSettings as well.

 

If possible give me some example. I tested with mesh collider some random planes with different scale, with object inside object with different scale in bouth and cant recreate bug.

line 846 is try-catch blosk of threadworker so if anything go wrong in threads then it will go here. In settings there is "Mulththred" checkbox, if possible disable it and recreate bug. Pathfinder will use coroutines instead of threads in that case and will show proper error line.

 

I attached one of the bushes I am using.

About the multi threading, I can only find the multi threading option for android. not desktop. If you mean "Graphics Jobs" it's already disabled.

 

Well. Actualy all seems alright. What did i saw:
I put collider in scene, saw it's already convex so nothing can go wrong here

Build navmesh with debugging voxels. Seems alright

When i tried to move around i saw it's hitting with head
Seems like issue. Then i debug places where Pathfinder volumes are make each others voxels unwalkable before offset to agent radius.

Well. Yeah. Default capsule with character controler are have 2 units of height. And BasicAgentPorperties are 1.55 height for debug purpose and i forgot i made that change and didnt revert it. Guess there is issue.
In agent properties ajust agent height and radius to your actual agent height and radius. Need to make it a bit more obvious.

No not that one. Here:
Windows > K-PathFinder > Menu

 

Thanks, that fixed the issue.

Now it's a NullRefrenceException in AreaPassabilityHashData line 103.

 

I figured out.
PathFinder/Generation/Collector/Terrain/ColliderCollectorTerrainCPU.cs
Around line 114 i forgot add else statment when i separate collector into three different collectors.

Change those lines of code into this

Code (CSharp):

1. if (terrain.alphaMap != null) {
2.     int[][] areaMap = ProcessAlphaMap(terrain);
3.  
4.     for (int x = 0; x < template.lengthX_extra; x++) {
5.         for (int z = 0; z < template.lengthZ_extra; z++) {
6.             int a = areaMap[x][z];
7.             terrainVolume.SetArea(x, z, areaLibrary[a]);
8.             if (a == 1)
9.                 terrainVolume.SetPassability(x, z, Passability.Unwalkable);
10.         }
11.     }        
12. }
13. else {
14.     terrainVolume.SetArea(defaultArea);
15. }

Will move some code arround related to terrain areas to prevent things like this.

Thanks a lot! It's very hard to catch bugs like this. When my own project in state when levels are made from white cubes

 

After I added the else statement and then reproduced the bug, I am getting another error.

You're welcome, happy to help . I will be letting you know if I find any other bug.

 

Oh this one. Yes i know about this bug. Find it couple days ago. It occure when multiple chunks queued at same space at same time with different agent properties. It's okay if it done with some delay though. I somewhat fixed it already but i dont realy like how i done it.
Still. Here is current state of project where it is fixed. https://www.dropbox.com/s/c51p08ra7tjoss3/K_PathFinder 0.38 test 5.unitypackage?dl=0

Need to rework all concept of WorkTemplate's. Have no clue how to proper organize work when half of it done in coroutines, half in threads and all depends on each other data to prevent duplicate works.

 

What files do I replace, since I have a few changed files with the new fixes we discussed. Are all the fixes we discussed in this new build?

Also, good luck in fixing these annoying issues .

 

Well you can include all, exept maybe PathFinder/Properties folder. Since all you reported and some extra are already applyed. In couple days will sibmit this version to asset store.

Related to this bug fixes was in:
PathFinder/Generation/Templates/InfoGeneration/TemplateChunk.cs
PathFinder/PathFinderMain.cs
Changed a bit how delegates work in this template.

Also was some fixes related to collecting trees using compute shaders, proper collecting collider shape for capsule collider and character controler, serialization. Also added some examples.

After some testing... nah. Now can be even worse. It's now possible to create two graphs at same space. Probably should remove all concept of global chunk library and make it part of navmesh graph. Or сome up with better idea. Will take some time though.

 

Now the Ai can go to other terrains fine, good job.

 

I noticed that the characters don't take account for each other. For example, characters could climb on top of each others, or try to push the others to get to their destinations.

 

Hi Krokozor. Very thanks for u asset. Can u tell about articles or sites where describes about nav mesh? I find some material (book-Game Wisdom, some articles and sites), but tell me please u own source(because I dont understand u code so much without math explanation).

Nice work.

 

Actualy not For now you just cant add additional jobs at same chunk for two or more agents. I started to fixing this issue to make this part of code robbust as possible. But i was bussy entire week.
And to fix this i kinda need rework large amount of project.

Cause currently i have class wich contain general information about current chunk. And it also have dictionary with navmeshes on it. So there is lots of places where i need this class as input. But turns out this was bad approach and there was already lots of places when this can go wrong. So i started to fix this.

Yeah i know. I talked about this already in this thread. Weakest part of this project is actual navigation. Will start work on it after next version.

Thanks Well yeah my code is kinda hard to understand. Even if i comment it.
Actiualy to generate navmesh there is no need to know much math. I used knowledge i gain in shool around 6-8 class in linear algebra. I can explain how it work if you have some particular topic.
Most i learn by reading code of already existed projects. (So i dont even know names of some techniques i used but understand how it works lol)
I recomend to read this
http://upcommons.upc.edu/bitstream/handle/2099.1/16508/Ramon Oliva.pdf very good example. Not much about rasterization but good explanation and lots of pictures. I used some parts about triangulation from it and how to structure voxels.

 

Thanks for answer, Krokozor.

I understand how u generate NavMesh (field contain cells. when we insert polygon we split cell on half quad and check intersaction splitted cells and polygon until its possible).

But triangulation...I dont understand why u reduce performance and use triangulation - A* really cant use splitted cells for pathfindind ( + funnel algorithm for optimal path)? Maybe triangulation unnecessary in u case? Or I wrong?

Thanks for previous answer.

 

Send today next version of PathFinder to asset store. Will be there after unity guys check it.

i dont know how well you understand it. i dont check intersection, raw data are more like set of images.

well if you are intrested in actual pathfinding i can explain how it works with help of paint:

Spoiler: Text and pictures

Cell represent some area, this area have some edges, all edges are convex.


Cells are connected to each other with only one edge cause cells are convex


Now. If we want no find path from one cell to another then we find wich cell contain start position and end position. Then we use some sort of graph search to find shortest path on cell graph between cells. And now when we know path on cells we also know wich gates are used to get from point start to end.


now we know path and right and left restrictions to use this path.


now it's start taking shape. then we apply funnel algorithm to find shortest path for real. i can explain how it works but you can find better sources than me. it's siquentialy check right and left gate points and if left point righter than right point then next point is right. and same for another side. this way we can find shortest path for real.

trianlulation (well in my case it's not really triangulation cause i dont use triangles. just make convex areas from contour) need to make graph. Graph need to find path on it. And all cells need to be convex to use further algorithms.
If cell count is lower then we obviously find path faster cause less branches need to be checked.

 

Changelog 0.37 => 0.38:
Here was mostly bugfixes.

Whats new:
* Some basic example scenes in scenes folder.
* Pathfinder.GetPath and PathFinderAgent.SetGoalMoveHere now have "Vector3 start" parameter to specify start position if needed. By default it was PathFinderAgent.position
* You can apply raycast before funnel algorithm.
requesting path now have two optional parameters bool applyRaycastBeforeFunnel and int maxRaycastIterations.
by default applyRaycastBeforeFunnel is false. if it true then before applying funnel algorithm PathFinder also check visibility of end node.
If node is visible then it return path. In short paths it will be more adequate result.


Whats Fixed:
* PathFinderScene will no longer cause exeption when it tries to fix existed in scene TerrainNavmeshSettings
* Newly created agent properties are will at least have enabled default physics Layer
* Fixed bug when adding new volumes dont fully apply to existing volumes
* Fixed bug with tree colliders
* Fixed zero length buffer bug related to collection trees using ComputeShaders
* Position inside navmesh after deserializing now works as intended
* Navmesh serialization in scenes now actualy works
* CapsuleCollider now scale properly into collider shape
* CharacterControler now scale properly into collider shape
* Queue multiple work at same space no longer cause dictionary exeption (i hope)
* Fixed threading issue during template population loop
* Fixed default graph being used during connection
* Fixed adding same work multiple times on huge perfomance hits
* Navmesh raycasting no longer return incorrect result if hit was before target length

Whats changed:
* huge internal changes related to storing graph chunks. expect some bizarre issues related to finding data in navmesh.
Before it was stored in dictionary wich stores mostly just connectivity to other dictionaries. This data was moved to graphs itself. Now there is no pesky task types wich contains only position but properties are not really relevant to it. For now it just fixed adding work on one space with different properties in very short time but overal adding work now more robust.
* Some folders was moved arround in more proper places so if you want proper folders alighment then remove PathFinder folder and reimport asset. (also restart unity cause you probably lost reference to settings files in that case. need to fix this in next version)

 

Hi Krokozor!

Thanks for explanation of work u pathfinding and for new update with bug fixing.
Probably I have bad understanding nav mesh creating (expecially it dynamic creating). If u got some free time can u explain nav mesh creating (equal as pathfinding in prev post)? I use project but dont understanding how it work as well.

Thanks a lot for u work.