🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Need few ideas on boring NPC AI
Author
This is about the conventional boring NPC AI. Like old console game NPC, such as Final Fantasy on Snes and Nes. For those who don''t know it, the 2D NPC sprites just walk "randomly" in towns in those games. They are the stereotypical old 2D tile based game (NOT isometric, but the same principle applies).
While they are very simple, I never quite worked out how their AI works. They just wonder around in the town but don''t seem to get "stuck". Like when there''s a side path next to house wall... if NPC gets into the path and "randomly" picks its path, it''s possible for the NPC to go too deep in. And if the path is 1 cell thick, then the NPC will be stuck for a long time till it "conveniently" picks its way out by chance. Also there''s a finite chance that yet ANOTHER NPC wonder into the same path, blocking each other''s way... It would be annoying if that path lead to a Weapon shop or something. Now you can''t go down the path because the two NPCs are wonderfully confused far down the path in front of the weapon shop door.
And none of that rubbish happens... is it purely by chance? There must be some simple logic behind it to prevent that sort of thing from happening.
I believe they have some sort of "bounding" areas, from where they can''t get out. So an NPC won''t stray far from it''s initial location. Or, perhaps there''s a percentage system, where the chance of walking in the opposite direction increases as the NPC walks off from its original spot. So the chance of walking North, South, West and East changes as the NPC displaces himself from his home spot.
I don''t know any of that for sure though. Nor have I practiced the use of simple NPCs in such RPGs. Does anyone have an idea, or have actually tried one? And what do you think, or what method did you use to prevent that?
You listed some good ideas. I have used a system similar to the bounding areas technique you listed. One other thing you could try is allowing the player to ''push'' the NPCs out of the way. Perhaps if the player walks into them, they will automatically take a step in the other direction. In this way, the player can move an NPC out of the way. Of course, there would have to be some sort of more open area at the end of every 1 tile wide path so that the NPC could get out of the way at the end of the shoving.
I think that "ancient" ^_- japanese CRPG''s doesn''t use any mechanism for avoiding "being stuck". I.E., in one walkthrough of "Tales of Phantasia", the autor describes one NPC getting "stuck" in a very important area of the game. But it''s difficult to see a NPC "stuck" in one area. Why?. First: See the maps. They avoid the problem creating 2-tiles paths. There''s no 1-tile path. Second: The chance of being "stuck" is very little.
But, if there''s one NPC "stuck". How to solve this?
There''s some methods for avoiding this problem (i''m using or i''m going to use them in my own game):
1) If there''s a tile with an "egg" (event-flag), a NPC will not step into it [Only if the behavior of the NPC is "random-movement"]
2) If i''m stuck, send a message (active a flag) to the NPC that is blocking me. That NPC will see the problem, and will move in the direction the flag tells him. And how much steps will that NPC walk?:
2.a) steps: more than 1, for avoiding "ping-pong" (one step up, one step down, one...)
2.b) only one step, but the "stuck" NPC will move also in that direction until having more than 2 exits: That "stuck" NPC will be "pushing" the other until an alternative exit comes!
One more thing: In old 2D games, NPC also had a little "script" for moving to certain areas (think in cinematic scenes). If you want to disscuss them here, do it, ''cause i know a lot about this term.
But, if there''s one NPC "stuck". How to solve this?
There''s some methods for avoiding this problem (i''m using or i''m going to use them in my own game):
1) If there''s a tile with an "egg" (event-flag), a NPC will not step into it [Only if the behavior of the NPC is "random-movement"]
2) If i''m stuck, send a message (active a flag) to the NPC that is blocking me. That NPC will see the problem, and will move in the direction the flag tells him. And how much steps will that NPC walk?:
2.a) steps: more than 1, for avoiding "ping-pong" (one step up, one step down, one...)
2.b) only one step, but the "stuck" NPC will move also in that direction until having more than 2 exits: That "stuck" NPC will be "pushing" the other until an alternative exit comes!
One more thing: In old 2D games, NPC also had a little "script" for moving to certain areas (think in cinematic scenes). If you want to disscuss them here, do it, ''cause i know a lot about this term.
Author
Thanks to both of you for reply.
jaxson: Yes, "shoving" idea is probably the simplest. That was used even from FF1, I think.
I''ve had probs with NPCs in general. Somewhat irrelevent to AI, but relevent in parts - Of course, it depends on the number of NPCs in one Zone, but say if you have 30 NPCs in one Zone, then the simplest checking routine would involve a loop (for or while or whatever) of 30. If 100 NPCs, then the loop quickly grows to 100. If two NPCs interact, one of the NPCs would then once again run the loop of 100 for certain conditions or parameters... if you do that for every NPC (and if you have 30 NPC) then the number of loop cycles would be 30x30 = 900. If 100 NPCs, then 100x100=10000. And thats not it... trying to achieve a little better AI could involve a fast growing number of cycles. Like as rrc2soft says, as NPCs try to move away etc, they could interact with other NPCs on the way, who in term get shoved... and so on. The way I do it, whether or not NPC is visible on the screen doesn''t matter. NPCs are active outside the visible screen. So if they bump into each other or an Obstruction cell, they naturally react to it even if players are far away from them to see them. Is this a bad, unrealistic model? I think those classic Snes games did it too, so there must be some way to avoid the loops, perhaps. So simple, yet potentially a game killer (because it slows the field engine). This is my design problem involving NPC AI (simple and stupid though they may be).
rrc2soft: Yes, please fire away with that script idea. I want to know how scripting (simple or otherwise) is done in those "crappy" 8 and 16 bit machines
Overall, to reply to you both, my main problem is Efficiency. The idea is there. And the theory. But implementing it is another issue all together. I think you know what I mean.
jaxson: Yes, "shoving" idea is probably the simplest. That was used even from FF1, I think.
I''ve had probs with NPCs in general. Somewhat irrelevent to AI, but relevent in parts - Of course, it depends on the number of NPCs in one Zone, but say if you have 30 NPCs in one Zone, then the simplest checking routine would involve a loop (for or while or whatever) of 30. If 100 NPCs, then the loop quickly grows to 100. If two NPCs interact, one of the NPCs would then once again run the loop of 100 for certain conditions or parameters... if you do that for every NPC (and if you have 30 NPC) then the number of loop cycles would be 30x30 = 900. If 100 NPCs, then 100x100=10000. And thats not it... trying to achieve a little better AI could involve a fast growing number of cycles. Like as rrc2soft says, as NPCs try to move away etc, they could interact with other NPCs on the way, who in term get shoved... and so on. The way I do it, whether or not NPC is visible on the screen doesn''t matter. NPCs are active outside the visible screen. So if they bump into each other or an Obstruction cell, they naturally react to it even if players are far away from them to see them. Is this a bad, unrealistic model? I think those classic Snes games did it too, so there must be some way to avoid the loops, perhaps. So simple, yet potentially a game killer (because it slows the field engine). This is my design problem involving NPC AI (simple and stupid though they may be).
rrc2soft: Yes, please fire away with that script idea. I want to know how scripting (simple or otherwise) is done in those "crappy" 8 and 16 bit machines
Overall, to reply to you both, my main problem is Efficiency. The idea is there. And the theory. But implementing it is another issue all together. I think you know what I mean.
PugPenguin: the solution to the rapidly growing interactions loops is surely to fix interactions to a bounded subset of the local environment, and make other NPCs part of this sensor model. Thus the NPCs are influenced by local event data with an upper bound on its size, hopefully giving you a linear time algorithm.
Additionaly, couldn''t you just pick n NPCs randomly to update each timestep instead of always updating all of them, giving a fixed-time algorithm (this selection could also be biased to favour NPCs near players). The problem of very long update times (i.e. being unlucky and repeatedly not being selected) could be lessened by selecting without replacement, such that NPCs were updated at least every 1000/n timesteps (and usually more often).
Additionaly, couldn''t you just pick n NPCs randomly to update each timestep instead of always updating all of them, giving a fixed-time algorithm (this selection could also be biased to favour NPCs near players). The problem of very long update times (i.e. being unlucky and repeatedly not being selected) could be lessened by selecting without replacement, such that NPCs were updated at least every 1000/n timesteps (and usually more often).
To agree with Adamru, the best approach is to update NPCs closest to the player. I am supposing that there''s more than one state variable to be updated:
NPCs closest to the player get frequent updates while other NPCs get updates at a "sliding ramp" rate, meaning updates at regular intervals involving major state variable changes (position changed by a block, or quarter mile as opposed to a few feet). I would suggest a determination of the maximum number of NPCs that may be in the immediate vicinity of the player - this being the number of highly dynamic updates - and the creation of a tabular database to "throw in" the attributes of all others, allowing for rapid updates without structure dereferencing overhead.
NPCs closest to the player get frequent updates while other NPCs get updates at a "sliding ramp" rate, meaning updates at regular intervals involving major state variable changes (position changed by a block, or quarter mile as opposed to a few feet). I would suggest a determination of the maximum number of NPCs that may be in the immediate vicinity of the player - this being the number of highly dynamic updates - and the creation of a tabular database to "throw in" the attributes of all others, allowing for rapid updates without structure dereferencing overhead.
Hi all!
As Adamru & Anonymous ^_- said, a good solution for avoiding "time-eater NPCs" is using a local enviroment mode. You only check & manage near NPC''s; and for far NPCs, they''re only managed at a "sliding ramp" rate.
But i''ve a little thing to say: PugPenguin, if one NPC interacts with another, there''s no need to manage its interaction in the same cycle. Think of NPCs like proccess: One sends a signal to another, but this signal is not managed inmediately: the signal is managed in the next cycle.
So for the "move away" problem, this could be the trace:
1) NPC1 Bloqued by NPC2. NPC1 see there''s no exit!!!. Signal signal_ey!_move_away NPC2.
2.a) NPC2 is managed after NPC1: Catch the signal, select a "shoved" behavior.
2.b) NPC2 is managed before NPC1: In next cycle catch the signal, stop actual behaviour (signal_ey!_move_away has more priority than actual behavior) and select a "shoved" behavior.
There''s no need to manage all NPC-NPC interactions in one cycle!. Only wait till next cycle.
And a little trick: If you have a problem and the player go to menu... well, it''s time to fix all problems ^_-! (only for NPC far from Main player''s position)
*** And as i said before, i''m going to talk about player scripts: ***
In console-type CRPG''s, NPCs has "no" AI. When i say "no" AI i say they are only moving randomly. They''ll avoid stuck problems, but nothing more. No Ultima or Baldur''s Gate behaviors.
So here''s my idea: NPCs has three main states:
- Walking randomly (more or fewer steps until direction changes)
- Stopped
- Scripting (<- what i''m going to talk now)
When an NPC has a script?: Cinematic scenes. I.E., in "Tales of Phantasia", Both main characters (Male & Female, i didn''t remember the names now [Cless is one? ^_-]) are talking to an NPC about magic. They (& the other NPC''s) move in that screen, talk about magic and make some magic stuff.
What type of things they do?:
1) Movements. NESW.
2) Look without walking
3) Make gestures (Cry, Smile, ...)
4) Wait some cycles
5) ... they do anything more? ^_-
So, in the most cases, NPCs (and also PCs) will have no script. They will be walking or being stopped. But when a behavior is assigned, how things work?
Behaviors are simple: So script-containers are too. Think of them like a pointer to an Array. Easy&Fast to access. And how a NPC behavior is stored?. Opcodes: N-X: Make X steps to North. G-X-Y: Gesture X during Y cycles. And so on...
So: In one cycle, an NPC look its behavior: Take arguments, and init some variables. In next cycle, start his behavior, and maintain it (one cycle, another, another...) until behavior ends. And look again to its behavior...
And what happens if there''s no more behavior?. Loops, or (i''ll explain this now) send a signal to a management routine (signal_ended_behavior)
There''s one more thing about scripting: what happens if you want two (or more) NPC''s to move AT THE SAME TIME and when THEY (BOTH) END, they make some things?.I.E.: Two guards approach you, and when the two are in front of you, the take their swords and yells you:
...
#Program(_Guard_One,"S3@"); // 3 steps south, signal_ended_behavior
#Program(_Guard_Two,"S2W2@"); // 2 steps south, then 2 steps west, signal_ended_behavior
#Manage(signal_ended_behavior,2); // 2 NPC''s will send this signal
#Wait_Till(signal_ended_behavior); // wait until they both ends their behavior
#Program(_Guard_One,"G0330"); // Gesture 3, 30 cycles
#Program(_Guard_Two,"G0330"); // Gesture 3, 30 cycles
#Sound(_Ey_You!);
...
You must implement a mechanism for waiting 2 or more NPC''s behavior. Here''s what i use (and what i think most CRPG''s use): Signals & Wait-Signals.
When an usecode script is being executed, there''s some internal variables. One of them is ENDED_BEHAVIOR. When (Active,0), the usecode is continued. If (Active,Not 0), usecode is stopped. So when we want to wait NPCs behavior, Active this flag, set it to the number of NPCs that are executing their script, and wait the flag to be 0.
...
// ENDED_BEHAVIOR = (Inactive, Unknown)
#Manage(signal_ended_behavior,2); ENDED_BEHAVIOR = (Active, 2);
#Wait_Till(signal_ended_behavior); // wait until ENDED_BEHAVIOR[2] = 0
// ENDED_BEHAVIOR = (Inactive, Unknown)
...
Well, these are the methods i''ve found (and use) for scripting NPCs. Comment it, Trace it, Criticize it, Mash it ^_- ...
As Adamru & Anonymous ^_- said, a good solution for avoiding "time-eater NPCs" is using a local enviroment mode. You only check & manage near NPC''s; and for far NPCs, they''re only managed at a "sliding ramp" rate.
But i''ve a little thing to say: PugPenguin, if one NPC interacts with another, there''s no need to manage its interaction in the same cycle. Think of NPCs like proccess: One sends a signal to another, but this signal is not managed inmediately: the signal is managed in the next cycle.
So for the "move away" problem, this could be the trace:
1) NPC1 Bloqued by NPC2. NPC1 see there''s no exit!!!. Signal signal_ey!_move_away NPC2.
2.a) NPC2 is managed after NPC1: Catch the signal, select a "shoved" behavior.
2.b) NPC2 is managed before NPC1: In next cycle catch the signal, stop actual behaviour (signal_ey!_move_away has more priority than actual behavior) and select a "shoved" behavior.
There''s no need to manage all NPC-NPC interactions in one cycle!. Only wait till next cycle.
And a little trick: If you have a problem and the player go to menu... well, it''s time to fix all problems ^_-! (only for NPC far from Main player''s position)
*** And as i said before, i''m going to talk about player scripts: ***
In console-type CRPG''s, NPCs has "no" AI. When i say "no" AI i say they are only moving randomly. They''ll avoid stuck problems, but nothing more. No Ultima or Baldur''s Gate behaviors.
So here''s my idea: NPCs has three main states:
- Walking randomly (more or fewer steps until direction changes)
- Stopped
- Scripting (<- what i''m going to talk now)
When an NPC has a script?: Cinematic scenes. I.E., in "Tales of Phantasia", Both main characters (Male & Female, i didn''t remember the names now [Cless is one? ^_-]) are talking to an NPC about magic. They (& the other NPC''s) move in that screen, talk about magic and make some magic stuff.
What type of things they do?:
1) Movements. NESW.
2) Look without walking
3) Make gestures (Cry, Smile, ...)
4) Wait some cycles
5) ... they do anything more? ^_-
So, in the most cases, NPCs (and also PCs) will have no script. They will be walking or being stopped. But when a behavior is assigned, how things work?
Behaviors are simple: So script-containers are too. Think of them like a pointer to an Array. Easy&Fast to access. And how a NPC behavior is stored?. Opcodes: N-X: Make X steps to North. G-X-Y: Gesture X during Y cycles. And so on...
So: In one cycle, an NPC look its behavior: Take arguments, and init some variables. In next cycle, start his behavior, and maintain it (one cycle, another, another...) until behavior ends. And look again to its behavior...
And what happens if there''s no more behavior?. Loops, or (i''ll explain this now) send a signal to a management routine (signal_ended_behavior)
There''s one more thing about scripting: what happens if you want two (or more) NPC''s to move AT THE SAME TIME and when THEY (BOTH) END, they make some things?.I.E.: Two guards approach you, and when the two are in front of you, the take their swords and yells you:
...
#Program(_Guard_One,"S3@"); // 3 steps south, signal_ended_behavior
#Program(_Guard_Two,"S2W2@"); // 2 steps south, then 2 steps west, signal_ended_behavior
#Manage(signal_ended_behavior,2); // 2 NPC''s will send this signal
#Wait_Till(signal_ended_behavior); // wait until they both ends their behavior
#Program(_Guard_One,"G0330"); // Gesture 3, 30 cycles
#Program(_Guard_Two,"G0330"); // Gesture 3, 30 cycles
#Sound(_Ey_You!);
...
You must implement a mechanism for waiting 2 or more NPC''s behavior. Here''s what i use (and what i think most CRPG''s use): Signals & Wait-Signals.
When an usecode script is being executed, there''s some internal variables. One of them is ENDED_BEHAVIOR. When (Active,0), the usecode is continued. If (Active,Not 0), usecode is stopped. So when we want to wait NPCs behavior, Active this flag, set it to the number of NPCs that are executing their script, and wait the flag to be 0.
...
// ENDED_BEHAVIOR = (Inactive, Unknown)
#Manage(signal_ended_behavior,2); ENDED_BEHAVIOR = (Active, 2);
#Wait_Till(signal_ended_behavior); // wait until ENDED_BEHAVIOR[2] = 0
// ENDED_BEHAVIOR = (Inactive, Unknown)
...
Well, these are the methods i''ve found (and use) for scripting NPCs. Comment it, Trace it, Criticize it, Mash it ^_- ...
Author
Thank you for input on growing loop problem. Particularly that idea on updating far-off NPCs in more "global" scale will be practically easy and effective, I''m sure. As for adamru''s update method at varying timesteps, that''d help as well, if I''m thinking this correctly. That''s done by using a member variable within NPC structure to count timesteps, right? And stay idle for N number of timesteps. I think I know what you mean.
rrc2soft: Thanks for that bit of script, I see what you mean now. I sort of expected the implementation of script engine as well though, if I may be greedy Any addition would help anyway, if you have time to elaborate on the actual mechanics of the script engine. If not, no biggie. I sort of have an idea of that myself, though I''ve never written a script engine for 2D RPG NPC I like hearing other people''s methods and ideas though, often I come across some real smart moves.
Quote:
Am I right in thinking that
ENDED_BEHAVIOR = (Active, 2);
is put INSIDE the script engine, no? That seems to make more sense. You use #Manage(signal_ended_behavior,2) to tell the engine to wait till 2 signal_ended_behaviors are sent to it, right? The engine then sets ENDED_BEHAVIOR flag appropriately, as part of the internal operation.
Am I thinking this correctly?
rrc2soft: Thanks for that bit of script, I see what you mean now. I sort of expected the implementation of script engine as well though, if I may be greedy
Any addition would help anyway, if you have time to elaborate on the actual mechanics of the script engine. If not, no biggie. I sort of have an idea of that myself, though I''ve never written a script engine for 2D RPG NPC I like hearing other people''s methods and ideas though, often I come across some real smart moves.Quote:
// ENDED_BEHAVIOR = (Inactive, Unknown)#Manage(signal_ended_behavior,2); ENDED_BEHAVIOR = (Active, 2);#Wait_Till(signal_ended_behavior); // wait until ENDED_BEHAVIOR[2] = 0// ENDED_BEHAVIOR = (Inactive, Unknown)Am I right in thinking that
ENDED_BEHAVIOR = (Active, 2);
is put INSIDE the script engine, no? That seems to make more sense. You use #Manage(signal_ended_behavior,2) to tell the engine to wait till 2 signal_ended_behaviors are sent to it, right? The engine then sets ENDED_BEHAVIOR flag appropriately, as part of the internal operation.
Am I thinking this correctly?
PugPenguin: Almost all that i'm talking about is implemented (In Pascal with FPK compiler & with spanish sources V_V). Check in my homepage: Downloads section -> "SW: Portal" (Source code .zip) -> U*PNJ.PP in /FUENTES/CAMPO. My homepage is in profiles section.
Also, This's the right code (I put it wrong ^_-):
<...>
// ENDED_BEHAVIOR = (Inactive, Unknown)
#Manage(signal_ended_behavior,2); // ENDED_BEHAVIOR = (Active, 2);
#Wait_Till(signal_ended_behavior); // wait until ENDED_BEHAVIOR = 0
// ENDED_BEHAVIOR = (Inactive, Unknown)
<...>
"ENDED_BEHAVIOR = (Active, 2)" was a comment, 'cause this task is done by "#Manage(signal_ended_behavior,2)" (#Manage actives the flag and set its value to 2).
The "Wait...Until" part is done by "Wait_Till(signal_ended_behavior)"
Sorry for any inconvenience.
NOTE: In my code, i don't use one flag ENDED_BEHAVIOR -> I use an Array of flags.
Edited by - rrc2soft on May 11, 2001 2:57:09 AM
Also, This's the right code (I put it wrong ^_-):
<...>
// ENDED_BEHAVIOR = (Inactive, Unknown)
#Manage(signal_ended_behavior,2); // ENDED_BEHAVIOR = (Active, 2);
#Wait_Till(signal_ended_behavior); // wait until ENDED_BEHAVIOR = 0
// ENDED_BEHAVIOR = (Inactive, Unknown)
<...>
"ENDED_BEHAVIOR = (Active, 2)" was a comment, 'cause this task is done by "#Manage(signal_ended_behavior,2)" (#Manage actives the flag and set its value to 2).
The "Wait...Until" part is done by "Wait_Till(signal_ended_behavior)"
Sorry for any inconvenience.
NOTE: In my code, i don't use one flag ENDED_BEHAVIOR -> I use an Array of flags.
Edited by - rrc2soft on May 11, 2001 2:57:09 AM
Author
Thank you, that''s been a great reference. I''m spending a lot of time planning this time (I''ve had many dodgy projects due to lack of planning lol), and this is an area I haven''t spent much time so far... so, thanks for guiding me around.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
