There's also the Pad/preset system that Perfect Dark, and some other Nintendo 64 games used. Where there would be hundreds of points on a map and the AI would run to the point, then move to the next one. The unique thing is the navigation presets would be manually programmed, so that if there was a preset running into a wall, there'd be no direct path to it, so the AI never ran off cliffs, since someone on the dev team specifically ensured they couldn't.
We learned about this in the Artificial Intelligence module of my degree. One of the assignments was to solve the Travelling Salesman Problem (TSP) using a genetic algorithm. I wrote a solution in Javascript so it can run on almost anything that has a browser. Genetic Algorithms are also used in game path finding, as they can be quite fast and pretty accurate!
Very disturbing: we have the same handwriting, including irregularly written e or a. That aside, this is a very nice video, as a game designer I enjoyed it very much. Very educatively put!
MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! MY TIMESKIP IS UNBEATABLE! ....."Time to make the donuts."
You slightly simplified the darkroot garden glitch as it is because the AI (In this case the humanoid AI meant to act like a player as most enemies in the game have different aggro and behaviour) knows you have bottleneck it so it is trying to get the jump on you as by driving to its death. If you don't break off from the enemies when running they will simple follow you inside of trying to find a way to sneak up on you so this is more a behavioural exploit than path finding after for the crystal golems they use a very simple shortest route to the player method so they only use one path finding method as like most simple enemies they only attack forward withing aggro range and cannon leave it to find away around as they would break aggro, This is beast found with the "super aggressive mod" that would stops this problem to only increasing agrro range. Ever way great video and subbed, keep up the great work.
wow happie cat your videos are very educational! Great Job explaining programming principles and how things work...i have a new perspective on some of those subjects thanks to you :D Finite State machine explanation was excellent :D
That was really helpful ; I am doing college project about pathfinding Visualizer I don't know the Topic is something just deep ; Thanks video just help me to understand pathfinding more effective ;
would it be conceivable to program mob AI to work 'clairvoyantly' in reverse from the target destination, eliminating path selection backwards. Ideally, this would not only make MUCH smarter mobs, but allow for some very complex mechanics to be selected between confrontation & aggro. thoughts on this..?
Can you explain to me how people find glitches in games like call of duty? In multilayer maps people find the weirdest things that I wouldn't even come close to finding out. How do people do this? Do they know where the grid mesh for the AI is(For zombie mode)?
That was pretty interesting. It is fun to know the underlying principles. I just know a few places in the game where pathing is lethal. Much to my delight.
i know the* algorithm but the pathfinding in starcraft 2 follow surprise me, It's so smooth and precise... how could the modules are disposed in the map? are there thousands of very little modules for everywhere or could have another system like modules inside of modules?
6:00 actually no. It just doesn't calculate the collusion that happens. If there was no collusion the AI would jumped down without falling off the edge. As the enemy is jumping down it steps on the characters head and then it's forced keep on walking forward.
well Pathfinind Algorithm has been imporeved now. since then its not completlty hardcoded anyway.. it just takes a simplified version of mesh with places marked as allowable and forbidden which can dynamically be triggered or switched.and then bots are configured with set of automated queries with a different buffer, that makes them aware of possible routes it has to reach , since path distance has already be calculated, hence so itll move like there . And yes noth everytime we need it to trace the shortest path and so its upto game logic ;) to mark places as forbidden forcing system to use longest path.
Ive noticed bethesda games dont have this problem despite being much larger. Ai routines must account for things like height. If you run up some stairs the enemies always run up after you, not into a wall below youm
Very informative. Graphics today in video games are very advanced and more realistic. In my opinion, pathfinding is still way too far complicated as compared to how a person does it.
The devs didn't patch this, because it is useful for bad players or players that need lots of souls. They could easily have patched it so that they back away from the corners of the map.
For my game, i am going to use an easier system. Its a tile mapping game so, it determines the distance to the player, it checks for obstacles and if it finds one it tries to go around it
A* is pretty useful even for large games, and the path finding algorithm in the graph usually is not the big challenge for the path finding AI. Both A* and Dijkstra can process only few of the nodes in each iteration of the gameloop. Bigger challenges is choose how to create the navigation map, how often recalculate the path finding in case that the target moves, what to do if the agent find an obstacle in an already planned path or how to deal with the momentum. A different algorithm may be required if there are a lot of agents moving at the same time (for example, the Zerg).
Subway stations in GTAV (particularly Portola Drive) is a great example of this. You can stand in the tunnels, take shots at passengers on the platform with a sniper rifle, and the police gather around the street above you, allowing you to rack up kills to increase the amount of ammo you can carry without the inconvenience of getting arrested or killed, or having to outrun the police.
I would like to add, that dijkstra's algo can be used to precompute graph for start node A. Then, any query that starts in path node A but ends whereever you want, can use the precomputed graph. Like this, you can keep list of precomputed graphs for various start nodes. (depends on game / situations). :)
Thank you. This is one of the better videos on how pathfinding actually works. Most videos are just tutorials of how to utilize a nav mesh in game engine X. Having taken discrete math, the idea of boiling a surface down to a series of nodes makes a lot of sense. Thank you.
When it comes about this topic, it's impossible not to mention StarCraft. Nice presentation, with examples and hilarious bugs from Dark Souls. That's the dream!
I have only 2 things to say. 1 your videos are amazing. I can only imagine how good they are for people without prior knowledge. 2 Dammit! I thought my idea of making simple instructional game development videos were unique 😄 guess it is good I didn't start yet
There's a fun video with a developer of C&C Tiberian Sun where he explains that the way they made the ai more efficient for processors was to not put allies into account and simply tell them to move if they collide. Thought of this when you said they just wait until the unit moves to continue.
That was really interesting! The cost based system reminds me of link state routing over computer networks, it's cool to see it applied here. I think I'll peruse this channel further :)
Very good stuff! More detail would be welcome, I think this kind of video can be a lot longer without loss of interest!
There's also the Pad/preset system that Perfect Dark, and some other Nintendo 64 games used. Where there would be hundreds of points on a map and the AI would run to the point, then move to the next one.
The unique thing is the navigation presets would be manually programmed, so that if there was a preset running into a wall, there'd be no direct path to it, so the AI never ran off cliffs, since someone on the dev team specifically ensured they couldn't.
+Lucetube GPlusStillSux Is that implementation similar to Half Life 2?
Probably, I'm not quite familiar with HL2's system though
And how is that different? It's the same idea: a graph is constructed than an algorithm searches to find a path across.
Really interesting, definitely looking forward to the next one!
She got my like at: "Obligatory Praise the sun", but seriously, cool stuff in the vid.
Great video
Dark Souls Forever! (You Died!)
We learned about this in the Artificial Intelligence module of my degree. One of the assignments was to solve the Travelling Salesman Problem (TSP) using a genetic algorithm. I wrote a solution in Javascript so it can run on almost anything that has a browser. Genetic Algorithms are also used in game path finding, as they can be quite fast and pretty accurate!
genetic algorithm ? you mean trying random path and keeping the best ones ?
Or... just go directly to the player.
if (botX < X) {
botX++;
} else {
botX--;
}
if (botY < Y) {
botY++;
} else {
botY--;
}
better?
Tanan ?
Tanan yes until there is a wall between them
OMG, the Dragoons of StarCraft 1 waiting for each other at bridges! :O
I came for the cat. Subscribed for the cat. And will stay for the cat.
Oh, and videos!
...like this one. Good stuff!
VaatiVidya brought me here, and I was not disappointed. This is an insightful look into an often poorly understood mechanic.
Sangheilitat117 From where did this get linked by VaatiVidya? Or did you find it from the subreddit?
Ah, he linked it on his tumblr actually.
Sangheilitat117 Woah!
Sangheilitat117 Was it before all the plagiarism stuff flooded or after?
I honestly have no idea what you're talking about.
that graph u drew, reminded of the Signal-Flow Graph in control theory, the only difference being what u call edges r actually called paths in SFG
Rebel Raime Yeah, high-level and low-level stuff share many of the same models. It's pretty cool.
Very disturbing: we have the same handwriting, including irregularly written e or a. That aside, this is a very nice video, as a game designer I enjoyed it very much. Very educatively put!
LOL, compare it to Me and tekking101, he's eerily similar to me. He looks like me, acts like me, and even a bit of his life stories are like mine.
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
MY TIMESKIP IS UNBEATABLE!
....."Time to make the donuts."
great explanation! I adore your very real world examples for explaining different mechanisms.
You slightly simplified the darkroot garden glitch as it is because the AI (In this case the humanoid AI meant to act like a player as most enemies in the game have different aggro and behaviour) knows you have bottleneck it so it is trying to get the jump on you as by driving to its death. If you don't break off from the enemies when running they will simple follow you inside of trying to find a way to sneak up on you so this is more a behavioural exploit than path finding after for the crystal golems they use a very simple shortest route to the player method so they only use one path finding method as like most simple enemies they only attack forward withing aggro range and cannon leave it to find away around as they would break aggro, This is beast found with the "super aggressive mod" that would stops this problem to only increasing agrro range. Ever way great video and subbed, keep up the great work.
PRAISE THE SUN!
More dark souls plz.
wow happie cat your videos are very educational!
Great Job explaining programming principles and how things work...i have a new perspective on some of those subjects thanks to you :D Finite State machine explanation was excellent :D
That was really helpful ; I am doing college project about pathfinding Visualizer I don't know the Topic is something just deep ;
Thanks video just help me to understand pathfinding more effective ;
would it be conceivable to program mob AI to work 'clairvoyantly' in reverse from the target destination, eliminating path selection backwards. Ideally, this would not only make MUCH smarter mobs, but allow for some very complex mechanics to be selected between confrontation & aggro.
thoughts on this..?
Nah, what's really happening here is that the NPCs realized their existence was pointless, so they committed suicide by jumping off the ledge. :-)
Can you explain to me how people find glitches in games like call of duty? In multilayer maps people find the weirdest things that I wouldn't even come close to finding out. How do people do this? Do they know where the grid mesh for the AI is(For zombie mode)?
Too easy for Dark Souls? Dark Souls is full of exploits that are legitimally accepted because of its punishing difficulty.
Yo that cat graph was rad as shit.
Krasnoya Ronin Your avatar is also rad as shit.
shit is not red 😡
shit is not red 😡
shit is brown... and rad
That was pretty interesting. It is fun to know the underlying principles. I just know a few places in the game where pathing is lethal. Much to my delight.
i know the* algorithm but the pathfinding in starcraft 2 follow surprise me, It's so smooth and precise... how could the modules are disposed in the map? are there thousands of very little modules for everywhere or could have another system like modules inside of modules?
programming tutorials with cat drawings? fuck yeah!
6:00 actually no. It just doesn't calculate the collusion that happens. If there was no collusion the AI would jumped down without falling off the edge. As the enemy is jumping down it steps on the characters head and then it's forced keep on walking forward.
well Pathfinind Algorithm has been imporeved now. since then its not completlty hardcoded anyway.. it just takes a simplified version of mesh with places marked as allowable and forbidden which can dynamically be triggered or switched.and then bots are configured with set of automated queries with a different buffer, that makes them aware of possible routes it has to reach , since path distance has already be calculated, hence so itll move like there . And yes noth everytime we need it to trace the shortest path and so its upto game logic ;) to mark places as forbidden forcing system to use longest path.
Ive noticed bethesda games dont have this problem despite being much larger. Ai routines must account for things like height. If you run up some stairs the enemies always run up after you, not into a wall below youm
and just 14k views? You deserve way more... Thanks for making these absolutely amazing videos!
Very informative. Graphics today in video games are very advanced and more realistic. In my opinion, pathfinding is still way too far complicated as compared to how a person does it.
I find your videos, Ur so awesome. THX for doing this videos. (I'm not a native speaker, so sorry if I make some mistake in my text)
I didn't find "Computer architecture" Playlist in your play list.
The most accurate and fastest pathfinding algorithm is A* with Euclidean distance
The devs didn't patch this, because it is useful for bad players or players that need lots of souls. They could easily have patched it so that they back away from the corners of the map.
Finally I learnt to pronounce Dijkstra's algorithm
Snake! :)
Thank you for the unique MGS alert sound!
Thank you sm I’ve been searching for ages to this answer
Just because your a girl and u like tech stuff doesn't mean, never mind, date me.
That's some lazy design, From :/
Awesome video. You are great! Thank you
through "nodes", it became much easier to understand! thanks mis!! :)
alekxsander eduardo Glad it helped! Thanks for watching!
For my game, i am going to use an easier system. Its a tile mapping game so, it determines the distance to the player, it checks for obstacles and if it finds one it tries to go around it
Really interesting from a development perspective
Fascinating stuff, I would love to see more of these.
gosh that was so neatly explained.. great channel.
That Dijkstra's looks like Viterby's.
You have restored my faith in women, thank you.
Very Nice You have saved my day beautifull
Cool and informative vid. Thanks
What happens when you put an NPC on a Mesh that isn't a NavMesh?
hey happie cat can you do a video on total war eats so much compute power
unless you're valve -- then it doesnt work at all
You made the Golems look like idiots! lol Nice video! =D
very cool video
more please!
Reminds me of gta 3 where you could get 6 stars, go onto the container ship and just watch the cop cars drive into the water, provided lots of laughs
awesome channel. thank you.
I knew about the A* algorithm, but I think it's not doable for large scale games to run it in runtime for several units at once. Great tutorial.
menosferato Many games do use A*, it's Dijkstra's that would take awhile for each unit :) Thank you!
A* is pretty useful even for large games, and the path finding algorithm in the graph usually is not the big challenge for the path finding AI.
Both A* and Dijkstra can process only few of the nodes in each iteration of the gameloop.
Bigger challenges is choose how to create the navigation map, how often recalculate the path finding in case that the target moves, what to do if the agent find an obstacle in an already planned path or how to deal with the momentum.
A different algorithm may be required if there are a lot of agents moving at the same time (for example, the Zerg).
Subway stations in GTAV (particularly Portola Drive) is a great example of this. You can stand in the tunnels, take shots at passengers on the platform with a sniper rifle, and the police gather around the street above you, allowing you to rack up kills to increase the amount of ammo you can carry without the inconvenience of getting arrested or killed, or having to outrun the police.
Thanks for the video =)
I would like to add, that dijkstra's algo can be used to precompute graph for start node A. Then, any query that starts in path node A but ends whereever you want, can use the precomputed graph. Like this, you can keep list of precomputed graphs for various start nodes. (depends on game / situations). :)
Thank you. This is one of the better videos on how pathfinding actually works. Most videos are just tutorials of how to utilize a nav mesh in game engine X. Having taken discrete math, the idea of boiling a surface down to a series of nodes makes a lot of sense. Thank you.
When it comes about this topic, it's impossible not to mention StarCraft. Nice presentation, with examples and hilarious bugs from Dark Souls. That's the dream!
could you explain why blighttown has frame rate issues?
+Arthur Ferreira they crammed it with particle effects that the engine couldn't handle
love your explanation.
you should make a Dijkstra's algorithm explanation video please!!! all the ones on youtube are weird and you explain things so well! thanks.
*very good* *hello* *im sorry* *help me*
I have only 2 things to say. 1 your videos are amazing. I can only imagine how good they are for people without prior knowledge. 2 Dammit! I thought my idea of making simple instructional game development videos were unique 😄 guess it is good I didn't start yet
this channel is everything
Loved this thanks!!
This is my first comment on youtube. Saw 2-3 videos of this channel, and I am in love with you 😀.
you should do gameplay!
:'D I was already in the act of grabing my mouse and twitched back at the "BUT WAIT" :'D
There's a fun video with a developer of C&C Tiberian Sun where he explains that the way they made the ai more efficient for processors was to not put allies into account and simply tell them to move if they collide. Thought of this when you said they just wait until the unit moves to continue.
I got it!!!!
Thanks for making things easier to understand
#TheHappieCat
:-)
why is it the norm to "abuse" games? why is cheating seen as such a great thing? what happened?!
Halskitchen What are you talking about?
That was really interesting! The cost based system reminds me of link state routing over computer networks, it's cool to see it applied here. I think I'll peruse this channel further :)
I like your videos so far! You're also absolutely gorgeous! :D
TheBcoolGuy go away shes mine.
Ryan Noble Hahaha. She's neither of us', mate. I just wanted to tell her that. I know you know this, but whatever, man.
Watching your videos is like reliving my CSI classes vicariously.
just found this channel, its amazing! much love from Mexico
you are so talented
A* is so useful
This is interesting.
Amazing video
I wish I had a cat
You've explained it very well, thank you! ^^
Legal, Cool :)
Thanks for creating this video! It is very interesting / enlightening!
You are awesome
Super informative, thanks!
You're sweet
Yay, A*, that is what I will be writing a school paper about!
Mein Kanal! Just stay a healthy distance away from the event horizon.
***** That means?
Mein Kanal!
Well, -10 nerd cred for you: en.wikipedia.org/wiki/Sagittarius_A*
***** Ah! Also, when you search for D*, you get you get some sort of radios :)
I like your videos so much! Thank you!
beep boop beep
You're amazing! Thank you :)
Damn right dark souls is a good game. I made it.
Oh, hello, Hidetaka Miyazaki!
Excellent
Marry me
awesome.
Great vid