AI for dynamic environments

[miki151]

If you run Dijkstra on a small subregion of a large map, you can either do it on an array with equal size to the small subregion, or on the corresponding region of the whole array (with a rectangle describing which tiles the results are valid for). In either case, the amount of re-initialisation to be done is miniscule.

That's a reasonable approach and exactly what I was doing till a few days ago. The problem, in my case, was that once in a while the path needed to leave the subregion, and the algorithm couldn't find it. Increasing the margin helps, but the problem goes away completely if you just use the whole map with the trick to re-initialize it. That's the "pro" way of doing it, I believe.

Also, the trick is widely used in other applications, it's good to remember about it. It's not a micro-optimization, it reduces the time complexity of some algorithms.

[Quendus]

Yes, it's a good optimisation in cases where there's a high ratio between the number of tiles potentially altered and the average number of tiles actually altered in each run.

Ok, my original post might have made it sound like I want everything and the kitchen sink, I might need to elaborate:

My idea is to group the creatures into two main categories of AI complexity:

• Stupid to moderately smart : all monsters
• NPC : characters that would play like the player

I'd like to have a good auto-play bot for the NPCs above, I don't care about perfection or true AI or whatever, but not visibly dumb.
I don't want either the monsters or NPC bots to cheat much, but not strictly prohibiting it.
I'd like to be able to run a number of those bots (a dozen or two) simultaneously in a level.
Levels could be large, and large levels with many smartsypants bots assume fast performance.

I don't think I'm asking the sky-and-stars, I'm just trying to think an extensible framework that can, for starters, satisfy *a few* of my requirements, and that I won't have to rewrite from scratch in a month.

What behaviours would you expect from the smart enemies? Do they really need to be smart, or can you simulate smartness by giving them advantages over other monsters and the player? What differences in behaviour do expect from the dumb enemies?

There's an opposition between individual-based AI routines that scale with the number of agents, and group/map-based AI routines that scale with the map size and number of different behaviours that must be supported.
Individual-focussed AI code may hinder your ability to add lots of dumb enemies, and group/map-focussed code may hinder the flexibility of the smart enemies. A dual approach may be twice as much work.

[reaver]

What behaviours would you expect from the smart enemies? Do they really need to be smart, or can you simulate smartness by giving them advantages over other monsters and the player? What differences in behaviour do expect from the dumb enemies?

There's an opposition between individual-based AI routines that scale with the number of agents, and group/map-based AI routines that scale with the map size and number of different behaviours that must be supported.
Individual-focussed AI code may hinder your ability to add lots of dumb enemies, and group/map-focussed code may hinder the flexibility of the smart enemies. A dual approach may be twice as much work.

In my (ideal) view, I want a system to allow for a hierarchy of needs.

• Dumb creatures only care about survival (flee to save their lives, chase to get food and prevail). 
• Smarter creatures care about survival, but also actively try to increase their chances in it. Fleeing thieves lock doors behind them. Monsters pick up and adjust equipment after/at every encounter, use potions etc.
• Smartest creatures plan more. They don't just rely on whatever equipment lies around, they plan to go exploring around the level (or more levels) to find better stuff. They might go to the city to restock/sell. They might attempt to form parties if they want to tackle a difficult dungeon.
  

(Obviously I'm not gonna think how to do party-formation now, just the dumb AI, I just want something sensibly designed that will keep whole-AI-system-rewrites to the minimum)

When you say about scaling, do they scale well or badly? I have no idea of how different they can be, and I've never done group AI. I bet I'll be using that though, as all dumb and many smarter/smartest creatures would probably exhibit groupthink in some form or another. The smarter the creature, the more the individual code I expect it to have, alongside higher-level group code.

By the way, does anybody use D*-lite around here?

[miki151]

I'd like to hear about the group/map-based AI, it sounds interesting.

[Trystan]

... it sounds a bit counter-intuitive though (splitting the AI/decision-making between the creature and its items), and spells/abilities are something that will probably come quite a bit later on

I made an NPC that can occasionally beat my 7DRL from last year. You can see it in action at http://trystans.blogspot.com/2013/09/pugnacious-wizards-2-version-10.html. The AI only uses spells since there are no other items but you could easily add items and have them use the same system. The main AI loop is 24 lines: https://github.com/trystan/PugnaciousWizards2/blob/master/src/Hero.as#L28. It's not perfect, but it's interesting and I'm pretty proud of it.

As a general rule, moving logic out of the creature class has worked well for me.

Has anyone seen a good example of group-based AI that worked well?

[Quendus]

Joshua Day has written a lot on this kind of programming. It's essentially an extension of the scent map/distance field idea. One map computed for the whole level can provide any number of monsters with a specific behaviour (like chasing the player, chasing members of a specific group of agents, fleeing from the same group, moving towards useful items and unexplored areas) essentially for free.This becomes inefficient on very large maps and when the number of different behaviours that need individual treatment is large.

If every agent has different relationships with others, then it's impractical. If they're divided into teams, then the performance bound would be on the number of teams times the size of the map. An agent can produce different higher-level behaviours by combining information from more than one map, recomputed once per turn, and avoid having to do any pathfinding of its own unless it has very unusual requirements.

http://paleoludic.com/writing/whitespace-reasoning/
http://paleoludic.com/writing/a-pathfinding-primer/
http://paleoludic.com/writing/engineering-pds/