Home Unity

Explain AI Pathfinding?

bpears
polycounter lvl 4
Offline / Send Message
bpears polycounter lvl 4
Hello, I am trying to understand how AI can work in Unity. I am trying to understand, all the ways an AI can basically communicate with a mesh to navigate.


I've seen tutorials using 'cells' as the navigation meshes, which were just boxes with colliders. But can you just use a flat mesh? and of whatever design? I just feel like there is a little more professional/optimized way of doing it other than having a bunch of boxes.

Is there a way to just use one, solid mesh, with as many verts and edges as you would have had, if it were a bunch of boxes?

I ask these questions because I don't really know how the AI communicates with the mesh. Is it looking at verts? the area of the mesh? I'm unsure. In the tutorial with a bunch of boxes, it seemed the AI was just constantly finding the box closest that was in path to it's target. Again, this seems like it would be a big drain on performance, and I have a feeling there are better ways.

Thanks for your time.

Replies

  • Vailias
    Offline / Send Message
    Vailias polycounter lvl 18
    I don't know Unity's specific implementation, however I can give you some general background on AI agent navigation.

    Generally speaking an AI entity in a game doesn't know a thing about the world around it that it isn't directly told.
    They tend to obey the same game logic rules as whatever the class they are controlling is (IE world to object collisions, damage rules, other assorted game rules that apply).
    They can navigate stupidly by just moving in some direction till they hit something, then turning some direction and moving again (like a roomba).
    Or they can have some more intelligent navigation options.
    One of these would be navigation points. Each point has links in it to the other points that have a direct line of navigation to itself, so the AI's can just walk from point to point and appear relatively intelligent.
    Another more advanced method is the Navigation mesh. This is a mesh built into the level, or auto-generated within it, that describes all surfaces which are traversable.
    Figuring out the best path through the mesh is up to the AI engine. This can be some cost/search algorithm (A* tends to be the best choice) which gathers its path cost data from the navmesh and or world.

    A bunch of boxes with colliders marking points which are impassable isn't that bad an idea. What seems like a really arduous and lengthy set of tasks of picking boxes and such is really next to nothing when you compare it to just rendering a mesh on screen.

    The AI can just look ahead on its path by a few moves(ticks, seconds, whatever) and determine if there is an obstruction. If there is it moves its next waypoint outside the collider and recomputes.

    As far as navmeshes go, its essentially defining safe zones for nav points which the AI can plot toward a goal. Any given point not within the bayrcentric coordinates of a navmesh triangle is invalid. As far as generating a navmesh goes I'll have to refer you to outside sources as I haven't done that personally,and its been a while since I read the specifics.

    This book is helpful: [ame="http://www.amazon.com/gp/product/1556220782/ref=yml_dp"]Programming Game AI by Example: Mat Buckland: 9781556220784: Amazon.com: Books[/ame]
  • bpears
    Offline / Send Message
    bpears polycounter lvl 4
    Vailias wrote: »
    ...
    Figuring out the best path through the mesh is up to the AI engine. This can be some cost/search algorithm (A* tends to be the best choice) which gathers its path cost data from the navmesh and or world.

    A bunch of boxes with colliders marking points which are impassable isn't that bad an idea. What seems like a really arduous and lengthy set of tasks of picking boxes and such is really next to nothing when you compare it to just rendering a mesh on screen.

    As far as navmeshes go, its essentially defining safe zones for nav points which the AI can plot toward a goal. Any given point not within the bayrcentric coordinates of a navmesh triangle is invalid.
    ...

    Yes, I would still like to stick to the more advanced A*, smarter AI pathfinding, using nav mesh. But unsure if I could just use one big mesh, or even just combine the boxes I mentioned into a single mesh on game load. But I suppose that would throw off navigation because the way it seemed to be set up was with OnTrigger detecting collision. But if there is a cleaner way, I'd rather do that. Always calculating the boxes seems like a heavy drain. But if this is best, I'll do it! :thumbup:
  • Farfarer
    I ended up writing my own A* pathfinding script in Unity that loads Navmeshes through XML, and a Navmesh XML exporter for modo.

    This was the page that made sense to me. Once I had the grid version written up, converting it to use arbitrary convex ngons was pretty easy.

    www.policyalmanac.org/games/aStarTutorial.htm
  • bpears
    Offline / Send Message
    bpears polycounter lvl 4
    How can I convert a .FBX file mesh into a NavMesh? Is What is a NavMesh made of in Unity? Nerbs primitive, volume primitive? regular polygon geometry? Do I just need to tag my mesh as NavMesh in the Unity editor?

    I just don't see why I can't just import a mesh, and say hey, pathfinding, use this! I have Unity Pro, so it is built in, but I don't want to bake it from the editor, I want to create my own in Maya, so I can be precise, since the level has lots of interesting paths that the Unity NavMesh baker would probably screw up.
  • Farfarer
    Well, you can't. So you'll have to write your own system or find one that's already been written.

    Have you tried the built in stuff rather than disregarding it straight off?
  • bpears
    Offline / Send Message
    bpears polycounter lvl 4
    Farfarer wrote: »
    Well, you can't. So you'll have to write your own system or find one that's already been written.

    Have you tried the built in stuff rather than disregarding it straight off?

    I don't understand why, I mean, it's just a mesh. There is no way to tell unity IT is the navmesh? I don't get that.

    No, but I've watched how it works and people setting it up. It works in basic levels. But when you have complex geometry it tends to get funky.
  • Farfarer
    It works with voxels. You can fiddle with the settings and tile sizes if you want a more accurate result (at the cost of area covered). But you can get decent accuracy up to about 5km x 5km areas. See the documentation.

    Or you can use a different system.
  • bpears
    Offline / Send Message
    bpears polycounter lvl 4
    Farfarer wrote: »
    It works with voxels. You can fiddle with the settings and tile sizes if you want a more accurate result (at the cost of area covered). But you can get decent accuracy up to about 5km x 5km areas. See the documentation.

    Or you can use a different system.

    Do you know if the built in pathfinding system (Unity Pro) is more optimized than using Unity boxes as said earlier? Or is it kind of the same thing? (...)

    But in the tutorials scripting it seemed that it used a lot of distance calculating, which is what I am worried about with this method, especially with a heavy/large scene.

    This tutorial is also what got me wondering about just importing a mesh, but not sure if that would even work with this method.
  • Farfarer
    Not sure, I haven't used the built-in navmesh, but it looks decent. I ended up writing my own system before Unity's own was released. It lets me export the navmesh info from modo to Unity (via XML). It's not very advanced but it works for me.

    All pathfinding uses a lot of distance calculation, that's part of how it works out what's the fastest route. It's generally a mixture of the distance travelled from the starting point, the distance remaining to the end goal and any fake "traversal costs" you've added to emulate the added difficulty of crossing hard-to-cover terrain (hills or swamps or rivers). It searches outwards from the start point, recording those values for each point it gets to, until it reaches the end goal. Then it works backwards through those points, at each step picking the one with the cheapest recorded cost until it reaches the start point. Reverse the order of the points you took to get from end to start you've found and there's your fastest path.

    I haven't watched that entire video... but from what I've skimmed of it, I'm not a fan of their method. I wouldn't recommend it.
  • osman
    Offline / Send Message
    osman polycounter lvl 18
    I'd say just create a small test case using unity default pathfinding, it's really good and very easy to setup. There's plenty of tutorials on it as well. http://docs.unity3d.com/Documentation/Manual/Navmeshbaking.html
  • cupsster
    Offline / Send Message
    cupsster polycounter lvl 11
    Unity built in navmesh is based on Recast project. Source is available online and if you google for recast a little you will find nice posts from its author with explanation of how stuff works. Also look to/for AngryAnt's implementation of A* pathfinding.
  • bpears
    Offline / Send Message
    bpears polycounter lvl 4
    I guess I will just have to test between the built in RAIN, and Unity boxes method. RAIN seems great but it is over complicated for what I need. I just need core pathfinding. All the behavioral stuff I am scripting anyway. Just wish there was a better way to manaully create the pathfinding mesh, besides box method.

    I wonder if there is a way to use custom grid mesh, but with the spots you want cut out, regular polygon geometry, so no special geometry. Basically grid based the way that RAIN pathfinding is, but with regular geometry. And just go toward closest vertex of that mesh that is along the path. And yet to say that the AI can travel between the connected verts, so that they are not constrained like with waypoints. Maybe a grid based geometry would even be necessary as long as you have verts and start/end of intersecting routes, so that it can find and choose that route.
  • cupsster
    Offline / Send Message
    cupsster polycounter lvl 11
    http://arongranberg.com/astar/features should solve all your trouble if you want grid. and https://code.google.com/p/recastnavigation/ if you really want to make meshes automatically before game is running. hope this helps
  • bpears
    Offline / Send Message
    bpears polycounter lvl 4
    Thank you, this is helpful. Gives an idea about each way to go about it. :)
Sign In or Register to comment.