So After more than two years of game programming I think I've finally achieved something decent as a game programmer: an AI system that doesn't totally sucks.
I called it AMOEBA because at the end of the day it really isn't artificial intelligence, but just a way of storing events and evaluating possibilities.
it stands for: Action, Memory Organization, Evaluation, Behavior, Action.
It required me several dozens of iterations, both "on paper" and on code, but I'm now at the point where I like it, it's working for simple test cases, and it's absolutely scalable.
I'm posting it here for sharing it with you fellow handmade developers, I feel like this community has given a lot to me and it's time to give something back.
Of course feel free to use, reuse, modify, suggest anything that's writter here.
I hope that someone will find it useful somehow, sometimes. :)
Before starting, I'd say that Dave Mark's book and talk on utility based AI were very useful and gave my the tools to develop all of this, so let me suggest you the book "behavioral mathematics for game ai" and this talk: https://www.gdcvault.com/play/1021848/Building-a-Better-Centaur-AI
Now let's start.
////////////////////////////////////////////////////////////////////////////////////////////
1) Big Picture:
I'm developing a multiplayer fantasy rpg (hopefully it will become an mmo one day), and I wanted my creatures and npcs to have an AI system that:
//////////////////////////////////////////////////////////////////////////////////////////////
2)Key Ideas:
////////////////////////////////////////////////////////////////////////////////////////////
3)High Level Routine:
////////////////////////////////////////////////////////////////////////////////////////////
4)Scalability
It's pretty easy to adapt the routine to a certain game's needs, especially as the number of entities to simulate grows:
/////////////////////////////////////////////////////////////////////////////////////////////
5) Implementation details of the memory system
Main requirement: retriving in costant times a LIST of all the associations relative to something. that something can be a CONCEPT, an IDENTIFIER, a LOCATION
every entity has a certain number of "associations slots" available, and that represents its entire memory.
every association contains both the actual association data (LOCATION, CONCEPT, IDENTIFIERS, ecc) and, for every member of that data, it contains a pointer to the next Association for that data member.
A set of hash maps will contains the first index of every concept, location, identifier present in all the associations.
So when we want to retrive all "ATTACKER" associations, we hash the "CONCEPT HASH TABLE", and that will tell us the most recent association that contains "ATTACKER" as a concept.
If we instead want to retrive all the associations relative to a position, we hash the "POSITION HASH TABLE" instead of the concept one.
Reference image: https://ibb.co/hYhR0L
Updating the memory means:
-cyclying over every associations, and lowering it's score based on how much time has passed since last update
-computing a list of the associations with the lowest score
-substitute them with the new ones, (if the new ones score it's higher).
Main problem is that every hashmap has to have a number of slots equal to the number of different associations, because for example every associations could potentially be at a different location.
So if an association contains: LOCATION, CONCEPT, IDENTIFIER, and we want an entity to have 1000 associations in its memory, we need:
1000 * sizeof(association) + 1000 * sizeof(LocationHash) + 1000 * sizeof(ConceptHash) + 1000 * (Identifierhash)
Assuming a generic data member is something like 10 bytes (64 bit of data + 16bit for the nextIndex assuming noone can have more that 0xffff associations), and a standard association that contains something like 6 members (concept, location, actorIdentifier, actorType, targetIdentifier, targetType) + some additional data,
80bytes per associations seems something close to reasonable.
Now, if Every hash slot is also 10 bytes (64 bits of data + 16 for the first association Index), to store a single association we need:
80 + 6 * (10) bytes, which is 140 bytes.
You can probably squeeze some bytes here and there, so let's make it 128bytes necessary for every association.
Allocating 4gb for the memory, you get 2^32 / 2^7 = 2^25 associations, assuming your world has 16k entities that needs memory: 2^25 / 2^14 = 2k associations for every entity, which seems like a reasonable amount of memory.
Thank you for taking the time for reading all of this, any feedback/suggestion would be really appreciated. :)
Leonardo
I called it AMOEBA because at the end of the day it really isn't artificial intelligence, but just a way of storing events and evaluating possibilities.
it stands for: Action, Memory Organization, Evaluation, Behavior, Action.
It required me several dozens of iterations, both "on paper" and on code, but I'm now at the point where I like it, it's working for simple test cases, and it's absolutely scalable.
I'm posting it here for sharing it with you fellow handmade developers, I feel like this community has given a lot to me and it's time to give something back.
Of course feel free to use, reuse, modify, suggest anything that's writter here.
I hope that someone will find it useful somehow, sometimes. :)
Before starting, I'd say that Dave Mark's book and talk on utility based AI were very useful and gave my the tools to develop all of this, so let me suggest you the book "behavioral mathematics for game ai" and this talk: https://www.gdcvault.com/play/1021848/Building-a-Better-Centaur-AI
Now let's start.
////////////////////////////////////////////////////////////////////////////////////////////
1) Big Picture:
I'm developing a multiplayer fantasy rpg (hopefully it will become an mmo one day), and I wanted my creatures and npcs to have an AI system that:
- allows them to have complex behaviors and to take reasonable decisions in a pretty quick way, taking into consideration "secondary" actions as well. (Like equipping one weapon only versus certain enemies, or drinking one potion at a certain time).
- allows them to memorize events occurring around them in a reasonable way and in a fixed amount of space assigned to each entity, forgotting the most useless events and remembering the most important ones for their entire lifetime possibly. Those events can then be retrived and used in deciding what to do.
- can be developed incrementally, and creature's behaviors can be enriched "on the fly" while the game's development keeps going
- it's totally customizable by the final customers, allowing them to add, delete, alter the creature's behaviors.
- scales very well on the number of entities in the simulation
//////////////////////////////////////////////////////////////////////////////////////////////
2)Key Ideas:
- ACTION: every entity can be doing only "atomic" action at a given time, and that can be, for example, "EAT", "ATTACK", "MOVE", "SWIM".
- CONSIDERATION: an expression (in my game evaluated via a script language) that results in a value, for example the "MY THREAT" consideration is defined as "myLifePoints / targetLifePoints"
- CRITERIA: define "what is what for each "kind" of entity. For example, a wolf will target a RABBIT as a PREY, while a deer won't.
- BEHAVIOR: a list of possible actions, that can be both "ATOMIC", or be theirself another BEHAVIOR, creating a sort of hierarchy of behaviors. For example the Behavior "HUNT" will be comprised of the following actions:
ATOMIC: KILL PREY (when available)
BEHAVIOR: GOTO INTERESTING LOCATION
BEHAVIOR: SEARCH FOR PRAY
BEHAVIOR: EXPLORE
Every action can have one ore more considerations associated to it, and a response curve is associated with each one. - MEMORY CONCEPT: a sort of "TAG" that the entity assign to some actions that occurs in the world: For example, when someone attacks you you will remember that and add a new association with the "ATTACKER" concept associated to it.
- MEMORY ASSOCIATION: an event that the entity decides to remember, associating some informations to the event:
CONCEPT: "someone attacked"
ACTOR: "mickey the mouse"
TARGET: "Leonardo"
WHERE: "Turin, Italy" - SYNTHESIS RULE: a way that allows the entities to map from atomic actions to memory associations. Example: "when someone ATTACK me, store a new ATTACKER association".
- CRITERIA RULE: a way that allows the entities to define what is what:
For example, the criteria "ENEMY" could be defined this way:
if(PresentAssociation(Attacker)): true;
if(PresentAssociation(HostileByNature)): true;
////////////////////////////////////////////////////////////////////////////////////////////
3)High Level Routine:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | UpdateAI()
{
UpdateMemoryAssociations(); #0
for(every other entity) #1
{
MemSynthesisRule * rule = PickTheRight SynthesisRule based on entity Action;
for(every option of the rule) #2
{
if(ConditionSatisfied)
{
AddOrRefreshMemory(rule->concept, entity); (ATTACKER, HOSTILE BY NATURE, HELPED, ...)
}
}
}
for(every releval criteria to what I'm doing now) (ENEMY, PREY, ...)
{
Build list with all possible targets for that criteria. (Also build an influence map if you need that). #3
}
for(every possible action) #4
{
EvaluateAction Using the action's considerations and the criteria I've filled.
for(every criteria relevant to the action) (PREY, ENEMIES, ALLIES, FOOD...)
{
Mark criteria as "relevant", so that the next time around the AI knows that that criteria needs to be evaluated.
}
if(bestAction is atomic)
{
ExecuteAction();
exit; #5
}
else
{
if(behavior->currentAction != bestAction) #6
{
PopEverythingFollowing(currentStackLevel);
}
PushBehaviorOnStack(bestAction->behavior);
DrilldownIntoBehavior(); #7
}
}
}
COMMENTS:
#0 when new associations are created, the associations with the lowest score are deleted, and the new ones are inserted
#1 of course, you can check only the nearby entities if you have a spacial partition available.
#2 As I said earlier, it's possible that the same entity perceives the same action in a different way depending on various things, for example if you are attacking one of my enemies, then I surely memorize that fact that you helped me, while if you're attacking one of my allies, I'll potentially add the "attacked allies" concept. (That later will result in you flagged as ENEMY, of course :))
#3 influence maps can be used in considerations, again see Dave's talk for references. But I could need to know "the safest place around me", or "the location with the highest concentration of PREYS"
#4 every entity has a behavior stack, and every action of every level of the stack is evaluated every time, this allows the developer to quickly differentiates entities only on certain part of their behaviors (for example, all the wolf will have the same HUNT behavior, but the "nine tails wolf" will have a special HUNT behavior associated to him.
#5 we'll drill down into more and more specialized behaviors until we find out that the best thing to do is an atomic action, at that point we'll do that and exit the stack loop.
#6 when we find out that what we should be doing is NOT what we're doing (we've find out that it's nighttime, and we don't hunting by night, we should go back home), we just pop everything from this point down on the stack, and we push the new one.
#7 see number 5
|
////////////////////////////////////////////////////////////////////////////////////////////
4)Scalability
It's pretty easy to adapt the routine to a certain game's needs, especially as the number of entities to simulate grows:
- the update frequency of the memory update can be decreased
- the distance at which an entity perceive stuff can be decreased to improve performances
- criteria target lists (and relative influence maps) could be cached, and reevaluated only once a seconds or something
- complex considerations can be cached on a per entity basis
/////////////////////////////////////////////////////////////////////////////////////////////
5) Implementation details of the memory system
Main requirement: retriving in costant times a LIST of all the associations relative to something. that something can be a CONCEPT, an IDENTIFIER, a LOCATION
every entity has a certain number of "associations slots" available, and that represents its entire memory.
every association contains both the actual association data (LOCATION, CONCEPT, IDENTIFIERS, ecc) and, for every member of that data, it contains a pointer to the next Association for that data member.
1 2 3 4 5 6 7 8 9 10 11 12 13 | struct MemAssociation
{
concept;
nextAssociationWithSameConcept;
identifier;
nextAssociationWithSameIdentifier;
location;
nextAssociationWithSameLocation;
...
};
|
A set of hash maps will contains the first index of every concept, location, identifier present in all the associations.
So when we want to retrive all "ATTACKER" associations, we hash the "CONCEPT HASH TABLE", and that will tell us the most recent association that contains "ATTACKER" as a concept.
If we instead want to retrive all the associations relative to a position, we hash the "POSITION HASH TABLE" instead of the concept one.
Reference image: https://ibb.co/hYhR0L
Updating the memory means:
-cyclying over every associations, and lowering it's score based on how much time has passed since last update
-computing a list of the associations with the lowest score
-substitute them with the new ones, (if the new ones score it's higher).
Main problem is that every hashmap has to have a number of slots equal to the number of different associations, because for example every associations could potentially be at a different location.
So if an association contains: LOCATION, CONCEPT, IDENTIFIER, and we want an entity to have 1000 associations in its memory, we need:
1000 * sizeof(association) + 1000 * sizeof(LocationHash) + 1000 * sizeof(ConceptHash) + 1000 * (Identifierhash)
Assuming a generic data member is something like 10 bytes (64 bit of data + 16bit for the nextIndex assuming noone can have more that 0xffff associations), and a standard association that contains something like 6 members (concept, location, actorIdentifier, actorType, targetIdentifier, targetType) + some additional data,
80bytes per associations seems something close to reasonable.
Now, if Every hash slot is also 10 bytes (64 bits of data + 16 for the first association Index), to store a single association we need:
80 + 6 * (10) bytes, which is 140 bytes.
You can probably squeeze some bytes here and there, so let's make it 128bytes necessary for every association.
Allocating 4gb for the memory, you get 2^32 / 2^7 = 2^25 associations, assuming your world has 16k entities that needs memory: 2^25 / 2^14 = 2k associations for every entity, which seems like a reasonable amount of memory.
Thank you for taking the time for reading all of this, any feedback/suggestion would be really appreciated. :)
Leonardo
Edited by erpeo93
on
Congratulations on making something like this. As I don't consider myself a good AI programmer, I can't really give feedback on the design itself. The considerations you made in your post do make sense in my opinion, but I don't have enough experience there to ask the "critical questions".
Do you have a demo or code sample to share ?
mrmixer
Do you have a demo or code sample to share ?
Unfortunately at the moment it would be very difficult for me to share something readable and "complete" directly from my codebase, as the system spreads across multiple files, and furthermore the system hasn't been pulled out from the game very much.
But if you have something specific in mind, or some specific question regarding an implementation detail I'd be glad to answer. :)
Regarding the demo, at the moment my current goal is to produce a decent internal build for my team to use, so I don't have time to focus on defining and testing complex behavior, all the creatures at the moment only have very simple behaviors, so you wouldn't really see anything special if I'd post something at the current stage.
But surely I'll update the thread as soon as there's something cool happening in the world :)
In the meanwhile, as I said, please feel free to ask about any implementation/design detail.
Leonardo
Edited by erpeo93
on
Presenting an idea like that in text without a demo or sample is not good in my opinion. It abstract and "hard" to figure out without spending time on it. Since you don't have "proof" that it's working and doing something interesting (you said you haven't tested complex behavior), I don't want to spent time on it.
It's cool that you shared your work, it would be cooler to see it in action. I'll check it out again when you give us an update. Good luck.
It's cool that you shared your work, it would be cooler to see it in action. I'll check it out again when you give us an update. Good luck.
mrmixer
Presenting an idea like that in text without a demo or sample is not good in my opinion. It abstract and "hard" to figure out without spending time on it. Since you don't have "proof" that it's working and doing something interesting (you said you haven't tested complex behavior), I don't want to spent time on it.
It's cool that you shared your work, it would be cooler to see it in action. I'll check it out again when you give us an update. Good luck.
Well, for now the purpouse of the thread was just giving you some ideas to implement on your own game, not a complete production ready solution.
I agree with the fact that a couple of "demostrations" would be really cool, but you'll understand the fact that those are costly, especially considering that I've a very limited amount of time, and a dayjob alongside game development.
But I'll upgrade the thread as we go, don't worry :)
Leonardo
If you want to give back to the community but you dont want to make a simple demo of something YOU created.
To be fair thats how people look at these things.
I think your intention is to just post some idea or concept or a write up on some AI system which is fine and may prove useful to someone.
To be fair thats how people look at these things.
I think your intention is to just post some idea or concept or a write up on some AI system which is fine and may prove useful to someone.
Also AI is one of the most complex topics in computer science.
So no-one is going to trust a guy who claims to have ivory-towered a silver-bullet AI system but hasn't created a bunch of examples and proof of concepts that doesn't breakdown into dumb behavior once it hits edge cases.
So no-one is going to trust a guy who claims to have ivory-towered a silver-bullet AI system but hasn't created a bunch of examples and proof of concepts that doesn't breakdown into dumb behavior once it hits edge cases.
ratchetfreak
Also AI is one of the most complex topics in computer science.
So no-one is going to trust a guy who claims to have ivory-towered a silver-bullet AI system but hasn't created a bunch of examples and proof of concepts that doesn't breakdown into dumb behavior once it hits edge cases.
No-one asked to trust me, and no-one claims that my system is silver-bullet or ivory-towered.
This is the architectural design I have in my game, and it's currently working for simple test cases. End of the story.
If you want and if you're able to critique the design, I'd be very happy to hear from you and to discuss with you which corner case could break it, and how to work around them.
It's pretty obvious that a cool showcase of the system working will be awesome, but it's also pretty obvious that it costs a lot of time.
I just want to share my architecture in the hope that it could be of help to someone, I don't want to convince anyone about anything.
Edited by erpeo93
on
While having a video or a working demo would be great, it's totally fine not to provide something like that. Otherwise nobody would talk about anything they are working on or share ideas and concepts. To me that would be worse.