Using influence-mapping

[Rasmus]

http://www.gamedev.net/page/resources/_ ... ping-r2799

Just want to share this thing, the reading tutorial may be abit complicated but check out the video, I find it really insperational! Especially if you are interested in AI..

Now I am just wondering how to implement it into DM.. The monsters dies way to quickly to be interested in knowing what happend in the past Maybe party bots.. hmmm

[Bit]

If you want it for the network game, you could save game results as history. The more experience the players bring in, the more the monsters get trained. Then, that's all not really new. I remember very old 'catch the horse' games on the first home computers.
More interesting could be another idea, i.e. pathfinding by 'view'.
Let assume you have a monster that smells food. It now has two possibilities to alert other monsters to help (or just to avoid exactly that for having the food for its own - depends on monster characteristics). There is 'sound' for those who can't see it, or 'gesture' for those who may see it. Pure 'noise' just gives a direction, that doesn't say anything about the real path. Including 'language' can have different effects. Monster B understands 'I'm under the bridge' and knows the location and the quickest path. That's the one extreme. The other is, Monster C doesn't understand the language at all and knows nothing about the current location. But if C can see the monster, it can interpret the gesture and repeat the gesture for B, the next monster that can see C, but can't hear A. B now runs to the bridge and C can follow by sight contact (ant - algorithm).

Selecting a character to be the favourite target should not only be the reason because it's the healer. The monster could have the history 'those in white taste best'... It now may happen that healers prefer white robes.

One thing is for sure: monsters die too fast. They should have more chance to escape - and hide in a nest that gets better not attacked in full population. Haven't seen any game that realized this, which could developers enable to set up way more challenging riddles.

[Rasmus]

I had a talk to Adamo at the chat yesterday, he said the same thing "Monsters die too fast!". And I agree, it would be cool creating monsters where every one is a challange, it doesn't have to be like high HP, because that is just boring. But that they have diffrent way of fighting, diffrent resistence etc. some may be incredably good at blocking/avoiding melee attacks, has high resistance, but are worthless against missiles etc.
But this is nothing new, even DM use this on some monsters, but some visual effects like a monster accually blocking or avoiding the attack would make some more realism to it.

Things like having favourite targets, fighting technics etc. isn't that hard to implement. I created a checkers game a couple of months ago, there I learned alot about using alpha-beta pruning (or min-max) and heuristic values. A short explanation for this is that the computer are searching for the best move by searching all posible moves (including opponents move), and when he reaches a certain depth he evaluates the gameboard and get a heuristic value. When every move posible have been searched at a certain depth the computer takes the move with the best heuristic value and make that move.

The whole fightingtechnic/movingtechnic can be created easely by just having diffrent heuristic value depending on what the monster wants to do. I have never implemented this into any rpg game before, but I think the result will be very good. The alpha-beta technic may be best sutied for several monsters in group, but will still work for one monster. Now lets say if the monster/monsters never has seen the party, any opponents. Then he wouldn't include them into the "searching", or that he have seen the party in a certain spot, then he will assume that the party still is in that spot/area when "searching".

Anyway, I don't want to wander of from the topic, so lets say that every monster has their own influence mapping. And that monster groups share the same influence mapping, and that the monsters can wonder of from the group and then copy the groups influence mapping and make it his own, or the other way around, wander into a group and take the groups influence mapping. in this way the monsters with the same "thinking" or wanting the same goals (getting the same heuristic value) will form groups automaticly. And by using a alpha-beta algoritm, groups of diffrent monsters will cooperate as long as they are after the same enemy. When implementing this right, I think we will get monsters accting as inteligent as any human playing, or even better because they would have a better overall view..

(I want to clarify that the influence maps would be used for getting a good heuristic value)

This is somewhat my vison:
Groups of monsters are in a room, they have spotted the party. Some groups like attacking right on, some attacks from distance with spells and some like flanking and others healing. The result would be that the party would be surrounded very quickly and it would be almost imposible predicting the monsters behaviour. Another scenario would be that one monster may have seen the party, but he decides to hide because he knows that an attack would be more succesfull as soon as the other monster nearby are there too. Maybe he tails the party until the party bumps into another group of monsters, THEN he attacks from the behind! It is almost imposible knowing exactly who the monsters would behaive, even if I programmed their AI myself. Another result may also be that if I give monsters a memory by using a specific influencemap for this. Then supprising a group of monsters may result in them running away very quickly because all they can remember from the party is that bad things happends when they are near.

It would be sooo cool..

[Bit]

Now - think about another problem.
Imagine the first room in CSB - three worms. This should be enough to catch the party sooner or later. But - the worms are probably meant to be pretty dumb (I mean, it's the first room...). Do monsters act more intelligent in the deep? No.
All that long monster movement calculation is for nothing after all. The only one which really acts a little bit intelligent is the thief - that's what I meant. A thief can be really annoying - isn't it?
Back to the first room and the example with the three worms.
I think, the influence mapping can not replace a good algorithm that would try to hunt down the party over the trigger, so that the group enlarges - and - the hottest influence point can't be the trigger itself, it's not of interest for the worms - it should even be kind of forbidden, because the party can't run over the foot plate as long as a worm is there!
No - influence maps may be of interest for other types of game - in a riddle based game like DM I think they fail (until you prove me to be wrong).
There are even more problems. Think about the end of zone, where a monster shouldn't follow the party. The snake are probably the fastest ones in DM - and they really hurt at that point. But just bring them to such a borderline, hide short to load all spells, then step aside and shoot that thing down. Against that strategy it stands no chance.

[Rasmus]

I agree that some monsters aren't smart enough to waste advaced AI technics on. Like the worms.. But then again some monsters are, I would like to say that a demon, hellhound, trolin (and some other monsters with some kind of head) are as smart or smarter than my fat cat and she knows how to hide and attack, search places she knows eatable animals would be etc. (not that I have any of those animals running around in my appartment). So I don't think it would be so weird if a hellhound would like to hunt the party in groups whatever instics a dog from hell would have..
I would like to say that diffrent attackpatterns/behaviours would give the monsters more personality, and be more fun to fight against (or maybe with).

About the triggering certain points in the influencemap. Correct me if I am wrong, but as I understod it from the tutorial the points triggered by the enemy gets blured out like bluring a image in photoshop. The speed of the blurring decides if the monster will act according to the present, past or future. If the monster see the party in a tile, the influencemap will give that tile a high value, and this value will get blured out over the map. Sooner or later it will reach the monster that will be drawn to the higher or lower values (depending on if he is hunting or fleeing). A voila we have a pathfinding algorithm that would seem realistic for a monster with limited knowledge about the partys whereabouts at low low cost. Adding that the tiles the monster itself stands on will give the influence map a low value, the monster will never backtrack and keep searching the dungeon even if he has never seen the party.

Lets say that a monster wants to sleep, what place would he choose? The place that he has never seen any enemies!
What places would he go to if he wants to join a group? The place where he has seen most of his fellow monsters!
It is just to add another influencemap for every need a monster would have, and smarter monsters would have influencemaps that blur faster for predictions on where the party would end up in some time, perfect for ambush.

The more I think about it the more it seems more natural to use it. I mean why not? Using A*Star pathfinding system would be an increadible waste of cpu in comperansment to using a influence mapping. I can imagine having a dungeon with thousands of monsters all searching at the same time after the fastest way to hunt down the party with almost zero cpu-cost. A monster that moves from one tile to another in 1 second would have about 1/2 second on him to update his influence map. And even that may be alittle bit to much..

(I am not saying that A*Star pathfinding would be the optimal way to do the AI with, I just used it as an example..)