How A Navigation Mesh Works in 3D Games | AI 101
Вставка
- Опубліковано 1 лип 2024
- AI and Games is a crowdfunded show and wouldn't be possible wthout the wonderful people who support it on Patreon.
/ ai_and_games
www.paypal.me/AIandGames
www.ko-fi.com/AIandGames
You can vote for new AI 101 topics on patreon now at:
/ 21904062
Get yourself an AI and Games t-shirt over on Teespring!
teespring.com/stores/aiandgames
You can follow AI and Games (and me) on Facebook, Twitter and Instagram:
/ aiandgames
/ aiandgames
/ aiandgames
/ get_tuda_choppa
--
In this first of a new series of AI 101 I take a look at navigation meshes: what they are, how they work and how some AAA games exploit them in some pretty interesting ways.
Special thanks to Pauline (The Kebab Dude), Matt (DarkCnix) and Jack (Milk D Seahorse) for helping out filming footage of Tom Clancy's The Division.
--
If you're interested in learning more about navigation meshes here are some links to some resources you might find useful:
- Theory and Overview of Navigation Meshes
en.wikipedia.org/wiki/Navigat...
www.gamedev.net/articles/prog...
developer.valvesoftware.com/w...
- Nav Meshes in Unity
unity3d.com/learn/tutorials/t...
• Video
- Nav Meshes in Unreal Engine 4
docs.unrealengine.com/en-us/R...
docs.unrealengine.com/en-us/R...
- Recast and Detour
github.com/recastnavigation/r...
--
Games in this episode (in order of appearance):
- Watchdogs
- Tom Clancy's Ghost Recon Wildlands
- Grand Theft Auto V
- Tom Clancy's The Division
- Assassin's Creed Unity
- DOOM (2016)
- Halo 3
- Far Cry Primal
- Left 4 Dead
- Outlast
- F.E.A.R.
- Metal Gear Solid V
- Turok 2: Seeds of Evil
- Quake III Arena
- Alien: Isolation
- Far Cry 4
- BioShock Infinite
- Tom Clancy's Rainbow Six: Siege
--
Soundtrack for this episode is "Debug_at_Your_Own_Leisure" by TeknoAxe under the terms of a Creative Commons 4.0 license.
/ teknoaxe
/ teknoaxe
#gamedev #navmesh #R6Siege - Ігри
Hope folks like the new format for AI 101, be sure to let me know in the comments. Meanwhile for any Rainbow Six: Siege fans out there, if you found that bit about the destruction and navmeshes interesting, be sure to check out Julien's full GDC talk. I've been waiting for an excuse to talk about it in a video! 😀
ua-cam.com/video/SjkQxowsL0I/v-deo.html
Is there any use of neural nets?
That explanation of the dynamic nav-mesh in R6 was beautiful
I don't know if that the objective of the channel, but it would be great to have more technical videos explaining the algorithms internally used (for example, to build a navmesh, find the path with A*, smooth it and traverse it)
This is exactly what I'm currently failing in attempting to find.
@@marksmanmerc1 I think the footage in the beginning of the video demonstrates it. First you generate a mesh of connecting surfaces, then you partition that mesh using voronoi fracture. The voronoi fracture can then be interpreted as a graph where you can ultimately apply A* to have your AI navigate through it. That's the basics of it, but implementing it is obviously not so trivial.
Loved this video! I know nothing about programming, so these more "conceptual" rather than technical AI 101 videos are much more engaging for me. Keep it up!
Glad you like the new format. Hoping it proves more accessible for folks.
learn you lazy bum
I’ve been learning programming in school for a year or two with the hopes of becoming a game developer, and I must say that these videos are so amazing. I’ve been playing video games for as long as I can remember, and ever since I started learning basic programming I’ve been imagining how the game’s programming works as I was playing it. These videos explain in great detail aspects of games that I guessed how they functioned, and taught me other parts that I didn’t even know about. This entire topic is extremely interesting to me and I’m so glad I found your videos, because they explain pretty much everything I’ve been curious about, not to mention they’re entertaining and engaging.
Great video that R6 trick at the end is cool. Buying time for the systems to work by using an animation or sequence while presenting to the player that they are engaged. I always felt I was 'doing something' during those moments playing R6 because of the detailed and quick animations; but i was fooled! :)
I love that you description is so well organised. I haven't started my game development journey yet but when I do I'm pretty certain I'll be spending most of my time on your channel. Keep up the good work 👍🏾
I'd suggest having a look at a long-forgotten game by the name of Carrier Command: Gaea Mission. That game manages to do pathfinding for wheeled vehicles with momentum, turning radius and large size, seemingly without a nav mesh or at least with minimal such. Well, it manages that for the most part... I'm told it's based on one of the Arma engines, so that might be interesting to explore.
Castle Story is another good one, if only because they've had AI pathing issues for the last decade or so :) It's a game that has to manage a large number of workers moving across pretty expansive voxel-based terrain with a lot of vertical crossover and blocked paths, all of it malleable in real time. To the game's credit, it does fairly well with what's a non-trivial problem.
I really like this, you're gonna be the first youtuber I actually hit the bell for.
Great video.
Usually when there is a terrain change, we don't recalculate the entire nav mesh, only the ones that are now considered dirty.
I really appreciate the range of knowledge provided in this video. I know about Nav Meshes but not the smarter tricks outlined in the games you mentioned.
0:34 lady where the hell are you going?
This comes at a pretty perfect time for me, as I’m currently dealing with some of these navmesh issues with my AI
Great video, looking forward to the rest of the series!
Man, much thanks for this channel. Best of luck to ya
GTA Glasgow
Missions:
Subcrawl
Wear a blue jersey in the Brazen Head
Try to cross Buchanan St on a busy Saturday
Set GSoA on fire
Secret base under the Necropolis
Powerboat up the Kelvin
Swordfight in Maryhill
@3:10 that Glasgow burn tho... xD
For more dynamic nav meshes you can actually split the mesh up a bit more and have join points like you would for different heights and such and simply have those be disabled when you can no longer get to the other area. This bypasses the need to redo the nav mesh as you build this ability into your navigation algorithm itself instead of needing to have the mesh do it.
Just what I needed for project thanks man
AI and Games Hey Tommy Thompson, I just wanted to write this comment to say I have been watching your videos since your vid on the AI of Alien Isolation. You do an awesome jobs with these videos and I can't wait for more of your content, have a good one.
Nav meshes really do add a lot. Half Life 2 originally used nodes that had to be manually placed within a level that would connect to each other to create the paths the AI could use, which is very tedious to put together. Once Valve started using nav meshes, they can be quickly generated and edited as well as make the AI act more natural.
Half-Life 2 and its derivatives still use nodes, though. But it's correct that navmeshes are much better for a variety of reasons.
This series is great keep it up ! :D
This explains why in the Test Server for Rainbow Six Siege's Neon Dawn season, on the redesign of the Skyscraper map the terrorists literally freeze up and don't enter the building if you play it as a defender.
Ubi has yet to update the Nav Map I guess.
Loved this. Subscribed.
I really like this 101 format
Thanks for creating this, you explain it ace, I am a novice, trying to learn about AI, this has helped me a lot, cheers
Great video,thanks for your hard work! :D
Always love your vids.
Well crafted video, if you keep this up it won't be long till you get a bigger community and more subs
Great video!
A good way to get an idea, fast, of how navigation meshes work is to use Far Cry 3, 4, 5 free map editors on PC or consoles. You could raise a water level (if randomly generated template didn't have water from the get-go), draw a road, place a couple of buildings here and there, then the editor will generate AI data, so you could see all nav meshes for characters, water and ground vehicles. It displays AI covers as well.
10:02 you can see the alien in the wall
Im still plugging through the bread production here, was a wonderful listen though, the Glasgow joke was nicely slipped in there by the way. Its thanksgiving here in Canada, not sure if you do it over there. If so, hope you have a lovely one.
I specifically searched for this subject and found this.
3:16 🤣🤣🤣🤣
13:02 you really went out of your way to say "themself", I can hear the exertion. It wasn't worth it.
14:48 that was really cool.
what a great video
12:43 "The game will search positions off-camera for the characters to spawn onto"
Character then spawns on-camera.
Fantastic video Tommy - I'm an aspiring game developer who learns a lot from your work. Do you have a patreon?
Thanks Chris. Glad you find my stuff useful. I'm over on Patreon at www.patreon.com/ai_and_games
I love Nav mesh stuff, can i have more now? :)
Ahh that Glasgow reference 😂
14:00 Oooohhhh, so that’s why my game tends to lag when I place a Mira. It has to calculate the separate nav mesh with the Mira placed, while also calculating and using the pre-Mira nav mesh. I think what it is, is that either my game is bugged so that the post-Mira nav mesh doesn’t sync efficiently or quickly, or Mira’s window isn’t optimized. I say this because my game typically stutters right as she finishes placing the window, so I assume it’s because it’s switching from one nav mesh to another.
I would love to see an AMA or some sort of Q&A about AI in games with a pro like yourself. Know where I can find something like this?
Who the hell uploads this early in the morning? It's all good though
With nav meshes, is it possible to give multiple values (i.e. speed vs safety (taking into acount cover and line of sight from the player)) to potential routes that the AI will take? For instance, in one circumstance where an AI needs to go to a certain place as quickly as possible regardless of risk to themselves versus another instance where it is best to take a safer route that may take longer.
I assume something like this would be a combined effort from the NPC's AI and the nav mesh provided to it, but that's just my best guess...
Yes you can apply a cost to a region or surface such that it changes how dangerous or important that area is in the eyes of the NPC.
Letting the client recalculate the mesh? I duno, given the importance of the mesh quality, that seems exploitable.
Now that's what I thought when I first heard about this. In the talk they explain that the changes are replicated server-side and then all clients download the update using the same random generator seed. The replicated version is often 99% accurate to client, but that allows them to ensure server authority on the overall destruction and navmesh.
This explain what it is, not how it works... was looking for some algorithms
This is sub-consiously how I thought about how NPCs work, and the Bioshock Infinite one was exactly what I thought!
I'm surprised that how heavily simulated games like Elder Scrolls and Deus Ex are even able to function. NavMesh must be really hard for them.
Bethesda tech games after Oblivion used the radiant AI system to make their NPCs more believable. Simply put, all NPC actors have a schedule that can be evaluated as a function of time. The games evaluate that function when NPCs are in range of the player and set them off to do whatever it is they are scheduled for. In those games nothing happens independent of the player, so when not in range they are not part of the simulation. The schedules are used to give the illusion that things do happen when the player is not around.
Thank you for adding subtitles ! As a french native, they are helpful when I don't understand or know some words. And Amazing content, too !
You're welcome! I understand that not only is the topic rather technical, but my accent doesn't always help either.
@@AIandGames Wow, that's such a fast answer ! Don't worry, your accent is all good, and I would even say that the reason I need subtitles is because you have a very rich english vocabulary (which makes me learn english vocab while also learning AI techniques, so cool !)
I'm really excited to discover your other videos. Thanks for your work !
I was wondering, do player entities also use nav meshes to determine where the player can and cannot go, or is it typically only used by NPCs? Or do player entities typically restrict movement by setting physical barriers or obstacles?
You probably found an answer to this already but just in case; as far as I am aware nav meshes and the like are generally used for AI controlled entities only. Players movement is normally restricted by physics etc as you guessed.
I wish all my school lectures where like this
For how Rainbow 6 Seige pre-calculates navmeshes, how does it handle equipment that explodes instantly like Zofia's grenades?
Lol "get tuda choppa" xD
Neat.
How does Non-ground-based a.i. navigate intelligently? I'm thinking of something like Half-life 2's gunships.
I'm working on a a game based in the ocean and need for npc's to be able to navigate the environment on their own.
Try looking into height maps. They're ideal for characters that move around in such a manner.
I'll be exploring this soon in a video looking at the flying characters in Horizon Zero Dawn.
My guess would be interconnected nodes.
I believe Half-Life 2's Gunships mainly used pre-set paths to move.
The map designer would just manually place a bunch of path nodes in the air, connect them up, and tell the Gunship NPC to start following a path, or even change it up and start following a different one.
@@randomcatdude HL2's gunships use A* based path finding. The 'path nodes' you refer to just relay geometry information to the flying AI. This is so that it knows the shape of the geometry it needs to avoid. However, I'm not sure that this is a fit for my use.
@@phillippi2 What is your source for this information?
This page on the Valve Developer Wiki that I've linked below, states that they do not follow air nodes(which is likely what you're thinking of there). I've also explored the maps themselves in Hammer before, and found the paths that Gunships are set to follow. Considering both of these things, I believe your statement about them using A* is incorrect.
developer.valvesoftware.com/wiki/Npc_combinegunship
Contrast's AI seems to have a lot of problem with the basic walking
Can I just mention that you sound terrifyingly identical to Scott Manley?
NPCs: _I do as the navigation mesh guides_
hmm, so in Rainbow Six Siege a hacked client can totally screw up all the AIs in the game?
I still think you sound like Ian Rider
What, Ewan McGregor? Nah.
I like Dűm more than Doom.
Dewm
DØM
Node Graph out of date. Rebuilding...
One broken NPC down-voted this video.
My UA-cam nemesis strikes again!
Ok, who else read it as "navigational memes"?
Very interesting video but trust me - The AI in Wildlands is utterly brain dead.
Oh I know how the Wildlands AI works and you're right, it's kinda dumb but the reasons for it are really interesting. There might even be an episode next year dedicated to it.