Enemy AI: chasing a player without Navigation2D or A* pathfinding | Hacker News Reader

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

abitawake.com

428 pointsatomlib118 comments

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

And in case you're wondering, Brogue source code is licensed on AGPLv3.

So basically just a shortest path algorithm starting from the player to all other tiles?

Sounds like that's what the base layer is yes, though the additional layers are interesting.

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.

Not really - a shortest path algorithm outputs a single path between a start and an end point.

This gives you a value (distance to player) for every square on the board; you can do a lot of things with that data, like choose between multiple "best steps" based on some other preference, or choose "best steps" for a large number of monsters efficiently.

No, it doesn't give you a distance-to-player for every square on the board. It is closer to giving you an ordered list of 'most recent player positions' - notably, the point directly in front of the player is not necessarily in this list. These positions contain "time since player was here," which is not a distance to player. (It could be thought of as a maximum bound on distance-to-player, I suppose).

If the player's route is not straight, some squares with "fresher scent" may be physically more distant from the player than squares with less fresh scent.

Your parent comment is referring to the Dijkstra Map algorithm described in the top-level comment, not the algorithm discussed in the article.

Assuming this is calculated on every turn: Then it is a shortest path tree from the player position (the root) to all tiles.

Sounds like a classic potential field implementation, and yeah, they're very useful. There are two problems: scaling with map size (large maps or high detail maps), and update cost in action-heavy games (if the field source moves on every frame). But for small roguelikes it's a very good fit.

Thanks for the alternative name! Helps further research the technique. The core idea is relatively simple so I'm not surprised these are known. But finding a name of something you know is not easy with just a search engine.

Sure thing! And as I mentioned in another comment, if you google for "potential fields" and "flow fields" in games, there's a whole bunch of papers and talks on this.

Interesting, because these kinds of potential fields are similar to the "predictive map" representations we see in the firing rates of hippocampal cells.

Now that you mentioned "flow field", I remember seeing it in a Supreme Commander AI demonstration technique. Two columns of tanks can navigate through each other seamlessly, without chaos. And in realtime. Imagine seeing this in the days of Warcraft 1, where it was common for a unit to use left hand rule across the entire map because the bridge was momentarily occupied.

https://www.youtube.com/watch?v=iHuFCnYnP9A

Also get called influence maps

And also called... dynamic programming in some communities. On of the most classical algo, just before the more interesting class of problems where the map size is too big to do it

That's what James Gosling called it in his paper about the Emacs screen redisplay algorithm.

https://news.ycombinator.com/item?id=22849522

https://donhopkins.com/home/archive/emacs/mw/display.c

https://donhopkins.com/home/documents/EmacsRedisplayAlgorith...

7. Acknowledgements

The people who did the real work behind this paper are Mike Kazar, Charles Liescrson and Craig Everhart; all from CMU.

Bibliography

1. Kevin Q. Brown. Dynamic Programming in Computer Science. CMU, February, 1979.

Presumably you could set the fill radius to a maximum corresponding to the largest detection distance possible (for the monsters you have in-game or even in-level)?

There's no point filling an entire level if monsters only react when the player gets within say 30 tiles. Even line of sight should have limits.

You could add something like an A* heuristic on top where monsters are drawn to the general direction of the player based on a vector, but switch to shortest-path when they're close. (but then you worry about getting stuck I guess)

Performance is a serious problem still. Well, if the world needs to be updated often (multiple times a second).

Consider a semi-open map with 30 tiles sides, we're talking a thousand tiles in total and/or paths a hundred tiles long. For the effect to propagate to the 30th tile away, the propagation algorithm has to iterate more than 30 times.

Graph algorithms are generally slow (whole milliseconds on large graphs) but repeated many times over they can get truly horrendous.

One trick is to spread the computation out over time, if you don't need to do it all at at once every frame. Since the enemies don't move that fast, a bit of delay might be good enough, depending on what you're tracking.

SimCity has several layers like pollution, land value, etc, which slowly diffuse over time. But it only does that computation every so often, not every frame. It has a 16 phase simulation clock, and it scans the cells of the map in eight stripes over eight steps, then scans different layers like taxes, traffic and rate of growth decay, power, pollution and land value, police coverage and crime, population density, fire coverage and disasters, and the RCI valves. (That made it possible to run on a C64!)

Chaim Gingold's SimCity Reverse Diagrams show how the different phases of "Simulate()" perform different kinds of analysis over time, and how the different map layers interact with each other.

https://lively-web.org/users/Dan/uploads/SimCityReverseDiagr...

>SimCity reverse diagrams, by Chaim Gingold (2016).

>These reverse diagrams map and translate the rules of a complex simulation program into a form that is more easily digested, embedded, disseminated, and and discussed (Latour 1986).

>If we merge the reverse diagram with an interactive approach—e.g. Bret Victor’s Nile Visualization (Victor 2013), such diagrams could be used generatively, to describe programs, and interactively, to allow rich introspection and manipulation of software.

>Latour, Bruno (1986). “Visualization and cognition”. In: Knowledge and Society 6 (1986), pp. 1– 40.

>Librande, Stone (2010). “One-Page Designs”. Game Developers Conference. 2010.

>Victor, Bret (2013). “Media for Thinking the Unthinkable”. MIT Media Lab, Apr. 4, 2013.

Yeah this is an interesting problem for exploring stuff like recursive/non-recursive code, the overhead of conditional statements when you have to run thousands of them, etc. I've seen some examples online where people claim a few million voxels a second (I've not tested though).

I think this is also how 3D printers work (effectively). They do a form of scan-line filling to minimise the number of jumps between sections of filament.

I encountered a similar problem in a very different situation a few years ago: I had to route video streams across a network of nodes connected by point-to-point connections.

At first I thought I would apply a pathfinding algorithm like A* to route each stream but given that it was an arbitrary graph and not a 2D map there was no obvious heuristic to guide the algorithm, so it devolved into an exhaustive search.

But then I realized that I had relatively few nodes (a dozen at most) and many more streams to route, so it made more sense to compute the distance between every pair of nodes once (n^2 with the number of nodes using a trivial implementation, less if you optimize it but I didn't even need to) and then I could lookup the path between any two nodes in linear time. Given that this was all running on an underpowered embedded system it made a significant difference in performance when routing hundreds of streams.

That lookup can be done in constant time, rather than linear, right?

I'm not very good at big-O. I meant that in order to build the path I would need to lookup the neighboring nodes to find the closest to the target, then just to that node and continue until the end. So it's linear with the average distance I guess.

Yeah, linear with regards to the number of nodes - double the amount of nodes and you'll need to do double the look-ups; and constant with regards to the number of streams - no matter how many streams, always the same number of look-ups.

James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc).

https://en.wikipedia.org/wiki/Gosling_Emacs

>Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not.

https://donhopkins.com/home/archive/emacs/skull-and-crossbon...

Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted.

https://donhopkins.com/home/archive/emacs/mw/display.c

    /*  1   2   3   4   ....            Each Mij represents the minumum cost of
          +---+---+---+---+-----        rearranging the first i lines to map onto
        1 |   |   |   |   |             the first j lines (the j direction
          +---+---+---+---+-----        represents the desired contents of a line,
        2 |   |  \| ^ |   |             i the current contents).  The algorithm
          +---+---\-|-+---+-----        used is a dynamic programming one, where
        3 |   | <-+Mij|   |             M[i,j] = min( M[i-1,j],
          +---+---+---+---+-----                      M[i,j-1]+redraw cost for j,2
        4 |   |   |   |   |                           M[i-1,j-1]+the cost of
          +---+---+---+---+-----                        converting line i to line j);
        . |   |   |   |   |             Line i can be converted to line j by either
        .                               just drawing j, or if they match, by moving
        .                               line i to line j (with insert/delete line)
     */

https://donhopkins.com/home/documents/EmacsRedisplayAlgorith...

https://dl.acm.org/doi/10.1145/1159890.806463

A redisplay algorithm, by James Gosling.

Abstract

This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques.

[...]

6. Conclusion

The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke).

Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach.

I wonder how the ratio of display overhead to cost to compute the minimal cost path has changed over the years? At some point it must be cheaper to do a "dumb" redraw if the display hardware is fast enough?

Also, it seems like this might also be useful for computing minimal diffs, eh?

It was definitely worth it if you had a 300 baud modem and a lightly loaded VAX mostly to yourself. But it became an overkill with higher baud rates and high speed networks.

It's based on the "string-to-string correction problem" (edit distance / Levenshtein distance), combined with "dynamic programming" (finding the best cost path through a cost matrix), which is (kind of) how diff works, on a line-by-line basis for inserted and deleted lines, and then on a character-by-character basis between changed lines. Each "edit" has a "cost" determined by the number of characters you have to send to the terminal (length of the escape codes to perform an edit in multiple possible ways, versus just redrawing the characters). Emacs computes its way through a twisty maze of little escape codes each time it updates the screen.

H. M. Wagner and M. J. Fischer. "The string-to-string correction problem." JACM 21, 1 (January 1974), 168-173

Citation: https://dl.acm.org/doi/10.1145/321796.321811

PDF: https://dl.acm.org/doi/pdf/10.1145/321796.321811?download=tr...

https://en.wikipedia.org/wiki/String-to-string_correction_pr...

>In computer science, the string-to-string correction problem refers to determining the minimum number of edit operations necessary to change one string into another (i.e., computing the shortest edit distance). A single edit operation may be changing a single symbol of the string into another, deleting, or inserting a symbol. The length of the edit sequence provides a measure of the distance between the two strings.

https://en.wikipedia.org/wiki/Diff

>In computing, the diff utility is a data comparison tool that calculates and displays the differences between two files. Unlike edit distance notions used for other purposes, diff is line-oriented rather than character-oriented, but it is like Levenshtein distance in that it tries to determine the smallest set of deletions and insertions to create one file from the other. The diff command displays the changes made in a standard format, such that both humans and machines can understand the changes and apply them: given one file and the changes, the other file can be created.

https://en.wikipedia.org/wiki/Levenshtein_distance

>In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.

https://en.wikipedia.org/wiki/Edit_distance

>In computational linguistics and computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.

Here's a Levenshtein demo that shows you the cost matrix with the shortest path highlighted. Try calculating the distance between "fotomat" and "tomato", and you can see the shortest path which has a cost of 3 edits (1: delete f at beginning, 2: delete o at beginning, 3: insert o at end):

http://www.let.rug.nl/kleiweg/lev/

>Levenshtein distance is obtained by finding the cheapest way to transform one string into another. Transformations are the one-step operations of (single-phone) insertion, deletion and substitution. In the simplest versions substitutions cost two units except when the source and target are identical, in which case the cost is zero. Insertions and deletions costs half that of substitutions. This demonstration illustrates a simple algorithm which basically looks at all of the different ways for operations to transform one string to another.

Cheers! I'm a big fan of yours BTW. Long ago, in a forum far away, your were the one to clue me in to NeWS (and pie menus too!) Blew open my concepts of what a display system could be. I'll always be grateful to you Don Hopkins.

This article made my morning, thank you. So fascinating how these things are still being uncovered today.

I've always known this as flow field pathfinding and it can get tricky if you have a dynamic map or enough changing that you need to recalculate often. Here's a random article I'm sure I read years ago describing it.

https://leifnode.com/2013/12/flow-field-pathfinding/

I believe what you're describing is called Collaborative Diffusion, and it's been used in Pacman. https://en.wikipedia.org/wiki/Collaborative_diffusion

Here's a good article I've read previously about large pathfinding problems in a theme park game: https://www.gamasutra.com/view/news/288020/Game_Design_Deep_...

What you're looking for is influence maps. See the 2 articles linked below. They helped me tremendously when I was developing AI for a 2D game.

Another unrelated thing I found very useful is Floyd Warshall. It's a graph algorithm to compute efficiently ALL shortest paths between any 2 nodes. Real time pathfinding was too slow to use, had to precompute wherever possible, turns out most of the world is fixed and can be precomputed.

https://gameschoolgems.blogspot.com/2009/12/influence-maps-i...

https://gameschoolgems.blogspot.com/2010/03/influence-maps-i...

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...

Ah, influence mapping... I participated in a fun thread on comp.ai.games in 1995 where a lot of these ideas were first fleshed out.

http://zhar.net/projects/gameai/influence_map.html

My contribution was to use heat transfer calculations to model the battlefield as a conductive plate with units as heat constraints.

Fun times. I always wondered if that thread inspired any real world games.

I believe this is "flow fields" or "potential fields" -- as mentioned by other commenters, scaling it with graph size and destination-count are two of the main issues with it.

In SimAirport we use flow fields, they're great for crowds & they scale incredibly well with agent count. We use them for "long distance" traversals, and then we use "local" A-star like grid search for the "last-mile" of an agent's journey.

For flow-fields, we start by dividing everything up into "sectors" based on game logic -- and then further, into "sub-sectors", essentially just basic abstractions of the graph with smaller node counts. It does have an impact on path quality but for the scale we operate at in SimAirport the trade-off is a no brainer. The abstractions then limit the flow-field's graph size & the destination-count that any given subsector (abstracted-node) can have -- essentially it's a hierarchical (pseudo HPA-star) approach to flowfield pathfinding / navigation, and the abstraction also has major benefits for reachability queries & game-logic driven "rules" (ie load-balancing of capacity-constrained paths [stairs/escalators], one-way paths [ie directed graph algos], etc).

IIRC he uses the same data structure but with hill climbing vs gradient descent to guide monkeys/imps/anything else that steals an item and runs from you. Clever.

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

I’ve always called this Lee’s algorithm https://en.m.wikipedia.org/wiki/Lee_algorithm

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

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.

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.

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.

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.

Is that a bad experience though? If I want an easy time, I'd rather fight fewer smart enemies than just dumber enemies.

Isn't that also due to the reason that consoles, once sold, last for close to 10 years and the game developers have to design their games for sub par hardware. Since graphics sell games more, they spend most of their available computation on graphics and other areas rather than coming up with intelligent AI which takes a lot of computation as well. This is probably the reason why we don't have many big single player games.

That’s not the issue as 20 year old hardware can run decent AI for modest numbers of enemies. The reality is most players simply want stupid AI and more importantly exploitable AI.

Spot-on. In our game the NPC AI is ... exactly what I wanted it to be, smart and extremely "opportunistic". And the gameplay is generally such that your goal is to build structures/layout the buildings in a way that the AI will make the AI most likely to reach their goals.

To me, that's a huge part of our game -- catering to the NPCs, specifically figuring out "why are they missing X? Oh, because they're walking Z distance to the nearest bathroom!". I think the AI is fantastic but, when functioning perfectly as [we would have] expected, we still get complaints about why the 'dumb AI' will do X or Y. Part of that is defintiely a UI/UX issue on our part -- but another part is that players generally aren't used to it and they expect much more "robotic" or obvious/easy behaviors from agents/NPCs.

Emergent & opportunistic behaviors are awesome (IMO at least), but a lesson we learned is that they may not always provide players with the desired or expected gameplay experience. It'll of course always be game-specific, but it's something we will keep in mind & likely simplify further in our next game.

Yes, even a simple implementation of selfpreservation would make KI so much more realistic. Meaning, if the enemy has low health, he is likely to run away. Or if they see all their allies die, etc.

This is really not so hard to implement, simple games could do this for ages.

Or at least basic tactics, I think in Far Cry 1 enemies did not run away, but were smart enough to sneak and circle around you, later in Crysis or the other Far Cry titles, they were just cannon fooder. Makes everthing more hollywood kaboom

It's a fine line. There are plenty of stories of games that dumbed down their AI because it started doing inscrutable things when fully unleashed - and simulating full sense perception for something like a soldier in a shooter game is very computationally expensive, so "smart" opponents tend to feel like cheaters since they are thinking in terms of the underlying representations instead of behaving or reacting in a believable way.

A lot of making the experience of a game is in managing perception and belief - in making the player agree that the game is doing "what I expected" - and when a feeling of realism is aimed for, the amount of falsified behavior needed to get that result goes up dramatically. The games where belief is easy to achieve are mostly stuff where the ruleset is abstracted, empirically tested and legible to all - board games, physics games, puzzle games, etc. Things where the decision making itself is the intelligence. In contrast making soldiers that are satisfying opponents requires a blend of assets: carefully managing their positioning, animation states and voice callouts so that their decision making is something that players can identify, respond to and overcome.

"and simulating full sense perception for something like a soldier in a shooter game is very computationally expensive, so "smart" opponents tend to feel like cheaters since they are thinking in terms of the underlying representations instead of behaving or reacting in a believable way."

I am not saying it is easy. But today, we got some more cpu power to throw at the problem. And even if you simplify a lot, you would still get better results, than plain cheating, which breaks immersion for me too, when they all storm my position, they could not know exactly.

"In contrast making soldiers that are satisfying opponents requires a blend of assets: carefully managing their positioning, animation states and voice callouts"

And here is the crux: there are tons of ressources thrown at the animation states and voice callouts, which is even more frustrating, when their behavior is as dumb as allways.

And not everything is expensive to simulate: in allmost every game with stealth elements for example: you can kill some enemies and the others are looking for you for some time - and then they go back to their default state with "ah, it must have been nothing", even though they might have been already wounded by you and witnessed comrades fallen.

Here you would not need more cpu power, but simply a third state: where they can still give up the search, but remain on guard. (And tend to their wounds, etc. )

I don't understand how you can use stealth as an example. The only way you can fairly simulate stealth mechanics is by making every enemy render the scene at low complexity and then check if it can see pixels of the player model. Maybe some games do this but from my experience what happens when you get caught is pretty boring. They sound the alarm and they all hunt you down as if they had a radar because actually doing the simulation is too expensive. There is no need for a third state. Once the alarm is on it is on but it shouldn't mean the enemy knows where you are.

Does having enemies run away make the game more fun for the player, or does the need to chase them become an annoyance?

If an enemy sneaks around the player, gets in cover and concealment, and shoots them while the player does not understand where the fire is coming from, is it an enjoyable experience?

Smarter and more realistic does not necessarily mean better. We don't write enemy AI for the purpose of it being effective in fighting, it's there to provide entertainment for the player.

It's also about creating the intended emotions. Games are intentionally designed to create a particular set of experiences. There's a niche of games that relies on gratification of overcoming some frustration (e.g. Dark Souls series) but the majority of gamer market prefers a 'power fantasy' emotional experience, so many games are intentionally targeting that. If we want the player to feel powerful, then we design so that their character can defeat many enemies; if we want the player to feel smart, then we design enemies so that their behavior has exploitable weaknesses that they player can discover and feel satisfied while 'outsmarting' or 'tricking' the opponents. In most game genres we don't want the player to feel outsmarted by the computer unless they have made a substantial mistake that the average player is able to notice and correct.

"Does having enemies run away make the game more fun for the player, or does the need to chase them become an annoyance?"

A good game mode does not require finding and hunting down all enemies. It has targets, like "go there"(story continues), "blow up X", "clear area Y"

"if an enemy sneaks around the player, gets in cover and concealment, and shoots them while the player does not understand where the fire is coming from, is it an enjoyable experience?"

If the game gets the graphics and gameplay right, for sure! (I still have memories from Vietcong, where you get ambushed in the jungle and don't see anything and just die, until you learn to move in cover and watch the terrain)

And you have the muzzle flash for example. And if you do not see it ... the fun is in getting scared and rushing to cover. Where the enemy cannot see you anymore (if the KI is not cheating) and then move to a different position to find him. Or you can have the kill cam, where you see upon death, where the enemy was, that killed you.

"If we want the player to feel powerful, then we design so that their character can defeat many enemies"

True, but there are various ways to implement this, without ZombieKI. Like in crysis for example, where you have superior tech. Or more hitpoints, because you play a badass. Or in general, you as a player have quicksave and load. The computer does not.

So yeah, I know that the target audience is dumb and wants fast food, so to say, but they also consume what is avaiable. And the standard is mostly ZombieKI, or ultra hardcore realism like in Arma, which is clearly not for everyone, but I really don't see, why the "AAA" games could not invest a tiny bit more in KI that does not break immersion.

> the majority of gamer market prefers a 'power fantasy' emotional experience, so many games are intentionally targeting that

Sure, but after a while, after seeing that in 100000 permutations, some people kinda move on from that and don't look back.

https://www.youtube.com/watch?v=h3rKmTFP9f4&t=8m50s

If it's just that essentially, but dressed up more nicely, I neither want to play it or make it. Personally I even got bored of collecting items for the sake of collecting them, or getting high scores for the sake of getting them, and exactly because every day 1000 games are made that follow all those patterns I feel perfectly free to ignore every one of them.

I still probably will never make a good game, but I learned a lot through trying, and I can feel good about what I tried, too. For me it's just something I do when I feel like coding, but have nothing "useful" to work on, after all.

Support indie developers!

It really depends on what the game is trying to achieve. I recall reading an article on smarter ai on stealth games, which unfortunately lead to an unfun experience. As a player I don't want to feel the AI is "cheating".

As an example the alien game released a few years back had both interesting yet an AI that didn't feel like cheating. In this context an AI that does intersting things is accepted since the goal is to strike fear, whereas with a modern shooter most enemies are made to bring some challenge but eventually be killed.

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.

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.

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.

This is how The Mighty Slime Mold hunts.

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.

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.

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.

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.

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.

You could use a traditional path finding algorithm, letting the mobs look around confused while the path is computed.

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

"If no line of sight..." I might add

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.

I'm not familiar with that problem.

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.

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.

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

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

class MicropolisZone_ChurchOfPacMania(MicropolisZone):

https://github.com/SimHacker/micropolis/blob/b0c5a3f495ebabb...

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

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

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 but it seems I deleted the experiment. The commit that has it is https://git.sr.ht/~sforman/SpaceGame/commit/7cc3981631db22be... FWIW.

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.

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

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.

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.

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

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.

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.

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.

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.

I think you've hit the nail on the head. I absolutely agree that "dumb" AI can be explained away and integrated into a game's design and story in ways that make it much more interesting and believable than typical bad AI on its own. I also agree that by providing a flexible and interesting enough scenario, with conflicting goals and motivations, you can improve the AI in ways that are both noticeable to the player and add extra layers of interesting gameplay.

As an aside, unrelated to your reply, I just remembered another common excuse, which is that the enemies only exist for X seconds before the player shoots them, so effort on smarts would be wasted on them. For some games, I think its for sure the case, but I also feel that in many cases the enemy only exists for a few seconds because they are dumb and uninteresting.

All agreed.

Both 'dumb' and 'interesting' AI can be useful in a game, it all depends on your game's design.

To give another silly example: Tetris by default has very 'dumb' AI that just gives you pieces at random. You could imagine variants of Tetris with more interesting piece selection.

For example, an AI that makes pieces as unhelpful as possible while keeping their distribution statistically indistinguishable from true random selection.

Or there was an inversion of the 2048 game, where an AI plays the normal game, and your task is to give them unhelpful numbers.

You might be able to achieve something like that by storing not only the position of the player in the "scent" but also its direction and speed. Then you can simulate this ghost image of the player that moves linearly in this direction and that the enemy targets.

Of course at this point you probably end up with something that's actually more CPU-intensive than a naive A* so it can't be used as an optimization. I think the cleverness of TFA is that it combines both a performance optimization and makes the enemies look smarter than omniscient bots doing A* perfectly every time.

> it can check if it can see any of these past positions, then follow them to the player. Since this is similar to how a dog would track something, we'll call it a scent trail.

This is how a scent dog tracks prey it cannot see.

I recommend the author hang out at the dog park and watch other kinds of working dogs, like retrievers and herd dogs. Very, very different behavior.

In fact I've heard that dogs can make a pretty nearly accurate guess about shortest path when dealing with terrain that has two different speeds. If, for instance, your dog is trying to get to you in the water and you are diagonal to his position, they will use two angles to triangulate on you, staying on the sand longer (but not until perpendicular with you) to minimize travel time.

One of my dogs definitely uses the Wayne Gretzky approach (go where the puck will be) but sometimes arrives before her target, resulting in collisions or acrobatics.

Interesting observation!

I wouldn't fault the authors too much, they just looked for an easy to remember name and the metaphor holds up well enough for that.

I may have come across as a bit condescending there.

Really, if you wanna do path finding, a dog park will give you tons and tons of food for thought.

Some dogs are very clever. Others dumb as a post.

Yes, lots of things to learn from dogs.

Insects and other animals are also good for inspiration. Even microbes!

There are some microbes that essentially follow this small program to find sugars:

- swim forward - wiggle around randomly - repeat

When the concentration of sugars is increasing, spend more time swimming forward. Otherwise, spend less time swimming between wiggles.

In a game, you would have the player leave a scent trail, and some of the other critters could behave like above.

really great tutorial.

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.

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

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.

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

A lot of modern work has focused on procedural animation versus behaviour but the two are quite intertwined: https://youtu.be/JZKaqQKcAnw

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.

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.

It is academic AI.

People simply have no clue what AI actually means and think it is only about sci-fi robots and ML.

A* search counts as academic AI. If-then statements do not.

If-then statements are definitely AI, and A* is also a bunch of if-then statements.

Such a wrong take. Decision trees are nothing more than if statements. Fancier versions of those (random forests) are consistently near SOTA algorithms like neural networks (and beat them on tabular datasets frequently). AI can be just a shit ton of if/else statements.

It's kinda cool that we get to interact with the final arbiter of the bounds of the term "academic AI".

That's fair. I guess I meant more "the frontier of academic AI", but then again I don't really keep up with academic AI at all, so I might just be wrong about what academic AI is. I can't really make any strong claims about academia.

My stronger claim is that this falls so squarely within the bounds of "game AI" that it's fairly ludicrous to say it's not AI.

I strongly disagree. For example, in this algorithm, there is "knowledge": the knowledge of the programmer that realizes that following a person moving can mean also follow one of the previous positions of that person (especially if we can revert to follow that person again at some point), and this knowledge is encoded in an algorithm using code, that is, yes, those "if-then statements" you seem to despise.

For years (but even now) Artificial Intelligence meant understanding how intelligent behaviors worked, and then understand what is the sequence of "if-then"s that could express those behaviors in an artificial setting. Use statistical inference is a "hack" (unavoidable, often) to cover the cases in which such behaviors seem to be too complex to be grasped - and then expressed - by one simple and/or comprehensive algorithm, but the (possibly unattainable) ideal would be having everything expressed as "pretty much an if-then statement" indeed.

> the (possibly unattainable) ideal would be having everything expressed as "pretty much an if-then statement" indeed.

This is flatly incorrect - the point of AI is to have a machine achieve intelligent behaviors without explicit programming.

If an "if-then" must be written by a programmer for every single behavior, then this is called "programming". It is not called "artificial intelligence".

No, the point of AI is to have agents achieve goals based on observing an environment. Nothing says they have to be complicated agents or not explicitly programmed. Any book on Computer Science AI will be largely filled with agents that use rather explicit logic and algorithms.

Still incorrect. And I would urge you to read one of these books you reference - they ALL aim to achieve that agent's action ON ITS OWN - i.e., by learning from its environment, and NOT by being explicitly programmed.

Yes, there are many explicit if-else style programs in Russel & Norvig, & other books - but those are the 'training wheels', until better methods are developed. For actual AI, the training wheels are supposed to come off, and the agent learns and acts on its own.

Not at all. AI does not need any learning at all.

You are talking about ML, not AI.

There is a distinction between what is AI and what is state of the art AI. Simple approaches are AI but not state of the art AI. At one point massive rule based systems were considered state of the art for example and those were nothing but explicit if-else statement. Now they're not but they're still AI.

BASIC, for example, would be considered merely a training wheel in any book on programing languages but it is nonetheless a programing language.

Because it's not the same kind of "AI" that you seem to be familiar with

AI does not mean ML, it is a broad field that is a superset and not a subset of ML. Or as Wikipedia describes it:

>In computer science, artificial intelligence (AI), sometimes called machine intelligence, is intelligence demonstrated by machines, in contrast to the natural intelligence displayed by humans and animals. Leading AI textbooks define the field as the study of "intelligent agents": any device that perceives its environment and takes actions that maximize its chance of successfully achieving its goals.

> AI does not mean ML

Hence the 'or' in my statement. Neither are present here.

>any device that perceives its environment and takes actions that maximize its chance of successfully achieving its goals.

This does exactly that.

Every program that has ever existed does this. So, you're saying that all programs that have ever existed, then, are all AI. You make no distinction whatsoever.

I would say that the more a program thinks on its own which actions to take to maximize its chances of success, the closer to AI it is.

If it's doing exactly what it's explicitly told, then it's not really intelligent, is it?

>>any device that perceives its environment and takes actions that maximize its chance of successfully achieving its goals.

>Every program that has ever existed does this.

No, not every program is self-tuning, nor do they all take inputs.

> There isn't any AI or ML.

You seem to acknowledge a distinction between ML and AI, but I'm not able to understand in your categorization, what would AI be?

A* search, any kind of heuristic estimation, learning, or simulated reasoning. All of those things would count.

We don't need mathematical optimization to call it "AI", but there SHOULD be more than a simple if-then.

At least show me that you're path-finding. That's not even being done here - this is just path-following.

"I leave a trail, you follow it." Explain to me how that qualifies as AI. Simple BFS/DFS achieves a lot more than this - which is considered by most to not even really be AI.

My first game was a homework assignment: write a 1-player pong game (like arkanoid without the bricks). I juiced it up a bit by adding a second "AI" player with a very rudimentary ball-following algorithm.

  if (ai.x - pad > ball.x)
     move_ai(-max_speed);
  else if (ai.x + pad < ball.x)
     move_ai(max_speed);

... or something like that, with some bounds checking and some logic for smaller moves. Bottom line, "just an if/then statement" can be sufficient to make a playable game with a challenging (or even unbeatable) computer player. Tic tac toe is another example of this.

Reply on news.ycombinator.com