11 ms·

Enemy AI: chasing a player without Navigation2D or A* pathfinding

428 points by atomlib 6y ago

60654 6y ago
TLDR: instead of doing generic pathfinding, the player avatar drops decaying "scent" into the world grid, and enemies follow the player by doing gradient ascent. The first time I've seen this technique in use was in the classic SimAnt game by Maxis, in the 90s; in research it was also explored in the ALife community. It's a cool trick, but by itself it's not quite enough, it's good for insect behavior but not much more. But what has been useful is combining standard pathfinding with this. For example, imagine if one of your units dies and drops some "scent of death" into the surrounding area - and that scent gets incorporated into A* as a large cost value for traversing this terrain. Now all your other units will "smartly" start avoiding the dangerous area for a while, without having to do any expensive analysis of why the unit died there, e.g. was there an ambush there or some such. (Google for "potential fields" and "flow fields" in games for more examples from commercial games.)
- anotheryou 6y ago
  "If no line of sight..." I might add
  - badloginagain 6y ago
    Makes me think you can add scent trails to many objects- like the path of a fired arrow. Would help mitigate the "stealthy archer" problem Skyrim AI has.
    - enchiridion 6y ago
      I'm not familiar with that problem.
      - flqn 6y ago
        The "stealth archer" build in skyrim is overpowered since the enemy AI can't usually know where the arrow came from, and they tend to aggro, look around their immediate area, then go back to the idle state allowing the player to shoot them again from a safe, hidden spot. Rinse and repeat, and almost any encounter in the game with hiding spots is trivial.
    - egypturnash 6y ago
      I’ve been playing AssCreed Odyssey as a stealthy archer and it’s solution to that particular problem seems to be attaching your location to each fired arrow; enemies within some radius of where the arrow hit are given a search target somewhere near your position when shooting. Add in some “It came from over there!” barks and it works pretty nicely If you are far enough away there is a big hole in this wherein they can’t get to your position before their maximum-amount-of-time-in-search-mode timer fires off and they go back to their normal location and behavior, though.
- DonHopkins 6y ago
  In Micropolis, the open source version of SimCity, I scripted a "PacBot" agent in Python: a giant PacMan who follows the roads around, looking for traffic to eat, always turning in the direction of the most traffic. The PacBot only has a limited local view down the roads a few cells, and can't see around corners. Even though they're extremely simple and stupid and short-sighted, they still have interesting emergent behavior when multiple PacBots are competing for the same traffic, like how PacBot will give up and turn around when its competitors eat the cars it was wok-a-wok-a-ing towards. There is a good example of lots of competing PacBots around 0:55: https://www.youtube.com/watch?v=8snnqQSI0GE https://www.youtube.com/watch?v=8snnqQSI0GE >Now you have some good, uuh, there's some traffic here. There's this thing called a PacBot. It's this PacMan that follows the road around looking for traffic. And then he eats it. So that's good for your city. And you can have a lot of different PacMans on the thing, and you know, just editing the road gives the PacMan somewhere to go. So their score is how many cars they've eaten. So it's an "agent", and it woks all around, and he follows roads. And you can put a lot of them on the map to keep the traffic low. MicropolisRobot.scanRoads looks down the road in a given direction for a given distance, and counts the number of cars (in the traffic density layer), attenuated by distance (further away cars don't count as much). https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropolisrobot.py#L238 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb... Then the PacBot simulator calls scanRoads in all possible different directions to get a score, and moves in the direction of the best score. https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropolisrobot.py#L513 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb... As it turns out, the PacBot is actually the God of the Church of PacMania (each Polytheistic PacMania Church spawns up to four PacBot God Agents, if it's connected to a road), and the church zone itself generates a LOT of traffic, in the hopes of attracting the PacBots. The emergent behavior is that followers of the Church of PacMania happily drive back and forth between church, home, work, and shopping, again and again, in the hopes of sacrificing themselves to their God, PacBot. And the PacBot Gods hang out around the Church of PacMania, eating their followers, and raising their scores -- everybody's happy! class MicropolisZone: def generateRobots(self): https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropoliszone.py#L239 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb... class MicropolisZone_ChurchOfPacMania(MicropolisZone): https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropoliszone.py#L310 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb...
mrspeaker 6y ago
So simple and obvious as soon as you see it in action. I love "hacks" like this: really easy to code, but with a big impact - and so many potential uses too! I'm adding "scent trails" to my bag of tricks for sure.
- enrichp 6y ago
  yes
FZ1 6y ago
Why are they calling it "AI", though? There isn't any AI or ML. You leave a trail for the enemy to follow, and they follow it. It's not even path-finding, it's path-following. Which is pretty much an if-then statement. It's a neat, simple approach, and fun to watch. But there isn't any learning, or knowledge, or other AI.
- tantalor 6y ago
  AI in the sense of "player vs. AI" is widely understood. AI does not require ML. "It's part of the history of the field of artificial intelligence that every time somebody figured out how to make a computer do something—play good checkers, solve simple but relatively informal problems—there was a chorus of critics to say, 'that's not thinking'." https://en.wikipedia.org/wiki/AI_effect https://en.wikipedia.org/wiki/AI_effect
- bkovacev 6y ago
  Could you provide a list of games that have "actual" AI/ML baked in for their NPCs? I'm curious as I haven't heard of them before.
  - meheleventyone 6y ago
    There’s a few, most notably this racing game used neural nets before they were cool: http://www.ai-junkie.com/misc/hannan/hannan.html http://www.ai-junkie.com/misc/hannan/hannan.html A lot of modern work has focused on procedural animation versus behaviour but the two are quite intertwined: https://youtu.be/JZKaqQKcAnw https://youtu.be/JZKaqQKcAnw
- dgb23 6y ago
  AI is much broader than ML. In gaming specifically you typically label behavior of dynamic, life-like entities as AI. Behavior trees, state-machines, path-finding and so on. A typical example: the ghosts in pacman.
- ncallaway 6y ago
  In games "AI" is the term for the system that controls the behavior of NPCs and other non-controlled entities. It's not claiming to be "academic AI". Games have been using this terminology for decades.
ariadnavc 6y ago
1
Dotnaught 6y ago
If you’re modeling an intelligent pursuer, the algorithm should anticipate future travel rather than just following.
- eru 6y ago
  Yes. But for simple enemies, the algorithm suggested gives interesting behaviour, and plenty of ways for players to manipulate it. The latter is useful to open up extra gameplay.
- itdagusszous 6y ago
  In games the goal of the developer isn't necessarily to have intelligent agents, but to have agents that are fun to play against. Sometimes the goal is to have them be intelligent, but sometimes having them behave in "dumb" but predictable ways makes the game overall more fun.
  - dkersten 6y ago
    This is the reason usually given for using relatively simple techniques like behavior trees, but, anecdotally, I find that the biggest let down in most games is that the AI is so dumb that it 1) is immersion breaking, and, 2) get same-y and boring very very quickly.
    - eru 6y ago
      Yes. It depends on what the game is trying to achieve. Subset Games, the makers of FTL and 'Into the Breach' have talked about this extensively. 'Into the Breach' deliberately has the enemies telegraph their plans one turn ahead of time, and the game is all about interfering with those plans. The rest of the game's design carefully reinforces the message that the enemy units are not intelligent. The backstory has them as basically oversized insects. If you have a game that pretends to give you realistic human antagonists, but they behave mechanically dumb and predictable, that breaks immersion like you suggest. One big problem is that having very smart AI that's purely there to oppose you in a zero sum game ain't fun to play against for most people. The handicaps a modern chess or Go engine would have to give you a normal human for a fair fight are ludicrous. And people seldom want fair fights in their games. They want a feeling of accomplishment, but without actually putting in all that much work. Even hardcore games like XCom cheat in your favour behind the scenes. There are at least two ways out of this while still avoiding the boring repetition: - carefully make the NPC make believable human-like (or animal-like) mistakes, instead of easily exploitable repetitive mistakes - give the NPC goals that are in conflict with the player, but not 100% so. A silly example of the second option: Take a game like Thief that's all about sneaking around stealthily and stealing stuff. Now realistically, most of the guards are just hired goons. They don't want to die, but they don't particularly care about protecting the place. They do care about being seen doing their job, so they don't get fired. So your job as a player could be, in addition to staying unseen, to provide plausible distractions and reasons for the guards not too investigate to closely. Higher ranked guards, and owners, would be under higher pressure to perform and won't get away with excuses. So they would be more alert. Using the same trick over and over again would lower it's effectivity: guards can't plausible claim to their higher ups to have been tricked again and again. If you are starting to become aggressive to a guard, or he learns that you called one of his friends, the guard's priorities will change towards more self-preservation. A pacifist run might even earn you respect and admiration from the lower level guards. Just like cat burglars are often admired in real life. Seen a bit more abstract, the game now becomes one of three factions: the thief (that's you), the low level guards and their employers. All with partially overlapping, partially conflicting goals. You can throw insurance companies into the mix, if you want to make it even more complicated. Thanks to the non-zero sum nature of the partial conflict, you can crank up how smart everyone acts, without overwhelming the player: Eg smarter guards might figure out a way to de-escalate that still looks like a plausible and even courageous move to their employers.
b0rsuk 6y ago
A fascinating AI technique is used in one of the best roguelikes, Brogue. The author called it "Dijkstra Maps". Basically it's about generating a heatmap for all the squares on the level. You can start with 0 at player position, and from that point use a simple floodfill algorithm, putting down increasing numbers with each step. Then a monster simply examines all adjacent squares and selects the one with lowest number. This has at least two notable advantages: 1. You only need to do the path generation once, and it scales very well with the number of monsters. 2. It's really good at combining several concerns, because you can generate a couple of heat maps for different concerns and add them up. For example one heat map is about proximity to player. Another could be about proximity to health pickups, or proximity to cover, or proximity to open space if a monster likes to keep distance and shoot. If a gas trap is triggered, you can use a "danger" heat map. Then a monster can easily get closer to player and at the same time choose the path which has fewer harmful effects. That's why centaur archers in Brogue are so annoying, monsters avoid traps intelligently, monster groups avoid wasting their numerical advantage by chasing player through a corridor. He described it in detail in this article: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps http://www.roguebasin.com/index.php?title=The_Incredible_Pow... And in case you're wondering, Brogue source code is licensed on AGPLv3.
- Jaxan 6y ago
  So basically just a shortest path algorithm starting from the player to all other tiles?
  - masklinn 6y ago
    Sounds like that's what the base layer is yes, though the additional layers are interesting.
  - fwip 6y ago
    Not exactly - a shortest path algorithm would lead to the monsters "anticipating" the player coming around the obstacle and cutting them off. The algorithm is summarized in the article as: "When an enemy enters the Chase state it tries to raycast to the player and if nothing is in the way - chase em! If something is in the way, it goes through the scent trail in order and tries to raycast to each scent until it can see one, then - chase it!" With complex geometry, this will frequently lead to a non-optimal route, and is probably more fun to play against.
DennisP 6y ago
It might make sense to have the monsters repulse each other. By spreading out, they'll end up taking multiple paths around obstacles, coming at you from different directions, so it looks like more intelligent coordinated behavior.
- ghthor 6y ago
  I've used this pattern before in game AI's and it works well. If you combine it with a somewhat random searching incentive the "hive" will spread out and search for the player(s). I also let the "hive" communicate with each other if they find a player they let each other know and then set a new waypoint for that area. When they repulse each other they take different pathways around objects and it looks a feels great to play against.
dfgdghdf 6y ago
This technique shows how game AI is different from academic AI. The goal is to create interesting gameplay with minimal performance overhead. This system is just as fun a as "correct" system, but far simpler to implement and cheap to execute.
- jfkebwjsbx 6y ago
  It is academic AI. A lot of papers go on how to implement algorithms fast or how to implement the best approximation within a given time, etc.
Datenstrom 6y ago
A former colleague of mine Meghan Chandarana was doing some really awesome work which incorporated a similar "bread-crumb" algorithm for swarms dispatching groups for tasks and navigation back to the swarm. It wasn't the primary focus but was really cool to see work. If you want to see a application of it for swarms her paper is here: https://www.ri.cmu.edu/wp-content/uploads/2018/08/SMC2018.pdf https://www.ri.cmu.edu/wp-content/uploads/2018/08/SMC2018.pd...
simias 6y ago
I'm always saddened that more works doesn't go into making fun and original game AIs. Most AAA games that are released these days have utterly predictable AI, modern shooters don't seem a lot more evolved that Quake 1. It's too bad because games like F.E.A.R. have shown that even simple AI heuristics can lead to very interesting emergent behavior. TFA demonstrates that very simple AI tweaks can make the enemies feel more organic and realistic. I suppose that some of the problem is that good IA doesn't make for nice trailers and ads (since you can just script those to do whatever you want anyway).
- lainga 6y ago
  I think most companies have given up on good AI (except maybe id) - all the money's in PvP. Single player campaigns are an afterthought.
  - colmvp 6y ago
    I think it's more cost efficient for companies to give the CPUs some absurd advantage (crazy amount of HP, powerful attacks) and call it day. Problem with AI is even if you spend a lot of time trying to get it right, it can make choices that are confusing to us humans and illicit ridicule from the player base.
    - hutzlibu 6y ago
      Well, the choice to make AI hordes braindead zombies who hust mindlessly storm you, is confusing to me as a player, too, if the enemie are supposed to be not zombies, but smart special forces.
      - rochak 6y ago
        Titanfall is a pretty good example of how to design good AI. Same goes for Age of Empires, I would say. XCOM, on the other hand, just increases the HP and count of enemies, which is a bad experience.
DonHopkins 6y ago
This is how The Mighty Slime Mold hunts. https://www.youtube.com/watch?v=7YWbY7kWesI https://www.youtube.com/watch?v=7YWbY7kWesI >How This Blob Solves Mazes | WIRED >Physarum polycephalum is a single-celled, brainless organism that can make “decisions,” and solve mazes. Anne Pringle, who is a mycologist at the University of Wisconsin-Madison, explains everything you need to know about what these slime molds are and how they fit into our ecosystem.
dmos62 6y ago
My first thought looking at the animation was Boids [0]. The scent trail approach is interesting because it simulates/respects fog of war (though the game doesn't seem to use it otherwise). [0] https://en.wikipedia.org/wiki/Boids https://en.wikipedia.org/wiki/Boids
unnouinceput 6y ago
This technique won't work if your player has teleport abilities like sorcerer in Diablo 2 or Assassin in GuildWars. In those case, you can teleport quite some distance and enemies in a 3D environment will get stuck on a upper slope while a simple path algorithm will make them still chase you.
- rochak 6y ago
  Well, teleporting is a tough problem to solve to begin with. One way to solve it is to have enemies distributed uniformly and restrict their movement to subsections. Once the player teleports, only the enemies in the closest subsections will use the algorithm to reach the player.
  - Skunkleton 6y ago
    You could use a traditional path finding algorithm, letting the mobs look around confused while the path is computed.
carapace 6y ago
Cool! I was playing around with my lil asteroid sim[1] and I wanted to trace the trajectories of the asteroids, so I put a particle generator in the asteroid "base class" and set it to emit sixty particles with lifetime set sixty seconds, zero momentum and velocity, and unaffected by gravity. I bet you could adapt that to make a "scent trail", eh? [1] https://git.sr.ht/~sforman/SpaceGame https://git.sr.ht/~sforman/SpaceGame but it seems I deleted the experiment. The commit that has it is https://git.sr.ht/~sforman/SpaceGame/commit/7cc3981631db22be3fa77dc479f111ff86f91a08 https://git.sr.ht/~sforman/SpaceGame/commit/7cc3981631db22be... FWIW.
timwaagh 6y ago
I had this problem as well with a simple game i made. what i did instead is to just randomize the movement a little. And that was really enough. Making them any smarter would have made the game really short.
x0re4x 6y ago
Hmm... pretty sure I already saw something like that long time ago: https://github.com/id-Software/Quake-2/blob/master/game/p_trail.c https://github.com/id-Software/Quake-2/blob/master/game/p_tr...
atum47 6y ago
really great tutorial.
JabavuAdams 6y ago
All of the obstacles in that video are small and convex. This is the easy case of obstacle avoidance. Basically use modified steering behaviours. If that's all you'll ever have, then great -- don't build a system that you don't need. If you ever move to large non-convex obstacles, like a maze -- there will be mounting problems until it would have made more sense to use a navigation or path-finding.
xg15 6y ago
What I'm surprised to not have seen more often is attempts to preprocess a map, group points of it into larger sections and then perform pathfinding on those sections - e.g.: - split a map into convex polygons - use pathfinding to find out which polygins you have to traverse (either by making each polygon a node in the pathfinding graph or by selecting points on the polygon's edges and using those as nodes) - move in a straight line inside a polygon. It seems, especially for "almost convex" maps, this could move a good deal of pathfinding computation into the build phase.

428 points by atomlib 6y ago

TLDR: instead of doing generic pathfinding, the player avatar drops decaying "scent" into the world grid, and enemies follow the player by doing gradient ascent. The first time I've seen this technique in use was in the classic SimAnt game by Maxis, in the 90s; in research it was also explored in the ALife community. It's a cool trick, but by itself it's not quite enough, it's good for insect behavior but not much more. But what has been useful is combining standard pathfinding with this. For example, imagine if one of your units dies and drops some "scent of death" into the surrounding area - and that scent gets incorporated into A* as a large cost value for traversing this terrain. Now all your other units will "smartly" start avoiding the dangerous area for a while, without having to do any expensive analysis of why the unit died there, e.g. was there an ambush there or some such. (Google for "potential fields" and "flow fields" in games for more examples from commercial games.)

anotheryou 6y ago
"If no line of sight..." I might add
- badloginagain 6y ago
  Makes me think you can add scent trails to many objects- like the path of a fired arrow. Would help mitigate the "stealthy archer" problem Skyrim AI has.
  - enchiridion 6y ago
    I'm not familiar with that problem.
    - flqn 6y ago
      The "stealth archer" build in skyrim is overpowered since the enemy AI can't usually know where the arrow came from, and they tend to aggro, look around their immediate area, then go back to the idle state allowing the player to shoot them again from a safe, hidden spot. Rinse and repeat, and almost any encounter in the game with hiding spots is trivial.
  - egypturnash 6y ago
    I’ve been playing AssCreed Odyssey as a stealthy archer and it’s solution to that particular problem seems to be attaching your location to each fired arrow; enemies within some radius of where the arrow hit are given a search target somewhere near your position when shooting. Add in some “It came from over there!” barks and it works pretty nicely If you are far enough away there is a big hole in this wherein they can’t get to your position before their maximum-amount-of-time-in-search-mode timer fires off and they go back to their normal location and behavior, though.
DonHopkins 6y ago
In Micropolis, the open source version of SimCity, I scripted a "PacBot" agent in Python: a giant PacMan who follows the roads around, looking for traffic to eat, always turning in the direction of the most traffic. The PacBot only has a limited local view down the roads a few cells, and can't see around corners. Even though they're extremely simple and stupid and short-sighted, they still have interesting emergent behavior when multiple PacBots are competing for the same traffic, like how PacBot will give up and turn around when its competitors eat the cars it was wok-a-wok-a-ing towards. There is a good example of lots of competing PacBots around 0:55: https://www.youtube.com/watch?v=8snnqQSI0GE https://www.youtube.com/watch?v=8snnqQSI0GE >Now you have some good, uuh, there's some traffic here. There's this thing called a PacBot. It's this PacMan that follows the road around looking for traffic. And then he eats it. So that's good for your city. And you can have a lot of different PacMans on the thing, and you know, just editing the road gives the PacMan somewhere to go. So their score is how many cars they've eaten. So it's an "agent", and it woks all around, and he follows roads. And you can put a lot of them on the map to keep the traffic low. MicropolisRobot.scanRoads looks down the road in a given direction for a given distance, and counts the number of cars (in the traffic density layer), attenuated by distance (further away cars don't count as much). https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropolisrobot.py#L238 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb... Then the PacBot simulator calls scanRoads in all possible different directions to get a score, and moves in the direction of the best score. https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropolisrobot.py#L513 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb... As it turns out, the PacBot is actually the God of the Church of PacMania (each Polytheistic PacMania Church spawns up to four PacBot God Agents, if it's connected to a road), and the church zone itself generates a LOT of traffic, in the hopes of attracting the PacBots. The emergent behavior is that followers of the Church of PacMania happily drive back and forth between church, home, work, and shopping, again and again, in the hopes of sacrificing themselves to their God, PacBot. And the PacBot Gods hang out around the Church of PacMania, eating their followers, and raising their scores -- everybody's happy! class MicropolisZone: def generateRobots(self): https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropoliszone.py#L239 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb... class MicropolisZone_ChurchOfPacMania(MicropolisZone): https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabbc51d5e45dac948d8e40fc53ee/MicropolisCore/src/pyMicropolis/micropolisEngine/micropoliszone.py#L310 https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb...

mrspeaker 6y ago

So simple and obvious as soon as you see it in action. I love "hacks" like this: really easy to code, but with a big impact - and so many potential uses too! I'm adding "scent trails" to my bag of tricks for sure.

enrichp 6y ago
yes

FZ1 6y ago

Why are they calling it "AI", though? There isn't any AI or ML. You leave a trail for the enemy to follow, and they follow it. It's not even path-finding, it's path-following. Which is pretty much an if-then statement. It's a neat, simple approach, and fun to watch. But there isn't any learning, or knowledge, or other AI.

tantalor 6y ago
AI in the sense of "player vs. AI" is widely understood. AI does not require ML. "It's part of the history of the field of artificial intelligence that every time somebody figured out how to make a computer do something—play good checkers, solve simple but relatively informal problems—there was a chorus of critics to say, 'that's not thinking'." https://en.wikipedia.org/wiki/AI_effect https://en.wikipedia.org/wiki/AI_effect
bkovacev 6y ago
Could you provide a list of games that have "actual" AI/ML baked in for their NPCs? I'm curious as I haven't heard of them before.
- meheleventyone 6y ago
  There’s a few, most notably this racing game used neural nets before they were cool: http://www.ai-junkie.com/misc/hannan/hannan.html http://www.ai-junkie.com/misc/hannan/hannan.html A lot of modern work has focused on procedural animation versus behaviour but the two are quite intertwined: https://youtu.be/JZKaqQKcAnw https://youtu.be/JZKaqQKcAnw
dgb23 6y ago
AI is much broader than ML. In gaming specifically you typically label behavior of dynamic, life-like entities as AI. Behavior trees, state-machines, path-finding and so on. A typical example: the ghosts in pacman.
ncallaway 6y ago
In games "AI" is the term for the system that controls the behavior of NPCs and other non-controlled entities. It's not claiming to be "academic AI". Games have been using this terminology for decades.

ariadnavc 6y ago

Dotnaught 6y ago

If you’re modeling an intelligent pursuer, the algorithm should anticipate future travel rather than just following.

eru 6y ago
Yes. But for simple enemies, the algorithm suggested gives interesting behaviour, and plenty of ways for players to manipulate it. The latter is useful to open up extra gameplay.
itdagusszous 6y ago
In games the goal of the developer isn't necessarily to have intelligent agents, but to have agents that are fun to play against. Sometimes the goal is to have them be intelligent, but sometimes having them behave in "dumb" but predictable ways makes the game overall more fun.
- dkersten 6y ago
  This is the reason usually given for using relatively simple techniques like behavior trees, but, anecdotally, I find that the biggest let down in most games is that the AI is so dumb that it 1) is immersion breaking, and, 2) get same-y and boring very very quickly.
  - eru 6y ago
    Yes. It depends on what the game is trying to achieve. Subset Games, the makers of FTL and 'Into the Breach' have talked about this extensively. 'Into the Breach' deliberately has the enemies telegraph their plans one turn ahead of time, and the game is all about interfering with those plans. The rest of the game's design carefully reinforces the message that the enemy units are not intelligent. The backstory has them as basically oversized insects. If you have a game that pretends to give you realistic human antagonists, but they behave mechanically dumb and predictable, that breaks immersion like you suggest. One big problem is that having very smart AI that's purely there to oppose you in a zero sum game ain't fun to play against for most people. The handicaps a modern chess or Go engine would have to give you a normal human for a fair fight are ludicrous. And people seldom want fair fights in their games. They want a feeling of accomplishment, but without actually putting in all that much work. Even hardcore games like XCom cheat in your favour behind the scenes. There are at least two ways out of this while still avoiding the boring repetition: - carefully make the NPC make believable human-like (or animal-like) mistakes, instead of easily exploitable repetitive mistakes - give the NPC goals that are in conflict with the player, but not 100% so. A silly example of the second option: Take a game like Thief that's all about sneaking around stealthily and stealing stuff. Now realistically, most of the guards are just hired goons. They don't want to die, but they don't particularly care about protecting the place. They do care about being seen doing their job, so they don't get fired. So your job as a player could be, in addition to staying unseen, to provide plausible distractions and reasons for the guards not too investigate to closely. Higher ranked guards, and owners, would be under higher pressure to perform and won't get away with excuses. So they would be more alert. Using the same trick over and over again would lower it's effectivity: guards can't plausible claim to their higher ups to have been tricked again and again. If you are starting to become aggressive to a guard, or he learns that you called one of his friends, the guard's priorities will change towards more self-preservation. A pacifist run might even earn you respect and admiration from the lower level guards. Just like cat burglars are often admired in real life. Seen a bit more abstract, the game now becomes one of three factions: the thief (that's you), the low level guards and their employers. All with partially overlapping, partially conflicting goals. You can throw insurance companies into the mix, if you want to make it even more complicated. Thanks to the non-zero sum nature of the partial conflict, you can crank up how smart everyone acts, without overwhelming the player: Eg smarter guards might figure out a way to de-escalate that still looks like a plausible and even courageous move to their employers.

b0rsuk 6y ago

A fascinating AI technique is used in one of the best roguelikes, Brogue. The author called it "Dijkstra Maps". Basically it's about generating a heatmap for all the squares on the level. You can start with 0 at player position, and from that point use a simple floodfill algorithm, putting down increasing numbers with each step. Then a monster simply examines all adjacent squares and selects the one with lowest number. This has at least two notable advantages: 1. You only need to do the path generation once, and it scales very well with the number of monsters. 2. It's really good at combining several concerns, because you can generate a couple of heat maps for different concerns and add them up. For example one heat map is about proximity to player. Another could be about proximity to health pickups, or proximity to cover, or proximity to open space if a monster likes to keep distance and shoot. If a gas trap is triggered, you can use a "danger" heat map. Then a monster can easily get closer to player and at the same time choose the path which has fewer harmful effects. That's why centaur archers in Brogue are so annoying, monsters avoid traps intelligently, monster groups avoid wasting their numerical advantage by chasing player through a corridor. He described it in detail in this article: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps http://www.roguebasin.com/index.php?title=The_Incredible_Pow... And in case you're wondering, Brogue source code is licensed on AGPLv3.

Jaxan 6y ago
So basically just a shortest path algorithm starting from the player to all other tiles?
- masklinn 6y ago
  Sounds like that's what the base layer is yes, though the additional layers are interesting.
- fwip 6y ago
  Not exactly - a shortest path algorithm would lead to the monsters "anticipating" the player coming around the obstacle and cutting them off. The algorithm is summarized in the article as: "When an enemy enters the Chase state it tries to raycast to the player and if nothing is in the way - chase em! If something is in the way, it goes through the scent trail in order and tries to raycast to each scent until it can see one, then - chase it!" With complex geometry, this will frequently lead to a non-optimal route, and is probably more fun to play against.

DennisP 6y ago

It might make sense to have the monsters repulse each other. By spreading out, they'll end up taking multiple paths around obstacles, coming at you from different directions, so it looks like more intelligent coordinated behavior.

ghthor 6y ago
I've used this pattern before in game AI's and it works well. If you combine it with a somewhat random searching incentive the "hive" will spread out and search for the player(s). I also let the "hive" communicate with each other if they find a player they let each other know and then set a new waypoint for that area. When they repulse each other they take different pathways around objects and it looks a feels great to play against.

dfgdghdf 6y ago

This technique shows how game AI is different from academic AI. The goal is to create interesting gameplay with minimal performance overhead. This system is just as fun a as "correct" system, but far simpler to implement and cheap to execute.

jfkebwjsbx 6y ago
It is academic AI. A lot of papers go on how to implement algorithms fast or how to implement the best approximation within a given time, etc.

Datenstrom 6y ago

A former colleague of mine Meghan Chandarana was doing some really awesome work which incorporated a similar "bread-crumb" algorithm for swarms dispatching groups for tasks and navigation back to the swarm. It wasn't the primary focus but was really cool to see work. If you want to see a application of it for swarms her paper is here: https://www.ri.cmu.edu/wp-content/uploads/2018/08/SMC2018.pdf https://www.ri.cmu.edu/wp-content/uploads/2018/08/SMC2018.pd...

simias 6y ago

I'm always saddened that more works doesn't go into making fun and original game AIs. Most AAA games that are released these days have utterly predictable AI, modern shooters don't seem a lot more evolved that Quake 1. It's too bad because games like F.E.A.R. have shown that even simple AI heuristics can lead to very interesting emergent behavior. TFA demonstrates that very simple AI tweaks can make the enemies feel more organic and realistic. I suppose that some of the problem is that good IA doesn't make for nice trailers and ads (since you can just script those to do whatever you want anyway).

lainga 6y ago
I think most companies have given up on good AI (except maybe id) - all the money's in PvP. Single player campaigns are an afterthought.
- colmvp 6y ago
  I think it's more cost efficient for companies to give the CPUs some absurd advantage (crazy amount of HP, powerful attacks) and call it day. Problem with AI is even if you spend a lot of time trying to get it right, it can make choices that are confusing to us humans and illicit ridicule from the player base.
  - hutzlibu 6y ago
    Well, the choice to make AI hordes braindead zombies who hust mindlessly storm you, is confusing to me as a player, too, if the enemie are supposed to be not zombies, but smart special forces.
    - rochak 6y ago
      Titanfall is a pretty good example of how to design good AI. Same goes for Age of Empires, I would say. XCOM, on the other hand, just increases the HP and count of enemies, which is a bad experience.

DonHopkins 6y ago

This is how The Mighty Slime Mold hunts. https://www.youtube.com/watch?v=7YWbY7kWesI https://www.youtube.com/watch?v=7YWbY7kWesI >How This Blob Solves Mazes | WIRED >Physarum polycephalum is a single-celled, brainless organism that can make “decisions,” and solve mazes. Anne Pringle, who is a mycologist at the University of Wisconsin-Madison, explains everything you need to know about what these slime molds are and how they fit into our ecosystem.

dmos62 6y ago

My first thought looking at the animation was Boids [0]. The scent trail approach is interesting because it simulates/respects fog of war (though the game doesn't seem to use it otherwise). [0] https://en.wikipedia.org/wiki/Boids https://en.wikipedia.org/wiki/Boids

unnouinceput 6y ago

This technique won't work if your player has teleport abilities like sorcerer in Diablo 2 or Assassin in GuildWars. In those case, you can teleport quite some distance and enemies in a 3D environment will get stuck on a upper slope while a simple path algorithm will make them still chase you.

rochak 6y ago
Well, teleporting is a tough problem to solve to begin with. One way to solve it is to have enemies distributed uniformly and restrict their movement to subsections. Once the player teleports, only the enemies in the closest subsections will use the algorithm to reach the player.
- Skunkleton 6y ago
  You could use a traditional path finding algorithm, letting the mobs look around confused while the path is computed.

carapace 6y ago

Cool! I was playing around with my lil asteroid sim[1] and I wanted to trace the trajectories of the asteroids, so I put a particle generator in the asteroid "base class" and set it to emit sixty particles with lifetime set sixty seconds, zero momentum and velocity, and unaffected by gravity. I bet you could adapt that to make a "scent trail", eh? [1] https://git.sr.ht/~sforman/SpaceGame https://git.sr.ht/~sforman/SpaceGame but it seems I deleted the experiment. The commit that has it is https://git.sr.ht/~sforman/SpaceGame/commit/7cc3981631db22be3fa77dc479f111ff86f91a08 https://git.sr.ht/~sforman/SpaceGame/commit/7cc3981631db22be... FWIW.

timwaagh 6y ago

I had this problem as well with a simple game i made. what i did instead is to just randomize the movement a little. And that was really enough. Making them any smarter would have made the game really short.

x0re4x 6y ago

Hmm... pretty sure I already saw something like that long time ago: https://github.com/id-Software/Quake-2/blob/master/game/p_trail.c https://github.com/id-Software/Quake-2/blob/master/game/p_tr...

atum47 6y ago

really great tutorial.

JabavuAdams 6y ago

All of the obstacles in that video are small and convex. This is the easy case of obstacle avoidance. Basically use modified steering behaviours. If that's all you'll ever have, then great -- don't build a system that you don't need. If you ever move to large non-convex obstacles, like a maze -- there will be mounting problems until it would have made more sense to use a navigation or path-finding.

xg15 6y ago

What I'm surprised to not have seen more often is attempts to preprocess a map, group points of it into larger sections and then perform pathfinding on those sections - e.g.: - split a map into convex polygons - use pathfinding to find out which polygins you have to traverse (either by making each polygon a node in the pathfinding graph or by selecting points on the polygon's edges and using those as nodes) - move in a straight line inside a polygon. It seems, especially for "almost convex" maps, this could move a good deal of pathfinding computation into the build phase.