Implementation Ideas

[Aerig]

I did read the description of this forum, but it seems to be the only place that seems viable for describing coding techniques in reasonable detail.

So I figured I would post a few ideas to one thread and that way the devs can read them and everyone else can ignore the thread if the want to

I dont intent to get into code because I only understand enough C++ to understand roughly what you are doing in the source, but I do have some reasonably evolved ideas that I hope you will find useful ...

[Aerig]

This one starts out from what I said at http://planeshift.oodlz.com/wbboard/thread.php?threadid=11448&boardid=11&styleid=3&sid=90365f71c4344c72c9c96c243feb6f92 but is augmented by having read the code in ./src/npcclient/npcbehave.h

The fact that the ideas are so similar to what I already posted was what prompted me to start this thread, since I figure that if we are already thinking that much along the same lines that my ideas will hopefully be a fairly logical extension of what you are already doing.

The initial topic was about NPC AI and how its realism would make a big difference to how the game plays.

Looking at the code, there is a similar basic idea that NPC\'s can have behaviour types and motivations (needs) but the empahsis here, I think, is a bit different. The behaviour I am talking about is not so much how the NPC model is animated as what the Pattern of behaiour that it will exhibit of its own volition or in reaction to the environment around it.

What occurred to me when I read the source was that though it would implement AI to a certain extent, it would end up falling down pretty heavily because of the inflexibility of the general mechanism when it comes to getting NPC\'s to shift from one behaviour to another.

So let me rehash a bit more clearly what I posted earlier ...

Take the idea that people\'s behaviour tends to depend on where they are and what they are already doing. If we are eating dinner, we are unlikely to suddenly get up and start a fight all at once.

This sort of circumstance, where our reactions have a limited but predictable relism under particular types of situation is what I will be calling context.

When we are eating dinner that would be one context, with a set of likely behaviours, and when we are standing watch at the village gates that would be another context with another set of likely behaviours.

The way I see it, you would get a much more flexible system if you had a class called npcContext that had the behaviour class as a fundamental structure within it.

So now, supposing that we are defining our NPC class description and one part of that class contains a list of contexts. We might have several typical types of context within the game that nearly every NPC would have defined as part of their description. For example:

Combat
Patrol
Lounging
Hunting
pcInteraction
npcInteraction
pcFollowing
npcFollowing

There could be dozens of these, but in any one of those contexts, there are going to be a limited number of likely behaviour types, ie a limited number of things that the NPC is likely to do of their own accord if they are not interrupted by some event external to themselves.

Simplistically, each thing that they might be doing could be assigned a probability of them deciding to do from one moment to the next. So we could assign each type of behaviour a percentage likelihood of being what the NPC will decide to do at the next tick.

In the case where an NPC is Lounging about with a bunch of compatriots, we might have something like ...

0-10 Stroll about
11-20 Decide to have a nap
21-30 Decide to have a chat with one of the others
31-40 Decide to go have a look at some relevant object / person etc
41-50 Decide to have a look beyond their immediate surroundings
51-60 Decide to leave their immediate surroundings
etc

Some of those things would clearly involve the NPC switching from one context to another. If the NPC decided to leave their physical surroundings they would literally be in a differnt physical context and so would be likely to perform a completely different set of actions.

But the idea of a table of rolls is obviously too simple on its own. If we checked the table every server tick, we would almost certainly see our NPC\'s starting to do one thing and then changing to do something else a few ticks later. So we need something to counter that.

Normally, we oppose distractions to and disturbances to completing or continuing what we are currently doing with our level of incentive to keep doing it. This is pretty much like the idea of needs that is defined in the npcbehave.h file.

In this case though, we are not talking about what will prompt us to undertake some action to begin with, but our natural inclination to keep doing it once we have started.

So, as well as having a roll level that decides what we will do when we do decide to do something else, we also have an incentive level for each type of behaviour that tells us how likely we are to keep doing that once we have started.

One way to implement that incentive level might be to have a starting value that decrements with every tick, thus making it more likely that we will be willing to do something else after we have been doing what we have been doing for a certain amount of time.

Effectively:
Start doing something.
At the next tick decrement our incentive to keep doing it
Roll to see if we keep doing it or stop of our own accord
Roll to find out what other activity we might be doing and ...


Consider how urgent that new thing is. This is a bit more like the need rates defined in the npcbehave.h file. If the thing is urgent enough, then it may overcome our incentive to keep doing what we are already doing.

For example, if we suddenly need to go to the toilet, that might take precedence over having a seat at the camp fire.

Then again, we might be cooking dinner at the camp fire and going to the toilet might have to wait a bit. The incentive to finish cooking dinner might well be greater than the urgency of stopping to go to the toilet.

Whichever the case, at this point we want to check to see how urgent the new demand on our attention is and stop doing what we are doing if our incentive to keep doing it is less.

We have two issues we have to consider at this point. Is what we are doing something we will want to go back to after we have done the other thing and will we still want to go back to it if the other things takes a long time or has the sort of critical urgency level that means that everything else gets thrown out of the window?

So we need to keep track of whether or not our behaviour is one that we might return to and we need to keep track of whether or not what interrupts us will overwrite any desire to do that.

Obviously we could simply decide that, if any interruption was sufficiently more urgent than our remaining incentive to complete our current activity, then we would scrap that activity even if we would normally go back to it.

So far all of this is within the range of likely types of self initiated behaviour in a particular context. But what happens when someone or something comes along and intrudes on our self contained context?

This is not so different from what happens when we check to see if our next possible activity is more urgent than our incentive to keep doing what we are already doing.

In fact we can elegantly resolve parts of the evaluation of each type of situation by having a method that we call upon the NPC that is something like

NPC->newEvent(evSource, evDescription, evUrgency)

and which results in us simply checking to see if our NPC is willing to leave off what they are currently doing to do whatever the newEvent requires.

This is where the idea of contexts becomes powerful because when the event causes us to switch contexts we can move to a completely new set of behaviours that are completely relevant to and consistent with that context.

Where\'s the difference between doing things that way, and just setting up a list of all the possible behaviours that an NPC might get invoved in?

To begin with, if you already have basic definitions of how NPC\'s react in a certain context then you can inherit those definitions more easily than defining them from scratch.

Better still. If every orc, for example, inherits a certain set of basic contexts that they might act within and every scout inherits a set of contexts that they might act within, then you can define an orc scout\'s basic behaviour pattern by simply inheriting both contexts.

More flexibly still, with a bit of ingenuity parts of the scout context can moderate parts of the orc context andor vice versa, so that an orc scout would be markedly different from a human scout in the way it behaves with very little effort required from the programmer.

But that is only the half of how flexible using a context class could be. You could also implement contexts that were specific to the local surroundings and that endowed every NPC existing within or entering them to inherit that context\'s pattern of activities and behaviour.

By having context supersets for different types of NPC you could have an extremely flexible, easy to implement system for realistic a diverse behavioural patterns in different types of NPC.

Orcs might have a whole set of default modifiers on inherited behaviour types that applied maximum and minimum limits on how much they might exhibit a type of behaviour and proportional or additive modifiers that directly affected the behavioural contexts that they inherited.

The same might be applied to scouts, warriors etc so that you could have a set of contexts with default parameters that were dynamically affected by a variety of aspects of the NPC\'s type, each of which applied its own modifiers to that NPC\'s patterns of behaviour in different contexts.

eg a Female, Orc, Cleric, Towndweller might have each of those attributes triggering modifications to the basic behaviour contexts that they inherited and so behave in a completely different way to a Male, Human, Barbarian, Plainsman inheriting the same basic context data and starting out in identical circumstances.


Try to visualise how all of that would work in the setting of a bunch of orcs around a campfire being observed by an unseen PC.

One orc is on patrol and is circuiting the boundary of the area. Another is simply walking about stretching his legs.

Another is sitting by the fire when he feels an irresistable desire to get up and go to the toilet. On the way to a darkened spot, he is intercepted by another orc who has had a sudden desire for conversation, but the first orc is caught up in the urgency of the need to relieve himself while the talkative one is equally caught up in the need to say what he has to say. Having relieved himself, the first orc finally responds to the second.

Because we are not programming a set sequence of actions but instead a pattern of possible actions, every time the server is reset, that campfire scene will look different and the game will get a very natural, realistic and atmospheric quality.

[dfryer]

Instead of determining by dice-roll whether to change actions or not, instead you could establish a slightly random duration at the beginning of the action, which would continue until the expiry or until some other interruption took priority.

Writing Really Good AI is tough, even many large games take the spawn-and-wander approach.  It may be necessary to have a \"herd AI\" managing (for instance) a group of orcs hierarchically, so that even though the orcs would have general tendancies to wander, interact, and eat raw squirrels, they\'d have a \"general direction\" (i.e. towards the road between two villages or something like that)

Also, I believe we want to provide for GMs of a certain level to be able to encourage NPCs to a certain action by fiddling with various \"goal\" parameters.  Something like fuzzy logic rule sets might be used to turn goals into actions.

[Aerig]

instead you could establish a slightly random duration at the beginning of the action

That\'s the way it looks like the code to implement physical actions as it is in npcbehave.h looks like its going to be implemented (as I say my C++ is rudimentary at best so I could be wrong there)

The reason I suggested the type of logic flow that gets determined by dice roll, is that AI often feels very unrealistic because the mobs otherwise end up simply following the same pattern of behaviour until some external event changes what they are doing.

Using a table of possible changes of action in each context would mean that the mobs could be made to appear as though they were doing things of their own accord.

What you suggest, I think, is much the same as my suggestion that we could have incentive levels and urgency levels, in the sense that the incentive level could be implemented as the action timer and its initial value modified according to the other things going on around the mob when they start any particular action.

I admit that there is a \'problem\' in the way that I am suggesting that things could be done, in so far as that the code evaluation overhead would be slightly higher, since you could not simply stick the mob on a queue of mobs whose next action is to be evaluated after some particular time period (though it looks as the though the code as it is is not doing that either, but polling each mob every tick).

On that front in the current code you could, when you start a mob on some action, stick it on a time sorted queue of mobs to be reavaluated and also on the queue of mobs that are performing some action or other.

When the mob received an event, it would be removed from the time sorted queue, its next action evaluated, and then moved, if necessary, from its current action queue to the queue for its new action and then replaced in the time sorted queue with an endAction time stamp.

Doing things that way would lower your server overhead, since you would not have to tick every mob every tick, but only those mobs that were due for reevaluation.

It would have the disadvantage, of course, of being slightly less flexible. But, if you know that the mob is going to keep doing something until some event stops it, whether that is timeout, being killed, killing or their target disappearing, then using a queue would save you having to increment a counter every tick.

With, say, ten thousand mobs to animate, thats a lot of server overhead that you could be getting rid of - not just a while loop running 10k times to increment loop counters, but also all the evaluations of structure pointers and subsequent memory fetches as well

instead you could establish a slightly random duration at the beginning of the action

Thinking a bit more about what you are saying here, it occurs that I might not have interpreted it as you meant it and that perhaps you meant that, having decided what the mob would be doing, a duration for how long it would do it could be determined and that mob then left alone to do that until it timed out or received an interrupt.

Resptrospectively, and thinking about what I was saying above, I agree that that would be a more efficient way to do things, processing wise at least.

I think my quibble would be that it might mean that the AI would be less flexible at the end of the day, in the sense that, if we want our AI to adequately simulate patterns of behaviour that feel real to us, then it feels more natural to implement those in a way that is representative of how human actually behaviour works.

Having spent a fair amount of time trying to work out how people behave and think, the mechanism I suggested reflects one main principle that I believe underlies real intelligence, ie that we accelerate our ability to analyse and respond to the environments around us by categorising them by context.

In the context of a game though I admit that it might be faster to sacrifice realism for lower server load. But with processor potential about to explode with the advent of full 64bit processor architecture, not to mention the recent (a year or so ago) introduction of dual pipeline raid-like memory access (MSI boards that I am certain of), I rather suspect that taking the time to implement well organised, flexible AI code architecture will pay off a lot more than worrying about server load.

That even more the case, given that PS is only just beginning to hit the threshold of the playable game and laying the right foundations now will save a vast amount of code revision later.

[Aerig]

Okay, this one is really about ingame socio-economics flux and interaction between different sections of the ingame N/PC community.

If you have played EQ, and just about any other MMORPG that implements the idea that different aspect of society have different interests and that PC\'s gain or lose interest with them according to their actions, you will have noticed that this is usually implemented with such crudity and lack of realism that it might as well not be implemented at all.

For example, take a human rogue starting out in the EQ town of Freeport. Apart from the faction points that you gain as you do the various parts of the quests and which then allow you to do other quests, faction has negligible impact in the game.

When has being a rogue, dark elf or any combination of race / class ever made any appreciable difference to what you can and cannot do in any MMORPG you have played?

The divisions are so often black and white and the initial choices of players so likely to conform to commonly chosen defaults that all that happens is that some major territory or aspect of the game writers efforts is deprecated and left largely unexploited because the majority of players alll go the same way to start with and then dislike the idea of moving into a quiet suburb of the game when they try the alternative(s).

So the first thing I would say on this is that factions should rarely be utterly in opposition to each other or completely mutually exclusive.

Guild memberships might be mutually exclusive, but how many real situations can you think of where people will simply not work with someone else just because that person does not belong to the same \'sect\'?

Human history has proven that that is a self destructive approach to dealing with the world at large that generally result in inbreeding and subsequent diminishment of those that attempt to do things that way.

On the other hand, factional competition is common, as is depreciation of people who promote the interests of those who are perceived as supporting the interests of those that the faction feels are supporting interests that are against their interests  

But this is rarely a simple matter of gaining a gestalt standing with any particular faction. How many times have you heard something like? ...

\"Yeah, well okay, s/he broke this trade agreement, but last week s/he brought us enough information to start a new guild house in X\"

So the first thing that I would be inclined to think when it comes to implementing factions is that part of every faction definition should be an outline of the faction\'s interests, which would fall into the following basic categories.

• Complete Mutual Exclusion
  
  This would be there to cater to the situation where some faction will have nothing at all to do with someone known to have interests or proactive behaviour with respect to some interest that the faction is against.
  
  \"You killed an orc ten years ago, so you will not be part of the League of Upright Orcs!\"
  
  
• Partial Mutual Exclusion
  
  This would cater to those situations where membership or certain levels of involvement with the faction would be prohibited depending on how much faction the N/PC has with the related interest of this faction.
  
  \"Well I have had it confirmed that you have killed one of our members. Even though that was in self defence, you will be denied the right to progress beyond the third rank.\"
  
  
• Complete Mutual Inclusion
  
  This would allow for those situations where fulfilling certain criteria would allow for participation in the faction, irrespective of all other faction ratings.
  
  \"As a lifelong resident and citizen of Laanx\'s Well, you are entitled to vote in the elections or stand as a candidate for the village council.\"
  
  
• Partial Mutual Inclusion
  
  This would cater to those situations where membership or certain levels of involvement with the faction would be permitted depending on how much faction the N/PC has with the related interest of this faction.
  
  \"Well I have had it confirmed that you have successfully burgled ten dwellings so, even though you are not acceptable as a member of our thieve\'s guild, we will allow you a limited charter within the bounds of our jurisdiction.\"
  
  
• For
  
  This caters to the simple situation where the N/PC, having acted in accord with the faction\'s interest to some extent would gain faction with the faction.
  
  \"Hey this guy made us 100 tria last week. He\'s not so bad\"
  
  
• Against
  
  This caters to the simple situation where the N/PC, having acted against the faction\'s interest to some extent would gain faction with the faction.
  
  \"Hey hold up, didnt she steal from one of our members friends last month?\"
  

So far thats not a much better faction system than seem to be implemented in other games.

But, if you take the situation where NPC\'s also have interests and that their personal reaction to those might make them more or less proactive with respect to the interests of any factions that they are part of and which then cause their interaction with PC\'s to vary as a result, then we begin to get a faction system that feels believable.

At the crudest level, by implementing NPC faction affiliations and personal interests at various levels we could could make their responses to players feel more dynamic by simply replacing forms of address and adjectives when PC\'s interacting with them achieve different levels of esteem in different areas of the NPC\'s interests.

Take the example of the high level PC who has raised their faction to a vast level and returns to see their guild master, only to get the same pat response that s/he gave them when they were a lowlie noob.


However, a much larger issue with current MMORPG\'s is that promoting or deprecating the interests of some faction or other generally has no impact on the general attitudes of members of that faction.

The result is that the world that the game is played in seems static, cardboard and unchanging, and that the player is left with the feeling that none of their actions ever actually affect the world that they live in.

For example, in EQ, if someone wins the Coldain War, irrespective of which side they help win, there is absolutely no visible change in the attitudes of the NPC\'s.

The way I would see it, if any N/PC, anywhere, did anything that gained them interest with some faction, then that faction\'s reactions should change with respect to how big an impact that made on the faction\'s interests.

If the Coldain won the coldain war, then they should be more willing to respond to people with less faction against the oppostion while the opposition should be more aggressive toward people with Coldain faction.

That is an extreme example. Suppose there was a stonecutter\'s guild in Laanx and that 10 N/PC\'s joined it all in the same day. Then the miner\'s guild should be droppping the price of ore by some amount to reflect the greater amount of ore that they have and they should also gain a lttle prestige with the town council as a result of being a larger guild.

At the same time, the lumberjacks guild might also lower their prices and at the same time lose some prestige with the town council, on account of their competition introducing cheaper products and gaining more prestige in the town.

They might also lower their membership requirements in order to try to attract more members themselves.

What we are talking about here is an apparently very complicated flow of responses by faction to impacts on their interests.

But implementing this is not necessarily so complicated as it might seem.

Supposing any faction with any interest in some area (for or against) was added to a list of factions that needed to change when some increase to that faction happened.

And that when the action occurred, that a method was called by the instigator of that action that caused all interested parties to have their total reaction level to that interest modified appropriately.

I can see all the coders going, oh god that would take vast amounts of processor potential. But it would not necessarily do so.

Supposing the interest was in dead orcs. The faction interests need not be updated every time an orc was killed but might be updated only when the N/PC contacted an NPC who had sufficient interest in the killing of orcs to pass that on to their faction.

NB at this point, I would mention that certain aspects of MMORPG\'s are better carried out by separate servers or service modules anyway and that incrementing faction counts is something that should actually be done on a per hit basis but in a way that does not affect the load on the main game server.

Implementing faction impact is one area where it is very obvious that it would be better to have a separate server or service module implement the changes without increasing the load on the game server.

To continue, an orc gets killed and the method is called to update all factions dependent, positively or negatively, on the killing of orcs.

All such factions get updated with that data. Then the impact of the change gets incorporated into any other interests that it affects in the faction concerned.

As each interest gets changed to reflect the change in a related interest those aspects of how the faction interacts with the rest of the world are updated at the same time.


So consider the situation we have, that a faction has N interests and that any one of thsoe interest may affect one of its other interest positively or negatively.

We might then create a 2 dimensional array (matrix) of how each intersest affects another interest of the same faction.

When we apply the initial change to one interest (eg the killing of an orc), all related interests get changed by multiplying the factions interest matrix by an Nx1 matrix.

Part of the implementation of that matricial multiplication would then be the calling of the method that gets called when each of the related interests get changed.

So ... someone kills an orc and that results in us updating the faction\'s interest in orcs. But then killing the orc results in us updating that faction\'s interest in A, B and C, which results in turn in us updating the faction\'s interest in those things that are related to its interests in A, B and C.

But any of A, B or C might be related to the interest, K, of killing an orc, which would result in an eternal loop.

So, when we call the method to update any faction interest, we also have to pass a list of all interests that have called that interest\'s update method and ignore those interests that have already called that interest\'s update method from the same root interest.

This means that our update method has to be able to identify which changing interests have already been taken into account so that we can halt the process if one interest results in updating another interest which also results in updating the interest that resulted in its own update.

ie If B updates C, then C must be denied the right to reciprocally update B. But anything that B updates that then update C should also result in C being denied the right to update B, because B has already updated C itself.

At the end of the whole process, we then call a clean up method that tells every interest to remove its record of what interests tried to update it as the result of the root call.

But ... when we get that root method clean up call that lets us know that we have updated all the interests in that derive from the update to the initial interest, we still have have to call a method that will allow other factions to reflect to how our faction\'s overall attitude has changed as the result of the call to the method that allowed our faction to change as the result of the change in our interest area.

......... read next post ...........

[Aerig]

IE We propagate the results of all changes to the interest are, kiling orcs, in all factions that have an interest in that. But we then have to propagate all changes to every faction that have resulted from the change to that particular interest.

Note what we are doing here.

We change one interest and that then changes every related interest in every faction with that interest.

Every related interest that changes must then change the interests in every faction that has that interest, and each of those changes must do the same.

But, we are not allowed to multiply change an interest that has come from the same initial change in interest, no matter what faction it originally came from.

So after all the interests have been changed as the result of every change in every interest of every faction and the cleanup method is called, we then have to reassess the gestalt change in each faction with respect to every other faction, ie we create another 2 dimensional array, this time of faction vs faction, and propagate the same process through that, not worrying about what each faction\'s interests are but about how each faction directly relates to each other faction.

Whatever changes we get in each faction\'s overall attitudes, with respect to each interest of that faction, should not propagate a new cycle of faction interest updates.

If our overall faction attitude causes a change in how that faction views certain interests, then that is a change that is internal to that faction and should not be passed on to how other factions react.

[Aerig]

So now we have a faction structure that will let our PC go do the sort of quests that only let you move on as you get more faction in the appropriate area.

eg get enough orc scalps and you also get enough faction with certain NPC\'s to be allowed to do other quests.

Which is fine as far as it goes. I get 500 faction in killing orcs so I get to do the next quest.

Note comments above about NPC\'s changing their attitude to you as they perceive you in a better light.

But what we really want to think about is how to implement a quest engine.

A simplistic approach would let you earn faction with the particular N/PC that gave you the quest as you repeated certain specific objectives.

That\'s all very well but a thief who has already proved that he can pickpocket, cutpurse, mug and burgle does not want to perform 1000 burglaries to get to the next quest level.

Apart from that, a quest engine that was completely (and probably inflexibly) objective oriented would not be one that would satisfy the more sophisticated type of player that we have today.

On the other hand, having quest objectives is practically inevitable. But with the type of faction engine described above, it does not have to be restrictive.

Consider an NPC who has certain interests.

A quest objective could be defined as attaining, overall, 500 points of faction with that NPC.

But with four or five different ways to earn faction with him/her we would immediately get around one problem that MMORPGs have had so far with their quest structures - ie there is usually only one way to complete the quest, which restricts players to a particular playstyle until the quest is complete.

However, assume the situation where the player has to have completed five specific objectives, ensuring that they experience certain aspects and environments of the game, but where the final objective(s) are achieved by attaining enough faction with the N/PC that gave out the quest.

If that N/PC has 10 interests, then that leaves the player free to try 10 different ways of completing the remainder of the quest requirement.


So lets think about what would happen in a pen and paper RPG ...

The DM says that you have met N/PC X and that they are \"not impressed by you\" but the N/PC refuses to give you info on what impresses them.

So you go to another N/PC and ask about the first one.

Supposing any N/PC had an interest in the people around them and that you had a skill to find out that information.

Then you would go talk to the other N/PC and find out that info and, having found it out, you would exploit that info to impress the N/PC - ie you would find out what would get you enough faction with that person that they would accept you when you had earned that amount of faction.

tbc (probably in a few days when I have more time to spare from RL)

ps Not writing this stuff on the assumption that the dev team have not already got a good design to work on, but in the hope that you might find a few useful ideas that you might like to include in the game.

[Aerig]

Guess who had a busy Xmas and New Year? I\'ll get back on this as soon as RL work gives me a break.