Smart AI vs Expensive AI

[MisterMoxxie]

Hey, there, Temple goers!

One of my driving motivations in developing a rogue-like has always been doing an interesting AI system, one that could produce results that would surprise the players, as well as myself. I've got some pretty interesting ideas on how I want to set the system up, how I want my creatures to react to certain things, etc. However, I can't get around one major stumbling block.

In the design process for a smarter AI system, one obvious thing comes up. Creatures need to be able to 'see' what is around them, in order to react to what is there and choose what task they're going to focus on. I've been trying to wrap my brain around a way to do this, without just calling a ton of field of view algorithms every time a monster moves or takes a turn.

The only plausible idea I have come up with, so far, would be to allow creatures to see everything that is in the room they are in. Then, when populating the dungeon, each room would contain a list of all objects that are in that room. It seems like it would work pretty well. However, when the creatures are in hallways or otherwise in between rooms, I would still have to do some sort of FoV call.

What are your guys' ideas? By the way, I'm using Libtcod 1.5.1 and Python, but it's a pretty general question, really.
Thanks in advance!
 

[chooseusername]

When the AI is close to the player, use FoV for fairness. When not close, you have several options.  Use FoV indiscriminately.  Cheat.  Approximate.  The last is the wisest choice IMO.

[mushroom patch]

Two possibilities:

Let monsters see everything within a certain distance. This sort of unrealism will not make your monster AI less interesting.

Use a cheaper proxy for vision like what you're talking about. For example, along the lines of what you're talking about, you can make a partition of your level by taking each room to be a piece of your partition. Fill out the rest of the partition according to the following procedure:

1.) pick a tile not already in your partition
2.) take its field of view
3.) remove all tiles in the field of view already in other pieces of the partition
4.) take the connected component of the resulting set that contains the starting tile
5.) repeat with other tiles until every tile is in the partition

Now you can record which pieces of your partition are adjacent to each other in a graph-like data structure. There are lots of libraries that provide such data structures, often with lots of interesting things you can do with graphs, but you could roll your own basic graph data structure easily enough. Mark each tile with an identifier so you know what piece of the partition it's in and keep a list of objects (updating as necessary) that live in each piece.

Once you have all this (not that hard to code since you already have the field of view part from libtcod), you have an easy to compute proxy for line of sight: Say a monster can see an object if the partition piece the monster's in is adjacent to the one the object is in. This is a very cheap (almost everything is precomputed), reasonably good approximation to line of sight, particularly if you make reasonably intelligent choices of initial tiles in the partitioning scheme above. If you have very irregular dungeons (e.g. tightly winding mazes or caverns), you may need to do a little more to make this produce reasonable AI, for example you may want the approximate line of sight to take more than one jump in the graph described above.

[requerent]

Are you looking to have anything other than reflex agents?

[MisterMoxxie]

Hmm. Thanks for the ideas, guys! I like the idea of using partitions, I'll definitely look into that.

@Requerent, what do you mean by reflex agents?

I want my creatures to have tasks/goals, not just be randomly wandering around until they see something, and then try to kill/run from it. Creatures will have values that give them some sort of 'personality' (ie aggression, greed, focus). A creature with more greed than aggression, would rather spend its time looking for treasure in the dungeon and hoarding it (either on themselves, or in a room/container). However, if that creature sees the something wearing some fancy armor / jewlery or weilding an expensive-looking weapon, it may decide to attack anyway. Where a creature with a high aggression will basically attack anything that gets too close to it. The 'focus' value would help to determine how easily they are distracted from whatever task they are currently focusing on.

This is just one set of examples, I have a lot of interesting ideas floating around that I may or may not end up implementing. But, basically, my goal is to have an AI that can run my non-enemy as well as my enemy creatures, and one that could produce results that may even surprise myself.

Trailing off a bit, I've also had an idea of doing a side-project with libtcod, using AI and neural networking in a sandbox-esque environment. This would also allow me to test how certain creatures react to each other, or other unorthodox AI implementations I might have, such as AI that actually 'evolves' and 'learns' to an extent.

[Numeron]

How will the player know why a creature is attacking the player/another creature?

How will the player know that a creature has a goal or destination in mind when they first see it compared to it standing perfectly still?

How can the player tell the difference between a creature that has specially hoarded the gold in its room/on its person compared to the same creature that spawned with those things already in place?

How will a standard enemy AI with one special ability learn/change in such a way that the player can tell the difference in the 5-10 turns it takes for that creature to be killed?

Sorry to be a downer, but the thing about interesting AI, sadly, is that it most often only ends up interesting from the back end.

[AdamStrange]

also it depends on your game mechanics:
realtime or turn based
If it is turn based, you probably won't see or understand complex ai
If it is realtime, then there are a lot things to deal with first, the main one being "trapped in corners" - get a simple movement that doesn't get trapped first then build a second behaviour. after you add a behaviour - check it works and your monster doesn't get trapped, or stan in one place going round in circles, etc

[tuturto]

How will the player know why a creature is attacking the player/another creature?

How will the player know that a creature has a goal or destination in mind when they first see it compared to it standing perfectly still?

How can the player tell the difference between a creature that has specially hoarded the gold in its room/on its person compared to the same creature that spawned with those things already in place?

How will a standard enemy AI with one special ability learn/change in such a way that the player can tell the difference in the 5-10 turns it takes for that creature to be killed?

Sorry to be a downer, but the thing about interesting AI, sadly, is that it most often only ends up interesting from the back end.

Numeron makes a really good point here. One idea I have been toying with is to give little thought bubbles for characters and have symbol there to show what it is currently thinking of. Sort of like how Sims or Dungeon Keeper does it. It would give player better idea what's going on. One can also just fake it and have thought bubbles without complex AI and let player to think that the creatures are actually pondering stuff when they're just randomly walking around.

If the game has very complex mechanics behind the scene and player never notices them, they don't really matter. On the other hand, if the player thinks that the AI is doing something really clever and complex when it isn't, it's like an almost free feature. There was an article about this in Gamasutra, but I couldn't quickly find it.

[AgingMinotaur]

And yet, it's possible to make AI interesting with pretty simple means. In fact, I think keeping it simple will make it much clearer to the player what's going on. Assigning sliders/values for stuff like "greed", "bravery", "anger" etc. is the kind of thing that sounds cool, but it is probably going to be too subtle. It might be a better idea to have something like "greedy" as a single trait that some critters have and other don't. In the original Rogue, for instance, orcs would always head over to pick up treasure. That kind of behaviour is instantly recognizable.

I get that you want something a bit more complex than that, but what I'm getting at is that hard and fast rules might be a better idea than weighing many subtle inclinations against each other. I do think it's a cool idea to have NPC and monster AI that brings the world alive with people doing their chores (farmers farming, cartographers exploring …) and killing time (going to the tavern, enjoying a game of cards), and can be influenced in different ways (an NPC who randomly hates canines will join you if he sees you kill a dog (but beware of being caught in the act by the owner), a carrion crawler can be lured onto a trap if you use raw meat as bait, etc).

Also, consider that these kinds of systems should affect gameplay in a fun and visible way. For example, a creature who goes around hoarding treasure might be uninteresting: it will mostly act of out the player's sight, and it results in levels where all the loot is in a single place, overriding your careful loot-distribution algorithm. A bit of pure flavor is ok, but direct your efforts towards stuff the player can use in some way. I remember this old platformer Abe's Odyssey, which featured a crablike monster that would chase (and instakill) the player, but which hated other monsters of the same type even more. So if you could lure two of them together on the same platform, they would ignore you for a while and start fighting between themselves. Flavor and tactics baked into one.

As always,
Minotauros

[mushroom patch]

I just want to push back a bit on Numeron's notion that complex AI is often too complex for a player to notice. I think he's basically right for pure hack and slash. Here, monsters are basically just maniacal killing machines and charge or at their smartest hit and run. But MisterMoxxie here is suggesting a game with monsters and NPCs that are not always aggressive and who nevertheless move around and do things. Anyone who's played a few angband variants knows how ridiculous such actors can be without adequate attention to AI. Non-hostiles quickly reveal a lack of interesting AI.

edit: Another thing here is that Numeron suggests we should be designing AI not just to be discoverable (whoever heard of such a standard in the world of roguelikes?) but to be easily, instantly discoverable in the way that the mechanics of a smart phone game strive to be. But roguelikes should be full of hidden nooks and crannies. If a subtle AI allows weird, counterintuitive tricks, that's a good thing. If it takes a long time for players to realize that certain monsters are stealing all the gold on their levels, this is great.

edit II: On the other hand, the question of how you know what your fellow dungeon goers are doing is a good one -- but it has good answers. E.g. non-hostile animals would withdraw when approached and give warnings, like hisses or growls, if they're feeling crowded or cornered. Monsters could address such warnings and signs of aggression to other monsters. This is good grist for messages -- no need for thought bubbles or other fancy stuff, just "The monkey fighting snake hisses menacingly at the cave lemur."

[Omnivore]

If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery.  Games are not simulations. 

Likewise, FoV calculation that goes beyond determining current direct line of sight at max awareness distance from the player's PoV is a waste.  LoS calcs should rarely be needed for AI purposes as the player-centric FoV map already has all the information needed.   Given mutable terrain and procedural map generation, I can't see any value in more detailed treatments.

There seems to be some unfortunate trend in roguelikes recently that end up putting far too much effort into 'realistic simulation'.  These high cost per mob AI implementations can easily lead to immersion breaking faults in actual game play.  One example from a well known and popular game are vault rooms where a player's AoE spells are greatly reduced in effectiveness because it would slow down the game too much if mobs responded to an out of LoS attack.  All vault mobs are ostriches with 'if I can't see you, you can't hurt me' immunity.

It is ironic that people who would never think of using a brute force solution to a low level problem, gladly employ brute force solutions such as simulation at the higher design level of modeling. 

[MisterMoxxie]

Wow, I'm glad to have so many different people in this discussion! Thanks, everyone, for your input! Lots of things I hadn't considered before.  Taking all of your guys' ideas into suggestion, I think I'm going to shoot for a system that can produce 'complex' or 'smart' decisions, without actually being that complex under the hood.

I think using behaviour tags would be a great option, for a few reasons. The way that two or more tags would combine could be very interesting, and it also gives me a more direct way to communicate creature behaviours to the player. Maybe after seeing a creature with the 'greedy' tag take items off the ground once or twice, the player will have discovered that creature is greedy. Any time they [L]ook at that creature, or otherwise gather information, the 'Greedy' tag will now be displayed as well as other relevant information.

On the note of my original question, using FoV or LoS, I think I've got a much simpler solution that I'm going to test today on that, as well. By simply giving all creatures a 'sight' value, I can check that against the distance from monster x to object x. If it's 'out of sight' they obviously can't see it. In any case where a creature can't directly 'see' the object (ie it's behind a wall, etc), it could be assumed that the creature was previously aware of it being there. I may have to do something a bit different for viewing the player, to avoid the 'smarter' aggressive monsters from always ambushing them by knowing when they're coming, even when the player is out of view. 

[mushroom patch]

If a player cannot observe a behavior it is irrelevant behavior, likely indistinguishable from pure randomness or other simple fakery.  Games are not simulations. 

This is a bit of a truism. I don't think anyone is talking about AI with no observable effects. Of course, it's important to take on board the criticism that complex/subtle AI can easily look indistinguishable from fairly mindless AI, as it seems people in this thread have.

Likewise, FoV calculation that goes beyond determining current direct line of sight at max awareness distance from the player's PoV is a waste.  LoS calcs should rarely be needed for AI purposes as the player-centric FoV map already has all the information needed.   Given mutable terrain and procedural map generation, I can't see any value in more detailed treatments.

There seems to be some unfortunate trend in roguelikes recently that end up putting far too much effort into 'realistic simulation'.  These high cost per mob AI implementations can easily lead to immersion breaking faults in actual game play.  One example from a well known and popular game are vault rooms where a player's AoE spells are greatly reduced in effectiveness because it would slow down the game too much if mobs responded to an out of LoS attack.  All vault mobs are ostriches with 'if I can't see you, you can't hurt me' immunity.

It is ironic that people who would never think of using a brute force solution to a low level problem, gladly employ brute force solutions such as simulation at the higher design level of modeling.

I see two problems with this criticism: First, your example seems hard to attribute to excessive attention to AI. And indeed, the OP is asking about how to make smart AI cheap, so that what you're describing doesn't happen. Second, this general line of thought seems to lead to the conclusion that the perceived room for development of better AI in roguelikes is not really there and that inevitably new games will look substantially the same as existing ones in terms of AI. I doubt this is true, but if it is, it seems that we should just stick to nethack (or rather, porting nethack to smart phones).

I think too many people have played Dwarf Fortress and seen something inspiring for the idea that monster AI is pointless outside of the player's line of sight to be persuasive.

[Omnivore]

I see two problems with this criticism: First, your example seems hard to attribute to excessive attention to AI. And indeed, the OP is asking about how to make smart AI cheap, so that what you're describing doesn't happen. Second, this general line of thought seems to lead to the conclusion that the perceived room for development of better AI in roguelikes is not really there and that inevitably new games will look substantially the same as existing ones in terms of AI. I doubt this is true, but if it is, it seems that we should just stick to nethack (or rather, porting nethack to smart phones).

I think too many people have played Dwarf Fortress and seen something inspiring for the idea that monster AI is pointless outside of the player's line of sight to be persuasive.

This is impossible to respond to as I did not state anything that you claim.

[mushroom patch]

Of course you didn't state anything that I claim. Maybe you meant you didn't state anything that I claimed you did. In that case, a more substantive response might include what you perceive those claims to be and how my perception is mistaken.

Anyway, I'm content, as you seem to be, to carry on as if you hadn't claimed anything at all. It's not impossible to respond to someone who prefers to defensively claim not to have said this or that rather than offering clarification or responding to counterpoints, but it's not often worth the time.