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!
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.
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). :)
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.
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.
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.
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
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!
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 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 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
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 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 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!
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.
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 ;
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?
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).
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
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)?
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.
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.
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."
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.
Each box has their own "cost" (distance between 'start' and 'end'). If 2 path leads to same box, the one with lowest Start Distance (G Cost) gets choosed.
A* is extremely useful for spatial distance since the "straight line" heuristic with respect to the space has the property of consistency ( therefore also admissible ) and you can ignore repeated nodes ( by different path ) and assume smallest cost node contains the best solution. Edit: With that assumption you don't have to check every node in the graph which otherwise for infinite ( or really big ) search spaces would take a long time. However if you are not sure you heuristic is consistent it is rather difficult to proof it is, and even more so to find one.
Problem with pathfinding algorithm in 3D games is that they are using 2D algorithm for pathfinding. Two guys have fallen off a cliff not because of pathfiniding (which is fine in this case), but because they are not aware of the cliff (which is AI issue, not just pathfinding). Solution for 3D pathfinding is to use "regions", and mark node for height difference, so pathfinding will include 3rd parent node (difference between 2 levels in height or walkable path for high/low ground). But this algorithm could be very expensive so it's best to mark (by mapping) floors/spots. However, illustrations for Dijkstra and A* algorithm is wrong. Node 2 and 4 is on the wrong side for A* example, and Dijakstra algorithm is not faster and harder for "us programmers". It's pretty much opposite, because Dijkatra algorithm explores a much more nodes which is not faster (which depence of A heuristics).
Actually both Dijkstra and A* are not dependent if the geometry is 2D or 3D and they can even be used for path findings for more than 3 dimensions. The main difference is about how to create the graph in both algorithms and in the case of A* is also which heuristic choose for distance estimation. Once the graph is created both algorithms don't care about the geometry of the original space. Also, when she said that Dijkstra is faster and harder, she was comparing Dijkstra to brute force, not to A*. EDIT: Just another point: the exploit that she showed in Dark Souls was not only about 2D vs 3D, I think was more about creating the nodes only representing the positions and ignoring the momentum. Take in account the momentum it's a huge problem in the path finding for videogames and there is not a clear solution (as I understand, most times the solution used is to create one navigation map with very few nodes, find the path in that graph and then between each pair of nodes do a completely different algorithm that takes in account the momentum(they call it "the local planner").
That is why I mention regions mapping with height difference, walkable ground, including 3rd node. Currently, this is the best (and almost bug free) algorithm.
I also thought that it is the momentums falt in the darksouls example. I think that stff like that is really difficult to programm. for example: you have a cliff and you can fall if you have enoth momentum to a ledge on the other side. it would be really hard for an Ai to realise that the fastest way is to first go a step back in order to exelerate longer. that is hard but possible. now emagine there is also wind changing in intensety and changing the momentum of the ai. As a sidenote: I love mincrafts zombie Ai, there are so many ways to make it run away from you just to walk into an obsticle ;-)
The problem, as mentioned, seemed more like it was that the enemies will try to go at you for an attack within a certain distance, and that this movement trips them off the edge. It's not a part of normal path-finding. I'd imagine the graph isn't actually linked across those height differences.
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 ?
Very good stuff! More detail would be welcome, I think this kind of video can be a lot longer without loss of interest!
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.
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). :)
Watching your videos is like reliving my CSI classes vicariously.
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.
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.
and just 14k views? You deserve way more... Thanks for making these absolutely amazing videos!
OMG, the Dragoons of StarCraft 1 waiting for each other at bridges! :O
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.
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.
you should make a Dijkstra's algorithm explanation video please!!! all the ones on youtube are weird and you explain things so well! thanks.
Fascinating stuff, I would love to see more of these.
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
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!
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.
just found this channel, its amazing! much love from Mexico
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.
This is my first comment on youtube. Saw 2-3 videos of this channel, and I am in love with you 😀.
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
Really interesting, definitely looking forward to the next one!
this channel is everything
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 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 :)
Thank you sm I’ve been searching for ages to this answer
gosh that was so neatly explained.. great channel.
Thanks for creating this video! It is very interesting / enlightening!
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.
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 cool video
more please!
Snake! :)
Thank you for the unique MGS alert sound!
Really interesting from a development perspective
I came for the cat. Subscribed for the cat. And will stay for the cat.
Oh, and videos!
...like this one. Good stuff!
Finally I learnt to pronounce Dijkstra's algorithm
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
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.
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 ;
She got my like at: "Obligatory Praise the sun", but seriously, cool stuff in the vid.
love your explanation.
Awesome video. You are great! Thank you
Super informative, thanks!
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?
You've explained it very well, thank you! ^^
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)
Cool and informative vid. Thanks
Loved this thanks!!
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).
I like your videos so much! Thank you!
Thank you for doing this!
I didn't find "Computer architecture" Playlist in your play list.
The most accurate and fastest pathfinding algorithm is A* with Euclidean distance
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
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..?
:'D I was already in the act of grabing my mouse and twitched back at the "BUT WAIT" :'D
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 :)
Great video
awesome channel. thank you.
programming tutorials with cat drawings? fuck yeah!
You're amazing! Thank you :)
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)?
PRAISE THE SUN!
More dark souls plz.
you are so talented
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
Amazing video
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.
What happens when you put an NPC on a Mesh that isn't a NavMesh?
Thanks for the video =)
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.
hey happie cat can you do a video on total war eats so much compute power
Excellent
I got it!!!!
Thanks for making things easier to understand
#TheHappieCat
:-)
you should do gameplay!
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 vid
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
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.
could you explain why blighttown has frame rate issues?
+Arthur Ferreira they crammed it with particle effects that the engine couldn't handle
I didn't understand how the path is found by the second way to do :c
A-star algorythm uses array structure. There we check all array points, and then find the way. Some books can understand it better than me.
each node have it's own "distance traveled to reach it" variable, when 2 path lead to the same node the path with the highest "dttri" is removed
Each box has their own "cost" (distance between 'start' and 'end'). If 2 path leads to same box, the one with lowest Start Distance (G Cost) gets choosed.
A* is extremely useful for spatial distance since the "straight line" heuristic with respect to the space has the property of consistency ( therefore also admissible ) and you can ignore repeated nodes ( by different path ) and assume smallest cost node contains the best solution.
Edit:
With that assumption you don't have to check every node in the graph which otherwise for infinite ( or really big ) search spaces would take a long time.
However if you are not sure you heuristic is consistent it is rather difficult to proof it is, and even more so to find one.
Very Nice You have saved my day beautifull
That Dijkstra's looks like Viterby's.
A* is so useful
This is interesting.
You have restored my faith in women, thank you.
awesome.
You are awesome
You made the Golems look like idiots! lol Nice video! =D
Problem with pathfinding algorithm in 3D games is that they are using 2D algorithm for pathfinding.
Two guys have fallen off a cliff not because of pathfiniding (which is fine in this case), but because they are not aware of the cliff (which is AI issue, not just pathfinding).
Solution for 3D pathfinding is to use "regions", and mark node for height difference, so pathfinding will include 3rd parent node (difference between 2 levels in height or walkable path for high/low ground). But this algorithm could be very expensive so it's best to mark (by mapping) floors/spots.
However, illustrations for Dijkstra and A* algorithm is wrong. Node 2 and 4 is on the wrong side for A* example, and Dijakstra algorithm is not faster and harder for "us programmers". It's pretty much opposite, because Dijkatra algorithm explores a much more nodes which is not faster (which depence of A heuristics).
Actually both Dijkstra and A* are not dependent if the geometry is 2D or 3D and they can even be used for path findings for more than 3 dimensions.
The main difference is about how to create the graph in both algorithms and in the case of A* is also which heuristic choose for distance estimation.
Once the graph is created both algorithms don't care about the geometry of the original space.
Also, when she said that Dijkstra is faster and harder, she was comparing Dijkstra to brute force, not to A*.
EDIT: Just another point: the exploit that she showed in Dark Souls was not only about 2D vs 3D, I think was more about creating the nodes only representing the positions and ignoring the momentum.
Take in account the momentum it's a huge problem in the path finding for videogames and there is not a clear solution (as I understand, most times the solution used is to create one navigation map with very few nodes, find the path in that graph and then between each pair of nodes do a completely different algorithm that takes in account the momentum(they call it "the local planner").
That is why I mention regions mapping with height difference, walkable ground, including 3rd node. Currently, this is the best (and almost bug free) algorithm.
I also thought that it is the momentums falt in the darksouls example. I think that stff like that is really difficult to programm. for example:
you have a cliff and you can fall if you have enoth momentum to a ledge on the other side. it would be really hard for an Ai to realise that the fastest way is to first go a step back in order to exelerate longer. that is hard but possible. now emagine there is also wind changing in intensety and changing the momentum of the ai.
As a sidenote: I love mincrafts zombie Ai, there are so many ways to make it run away from you just to walk into an obsticle ;-)
The problem, as mentioned, seemed more like it was that the enemies will try to go at you for an attack within a certain distance, and that this movement trips them off the edge. It's not a part of normal path-finding. I'd imagine the graph isn't actually linked across those height differences.
What about GTA GPS pathfinding?
The method she explained isn't limited to Dark Souls, so GTA probably uses a similar system.
Most games use similar approach, but it's not the only one..
I'm almost sure that GTA GPS uses A*, mainly because it's a very standard algorithm and I don't find any reason for trying another approach.
subbed
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.
Dark Souls Forever! (You Died!)
Legal, Cool :)
Nah, what's really happening here is that the NPCs realized their existence was pointless, so they committed suicide by jumping off the ledge. :-)
Damn right dark souls is a good game. I made it.
Oh, hello, Hidetaka Miyazaki!
I wish I had a cat
zoink!!
3:00 "much more faster" xD
unforgivable
Just because your a girl and u like tech stuff doesn't mean, never mind, date me.
i think im in love, haha
way to go lady!!