5 ms·

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

by 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...

by 60654 6y ago

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...