A* tricks for videogame path finding
timmastny.com
A* tricks for videogame path finding
1–10 of 108 posts
Re: A* tricks for videogame path finding
#2It would be interesting to see these classical methods compared to a simple RL method that optimizes a tiny neural net or decision tree which is given access to the map, player, and monster positions. I think it would cost a tiny bit more compute but have fewer annoying edge cases.
Re: A* tricks for videogame path finding
#3Any time A* comes up, someone plugs this great resource: https://www.redblobgames.com/pathfinding/a-star/introduction...
Re: A* tricks for videogame path finding
#4It would be interesting to see these classical methods compared to a simple RL method that optimizes a tiny neural net or decision tree which is given access to the map, player, and monster positions. I think it would cost a tiny bit more compute but have fewer annoying edge cases.
I suspect that it would have a similar number of edge cases, but they would be harder to interpret and reproduce. That's just been my experience with moving from unlearned algorithms to deep learning in general.
Re: A* tricks for videogame path finding
#5The “depth too small” problem shown in the last animation produces an interesting behavior appearance; it looks like the monster is “waiting to see” which way you’ll go. I think you can even “fake it out” by starting to go in one direction, then switching, right?
Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
Re: A* tricks for videogame path finding
#6The “depth too small” problem shown in the last animation produces an interesting behavior appearance; it looks like the monster is “waiting to see” which way you’ll go. I think you can even “fake it out” by starting to go in one direction, then switching, right? Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
Author here: That's a cool idea, I hadn't thought of that! It doesn't quite work in the current implementation, but would with some small tweaks.
Basically we would need to have the enemy update their path only after a small delay (instead of every frame), so "momentum" would carry them on their existing path so the player could fake them out.
Re: A* tricks for videogame path finding
#7The “depth too small” problem shown in the last animation produces an interesting behavior appearance; it looks like the monster is “waiting to see” which way you’ll go. I think you can even “fake it out” by starting to go in one direction, then switching, right? Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
Author here: That's a cool idea, I hadn't thought of that! It doesn't quite work in the current implementation, but would with some small tweaks. Basically we would need to have the enemy update their path only after a small delay (instead of every frame), so "momentum" would carry them on their existing path so the player could fake them out.
It could also be interesting to target a tile some number of nodes in front of the player, so the monster will go to “cut the player off” sometimes. Maybe it could result in some interesting behavior if combined with your momentum idea. The goal of enemy AI is to be trick-able in a fun manner, right?
Of course, it is easy to come up with fun ideas for enemy AI, I think if you went after all of them you’d never have time to write the nice blog post.
Re: A* tricks for videogame path finding
#8Earlier quoted context omitted.
Author here: That's a cool idea, I hadn't thought of that! It doesn't quite work in the current implementation, but would with some small tweaks. Basically we would need to have the enemy update their path only after a small delay (instead of every frame), so "momentum" would carry them on their existing path so the player could fake them out.
It could also be interesting to target a tile some number of nodes in front of the player, so the monster will go to “cut the player off” sometimes. Maybe it could result in some interesting behavior if combined with your momentum idea. The goal of enemy AI is to be trick-able in a fun manner, right? Of course, it is easy to come up with fun ideas for enemy AI, I think if you went after all of them you’d never have t…
You have invented the pink ghost from Pac-Man.
Re: A* tricks for videogame path finding
#9The “depth too small” problem shown in the last animation produces an interesting behavior appearance; it looks like the monster is “waiting to see” which way you’ll go. I think you can even “fake it out” by starting to go in one direction, then switching, right? Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
i did exactly this implemented w a turn delay + "scent trail following" added on too, it works out nicely and at times looks like the ai is pausing to recollect itself before beelining towards the player lol
Re: A* tricks for videogame path finding
#10Earlier quoted context omitted.
It could also be interesting to target a tile some number of nodes in front of the player, so the monster will go to “cut the player off” sometimes. Maybe it could result in some interesting behavior if combined with your momentum idea. The goal of enemy AI is to be trick-able in a fun manner, right? Of course, it is easy to come up with fun ideas for enemy AI, I think if you went after all of them you’d never have t…
You have invented the pink ghost from Pac-Man.
The pac-man ghost AIs are definitely worth a search, fun stuff from such a simple program.