NPC Scripting

Game Mechanics Artificial Intelligence
#1

Hi,

at the moment I am thinking about how I would breath live into my game objects. I am at an early stage of my project
but try to take these issues into account as early as possible.

I chose Java as a development language primarily because of the great benefits I hope the language holds in account
for content creation/level scripting. I plan to achieve that by loading classes at runtime.

Lately i ran into a problem, while thinking about AI scripting. I want to do NPC animation and interaction as well as
the GUI cutscenes etc. with the scripting.

I found that, what I really would like is to assign scripts to objects and let them do their work concurrently.

roughly something like this:

headTo(treasureChest);
walkTo(treasureChest);
bendDown();
say("I have no key - I can't open it");
standUp();
headTo(Door);
walkTo(Door);

Well this is really simple, an actual implementation would look different - but I have never done that before - so
excuse my lacking experience =)

What I realized is:

  • the execution is delayed, after the invocation of headTo an animation is started which will take some time. The
    script should be freezed till then. After the animation has finished, the game engine or player object will execute
    the next statement of the script.

The only way I can think of to do this in java is: threads.
Would it be a good idea to have lets say 1000 threads running ? Is there a way to have 1000 JavaVM threads, if
there is such a thing ? Threads on operating system level may be too costly.

Then the second thing is: How do the freezing ? Something like “stepping the vm”.

I am not sure if this is a showstopper and I would have to implement my own scripting system cough

I know that I could do the animation with a Finite State Machine, but I would prefer to use them not, because
they are not comfortable. The most pleasing would be to program each object with concurrently running scripts.

I apologize for the long post,
I would really appreciate if someone could give me some input on this,
thank’s
Frederick

#2

My recommendation is to put all the npc scripts in one thread. Have a loop that loops over all the npcs and calls a method to execute their script. You can’t afford to create 1000 threads. Using thousands of threads is a task for web servers, not a task for games.

Having only 1 extra thread has the benefits of getting the scripting off of the main thread, while avoiding the overhead of creating a thread for each npc.

You can also set it up so that idle npcs are skipped or something. Perhaps you could prioritize the npcs by how important their tasks are and then only execute the scripts for as many npcs as you have time for. This sort of thing would only be necessary if you started having performance problems.

Each npc can have a flag “isDoneWithCurrentTask”. You can set this flag to false at the start of the task and then to true at the end of the task. Then you can only go to the next step in the script when the flag is set to false.

#3

It’s a pretty broad topic. Well, I would execute the NPC stuff on the main thread. The first thing to figure out is how to minimize the load. Usually the NPC interaction is rarely on a global scope. Most of em are bound to their area and very few of em will travel around the world. And if it’s the other way around you don’t need to keep track of em accurately (no one will be able to tell the difference after all). So, even if there are thousands you only need to execute the scripts of a few.

The other thing are tasks. The NPC grabs a task of its list and executes it. Once the goal is reached it grabs the next one. So, an NPC’s tick() would be something like:

public void tick(){
	if(task.isFinished())
		task=nextTask();
	task.tick(this);
}
#4

[quote]You can’t afford to create 1000 threads
[/quote]
Yes I see, I had a thinking error there, I thought that Java being a VM is similar to a scripting language VM, which can happily process on several scripts in one system thread. But Java is a jitted VM and that makes the case different so every JVM thread will require a system thread also, because when invoking jitted code the JVM looses control and can´t interrupt the execution - this can only done by the processor itself, so it has to use real OS-Threads. So I suppose those “virtual” JavaVM Threads, I thought of, do not exist.
So using Java threads is not a solution.

[quote]The NPC grabs a task of its list and executes it.
[/quote]
That sounds like the first step into the implementation of an own virtual machine.
The problem is that a list of tasks may not suffice - one would like loops, branches and tasks build up from smaller tasks.

This could all be done with this approach - like

Task runningHeadLessAround = new TaskSequence();
runningHeadLessAround.add(new RunningTask(Direction.FORWARD, 10));
runningHeadLessAround.add(new ShoutingTask("Help!!! I have been robbed!"));
runningHeadLessAround.add(new RunningTask(Direction.BACKWARD,10));


Task NPCBehaviour = BranchTask(new LoopTask(runningHeadLessAround), new TalkTask("Ah my hero please safe me", new HeroIsNearCondition());

Phew… I would LOVE my own custom language at this point… even this example is exhausting :slight_smile:

At the moment I am tending towards the development of a custom language… maybe one without compiler - assembler only first :slight_smile:

#5

Only ‘roll your own’, when you got a lot of time on your hands, and like the challenge.

Use janino. Create some utilitiy-methods that create the java-sourcecode, from your ‘own language’, and directly compile it to bytecode.

#6

[quote]Use janino. Create some utilitiy-methods that create the java-sourcecode, from your ‘own language’, and directly compile it to bytecode.
[/quote]
The problem with that is - I need the “slow-motion” execution. The VM does only execute the next command, when the action described by the previous one is completed - that may be several seconds. So I need to control the execution which is not possible to do with the JavaVM, which is the reason why I would have to come up with my own.

Maybe something not too complicated… just branches loops and commands - no highlevel features like expressions blocks etc.

#7

Hi, you can use Javaflow which implements continuations in Java.

#8

Even if you include the npc tasks on the main thread, you will probably want to move their pathfinding to a separate thread. In the only RPG I’ve made that was more or less complete, there was one spot where several NPCs moving towards a semi-distant goal at the same time slowed down the game for a short time.

Regardless of how the scripting is implemented, you can use the flag I mentioned in my previous post to prevent the next command from being executed too soon. The only caveat is that the flag must always be accessed from the same thread.

#9

[quote]Hi, you can use Javaflow which implements continuations in Java.
[/quote]
Thanks that might be useful =) But I´d rather prefer not to include 3rd party code I haven´t written myself,
that´s what holding me back from Javaflow.

Hi fletchergames,

I think I didn´t get the idea with the flag quite right:


class Lissy extends NPC {
public heartbeat(Time elapsedTime) {
if(!action1.finished()) {
action1.heartbeat(elapsedTime);
return;
}

if(!action2.finished()) {
action2.heartbeat(elapsedTime);
return;
}
}

That´s not what you described !? Basically the method is called every timestep and already executed commands would be skipped. This would
become ugly when loops are involved -I woudn´t like that too much…

#10

That is vaguely like what I meant, but implemented so incredibly wrong that it wouldn’t work at all.

Let’s say hypothetically that you parsed your script into tokens called “Actions”. Each action is one command like “headTo(treasureChest);”. In the case of loops, the entire loop would probably be one action that takes a long time.
The loop could keep track of its own current action within the loop.

class Lissy extends NPC {
Action currentAction;
boolean isCurrentActionComplete;

public heartbeat(Time elapsedTime) {
   if(isCurrentActionComplete) {
      currentAction = currentAction.getNextAction();
      currentAction.startExecution();
   }

   /*you might include an else here if you don't want startExecution and continueExecution to be called in the same heartbeat*/
   isCurrentActionComplete  = currentAction.continueExecution();
}
}

An alternate version for if you don’t use a startExecution method (maybe the Action class takes care of this itself) would be:

class Lissy extends NPC {
Action currentAction;

public heartbeat(Time elapsedTime) {
   boolean isCurrentActionComplete  = currentAction.continueExecution();
   if(isCurrentActionComplete)
      currentAction = currentAction.getNextAction();
}
}

Either way, my idea is basically the same.

The continueExecution method does something like take a single step for the task “walkTo(treasureChest);”. The startExecution method would set up the task somehow. For “walkTo(treasureChest);”, I would probably make that turn the character to face the treasure chest, rather than having “headTo(treasureChest);”. Maybe it would start the pathfinding or something.

Note the existence of the getNextAction method. For most lines of the script, this would just go to the next line of the script. Conditionals would return a different Action depending upon whether the conditional was true or false. There might also be some kind of “change state” action.

If the Actions are stored in an array or something, the getNextAction might be partly in the NPC class.

In your original script:

headTo(treasureChest);
walkTo(treasureChest);
bendDown();
say("I have no key - I can't open it");
standUp();
headTo(Door);
walkTo(Door);

It would work as follows (assuming each action other than walkTo only takes 1 heartbeat).

Heartbeat 1: headTo(treasureChest); [Face treasure chest.]
Heartbeat 2: Change to next action. walkTo(treasureChest); [Take 1 step.]
Heartbeat 3: [Take 1 step.]
Heartbeat 4: [Take 1 step.]
Heartbeat 5: [Take 1 step.]
Heartbeat 6: (Lissy is at the treasure chest.) Change to next action. bendDown(); [bend down]
Heartbeat 7: Change to next action. say(“I have no key - I can’t open it”); [talk]

And so on.

Loops would probably be done with a Loop class that would be similar to the NPC class.

#11

First, what is “NPC” ? I’ve found no mention of this short name…
hopefully I’d bet all the problem is what and when you want to execute a specific action without overlapping the Processes each other. This is a.k.a sequential logic algorithms and NOT continuation. that is apprx. the AI of a simple game logic.
If you’ve read up above the Javaflow desc. it talks about a “continuation” object that would stand for an applicative STATE and not LOGIC.
Hence, regarding your issue it is obvious that 5 STATES functions fight each other to handle a character AI. To implement that into an usual applicative logic, define a what you’d call a “continuation” Object that can identify 5 DIFFERENT STATES.
handling those 5 STATES into a map would look like :


HEADTO -----location-----> WALK ---- no treasure ---> HEADTO-...
     ^                                                       l                                                           ^
      l                                                   treasure                                                  l
      l                                                       v                                                           l
      l                                             LOOK DOWN and find the key ------ no key 
      l                                                       l
      l                                                    key is in the inventory
      l                                                       v
      ^------- known location ---SAY("Well, what can I do with this treasure map ?")
                                                                l
                                                                 ------- unknown  location ---------> WALK -....

And so on with new STATES you can define an acceptable AI algorithm. However, defining more than 3-5 diefferent STATES can issue in an unresolvable map… Wouldn’t you try with less states and find the treasure, would you ? :wink:

#12

First, what is “NPC” ?

NPC=non-player character

#13

[quote]That is vaguely like what I meant, but implemented so incredibly wrong that it wouldn’t work at all.
[/quote]
:-X :o :-X Incredible wrong … ouch

But I have something to say for my apology :wink:

I tried to understand in a way, that Java itself could be used to script the actions, but that is not possible, that´s
what I have understood by now.

[quote]Let’s say hypothetically that you parsed your script into tokens called “Actions”. Each action is one command like “headTo(treasureChest);”. In the case of loops, the entire loop would probably be one action that takes a long time.
[/quote]
In my ears that sounds like a step into the direction of an own custom scripting language. The “Actions” could be understood like bytecode instructions. I wanted to avoid to use another scripting language beside java, because I thought that java is a great scripting language by itself. Your answers have shown that this is not possible and some kind of a custom script language should be the way to go. I also assured myself that perfomance in this case is really not a problem, because actions of this custom language are evaluated which such a low frequency that it won´t matter. The only issue is that I have an additional language in my project then, and I will have to decide where to use this language and where to use java. Java only would really be more like KISS :wink:

Thank´s a lot fletchergames, i think i got it now due to your very understandable explanation.

[quote]I’d bet all the problem is what and when you want to execute a specific action without overlapping the Processes each other
[/quote]
My initial question was how scripting code could be assigned and applied to non-player-characters and cutscenes etc. and if it could be
done with the java language, or if the use separate scripting language is necessary.
I plan to execute the scripts single threaded, so there should be no problem. But you have a definite point there, if NPC´s were running
in different hardware threads bad things could happen because they all share the same world and may simultaneous remove the same object from
the world or the like.

[quote]Hence, regarding your issue it is obvious that 5 STATES functions fight each other to handle a character AI.
[/quote]
Hi, i am not sure what you mean by state function, I know the term “state transition function” but I suppose you mean something different.

[quote]nd so on with new STATES you can define an acceptable AI algorithm. However, defining more than 3-5 diefferent STATES can issue in an unresolvable map…
[/quote]
I am not sure what you are saying there, but you seem to have some kind of AI algorithm in mind, which is more complicated than what I want to do, for the beginning I will be very happy when I am able to realize simple scripted scenes.

I want to say thank you for all the answers - this is really a friendly and helpful forum !

#14

It sounds like you understand what I was saying now.

If you really want to avoid writing your own scripting language, you can just define an Action array (or whatever data structure you want to store the Actions in) within your code. I advise against this though. I used to do something vaguely like that, but I purchased a book about writing compilers and interpreters and found parsing to be easy enough to make it worthwhile having a simple scripting language.

Even so, I have yet to write a full-featured scripting language. I’ve been working on other things since my last RPG, in which I used Beanshell. My experiences with Beanshell are why I wanted my own custom scripting language in the first place. Beanshell works, but it would be much less verbose to have a custom scripting language (at least the way I was using Beanshell).

Some people have posted about continuations. I imagine they would work fine, but it would be basically like using C function pointers in a more typesafe manner. I believe that would be overkill for what you’re doing, but there must be some cases where it would be beneficial. I don’t understand continuations too well, so I may not be 100% right about this. But I think they’re way too complicated.

#15

I never really did it, but I once had the same thoughts about how to control the actions of game objects like npcs or such.

I would basically add all orders into a list, and the object will do the current task until it is finished, then it removes the task and continues with the next one.

Operations on the list would be:

  • Add a task to the end
  • Add a task to the beginning, so that the object now does the new task first, but then continues where it was before
  • Remove tasks (and add new ones)

I was plannig for a RTS and how I could handle a dozen of tanks all do something senseful. Whenever they encounter a problem, there must be a way to add a task at the beginning and resume the remaining tasks after that. I would have atomic tasks (like move north) and semantic tasks like find path to or react on enemy, which involve more AI and produce atomic tasks. React on AI would probably look for cover, which would then add find path to cover position, which would start pathfinding and add simple move orders from tile to tile. Then it would add some kind of “analyse situation”, which would either continue to react on the enemy or if it is destroeyed or away would continue the old tasks.

So you dont actually need to freeze the script. You need to set the elements into a list. Each frame the NPC would perform the current task, like turning into a direction or making a move or playing an animation. If the task is done, it is removed and the next one is performed. Something like headTo(treasureChest); would add a task to turn the NPC by some degrees each frame until it has the right direction.

-JAW

#16

Treasure quest AI logic approach

#17

I’m not sure I totally agree. I’ve written several custom languages and they’ve been a good fit for their purpose, but in the OP’s case I wonder if that’s overkill. Scripting languages make sense when :

(a) You’re coding in C++ where a recompilation cycle will require you to take several coffee breaks before it finishes, so you’d rather avoid that by using a scripting language.

(b) You expect your end user or other non technical internal staff (probably designers) needs to be able to alter game behaviour.

I don’t think either of these apply. Java has super fast compilation and as long as you don’t need to allow non-developers to alter the game, I can’t see the argument for scripting languages in Java games.

Oh, and another annoying consequence of scripting languages in games is that they often put a brick wall into your debugging process. I.e.: you’re debugging your game code, it calls out to script, but the IDE can’t debug into that. It’s very annoying when you’re squashing bugs.

#18

Basically, I think that everything that can be outside of the code should be outside of the code. You don’t necessarily need to have a fully functional scripting language, but you should be able to store the bulk of NPC dialogue and actions in an easily modifiable external file.

In a simple game, it may not matter much.

#19

I agree that games are often best being data-driven

#20

This is how I did it:
I use beanshell. I wrote code in my game-editor. Beanshell is almost exactly like standard java. Before each script executed, I loaded it with some handy object: the player, the map etc.

When I wanted to queue many actions I created a Tactic object for each line and queued them. Each Tactic object took control of the character and performed the task. This is done in the characters update method. It runs every frame (or every 10th frame). A tactic could be WalkToTactic. This has the advantage that if something moves the character (say an explosion) it will get back on track automatically. When the tactic is finished, the next in queue is loaded and takes control.