Search Unity

  1. Unity 2019.2 is now released.
    Dismiss Notice

Is the Unity Navmesh system missing an agent avoidance element?

Discussion in 'Navigation' started by Arowx, Feb 23, 2016.

  1. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    The Unity Navmesh system is good, but say you want your NPC's to avoid monsters/enemies and not run past them.

    There is a dynamic obstacle avoidance element but you cannot put it on a monster using the navmesh agent as the monster would try and avoid itself. Or you end up with a monster afraid of it's own shadow and erratic behaviour.

    Is there a way around this conundrum, as I'm just surprised the rather good navmesh system does not have an easy way to add predator/prey behaviour.

    Also it could use a layer or matrix system for neutral, attract, avoid. Which should work in most games.

    It would allow the construction of biomes with competing fauna a flora a relative doddle or just plain fun. Build an island of competing critters and plant life and just see what happens.
     
  2. Ostwind

    Ostwind

    Joined:
    Mar 22, 2011
    Posts:
    2,776
  3. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    See" http://docs.unity3d.com/Manual/class-NavMeshAgent.html
    ---------
    You'll need more complex behavior for that.
     
  4. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    That just prevents them from getting stuck bumping into each other in a crowd or busy intersection.

    I'm talking about a dragon appearing in a medieval village or evil monster/robot in a city street, you would expect basic NPC characters to move away from them and find ways around them not walk near them.

    Good point looked briefly but did not notice that section, moderator could you teleport this thread please?
     
  5. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    That's job for AI, not pathfinding system.

    Your villagers would first need to sense the dragon, then decide where do they want to go and what do they want to do.
     
    Schneider21 likes this.
  6. GarBenjamin

    GarBenjamin

    Joined:
    Dec 26, 2013
    Posts:
    7,442
    @Arowx Seems like you're looking at making the kind of thing I find interesting and keep exploring. I've also run into challenges trying to get what I want. I never tried the navmesh system until a month or so back. It seems ok. Actually great for simple cases. The stuff I want to do seems simple to me yet it is not so simple to implement it using these canned solutions.

    You could just ditch all of that stuff and build your own systems from scratch. Right now I am checking into alternatives for 3D gamedev however if I end up just coming back to Unity for it I will just start from the ground up building what I need.

    In my experiments I have the NPCs (critters whatever) just using casts to get information about their environment. This includes both the scenery of the area as well as objects such as doors and other critters. That works pretty good.

    My next attempt will rely on a simple grid (or actually cube). It's such a no brainer thing I am really surprised this isn't something I ever see in any examples. I think that is due to there being no built-in support for such a structure inside of Unity and most folks seem to rely on whatever is built-in or available on the asset store.

    Anyway, if you had a simple cube map data structure just the 3D equivalent of a 2D tile map you could easily place markers inside the enemy layer for example representing the critters. The data structure would also make it incredibly easy to build navigation systems as well as detect items of interest (food, a predator or its prey).

    That is what my next test will do. Like I said right now I am spending time taking a good look out there to see just what all is available. My mind works much better with data structures than visual or canned systems. Probably because for me I cannot really see anything with those cases whereas with a straightforward data structure I can.

    Anyway, maybe this is something you can explore (a custom data structure based system inside of Unity).
     
    Last edited: Feb 23, 2016
  7. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    @neginfinity But without a way to transfer avoidance or even attraction behaviour into the pathfinding system you can still have NPC moving near to the dragon. Also you are doing a lot of work* for a behaviour that could be built into the pathfinding system.

    * E.g. the Dragon would have to detect all surrounding NPC's, inform them of it's position and threat level.
    The NPC would have to take note of the Dragons position and threat then 'plan' to move away from the dragon.
    Now what if we have multiple enemies, our NPC's calculations and enemies detection logic go up massively.

    If the navmesh had a dynamic avoidance/attraction layer then NPC's could continue trying to going from A to B whilst pathing in a believable way with minimal additional calculations needed by the game developer. Just some kind of state update for threat level changes or attraction level, so NPC would run away from immediate danger and cower further away.

    But there is LOS or Detection Logic, e.g. Someone round the corner from a threat would not notice it until they walked into LOS.

    @GarBenjamin Actually thinking about it maybe a voxelized pathfinding system combined with with the umbra occlusion system and a voxel based sound map would allow for a good data driven system that would update NPC's so their pathfinding and behaviour match the scene. E.g. Dragon landing in Viking village.

    And what if the system could dynamically calculate a safe/danger or hazard map your NPC's could dive behind cover and your troops use cover to advance upon an enemy.

    Take the emergent Automatic Car Market (5-10 years), our AI systems have improved but it's the level of data mapping of the world's roads that we have gathered that have allowed it to happen.

    If we have an improved Navmesh system with Avoidance and Attraction built in, precomputed but dynamic then we could very easily land Smaug in the Viking village have it breathing fire and getting NPC's that behave believably.

    And Unity has the Occlusion culling data for fast LOS and 'Not In LOS' calculations, Navmesh data with definable navigational 'costs'. Unity would probably need to build a voxel soundscape model so areas with different audio properties would propagate sound differently and a sound made in one place impacts NPC's further away.

    IMHO such a navigation system ideally combined with a good API system and a Behavioural State FSM using and working with the Mechanim UI would provide Unity with a very nice AI/Behavioural subsystem out of the box.

    But what do you think?
     
  8. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    That is backwards. NPCs should be ones detecting dangers.

    Which is not an issue unless you have few thousands of them.

    Which will result in boring and mindless behavior.

    You're trying to push AI job onto pathfinding.
    What's more, behavior for this kind of system can be made into AI controller fairly quickly. It is not a difficult issue...
     
  9. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    By the way.

    Umbra occlusion data is completely inaccessible from scripts. I tried to use it. It is a blackbox in unknown format. And there are no routines to query it.
     
  10. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    So a village of say 100 villagers should each scan for danger, does that mean that each will have a trigger volume or that they will each do intermittent sphere casts. Then if they detect a danger a LOS test and then move into an appropriate behaviors.

    Wouldn't it be more cost effective for the dragon or enemy to have a trigger volume/sensor as it is going to have to detect the villagers and pursue/attack them anyway.

    Your system needs to run 101 sensors (trigger volumes or sphere casts) mine 1 per enemy. But if you start attacking with a horde or multiple dragons a navmesh threat/attraction system would surely be the best solution.

    Not with a simple callback system, the Navmesh lets the NPC know that it's threat level has changed and with occlusion information you could have villagers running, leaping and diving for available cover.

    I suspect that a lot of the AI you see in games will be baked or built into or onto the pathfinding system. With the addition of a simple attraction/avoidance map NPC's could look as though they are drawn to Gandalf's firework show and run in fear from the arrival of Smaug. Or troops use cover to advance on an enemy.

    That's OK as it would only be used to change the navmeshes attraction/avoidance layers values, areas that provide defensive shadows from Smaug would attract NPC's, or places on top of balconies or carts would attract NPC's to see Gandalfs magic show. So it would stay under the hood, but it would need to allow for dynamic changes e.g. Levolution or Moving cover objects.
     
  11. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    It's not really a behaviour AI system as it only provides animalistic predator/prey attraction/repulsion behaviour, good enough for basic NPC gameplay.

    Higher Level AI behaviour would be someone raising the Village alarm when Smaug is seen or the Village Juggler going to the inn for a pint and rest while Gandalf does his thing.
     
  12. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    No, each individual villager might check for danger at irregular intervals, say once or twice per second.

    That's premature optimization. First implement prototype, then check if performance is an issue. Then locate bottleneck, and fix it.

    Frankly, that's a strawman.

    Your system will have 101 pathfinder. That may be more expensive than collision queries. Which doesn't have to be running every frame.

    Basic animalistic behavior is what game AI does.
     
  13. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    Either way, do you have a prototype? With dragon and 100 villagers?
    Have you run into actual problem or are you doing mental exercises here?
     
  14. Murgilod

    Murgilod

    Joined:
    Nov 12, 2013
    Posts:
    6,154
    This is an Arowx thread, so probably the latter.
     
    neginfinity likes this.
  15. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    I'm working on a 'quick' mini LD game and wanted an avoidance behaviour as NPC's were running right past enemies, I noticed the NavMeshObstacle and thought cool Unity has solved the problem. Then I hit the afraid of your shadow problem when it was attached to enemies. (as mentioned in first post)

    Unity's navmesh is well 'binary' or 'flat', you can cut a hole in it but not distort it's topology, e.g. avoidance/attraction. Or simply the dynamic ability of a NavMeshObstacle to alter the cost of it's area of navmesh. But it really needs to be layered e.g. NPC's avoid Dragon, Dragon attracted to NPC's. This could be done with multiple navmeshes, one for each faction, but get's complex when you add a third or more faction e.g. Orc's / Dark Elves / Ogres. So the best approach would probably be a layered or masked attraction/repulsion system on top of the Navmesh.

    Ideally Dynamic Voxelized with Light and Sound Occlusion built in.
     
  16. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    Alright, since I'm not in the mood for mental exercises today.

    While it may make sense to have a dynamic field that alters navigation cost, you're really clumping several problems into one, blame it all onto navigation system, and then overthink it.

    The best approach is the dumbest one that works. Not the most elaborate one.

    For navmesh routines see RAIN framework - I haven't had the chance chance to play with it properly, but it had multi-navmesh support. So take a look at that.

    Also, I highly recommend to continue looking for the dumbest solution you can think of.
     
    hippocoder likes this.
  17. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    See that would not look believable as your flight or fight responses are hardwired to fire within milliseconds.



    It's common sense, 99% of the time your villagers will have a boring existence, the player shows up and boom the evil dragon hits town. Why not attach the "event" or sensor/trigger to the dragon and not the NPC's.

    A system where the NPC's use up useless CPU time testing for a game driven event is inefficient, whereas one with the Enemy AI triggering the action will be more efficient.

    Think of it as an Event, would you want your Passive Listeners to be constantly polling the Event System for new events or for them to register with the Event System and the Event System to call them when something does happen.
     
  18. neginfinity

    neginfinity

    Joined:
    Jan 27, 2013
    Posts:
    6,434
    I'm not in the mood for this. You'll sit on ignore list till my mood gets better. Have a nice day.
     
  19. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    25,825
    Teleportation 96.4% successful. No responsibility taken for missing protrusions.
     
  20. GarBenjamin

    GarBenjamin

    Joined:
    Dec 26, 2013
    Posts:
    7,442
    @Arowx I don't much about most of the things you said. This is a big part of why I am trying to start lower level. It has been good too. I think in the past week of playing around with OpenGL and other things I have learned more about 3D than I have in the past two years.

    All I know is this stuff (basically anything) should be simple and likely is simple. You (well me anyway) just need to start with a blank slate of nothing. Then figure out what the goal is. Then figure out what we need to accomplish said goal. Then look for that stuff or just build it. Then sooner or later assemble it all. And so forth.

    That is what I am used to doing. All of these systems and things that have been made I think are certainly useful but I think you can also waste way more time trying to force everything to suit your use case than what you would spend just building it all from scratch with the added benefit of everything actually being suited to your use case instead of forcing a square peg into a round hole.

    That's my view of it all. :)

    I actually managed to get Unity 5 installed and working the other day. So, I am thinking now about possibly giving it one more shot but this time just throwing everything out. Basically returning to my approach of using Unity as just a way to load assets, render graphics, play sounds and so forth.

    Start from scratch completely. And just building everything else from the ground up as would be done in anything else. Like even the monobehaviors I think I will throw that all out. I'll have one of them only: Game. And that will be basically the main program. Might be completely wrong for you and most folks but for me I think this is just what I need to do. This way I can develop in Unity the same as folks do in OpenGL, MX or basically anything else.

    I'm actually looking forward to it. A complete blank state and build from there.

    You might want to try something along those lines.
     
    Last edited: Feb 23, 2016
    pjbaron likes this.
  21. RockoDyne

    RockoDyne

    Joined:
    Apr 10, 2014
    Posts:
    2,234
    First off, look into heatmaps. Their main point is to add more details onto nav graphs, mostly by changing the values of an area of the graph.

    Second, this sort of behavior is way beyond just pathing safely around something. NPCs would completely flee the town and retreat to a secure place, probably to another town, and your normal navmesh containing these points of interest is not too likely.

    Would you rather page every NPC at once to change their behavior, or have only the NPCs that matter be updated when it would be natural for them to update? It's generally advised to have consistent performance, and not massively variable performance.
     
  22. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    That was just an analogy, the idea is to have the Dragon update the pathfinding system negatively for the Villagers, villagers within the "footprint" of the Dragon would get a callback to inform them of their hazard status.
     
  23. GarBenjamin

    GarBenjamin

    Joined:
    Dec 26, 2013
    Posts:
    7,442
    I'd never done any of these pathfinding / waypoint solutions until testing things in the past month or two in Unity. I've always just dropped in an object (one of your NPCs) for example and had them analyze their environment (terrain, structures, other characters etc), and decide what to do based on the current situation.

    I might be completely missing something but using these common approaches felt like a step backwards to me. I'd rather just have my NPC look around, assess the situation, decide what to do then react accordingly.

    Like in your example, say a few NPCs are just roaming around and a dragon lands a short ways in front of them. They'd find that information as a part of their routine scanning of their local area. So they then flee. Of course, you can build a manager on top to help coordinate their fleeing behavior if you like. Or you can use the "corners" method established by pac man long ago. Basically, I just program this stuff by trying to put myself into the NPC and think "now what would I do? What would this person do?" and then just program that behavior in.

    I guess I have an odd approach because long ago when playing games I never considered developers were laying down markers or otherwise defining paths and such so when I set out to duplicate what I saw in the games I designed and developed over iterations to drop a monster or whatever into an area and have it scan the local area and decide what to do based on that information. Of course, sometimes trails of a sense came into play if a monster had a routine / project it was working on then obviously it had knowledge of get this from here and take it to there. But in general every enemy is basically just a little virtual person. Because that is how it appeared to me when playing games that is how I approached the problem.

    Anyway... you can consider this route. I find it is the simplest of all. Just define information gathering means, rules for how to process based on the NPC type and just move them through different states as needed.

    Or maybe try to use the navigation and other systems that are built-in. A lot of people seem to use them so they may be able to do what you want.
     
    Last edited: Feb 23, 2016
  24. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    I've used a similar logical approach up until now, NPC's with sensors and LOS checks update their status and behave accordingly. But what if for most of that you just needed to hook your NPC up to the Navmesh system and handle callbacks on relevant 'threats/rewards' and be able to query for nearby defensive positions.

    Take the Dragon in the village example, one of your NPC's is out in the street but near a well, your NPC would avoid the well normally but now it is an ideal place to hide.

    To get that kind of behaviour you would need your NPC to be informed or detect the dragon then scan for nearby places to hide and jump into the well or dive behind the well relative to the dragon. What if the navmesh once updated with the dragons presence also updated good defensive positions from the dragon e.g. the well and behind the well.

    So your code goes from a prebuilt and dynamically updated 'map' or awareness of their environment that you can query to you manually coding and building defensive points and working out if they are in LOS of enemies.

    Now think about a large world being invaded by a horde of monsters, the map system will have a lot of updates as the hordes attack villages and NPC's respond, but the map system if well optimised should be faster than the physics sensor system, as one is doing complex 3d calculations and the other is updating a voxel or even 2d navmesh.

    The question then is which system will be faster a voxel based but layered threat/reward system or a 3d physics engines trigger volumes and casts.

    I think the physics engine driven one will work amazingly well with dynamic destructible environments. Effects that could really slow down a voxel navmesh system with big updates or trigger it to use the physics engine.
     
    Last edited: Feb 23, 2016
    GarBenjamin likes this.
  25. GarBenjamin

    GarBenjamin

    Joined:
    Dec 26, 2013
    Posts:
    7,442
    Well I think the problem is you're relying on something you cannot control. The NavMesh system is completely outside our control. It's a canned solution created by other people. And likely what you are describing is way beyond its intended purpose.

    Really I think all you'd need to do is set properties on every object or define zones and set properties on those. Take the well for example... when I make a game generally everything in it is defined meaning if there is a rock or tree or well that is defined as such. So you could just make a (virtual) zone around the well and define properties on it such as HideValue=90, DangerValue=50.

    This way when the little fella is in a Normal state (roaming, idle, whatever) he avoids the well due to the danger rating on the surrounding zone. However when the dragon appears and the little dude's state changes to flee/hide and scans for cover he sees the well zone has a very high hiding rating and decides to hide in the well. If there are other potential hiding spots he can consider both the danger and hiding values of each to find the best combination of concealment and safety. Of course, some of this could be influenced by other characteristics of the NPCs.

    That's likely how I'd do it. All of this stuff is just simple values assigned to things and then little comparisons and so forth. Well ideally anyway. To me it is all just data structures. Having a really solid data structure makes everything so easy. But if you rely on the NavMesh or any other canned systems I think it will turn something that is very easy into a nightmare. At least that has always been my experience in using such high level systems. It's because you cannot actually see what is going on. Cannot get to any easy to use data structure.
     
    Last edited: Feb 23, 2016
  26. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
    OK so with the existing Navmesh system what is the best way for NPC's to avoid the dragon, and the dragon to pursue the NPC's?

    As I don't think it's possible to have multiple nav meshes for different factions.
     
    Last edited: Feb 23, 2016
    GarBenjamin likes this.
  27. GarBenjamin

    GarBenjamin

    Joined:
    Dec 26, 2013
    Posts:
    7,442
    Hopefully someone who uses the NavMesh can provide their solution and it will help a lot of folks. I guess I just can't see a reason to use both the NavMesh for movement and then still need my own map/structure of data to work with for the other things. It seems like it would duplicate pieces of functionality and would make more sense to just do it all myself so I can have everything I need in basically the same data structure.

    It's a great question and it will be interesting to see what folks say.
     
  28. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    7,139
  29. GarBenjamin

    GarBenjamin

    Joined:
    Dec 26, 2013
    Posts:
    7,442
    I didn't know Unreal actually had such a thing but yeah I have been saying for a long time we need a way to query the environment/game world. That is the whole key to building an interactive game period I think.

    With 2D it is simple just use a tile map data structure. With 3D I don't know what in heck people are using (besides countless casts or simply not tackling such things at all). I'd just use a cube map in 3D to do the same.

    I decided when I return to Unity3D I am going to treat it like any other tool. Normally the first thing I'd do is figure out what I want to build (game wise) and what I need to build it. So I end up with a short list of tools I need to build first before I can actually do any real development. That's just the way it always is in other frameworks. The norm in general I think. My mistake was that, for whatever reason, I thought Unity was a complete system that had all of these basics taken care of right out of the box. It was only after digging into it and wrestling with trying to make any kind of non trivial game that I realized no... it really doesn't have the foundation needed. But that is okay! It does have a lot and we can build what we need.

    Anyway you are exactly right. What is needed is a system focused on creating easy to use data structure that can then be queried at any time. I've checked the asset store a lot and the focus seems to always be on world building tools. But without any underlying data structure to easily work with to "read" and change the world what good is it to build the world? lol

    I mean if I decide to go with OpenGL or anything else besides Unity I planned on making my own 3D World Editor to generate both the visual data and the query data. So it makes sense I might as well start there with Unity too. It's not a Unity problem. More that I think people just think Unity handles all of these things (or should handle them all) so get frustrated when they spend so much time digging and testing and find no it does not.
     
    Last edited: Feb 24, 2016
  30. badgerCopter

    badgerCopter

    Joined:
    Sep 3, 2015
    Posts:
    6
    Sorry to necro this thread, but there may be a way to do this that doesn't involve rolling your own navmesh.

    As far as obstacle avoidance is concerned the following writeup ( http://simonwulf.se/2014/04/mechropolis-fleeing-ai/ ) used navmesh raycasts and a distance check to achieve some decent results, haven't had a chance to test it yet, but came across it this morning (and eventually this post).

    As for the whole of your idea, I think what you're looking for is a way of editing the heuristics/heat-map real-time, somewhat like what oldschool UT did with degrading fearspots/killspots (don't remember the lingo) which made bots avoid areas where a character was just killed (and thus avoid them getting mowed down by some opportunistic player). But, I don't think it's currently possible in Unity since it's navmesh is pre-baked, etc.

    What you can do is role your own navagent as a sort of hybrid, using a physics mover and a navagent together, sort of like The Mecwarriors' (this guy: http://forum.unity3d.com/threads/in...-animation-experts-we-write-tutorials.223903/) solution for combining root motion and navagent movement (would've posted the direct link to said writeup, but it seems to be down). AngryAnt also did a writeup of his own which may give you some ideas as well (http://angryant.com/2014/03/07/Moving-in-Unity/) along with an example cs, but even he said it wasn't complete.

    Long and short is having a navagent that doesn't actually move the character (just get's a desired next location) and have the character's collider extrapolate velocity to follow it. I'd post a hackish example I made awhile back, but it's been misplaced since my last reformat. IIRC it took way more time to research and refine it than it did to write it and I'm not even a coder, just an art monkey pretending to be one.

    You could then use a sphere trigger to add whatever influence you like- push or pull, based on a distance check to the trigger's position(s)- to the physics object's velocity (before applying it) and lerp between that and the navagent's desired location. It'd get kinda hairy the more volumes/triggers you had, but if you wanted it badly enough you could find a way. Finally you'd probably need a coroutine to check a couple times a second to see if the path needs to be recalculated or not. It sounds like a lot of work at the outset, but you only have to do it once, then just slap it in a prefab, toss whatever character you want on it; profit. Helluva lot easier than writing a performant navmesh from the ground up.
     
    Last edited: Apr 27, 2016