Incremental Script Execution in games

Incremental Script Execution in games

Postby Sauer2 » 28 Sep 2017, 18:05

By which I mean running a couple of bytecode instructions each game update instead of running a whole script at once.
It seems like it would be relatively easy to implement and might be the best way to prevent the consequences of infinite loops, among other advantages, like easy-to-pause/save game state, latent functions as bonus etc pp.

Yet only a few AAA studios seem to bother. Is there a huge technical drawback to this approach?
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby Lyberta » 29 Sep 2017, 12:12

What about the halting problem?
Some crazy person on the Internet.
User avatar
Lyberta
 
Posts: 307
Joined: 19 Jun 2013, 10:45

Re: Incremental Script Execution in games

Postby dulsi » 29 Sep 2017, 16:17

The complexity is the drawback. You have to know where you are in every script. You have to craft the script with the knowledge they may not complete at once. It is also common to use an embedded language like lua or python or javascript. In most cases the engines probably don't support this mode so you would need to code it up yourself.

Halting problem doesn't matter in his case. If the script is broken and produces an infinite loop, it just runs forever wasting cpu. However if the game had cinematics that take control away from the player, this solution won't help if the cinematics script is stuck.
dulsi
 
Posts: 75
Joined: 18 Feb 2016, 15:24

Re: Incremental Script Execution in games

Postby Sauer2 » 30 Sep 2017, 13:39

Lyberta {l Wrote}:What about the halting problem?

The script may run for all eternity, but as a dev you can abort interpretation e.g. with a console command or as user you can leave the game or reload the latest savegame.
Of course that doesn't solve the bug itself, but neither do the alternatives that might hang your game or require a lot of hacks in the interpreter.

dulsi {l Wrote}:The complexity is the drawback. You have to know where you are in every script. You have to craft the script with the knowledge they may not complete at once.

To be honest, I don't see how that is better the other way.
Depending on how one uses e.g. Lua, you'd still have to deal with multiple scripts running at once, deactivating and activating scripting hooks in time and depending on how all is implemented, you merely shifted some global state to some other part of the engine, at best.
It's not like game devs are supposed to write single scripts that span an entire quest.

It is also common to use an embedded language like lua or python or javascript. In most cases the engines probably don't support this mode so you would need to code it up yourself.

In general, people using inappropriate technology and then getting owned for it sure is a problem.
That said, there is a handful of common embedded languages that claim to be designed for game scripting like Squirrel, AngelScript, GM and the only interpreter I found offering incremental execution out of the box is Jinx, something unknown with weird multi-word name syntax.

However if the game had cinematics that take control away from the player, this solution won't help if the cinematics script is stuck.

That is just bad design of the cinematics mode and problems like that can happen with Lua et al. as well.
Now that you mention it, it always sucks that some games have parts you can't abort by menu or at least by tabbing out of the window, whereas some allow even tabbing out of the loading screen, as they should.
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby onpon4 » 30 Sep 2017, 15:50

By which I mean running a couple of bytecode instructions each game update instead of running a whole script at once.

That would be largely pointless. If you're running the scripts independently of the rest of the code, you would do that with multithreading. Then you also get the benefit of parallelization of computing. But it doesn't work well for every game. Sometimes the engine needs to wait for a script to finish, and if that happens often enough, what's the point of parallelization? In fact, trying to run scripts at an arbitrary rate in parallel with the engine can easily cause important synchronization to be lost; imagine, for example, you have a script which walks your character 20 meters to the right before shutting a door behind him. If the script is running 2 times faster than it should, or more likely the game is running only half as fast as it should, then the door shuts before the player makes it, breaking the game. This can not be a problem depending on the game, but otherwise, it's just not worth it.
User avatar
onpon4
 
Posts: 382
Joined: 13 Mar 2014, 18:38

Re: Incremental Script Execution in games

Postby Sauer2 » 30 Sep 2017, 17:10

onpon4 {l Wrote}:
By which I mean running a couple of bytecode instructions each game update instead of running a whole script at once.

That would be largely pointless. If you're running the scripts independently of the rest of the code, you would do that with multithreading. Then you also get the benefit of parallelization of computing. But it doesn't work well for every game. Sometimes the engine needs to wait for a script to finish, and if that happens often enough, what's the point of parallelization? In fact, trying to run scripts at an arbitrary rate in parallel with the engine can easily cause important synchronization to be lost; imagine, for example, you have a script which walks your character 20 meters to the right before shutting a door behind him. If the script is running 2 times faster than it should, or more likely the game is running only half as fast as it should, then the door shuts before the player makes it, breaking the game. This can not be a problem depending on the game, but otherwise, it's just not worth it.

That all sounds just technically wrong.

The point isn't parallelization in the first place, the point is giving modders a safe way to create high level game logic without actually giving them control over the software.
And as a rule of thumb: If throughput is ever a problem for scripting games that just means the API is designed too low level or the user is misusing them.

Running e.g. Lua in a separate thread most likely comes with all kinds of other problems. Even searching the web for about 5 minutes turns up issues like Lua not being thread-safe in various aspects and that the only way to stop it is killing the thread, with all the headaches that might come with it.
Besides, it's probably not even a win in throughput. I suggested the same thing a couple of years ago for another game and the main devs pointed out that, since the scripts aren't doing pure calculations but changing the game state all the time, the overhead of synchronizations eats any gains.

As for the last point, that is obviously something nobody competent would solve by waiting a specific time, but instead use callbacks or - more likely with incremental execution - call a latent function that waits for event x to happen. In that example, the function to walk to position x could be latent and continue execution once the character reached the position.

Come on guys, I can buy the argument that there are almost no options available, but state synchronization is hardly more a problem than usually.
Debugging might be a point. But then again, it's mostly a part of the no-options argument or a matter of dev ressources.
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby onpon4 » 30 Sep 2017, 17:30

the point is giving modders a safe way to create high level game logic without actually giving them control over the software.

This doesn't make sense. Scripting is intertwined with the game engine somehow; otherwise it would be useless. You can't completely separate them.

that is obviously something nobody competent would solve by waiting a specific time

:shrug: I guess I'm incompetent then. But this is not the only sort of situation that can cause synchronization problems. It's just the easiest example I could think of. Anything else would require knowing the specifics of the engine.

If I understood your proposal correctly, and please tell me if I'm wrong, you're proposing for the script interpreter to stop interpreting, arbitrarily, outside the scripter's control, after a certain amount of instructions or time, and then continuing what the game engine wants to do (effectively, advancing a frame) before continuing with the next couple lines or whatever of the script. I don't understand what you are trying to accomplish with this, when simple parallelization would be much more reliable, simple, and have all the same problems.
User avatar
onpon4
 
Posts: 382
Joined: 13 Mar 2014, 18:38

Re: Incremental Script Execution in games

Postby Sauer2 » 30 Sep 2017, 19:45

This doesn't make sense. Scripting is intertwined with the game engine somehow; otherwise it would be useless. You can't completely separate them.

You wouldn't want untrusted mods with direct file access. In the same way, wouldn't it be nicer instead of crashing the game with an unstoppable infinite loop, possible hanging other parts of your system in the process you could just laugh, go back to the main menu, delete the mod and load the game again?
:shrug: I guess I'm incompetent then.

Maybe. The issue with that is that desktop computers aren't hard realtime singletask machines and hickups happen. For really rough timer based puzzles I guess you have to take that risk. But cinematic sequences with tight timing?
But this is not the only sort of situation that can cause synchronization problems. It's just the easiest example I could think of.

Fair enough. I think some systems solve this with proper API design. In smaller games you'd probably get away with only giving certain actors certain APIs or not having many actors to begin with. In bigger games there probably is the risk, but given that most scripted events that aren't put to hold with a latent function still run almost in an instant - hickups included - it's not a big risk.
If I understood your proposal correctly, and please tell me if I'm wrong, you're proposing for the script interpreter to stop interpreting, arbitrarily, outside the scripter's control, after a certain amount of instructions or time, and then continuing what the game engine wants to do (effectively, advancing a frame) before continuing with the next couple lines or whatever of the script.

You're correct. The script interpreter would execute a handful of instructions each game tick, unless stopped by some function call that tells the game not to update the interpreter until X happens.
when simple parallelization would be much more reliable, simple, and have all the same problems.

If by parallelization you mean OS threads, those aren't much more reliable, simple, but they come with fancy new problems. For example, when I wrote about headaches of killing threads I vaguely remembered something bad about that. Now, that I looked it up, it turns out that is basically impossible to properly kill a thread from the outside.

Look, if it was only Bethesda using this technique, I'd probably agree with you and shrug it off as just another example of poor craftmanship from their side, but some of the games with the least bugs I encountered use it as well, so there must be some point to it.
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby farrer » 30 Sep 2017, 21:04

On former DNT (which is a RPG), using an own script language, I've used the approach of 'n' executed lines per script at the main game loop. The biggest drawback of this approach was letting the main thread (DNT was almost single threaded, with the exception of A* search and sound play) depended of the scripts. If I do remember acordingly, I've defined a global max number of lines could be interpreted each cycle. When much scripts are running, each script could take 'forever' to be resumed again, otherwise it will affect for worse the game's frame rate, etc. And a script taking forever to resume, is for sure a not-very-responsive one, which, for the user, isn't a good thing to have.

On current DNT, using AngelScript, I use mostly a secondary thread for script execution, running on its own frequency, totally independent of the renderer thread, but implemented as a scheduler (one script per time, with a maximum of lines per script). The result is much better than the previous one. The main thread could still call a 'direct-result' script function (usually for retrieving a value), but it's not often (for consistency, they lock the script scheduler. And couldn't be suspended. if not returned in 'x' time, they are removed, but we'll miss the return value, which will probably result on a failure somewhere else).

Also, on both, there's a concept of 'pending actions'. Those are actions that need more than 'immediate time' to finish (for example, character walk to a position, or even a delay function). Those will suspend the script, that are put to 'sleep' (ie: our script scheduler will not call to resume this script) until they are finished.

On both. there's no problem of a infinite loops stalling the application. But, maybe the problem is just dislocated to 'zombie' scripts (but not 'zombie threads or a 'zombie main game'). But a zombie script is a mod-failure, not the application fault, I believe.

Not sure if I explained it well. Probably not.
User avatar
farrer
 
Posts: 77
Joined: 24 Feb 2014, 21:00

Re: Incremental Script Execution in games

Postby Sauer2 » 30 Sep 2017, 21:30

farrer {l Wrote}:On former DNT (which is a RPG), using an own script language, I've used the approach of 'n' executed lines per script at the main game loop. The biggest drawback of this approach was letting the main thread (DNT was almost single threaded, with the exception of A* search and sound play) depended of the scripts. If I do remember acordingly, I've defined a global max number of lines could be interpreted each cycle. When much scripts are running, each script could take 'forever' to be resumed again, otherwise it will affect for worse the game's frame rate, etc. And a script taking forever to resume, is for sure a not-very-responsive one, which, for the user, isn't a good thing to have.

On current DNT, using AngelScript, I use mostly a secondary thread for script execution, running on its own frequency, totally independent of the renderer thread, but implemented as a scheduler (one script per time, with a maximum of lines per script). The result is much better than the previous one. The main thread could still call a 'direct-result' script function (usually for retrieving a value), but it's not often (for consistency, they lock the script scheduler. And couldn't be suspended. if not returned in 'x' time, they are removed, but we'll miss the return value, which will probably result on a failure somewhere else).

Also, on both, there's a concept of 'pending actions'. Those are actions that need more than 'immediate time' to finish (for example, character walk to a position, or even a delay function). Those will suspend the script, that are put to 'sleep' (ie: our script scheduler will not call to resume this script) until they are finished.

On both. there's no problem of a infinite loops stalling the application. But, maybe the problem is just dislocated to 'zombie' scripts (but not 'zombie threads or a 'zombie main game'). But a zombie script is a mod-failure, not the application fault, I believe.

Not sure if I explained it well. Probably not.

I kind of have trouble to make sense of the first paragraph, to be honest. ;)
In particular, what was the drawback of letting the main thread depend on the scripts if you had a limit for the interpreter?
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby farrer » 01 Oct 2017, 00:35

Sauer2 {l Wrote}:I kind of have trouble to make sense of the first paragraph, to be honest. ;)
In particular, what was the drawback of letting the main thread depend on the scripts if you had a limit for the interpreter?


Let's see if I can explain without messing it up. The main loop itself has its own frequency, dependent of the fixed frame rate (usually 30 or 60FPS). The simplest approach could be, each frame, just call a single line for a single script (in fact it was up to n-lines of a script, and up to 'x' lines for all scripts, cycling between them until have x lines or all scripts ran at that cycle... example: 3 lines per script and up to 12 lines treated per rendering cycle).

If there isn't the global limit the frame rate could drop considerably when with lot of active scripts (even with non-fixed frame-rates... remember that with vsync set by driver option, the frequency could be fixed beyond application control).

But with this global limit, with lots of scripts active, one script should only be resumed after too much time passed since the last time it ran before, being with a considerable delay from the action it detects or expects or made happen. That also happens on complex scripts, with lots of lines.

That's the drawback of this old - naive - approach I had. Hope it's better understandable now.
User avatar
farrer
 
Posts: 77
Joined: 24 Feb 2014, 21:00

Re: Incremental Script Execution in games

Postby Sauer2 » 01 Oct 2017, 00:42

farrer {l Wrote}:
Sauer2 {l Wrote}:I kind of have trouble to make sense of the first paragraph, to be honest. ;)
In particular, what was the drawback of letting the main thread depend on the scripts if you had a limit for the interpreter?


Let's see if I can explain without messing it up. The main loop itself has its own frequency, dependent of the fixed frame rate (usually 30 or 60FPS). The simplest approach could be, each frame, just call a single line for a single script (in fact it was up to n-lines of a script, and up to 'x' lines for all scripts, cycling between them until have x lines or all scripts ran at that cycle... example: 3 lines per script and up to 12 lines treated per rendering cycle).

If there isn't the global limit the frame rate could drop considerably when with lot of active scripts (even with non-fixed frame-rates... remember that with vsync set by driver option, the frequency could be fixed beyond application control).

But with this global limit, with lots of scripts active, one script should only be resumed after too much time passed since the last time it ran before, being with a considerable delay from the action it detects or expects or made happen. That also happens on complex scripts, with lots of lines.

That's the drawback of this old - naive - approach I had. Hope it's better understandable now.

That makes sense. Thank you.
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby Sauer2 » 01 Oct 2017, 23:11

@onpon4: Joke's on me and you were half right. Stopping a thread from the outside is not possible, but AS seems to have a stop flag that you can set during execution from a proxy thread: http://www.angelcode.com/angelscript/sd ... meout.html
That still looks very heavy-handed, but I guess that is what thread pools are for.
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby c_xong » 02 Oct 2017, 10:30

As an engine developer, the only good choice you can make is to terminate a level if a script is misbehaving. You don't really know which scripts are critical to the level (e.g. a script that controls level end conditions) and hence can't be safely suspended or terminated without breaking the level itself. This includes problems like script infinite loop; leave it running and the game stalls, terminate it and you could break the level.

So the easier solution would be to monitor the health of the script, and terminate if it is unresponsive. I believe a lot of games do this already. It's really up to the script writer to fix such problems, there is no good general solution.
User avatar
c_xong
 
Posts: 202
Joined: 06 Sep 2013, 04:33

Re: Incremental Script Execution in games

Postby Sauer2 » 02 Oct 2017, 15:25

c_xong {l Wrote}:So the easier solution would be to monitor the health of the script, and terminate if it is unresponsive. I believe a lot of games do this already. It's really up to the script writer to fix such problems, there is no good general solution.

... So, the answer for Lua and most other interpreters is to modify the interpreter to have a volatile cancelling flag in its interpreter main loop?
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby dulsi » 03 Oct 2017, 18:52

Sauer2 {l Wrote}:
c_xong {l Wrote}:So the easier solution would be to monitor the health of the script, and terminate if it is unresponsive. I believe a lot of games do this already. It's really up to the script writer to fix such problems, there is no good general solution.

... So, the answer for Lua and most other interpreters is to modify the interpreter to have a volatile cancelling flag in its interpreter main loop?

I don't agree with c_xong's statement. The answer is to decide how important is the issue to you. Determine if it is worth the development time to solve. Plenty of games have used lua without solving that. Can you mod them to hang? Probably but if your goal is a produce a fun game, fixing this may not help you achieve that goal. If your goal is a great engine for others to develop with, it may be a reasonable feature to develop. I agree with onpon4 in that preempting scripts may make different kinds of scripting bugs. Whether it is easier or harder probably depends on the specifics of the game engine. I personally don't see a lot of point in preventing infinite loops in mods. It is up to the modders to QA their mods. A commonly used language like lua might lead to less bug due to familiarity than a less common language. (I don't particularly like lua. It is just an example.)
dulsi
 
Posts: 75
Joined: 18 Feb 2016, 15:24

Re: Incremental Script Execution in games

Postby Lyberta » 04 Oct 2017, 08:29

Wait, is there an ability in Lua implementation to set the maximum time the function call may take?
Some crazy person on the Internet.
User avatar
Lyberta
 
Posts: 307
Joined: 19 Jun 2013, 10:45

Re: Incremental Script Execution in games

Postby farrer » 04 Oct 2017, 11:56

Lyberta {l Wrote}:Wait, is there an ability in Lua implementation to set the maximum time the function call may take?


I do think there's a workaround to behave like a timeout with lua (or even the 'single line call steps'). To answer this, a look on AngelScript way to do timeouts should help.

One way is with a line callback function, quoting from the link:
{l Code}: {l Select All Code}
// The line callback function is called by the VM for each statement that is executed
void LineCallback(asIScriptContext *ctx, DWORD *timeOut)
{
  // If the time out is reached we suspend the script
  if( *timeOut < timeGetTime() )
    ctx->Suspend();
}


Not the best way to do, but very straightforward and workable. The next thing is, Lua do have a way to set a line callback function, with hooks:

The hook mechanism of the debug library allows us to register a function that will be called at specific events as your program runs. There are four kinds of events that can trigger a hook: call events happen every time Lua calls a function; return events happen every time a function returns; line events happen when Lua starts executing a new line of code; and count events happen after a given number of instructions.


Maybe there's other ways to implement that on Lua (I'm not a Lua programmer, and either like the language... in fact I had a bad time using it lot of years ago), but this is a possible one (not sure either about performance hits doing this on Lua, etc).
User avatar
farrer
 
Posts: 77
Joined: 24 Feb 2014, 21:00

Re: Incremental Script Execution in games

Postby Sauer2 » 04 Oct 2017, 13:36

Lyberta {l Wrote}:Wait, is there an ability in Lua implementation to set the maximum time the function call may take?

It is implied by a number of web sites that there are at least two options:
1. As farrer mentioned, one is setting a callback hook for a specific number of instructions. However, according to https://www.lua.org/manual/5.3/manual.html#4.9 that works only inside of Lua functions.
Also, hooks are made for debugging, so maybe they come with substantial overhead.
2. According to some github issue https://github.com/jerryscript-project/ ... ssues/1356 it is possible to call lua_error from a watchdog thread, similar to how it's mentioned on the AngelScript wikipage. It also mentions that there might be still leak problems with doing so, because the function is meant to be called inside a binded C function call.

If you are planning on testing it, feel encouraged to document the results in the wiki.
User avatar
Sauer2
 
Posts: 418
Joined: 19 Jan 2010, 14:02

Re: Incremental Script Execution in games

Postby Lyberta » 05 Oct 2017, 09:00

Thanks, but I can't stand languages with dynamic typing. I was just wondering because the ability to stop VM is a very useful thing.
Some crazy person on the Internet.
User avatar
Lyberta
 
Posts: 307
Joined: 19 Jun 2013, 10:45

Who is online

Users browsing this forum: No registered users and 1 guest