Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Pathfinding in unity: Beta of Path now online

Discussion in 'Made With Unity' started by AngryAnt, Mar 31, 2008.

  1. Alec

    Alec

    Joined:
    Mar 11, 2008
    Posts:
    1,330
    So is this leading to creating paths in terrain? That would be mad!
     
  2. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    You can create pathfinding on any surface you like. The path mesh is completely independent of the surface being navigated. All you need to do it to have the path mesh roughly correspond to the surface in order to get meaningful navigation.

    In the case of 2.0 terrains, you could export the heightmap, generate a mesh in a 3D app based on that heightmap and then use some detail reducing methods to get the polycount down on that mesh. That resulting mesh would then be more than suitable as path mesh.
     
  3. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    32,401
    Or use this. (I was going to make that a proper editor script, but couldn't think of a good way to do the resolution choosing.)

    --Eric
     
  4. Alec

    Alec

    Joined:
    Mar 11, 2008
    Posts:
    1,330
    Ahh this is great! I'm doing a lot of pre production for my first official entry when I buy unity (8 weeks).

    I've already guine piged my mate who has unity, we have already prototyping a day/night cycle which has been a blast. :D

    i can't wait to get unity. :D
     
  5. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    I'm sorry about this departure from the mostly praising replies in the other posts... I do think this project is a great initiative and that it is very promising - however...

    I downloaded and tried the demo project, and it looks like if though navigational meshes have been implemented here as though it was waypoints, and doesn't take advantage of the possibilities of a navigational mesh at all.

    Referring to the recently posted link about navmeshes:
    http://www.ai-blog.net/archives/000152.html

    Two of the primary advantages of navmeshes are:

    :arrow: The number of nodes can be greatly reduced.

    However, in the demo, instead of a minimal number of connected convex polygons, there is a large amount of connected triangles, forming mostly just a plane.

    One thing is that this makes it hard to see the point of the navmesh, since this is just as inefficient as using lots of waypoints.

    But more importantly, since the triangles are so dense, it's impossible to see if this navmesh system works correctly with convex polygons that form very large areas.


    :arrow: Zig-zagging motion is avoided

    All articles about navmeshes that I have seen show the paths going in straight lines across multiple convex polygons whenever possible. In this project however, the paths are zig-zagged, just as if waypoints were used. Sure the route actually followed is somewhat smoothed out, but you'd do that when using waypoints too. As far as I understand, straight line paths is normally an integrated part of a navmesh implementation.


    So judging purely from the included demo, the current progress of the system looks more like an alternative implementation of waypoints, where the waypoints are automatically created from a (dense) mesh, than like a true navmesh implementation.

    I could give the system the benefit of the doubt, and try to construct my own mesh to use with the system, as well as my own path follower to see if the system then works as expected. But I really think this is the job of the included demo, not my job: To properly show off the advantages of navmeshes, and that this implementation does indeed provide those advantages.

    I feel quite demanding here, but I try to be equally service-minded when I'm the one designing systems - and demos of those systems - for others to use.

    I do believe that there is great potential in this; I merely try to illustrates that there is some room for improvement. :)

    Rune
     
  6. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Hey Rune

    Thanks for giving the system a go. However if you'd read some of the earlier posts in this thread, you'll find that your questions are already answered.

    First and foremost understand that the provided demo is a tech demo - a demo of the path finding system. You refer to the zig-zagging of the character and while this is totally valid, it is not a part of what this system provides.

    I've created a demo path following script just for this demo and this is what is causing the zig-zagging. You're free to implement your own smooth path following script. The goal of Path is simply to reduce headaches while adding path finding to your game - path following and other character steering stuff is out of the context of Path.

    Regarding the NavMesh used in the example: It is just an example mesh and as I've described in an earlier post, its created by someone with very poor skills in 3D modelling (me) with an application which does not support the kind of optimisation I'd like to see in a NavMesh and which this demo one clearly needs.

    Please poke away some more at the system - all feedback is greatly appreciated :D
     
  7. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    To assist in creating a good path following script, I've provided a method for cutting corners rather than navigating between the centres of the NavMesh polygons:

    public Vector3 GetNearestPoint( Vector3 point, float clearRadius )

    http://eej.dk/angryant/pathdoc.html#PathMeshTriangle

    If the point provided is within the polygon, the same point is returned - otherwise the nearest point on the nearest edge is returned, taking the provided clearance radius into account.

    I think I'm using this method in the demo path following script and that I've just not including any rotation smoothing. However given how the demo NavMesh contains way too many unnecessary polygons, a lot of the zig-zagging is also caused by the movement between all these different polygons.

    For extra lazyness factor, I've changed the custom PathMesh component script used in the demo to default to the mesh used in the GO MeshFilter if no mesh is given as NavMesh. Not very optimal, but good for rapid prototyping.

    This along with more optimisations, bug fixes and possibly some new features (if they make the cut) are all going in the much delayed 0.4b release.
     
  8. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    In this specific thread or in another thread about the system? I did read through through all the posts in this thread and didn't find anything.

    Edit: Well I did a search and found this post, but it's in a different thread:
    http://forum.unity3d.com/viewtopic.php?p=80339#80339

    Also - while that posts implies the ability to define one's own path follower, it is not at all clear if it would allow for moving in straight lines between start and destination if there is clear line of sight, i.e. does the interface support full string-pulling?

    Okay, understood. Still, my point is when it comes to a NavMesh (with potentially huge nodes=polygons), the way to navigate between cells is just as important for efficiency as which cells to go through.

    I am *not* talking about smoothing but rather about finding the shortest path through the cells, taking the shape of the cells themselves into account. This is an issue of some complexity, and by not providing any help with solving this issue, the system really only solves one half of the problem of path-finding, while leaving the other half to be solved by the user.

    Before even beginning to handle path following/smoothing, the user must first implement routines to properly find the shortest path through the polygons. After the shortest path has been found, using some sport of string-pulling, then the smoothing can be handled (which I agree is too domain-specific and not necessarily the task of a general library).

    In other words, you're saying that actually creating the meshes needed by the system is too difficult or requires too specific software that it was actually pulled off by the author of the system... :p

    In case you're interested in doing more of the hard work for the user, there are articles about efficiently creating low-poly NavMeshes from higher poly detailed collision meshes, completely automated. For example, there's one article about it in AI Game Programming Wisdom 2 and another in AI Game Programming Wisdom 3.

    I'm looking forward to see the further development of the system!

    Rune
     
  9. GusM

    GusM

    Joined:
    Aug 27, 2005
    Posts:
    585
    I have just tryed it out and I must say its an impresive job, congratulations.
     
  10. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    To illustrate my previous points, I've attached some screenshots that shows some followed paths where the unnecessary twists and turns cannot be explained merely by unnecessary polygons, since a more direct path could have been followed within the same polygons that were used.

    Rune
     

    Attached Files:

  11. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Ah. Sorry. I thought that was in this thread. Oh well - now it is. Thanks for bringing it up :wink:

    Regarding your illustrations of zig-zagging pathes: Please don't confuse the actual followed path with the debug rendering (the one you're referring to) the debug rendering simply serves to show the order of the polygons in the path.

    I do indeed plan to get a better NavMesh for the demo, but in this beta stage I've set that on low priority. This author is not a very good 3D artist, but I'm betting on that not being central in peoples decision of using the system or not.

    Regarding the path following script and its abilities, I highly recommend you read the documentation at http://angryant.com/pathdoc.html and shift through the example code provided in the demo project (its not much).

    I don't get which features you're missing from the pathfinding functionality and which you're requesting in a path following script. Currently the only parameter used aside from distance in pathfinding is the radius of the path finding agent. More are coming in 0.4b.
     
  12. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    I'm not confusing them - that's why I explicitly created a thick orange trail showing the *actual* path followed. My point is that this actual followed path takes a route that is far from optimal within the traversed polygons. And I don't just mean that it should be smoother - I mean that it makes several turns that are not necessary and ultimately does not follow the shortest path possible (again, within the triangles used).

    Rune
     
  13. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Ah right. Now I get what you're saying! :)

    While it's still in the realm of path following, I'll make a note of it for an updated path following script for the demo :)
     
  14. Charles Hinshaw

    Charles Hinshaw

    Joined:
    Feb 6, 2008
    Posts:
    1,070
    If I'm following this discussion correctly, the real distinction being made (after removing mesh creation - whether by an artist or programatically) is between path finding and path following with Path being concerned only with the former? More specifically, that the distinction between finding and following should be made after sequencing polygons? (that the route through the polygons falls under "following"?)

    I wonder if users will intuitively understand the distinction between the two or if they will view them as all part of the same problem and see the line between finding and following as being blurry. The challenge, I suspect is in the demo -- to demo path finding, you need to implement path following. If you implement something that is efficient and generalized enough to make a good demo, you have effectively expanded the scope of the project to include both. If you implement something that does the minimum required to move across the path that you have found, users might mistake poor path following for poor path finding.
     
  15. dhogan

    dhogan

    Joined:
    Jun 2, 2008
    Posts:
    55
    I've been following this thread as well, and I think you make a very good point. Speaking as an artist, I do find it easy to blur that line. I can picture what I want to happen with the game object, and that seems to overshadow what is really necessary programmatically.

    So I guess the question from my point of view it, once the path is found, doesn't the next step become use specific? I.e. the pathfinding is creating a set of point information that is then passed along to another function. Along those lines, isn't the navmesh itself specific to your use? For example, a wandering, ambient NPC would have a much coarser navmesh than an AI-using, fighting NPC?

    My thinking is that the resulting path issues being discussed are potentially better or worse depending on what navmesh you wind up with and ultimately what the routine is 'looking for' when it's developing the path.
     
  16. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Charles:
    You're spot on. And the recent discussion in this thread has made it very clear to me that once I get to a release, I'll have to beef up the demo and the documentation heavily.

    dhogan:
    Not quite. The idea of the Path project is to have one system using one set of data (one collection of inter-connected Nav Meshes) for all pathfinding in a game or other simulation.

    The reason why I've chosen to abstract path following as much as it is, is because of the wide range of different aspects path following may or may not need to cover in a project.

    To illustrate the benefit of using an abstracted path following mechanism, take this as an example:
    You've got a city simulation with three types of AI controlled entities: A citizen, a policeman and a car.

    The citizen could be implemented very simply by having a set roaming area decided by a spread of pathes to choose from. These could very well be calculated once and then stored and reused over and over. Should one or more of the pathes become invalid by a building collapsing and blocking a street or something like that, the citizen script would be notified by the Path system and an appropriate response could be implemented (most likely the calculation of a new path between the points previously connected by the now invalid path).

    The car could also use a similar mechanism, but its path following routine would be quite different as it'd need to take turn radius etc. into account.

    If the policeman was implemented with a simple two-state behaviour patrol and pursue, it would be able to re-use much from the citizen script, but for the pursue part it'd need much more dynamic scripting.

    Despite the different behaviour, these three entities would still use the same system, operating on the same dataset for all their pathfinding needs.

    While designing this system I very decided to abstract rather than finitely implement path following for this very reason. I believe that this way the programmers using the system will have a desirable level of freedom without having to do too much legwork on their own. Rephrased: I believe that further development and direct integration of path following would restrict the developers to an undesirable level.

    I've got some features in the pipeline for extended dynamic path finding by storing more meta data in the Nav Mesh itself - I'll put up a more detailed description of the idea behind the system once those are stable as that'll hopefully make things more clear.
     
  17. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    I think this is what AngryAnt is arguing, but I'd still say that string-pulling is a pretty integral part of a NavMesh implementation with only smoothing being use-specific (see attached image).

    No, one of the advantages of NavMeshes is that you only need one. The same NavMesh can support small and big characters, and is independent of their behavior.

    Rune
     

    Attached Files:

  18. dhogan

    dhogan

    Joined:
    Jun 2, 2008
    Posts:
    55
    Ah, I see! Thank you both for a good explanation!
     
  19. HJPuhlmann

    HJPuhlmann

    Joined:
    Oct 18, 2007
    Posts:
    47
    @AngryAnt

    what I see, is, you have a problem with the conversion of A*. Because the shortest way is not always found. Try the over-lying corners.
     
  20. Charles Hinshaw

    Charles Hinshaw

    Joined:
    Feb 6, 2008
    Posts:
    1,070
    I don't think that is correct or what anyone is suggesting -- it appears to be finding the shortest sequence of triangles to travel. I think Rune's diagrams on string pulling and smoothing are helpful to demonstrate why it doesn't appear to be the shortest path.
     
  21. Dragon Rider

    Dragon Rider

    Joined:
    Jan 17, 2008
    Posts:
    280
    So.. Will this system work with Unity Terrain as the navmesh? I know you can read the angle ( relative to 0 = flat ) of a terrain tri( the fps controller prefab script does it ), but is that enough?
     
  22. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    HJPuhlmann:
    None of the examples shown in this thread reveals any bugs in my A* implementation. I have however found some cases where a faulty route will be returned - this bug has been fixed in my current build and will be made available in 0.4b.

    Dragon Rider:
    The idea of a Nav Mesh is that you have an extra mesh, used for navigation, which estimates the surface being navigated (for instance a unity terrain).

    This means you can indeed navigate a unity terrain, but using the terrain itself as Nav Mesh would not make sense - way too many polygons which would generate outrageous pathfinding times.

    In stead, for a level with a terrain, I'd export the terrain to a 3D application and in that create a simplified mesh which estimates the terrain.
     
  23. HJPuhlmann

    HJPuhlmann

    Joined:
    Oct 18, 2007
    Posts:
    47
    Awesome, I'm looking forward to see the further development.
     
  24. Charles Hinshaw

    Charles Hinshaw

    Joined:
    Feb 6, 2008
    Posts:
    1,070
    If you wanted a simple way to create a NavMesh from a terrain, you could probably just scale the height data (as if you were scaling an image) and then create a mesh from that. You would end up with a simplified mesh roughly matching the terrain. You could then check the normal of each triangle and if the triangle is too vertical to be navigable, you could remove it.

    This wouldn't be a very nice mesh, but it could be generated quickly with little code if you had a terrain that was generated programatically, for example.
     
  25. aaron-parr

    aaron-parr

    Joined:
    Apr 22, 2007
    Posts:
    577
    To learn 3d modeling, I set to work on a test area and animated critters for AngryAnt to use in demoing his project. This is unfortunately still in the works as I did not know a polygon from a spline when I started (and still sometimes feel over my head), but in any case a finalized package should be shipped to AngryAnt before another month passes.

    My strategy for creating the nav mesh is as follows:
    ( 1 ) Construct terrain object in Unity.
    ( 2 ) Add to the Scene with other 3D assets. (Things like cliffs that need good texturing on vertical faces for example)
    ( 3 ) Export terrain's height map from Unity.
    ( 4 ) In Cheetah3D create a "Relief" object using the exported height map.
    ( 5 ) Fiddle with Relief object's polygonal resolution before making it editable as a Mesh. (Will need to find the sweet spot of overlap between minimal polygons, and usefulness.)
    ( 6 ) Factor in obstructions from other 3D assets not expressed by the heightmap (like trees, and other 3D assets plopped into the scene), and remove these areas from the Nav Mesh.
    ( 7 ) Export Nav Mesh to Unity.
    ( 8 ) Orient Nav Mesh to sit just over the Terrain Object, and put on an unrendered layer.

    I have gotten as far as step 5. Steps 3 - 5 once you know what you are aiming for take about 10 minutes tops.

    I have an idea about how to handle Step 6, but would like to finish my area and talk with AngryAnt about it before leading any of you astray. Steps 7 and 8 are easy.
     
  26. Quietus2

    Quietus2

    Joined:
    Mar 28, 2008
    Posts:
    2,058
    In most A* implementations I've seen the 'smoothing' involved recursively traversing the calculated path and removing unneeded nodes. For example, the system calculates a shortest node to node path of a->b->c->d->e. It then determines if a->e is actually traversable and if so removes b, c and d. Your avatar then moves in a straight line between the a and e nodes, the true shortest path.

    There are other unity related questions I would have, the main being node 'weighting.' Take say, a path across a body of water and a path around it. If weights (essentially a proxy for movement speed) are taken into account then in certain circumstances crossing the river might be faster than moving 100 yards downstream to cross a bridge. I'm unaware of any way in Unity to determine the terrain 'type' other than maybe somehow sampling the texture under your feet? Being able to somehow insert this proxy info into the navigation mesh would be useful if not..

    Lastly, you had said last spring that you had yet to load test your implementation with a slew of characters. Have you got around to that yet? Curious as to wether or not C# is going to be fast enough for heavy use of this, as opposed to a pure C++ implementation. Especially as the number of avatars and the resolution/size of the navigation mesh grows.

    Great work and looking forward to Path getting out of beta stage one day!
     
  27. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    I'm currently focusing all my energy on the Behave project. As Path was my first unity project, I had to redesign quite a bit while developing it, as I learned the ways of unity. Furthermore, the addition of the EditorWindow class in unity 2.1 opened a lot of possibilities which I'd really have liked to have when I first started the Path project.

    Therefore, as soon as I have the Behave project at a stage where I can throttle down development a bit (which isn't that far into the future), I will begin redesigning large parts of the Path project. I will be taking all input from the community into consideration while doing this plus my experience in working with editor scripts in the Behave project.
     
  28. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi.
    is it possible to use the terrain as the pathfinding mesh?
     
  29. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Currently no. And I have no plans to make it a feature. The terrain is way too polygon heavy to serve as a navmesh.
     
  30. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Darn! Do you know about another pathfinding system using the terrain(or can handle a massive amount o polys)?

    /Aron
     
  31. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    You need to read up on navmeshes. No navigational system I have ever heard of uses raw high-poly level geometry directly.
     
  32. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Alternative response (attempted to be written from a user-centric perspective rather than from a programmer point of view):

    You need to find a way to create a low-poly NavMesh based on a higher-poly collision mesh or visual mesh, since that is not part of the solution that the Path library provides.

    There exist tools that can completely automatically create such a low-poly NavMesh based on a higher-poly collision mesh or visual mesh, but I don't know of any free ones. Conversely, when using those tools, you'd typically also use them to store and traverse the NavMesh too, and create smooth paths, since these tools typically provide a full path finding solution including the functions provided by the Path library.

    Alternatively you can create a NavMesh manually, for example in a 3d modeler software package. However, this requires knowledge not only of the 3d software but also of how to best create optimal NavMeshes. Furthermore, this approach requires you to modify the NavMesh manually every time the underlying level geometry is modified, which can be time consuming when building and tweaking levels. For these reasons professional studios probably rarely build NavMeshes manually but rather use in-house or third-party tools to do it automatically.

    We can hope that a full path finding solution will be available for Unity at some point.

    Until then, good luck!
     
  33. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Thanks.
    It looks like I wont be able to use the terrain as a navmesh. But... What are strategy games using, like starcraft or command and conquer? Is that sollution possible to use/create?

    /Aron
     
  34. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Sure. Perhaps I formulated my response badly (made it "alternative" as you say). You can generate low poly navMeshes based on high poly resources using a wide range of techniques, but that is not pathfinding using the terrain. That is pathfinding using a generated navmesh *based* on the terrain data.

    I got the impression that the poster hadn't grasped the idea of navMeshes and therefore found it prudent that he research the area more to get a better understanding of why Path has been designed as it is.

    Sure I could have posted an in depth description of what navMeshes are and why directly using the terrain mesh as one would make little sense, but I don't really want to turn this thread into a discussion about what pathfinding is.

    I only ask that people do their research before going more in-depth with my products. I do not provide "click here to solve all your AI" solutions, but tools supporting game developers in their quest to implement their AI knowledge and plans.

    I'm sorry if that is too "alternative" to you, but that's how I ride.

    The Path project has *never* targeted game designers drag-dropping prefabs into unity or artists demoing their show-reel using unity. This solution is *designed* for programmers or at least developers with a fair programming knowledge.

    If you trust me to develop this project in the direction you wish, would you then please care to share what you would want "a full path finding solution" to contain?
     
  35. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    No, it's perfectly fine with me. :)

    I was merely trying to provide some extra additional information that might be useful from a user's point of view. The problem is that in order to understand what your library offers and what it doesn't, one first need to know some basics about how path finding works in the first place.

    Some users might not want to research that in depth now but just know if the library can solve their problem or not (because if it doesn't then there might be no need to do the research in the first place). So I was trying to provide that information in an easily accessible way, so they can then decide for themselves if they really need to do more research, find other ready-made solutions, or simply drop the idea completely for now.

    Rune
     
  36. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Mah. Sorry. I haven't had my coffee yet. :?

    Still I'd like it very much if you would provide a list of features you would like to see in "a complete pathfinding solution for unity". I'm slowly sketching some plans on what to do next with Path. :)
     
  37. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Sure!

    Most of all, the ability to fully automatically create a suitable NavMesh from a high-poly collision or visual mesh.

    There are some articles on how to do that on the books AI Game Programming Wisdom and AI Game Programming Wisdom 3 (two different approaches, the second being better and also more difficult to implement). I've looked at them, and they're too difficult for me, but you might be up to the challenge. :)

    Rune
     
  38. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Fair enough. That's on my to-do already. I was half-expecting you to list a lot of path-following wishes :wink:
     
  39. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Yeah, I'm busy right now, but I'll get back to this later. :)

    Rune
     
  40. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hm... Is it possible to export the terrain to a .obj file but making it a low poly mesh(I'm talking like 1/8 of the size (already tried with 1/4 it didn't work))?
    How low must the poly count be?

    Thanks /Aron
     
  41. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    I'd still recommend you read up on navmeshes. In a navmesh a polygon identifies an unobstructed area.

    Ideally a game has no obstacles at all in which case the navmesh would be one big polygon (but then you wouldn't need pathfinding :wink:). Basically you need to cut holes in your mesh matching each static obstacle in your environment. That would create some polygons forming the area around the holes and these are then used for navigation.

    The polygons of a navmesh are converted into a network of navigation nodes - similarly to waypoint networks. The more navigation nodes you have, the longer it takes to calculate a path between two nodes in the network.

    So the more polygons your navmesh has, the more CPU cycles will be consumed by pathfinding.

    Regarding generating navmesh data from terrain (which I still won't recommend), Charles and Aaron came up with some suggestions on page five of this thread. Eric linked to this terrain exporter: http://www.unifycommunity.com/wiki/index.php?title=TerrainObjExporter
     
  42. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Ok, here goes:

    I'm not quite sure how the paths are currently returned by the library (I must admit that I haven't looked much into it) but judging from the demos it seems that a list of polygon mid-points are returned, or at least that your demo implementation does this.

    Generally with a NavMesh, it is desirable that a list of edge connection between the polygons in the path is returned instead ("edge" referring to edges of the polygons, not edges in the graph).

    The reason: Going in straight lines from polygon-center to polygon-center may cross blocked areas, but going in straight lines from edge mid-point to edge mid-point will always be confined to the allowed space. Also, string-pulling is normally implemented on top of edge mid-point based segments.

    Next wish of course would be string-pulling that takes a given radius of the agent into account. It should also take into account if the neighboring edges of the polygons are blocked or not - the path doesn't have to keep the radius distance to edges that are not blocked.

    Personally I'd be very happy at this point, but you could make it even easier for users by implementing smoothing on top of the string-pulled paths. Bezier curves are handy for that, and easy to implement.

    Rune
     
  43. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Thanks :D

    A list of polygon data is returned - instances of a data structure which represents a navmesh polygon.

    Currently the path length is calculated from midpoint to midpoint, but the path following script moves from "nearest point" to "nearets point" - given by GetNearestPoint which, for a given polygon, takes a current position and a unit radius and returns the closest point (on the nearest polygon edge).

    Yep. That'd be awesome. :D
     
  44. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    So I could inspect the edges of two adjacent polygons on a path and compare them to find the common edge that connects the two polygons?

    With all respect, I don't see how that's very useful. The path necessarily needs to go through the edges that connects the polygons, not just any random nearest edge (unless I'm misunderstanding you). See attached sketch.

    Length calculation would also be more accurate if it's based on line segments that go though the edge mid-points rather than the polygon mid-points, although it's still not perfect. I'm not sure how to make it any better than that though.

    Rune
     

    Attached Files:

  45. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Currently the navmesh implementation only supports triangular polygons - that's why I'm going about it this way. Obviously non-triangular polygons are high on my list for the next update which means this "nearest edge" technique will need to go as well :wink:
     
  46. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Well, the problem I mentioned can happen with triangular polygons too. See attached.

    Sounds really good that you're going to support non-triangular polygons! The "nearest edge" technique would have to go either way though. ;)
     

    Attached Files:

  47. aaron-parr

    aaron-parr

    Joined:
    Apr 22, 2007
    Posts:
    577
    Couldn't you figure out nearest contiguous edge?
     
  48. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Usually there'll be only one connecting edge between two convex polygons, but, yeah, that's the general idea I wrote about here: http://forum.unity3d.com/viewtopic.php?p=102428#102428
     
  49. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    /me goes digging through the Path source...

    Woops. Thats right. Not checking whether the edge is shared by current and next polygon. Thanks!
     
  50. PhilipV

    PhilipV

    Joined:
    Aug 25, 2008
    Posts:
    103
    He AngryAnt,
    First I'd like to thank you for developing and keeping free such a great tool, that i am using to create some experience for myself (i have little experience apart from tutorials).
    I am currently trying to create a free time rts style game, and to do so, i thought that using your path system would have been a great idea.

    I curently created a whole selection/priority system, build/train system for units, but just recently hoticed some errors in path calculations:

    When the character is atop of the "cliff" and i tell to go down, on the right of the hole, EVERYTIME i tell him so he will make a much longer path than necessary, as you can see in the screenshot.



    Unless I mark as untransitable the road leading to the longer path, in wich case, he will get the shortest one.





    Also, why did you put the Y offset of the Char controller to "1", instead of 0?