Explain AI Pathfinding?
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.
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
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]
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:
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
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.
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.
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.
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.
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.