Long-lived Guile scripts in a mono-threaded game engine

Long-lived Guile scripts in a mono-threaded game engine

[Sylvain Beucler]

i,

I'm contemplating adding Guile support in GNU FreeDink, which is a
game engine for Dink Smallwood, a 2D scripted game.

Currently there's a "manually coded" scripting engine which is pretty
limited and buggy, though it works decently enough and was already
used for large extensions.

I'd like to add Guile as an alternative :)


Currently I'm facing several issues, the main one is how to manage
long-lived scripts:

The engine runs in a single thread, and the game loop essentially:

- passes over all sprites in a screen, and runs the scripts attached
  to those sprites

- detect collisions and run associated scripted hooks

- perform other non-scripted transformations such as sprite
  progressive moves, update the status bar, etc.

- the game screen is then refreshed with the new game state

- repeat


Scripts last more than a single game loop. They are not basic scripts
that describe what happens in a single engine step; instead they
describe what happens in the story.

For example, a game introduction will create sprites on the screen,
move them around, make them say lines that the user can read (or pass
using [space]), etc.

That script can also change the current screen (which kills all other
scripts in the current script).

Multiple scripts can run in a single screen, but they run the one
after the other, not in parallel. The order/priority is known.

Scripting is essentially frozen during the screen refresh. This avoids
putting mutexes everywhere.




How could I do something similar with Guile? I didn't find a way to
make a guile script pause (and return to the caller).

I guess one possibility is to run all scripts as independent threads,
and make them lock on a global mutex. However, as emphasized in this
article
http://harkal.sylphis3d.com/2005/08/10/multithreaded-game-scripting-with-stackless-python/
I would appreciate non-preemtiveness, for simplicity.

I think what I'm looking for is similar to Lua's coroutines
(a.k.a. fake threads - one coroutine at a time)
http://lua-users.org/wiki/CoroutinesTutorial

It's also important that running scripts can be terminated by the game
engine if need be.


How would you do this with Guile? :)

Thanks,

-- 
Sylvain

Re: Long-lived Guile scripts in a mono-threaded game engine

[Ludovic Courtès]

Hi Sylvain,

Sylvain Beucler <beuc@beuc.net> writes:

> I'm contemplating adding Guile support in GNU FreeDink, which is a
> game engine for Dink Smallwood, a 2D scripted game.

Nice.  :-)

> Scripts last more than a single game loop. They are not basic scripts
> that describe what happens in a single engine step; instead they
> describe what happens in the story.
>
> For example, a game introduction will create sprites on the screen,
> move them around, make them say lines that the user can read (or pass
> using [space]), etc.
>
> That script can also change the current screen (which kills all other
> scripts in the current script).
>
> Multiple scripts can run in a single screen, but they run the one
> after the other, not in parallel. The order/priority is known.
>
> Scripting is essentially frozen during the screen refresh. This avoids
> putting mutexes everywhere.
>
>
>
>
> How could I do something similar with Guile? I didn't find a way to
> make a guile script pause (and return to the caller).

IIUC, "scripts" are only invoked via hooks, e.g., the engine wants to
ask them to do something specific.  If that is the case, it suffices to
not invoke the script.

Surely you can implement coroutine-like behavior, either using `call/cc'
(but that is going to be prohibitively expensive), or using explicit
continuation-passing style or similar.  For instance, when a hook is
called by the engine, it would systematically return a thunk (a
zero-argument procedure) that the engine would later invoke.  Example:

  (define (my-hook action)
    (let ((stuff (do-some-computation action)))
      (lambda ()
        ;; This will be executed at some later point, when the engine
        ;; feels like invoking it.
        (do-the-remaining-computation stuff))))

Does this help?

Thanks,
Ludovic.

Re: Long-lived Guile scripts in a mono-threaded game engine

[Sylvain Beucler]

Hi,

On Tue, May 27, 2008 at 09:58:46AM +0200, Ludovic Courtès wrote:
> > Scripts last more than a single game loop. They are not basic scripts
> > that describe what happens in a single engine step; instead they
> > describe what happens in the story.
> >
> > For example, a game introduction will create sprites on the screen,
> > move them around, make them say lines that the user can read (or pass
> > using [space]), etc.
> >
> > That script can also change the current screen (which kills all other
> > scripts in the current script).
> >
> > Multiple scripts can run in a single screen, but they run the one
> > after the other, not in parallel. The order/priority is known.
> >
> > Scripting is essentially frozen during the screen refresh. This avoids
> > putting mutexes everywhere.
> >
> >
> >
> >
> > How could I do something similar with Guile? I didn't find a way to
> > make a guile script pause (and return to the caller).
> 
> IIUC, "scripts" are only invoked via hooks, e.g., the engine wants to
> ask them to do something specific.  If that is the case, it suffices to
> not invoke the script.
> 
> Surely you can implement coroutine-like behavior, either using `call/cc'
> (but that is going to be prohibitively expensive), or using explicit
> continuation-passing style or similar.  For instance, when a hook is
> called by the engine, it would systematically return a thunk (a
> zero-argument procedure) that the engine would later invoke.  Example:
> 
>   (define (my-hook action)
>     (let ((stuff (do-some-computation action)))
>       (lambda ()
>         ;; This will be executed at some later point, when the engine
>         ;; feels like invoking it.
>         (do-the-remaining-computation stuff))))
> 
> Does this help?

Ok, so what I'm looking for isn't supported natively :/


Here's a sample script (very close to the C bindings, for a start):

(define (hit)
  (if (> (sp_gethitpoints (current_sprite)) 10)
    (begin
      (sp_sethitpoints (current_sprite) (- (sp_hitpoints (current_sprite)) 10))
      (dialog1))
    (begin
      (say_stop "ARRRRrr.." (current_sprite))
      (sp_kill (current_sprite) 0)
      (say_stop "Uh, I was supposed to protect him, not kill him!" 1)))
  (set_honour! (- (get_honour) 1)))

(define (dialog1)
  (say_stop "Why are you hitting me, player?" (current_sprite))
  (say_stop "Uh, sorry I won't do that again" 1))


Now every time we see a (say_stop), the script will pause for 2
seconds, so the player can read the text.


If I use CPS, this means I'll have to rewrite all my scripts in CPS
style. This would be pretty cumbersome. This is supposed to introduce
people to the beautiful world of scheme, not scare them to death ;)


call/cc has another issue: how do I return? Let's say I'm in the
middle of (dialog1) and I need to stop the script. Maybe with a set of
double continuations: one continuation at the top level to return to
the point before I called the initial procedure (which would stops the
script); and another one that is set at each (say_stop) to return to
the following line (to resume the script). Hopefully this is not as
inefficient as you suggested.


Maybe I'm missing a more simple solution?

-- 
Sylvain

Re: Long-lived Guile scripts in a mono-threaded game engine

[Ludovic Courtès]

Salut,

Sylvain Beucler <beuc@beuc.net> writes:

> Here's a sample script (very close to the C bindings, for a start):
>
> (define (hit)
>   (if (> (sp_gethitpoints (current_sprite)) 10)
>     (begin
>       (sp_sethitpoints (current_sprite) (- (sp_hitpoints (current_sprite)) 10))
>       (dialog1))
>     (begin
>       (say_stop "ARRRRrr.." (current_sprite))
>       (sp_kill (current_sprite) 0)
>       (say_stop "Uh, I was supposed to protect him, not kill him!" 1)))
>   (set_honour! (- (get_honour) 1)))
>
> (define (dialog1)
>   (say_stop "Why are you hitting me, player?" (current_sprite))
>   (say_stop "Uh, sorry I won't do that again" 1))
>
>
> Now every time we see a (say_stop), the script will pause for 2
> seconds, so the player can read the text.

IOW, `say_stop' does a `(sleep 2)' (or `sleep (2)'), or waits for some
UI event, is that right?

> If I use CPS, this means I'll have to rewrite all my scripts in CPS
> style.

Yes, but you said this was work-in-progress, so I suppose there's no
backward compatibility concern.  ;-)

> This would be pretty cumbersome. This is supposed to introduce
> people to the beautiful world of scheme, not scare them to death ;)

Well, it's not necessarily that scary, and it depends on how often you'd
have to use it.

> call/cc has another issue: how do I return? Let's say I'm in the
> middle of (dialog1) and I need to stop the script. Maybe with a set of
> double continuations: one continuation at the top level to return to
> the point before I called the initial procedure (which would stops the
> script); and another one that is set at each (say_stop) to return to
> the following line (to resume the script).

Yes, something like that: a continuation to invoke the "scheduler" (the
engine), which would be passed the continuation within `dialog1' that
needs to be resumed eventually.

> Hopefully this is not as inefficient as you suggested.

Depends on how often (and when) you do it, but expect it to be
inefficient as it copies the stack (see the "Continuations" node in the
manual).

It may actually be simpler to run the Scheme code in a separate POSIX
thread, and have it woken up by the engine when it should start working.

Thanks,
Ludovic.

Re: Long-lived Guile scripts in a mono-threaded game engine

[Paul Emsley]

Sylvain Beucler wrote:
> Hi,
>
> On Tue, May 27, 2008 at 09:58:46AM +0200, Ludovic Courtès wrote:
>   
>>> Scripts last more than a single game loop. They are not basic scripts
>>> that describe what happens in a single engine step; instead they
>>> describe what happens in the story.
>>>
>>> For example, a game introduction will create sprites on the screen,
>>> move them around, make them say lines that the user can read (or pass
>>> using [space]), etc.
>>>
>>> That script can also change the current screen (which kills all other
>>> scripts in the current script).
>>>
>>> Multiple scripts can run in a single screen, but they run the one
>>> after the other, not in parallel. The order/priority is known.
>>>
>>> Scripting is essentially frozen during the screen refresh. This avoids
>>> putting mutexes everywhere.
>>>
>>>
>>>
>>>
>>> How could I do something similar with Guile? I didn't find a way to
>>> make a guile script pause (and return to the caller).
>>>       
>> IIUC, "scripts" are only invoked via hooks, e.g., the engine wants to
>> ask them to do something specific.  If that is the case, it suffices to
>> not invoke the script.
>>
>> Surely you can implement coroutine-like behavior, either using `call/cc'
>> (but that is going to be prohibitively expensive), or using explicit
>> continuation-passing style or similar.  For instance, when a hook is
>> called by the engine, it would systematically return a thunk (a
>> zero-argument procedure) that the engine would later invoke.  Example:
>>
>>   (define (my-hook action)
>>     (let ((stuff (do-some-computation action)))
>>       (lambda ()
>>         ;; This will be executed at some later point, when the engine
>>         ;; feels like invoking it.
>>         (do-the-remaining-computation stuff))))
>>
>> Does this help?
>>     
>
> Ok, so what I'm looking for isn't supported natively :/
>
>
> Here's a sample script (very close to the C bindings, for a start):
>
> [snip script]
>
> Now every time we see a (say_stop), the script will pause for 2
> seconds, so the player can read the text.
>   

what is the nature of the pause? (I think that that might be 
important.)  How do you interrupt the tight little say_stop sleep loop 
(if that's what it is) when you are using C bindings?

> Maybe I'm missing a more simple solution?
>
>   

Maybe.

Re: Long-lived Guile scripts in a mono-threaded game engine

[Sylvain Beucler]

Hi,

On Tue, May 27, 2008 at 03:20:55PM +0200, Ludovic Courtès wrote:
> Sylvain Beucler <beuc@beuc.net> writes:
> 
> > Here's a sample script (very close to the C bindings, for a start):
> >
> > (define (hit)
> >   (if (> (sp_gethitpoints (current_sprite)) 10)
> >     (begin
> >       (sp_sethitpoints (current_sprite) (- (sp_hitpoints (current_sprite)) 10))
> >       (dialog1))
> >     (begin
> >       (say_stop "ARRRRrr.." (current_sprite))
> >       (sp_kill (current_sprite) 0)
> >       (say_stop "Uh, I was supposed to protect him, not kill him!" 1)))
> >   (set_honour! (- (get_honour) 1)))
> >
> > (define (dialog1)
> >   (say_stop "Why are you hitting me, player?" (current_sprite))
> >   (say_stop "Uh, sorry I won't do that again" 1))
> >
> >
> > Now every time we see a (say_stop), the script will pause for 2
> > seconds, so the player can read the text.

> IOW, `say_stop' does a `(sleep 2)' (or `sleep (2)'), or waits for some
> UI event, is that right?
---
> what is the nature of the pause? (I think that that might be important.)
> How do you interrupt the tight little say_stop sleep loop (if that's what
> it is) when you are using C bindings?

Basically, a timestamp (for 'say_stop' and 'wait') or more generally a
goal (coordinates for 'move_stop') is attached to the script. The game
loop, before refreshing the screen, passes on each active script and
see if it needs to be resumed.

If at a point the engine needs 3s to load a bunch of graphics and
sounds from the disk (e.g. during a screen change), the paused script
won't wake up during that, but instead will be awaken by the engine
when it's done with the loading.

So the script does not (sleep). In this game, the engine is a mini-OS
with a non-preemptive process model. This is often used in games for
efficiency and ease of debugging (no concurrency). In my case this is
because the code was like this before I put my hands on it :)

Currently when the script engine interprets 'say_stop("Hello");', it
will set the timestamp at now+2s, save the script resume point, and
return to the main game loop.


> > This would be pretty cumbersome. This is supposed to introduce
> > people to the beautiful world of scheme, not scare them to death ;)
> 
> Well, it's not necessarily that scary, and it depends on how often you'd
> have to use it.

Let's precise the audience: most often, 15-20 years-old with little
programming skills. If we get them to try out Scheme despite Lots of
Irritating Superfluous Parentheses, that will already be a success ;)

Maybe Guile support could then be reserved for Real Programmers, but
to answer your question scripting is used very often in this engine,
so I doubt CPS will please them.


> > call/cc has another issue: how do I return? Let's say I'm in the
> > middle of (dialog1) and I need to stop the script. Maybe with a set of
> > double continuations: one continuation at the top level to return to
> > the point before I called the initial procedure (which would stops the
> > script); and another one that is set at each (say_stop) to return to
> > the following line (to resume the script).
> 
> Yes, something like that: a continuation to invoke the "scheduler" (the
> engine), which would be passed the continuation within `dialog1' that
> needs to be resumed eventually.

Well, I don't think the engine should be called _by_ Guile. Rather the
opposite: the engine calls Guile, and does it one time per active
script or hook.


> It may actually be simpler to run the Scheme code in a separate POSIX
> thread, and have it woken up by the engine when it should start working.

Yeah, I was trying to avoid introducing threads in the engine :)
But it sounds like the only usable solution as of now.

Ideally Guile would offer a '(pause)' function that would return from
'scm_eval_string' or similar, with another 'scm_resume()' function
that would unfreeze it :)

-- 
Sylvain

Re: Long-lived Guile scripts in a mono-threaded game engine

[Ludovic Courtès]

Hi,

Sylvain Beucler <beuc@beuc.net> writes:

> So the script does not (sleep). In this game, the engine is a mini-OS
> with a non-preemptive process model.

So "scripts" are supposed to be cooperative, and invoking `say_stop'
amounts to doing a `yield', right?

Then your question boils down to how to implement `yield'.  Using
continuations, that would be something like this:

  (define (my-hook schedule)
    (define (yield)
      (call/cc schedule))

    ;; do stuff...

    (yield)

    ;; do more stuff
    )

Where `my-hook' is invoked by the engine and SCHEDULE is a continuation
to invoke the engine, which may in turn schedule another co-routine, and
so on.

You could save one `call/cc' by abusing exceptions (which do not involve
stack copying, unlike `call/cc'):

  (define (my-hook)
    (define (yield)
      (call/cc
        (lambda (resume)
          (throw 'yield-to-scheduler resume))))

    ;; do stuff...

    (yield)

    ;; do more stuff
    )

... where the `yield-to-scheduler' exception would be caught by the
engine.  With a bit of syntactic sugar, this could be hidden from
programmers.

But again, I would avoid `call/cc' at all because of its performance
hit.  Avoiding it would require explicit CPS, which may admittedly be
unsuitable given the audience:

  (define (my-hook)
    (define (yield resume)
      (throw 'yield-to-scheduler resume))

    ;; do stuff...

    (yield (lambda ()
             ;; do more stuff
             )))

Given the drawbacks of these solutions, evaluating scripts in a separate
pthread looks like a good solution.  :-)

> Yeah, I was trying to avoid introducing threads in the engine :)
> But it sounds like the only usable solution as of now.

It's actually not silly now that we've entered the multicore era.

> Ideally Guile would offer a '(pause)' function that would return from
> 'scm_eval_string' or similar, with another 'scm_resume()' function
> that would unfreeze it :)

That would most likely have to be implemented in terms of `call/cc' as
shown above, so it wouldn't help much.

Thanks,
Ludovic

Re: Long-lived Guile scripts in a mono-threaded game engine

[Clinton Ebadi]

Sylvain Beucler <beuc@beuc.net> writes:

>> IOW, `say_stop' does a `(sleep 2)' (or `sleep (2)'), or waits for some
>> UI event, is that right?
> ---
>> what is the nature of the pause? (I think that that might be important.)
>> How do you interrupt the tight little say_stop sleep loop (if that's what
>> it is) when you are using C bindings?
>
> Basically, a timestamp (for 'say_stop' and 'wait') or more generally a
> goal (coordinates for 'move_stop') is attached to the script. The game
> loop, before refreshing the screen, passes on each active script and
> see if it needs to be resumed.
>
> If at a point the engine needs 3s to load a bunch of graphics and
> sounds from the disk (e.g. during a screen change), the paused script
> won't wake up during that, but instead will be awaken by the engine
> when it's done with the loading.
>
> So the script does not (sleep). In this game, the engine is a mini-OS
> with a non-preemptive process model. This is often used in games for
> efficiency and ease of debugging (no concurrency). In my case this is
> because the code was like this before I put my hands on it :)
>
> Currently when the script engine interprets 'say_stop("Hello");', it
> will set the timestamp at now+2s, save the script resume point, and
> return to the main game loop.

You are pretty much doing what call/cc does, and so could
straightforwardly rewrite the functions that cause scripts to freeze
to capture the current continuation and schedule an event to resume
this continuation when needed. So something like:

(define (say-stop message)
  (call/cc (lambda (k)
	     (%say-stop message k))))

This might be worth trying and might perform well enough, but Guile's
call/cc is fairly slow and heavyweight as it must copy the entire C
stack.

An alternative approach could use a thread per script. You'd stash the
thread you want to resume into the event, put it to sleep immediately,
and awaken it again when the event triggers. This would probably be
fairly easy to implement using condition variables. The disadvantage
here is that now every script has a thread which could become
problematic if enough scripts are loaded.

-- 
                   It's no contest, but we still race there                   
                Like the saintly tortoise and the godless hare                

Re: Long-lived Guile scripts in a mono-threaded game engine

[Sylvain Beucler]

Hi,

Thanks for your answers Ludovic and Clinton.


> An alternative approach could use a thread per script.

By the way, I have a question about threads: is there a way to kill a
running thread? For example when the current game screen changes, all
current scripts are terminated. Or does this need to be implemented
manually?


> > Yeah, I was trying to avoid introducing threads in the engine :)
> > But it sounds like the only usable solution as of now.
> 
> It's actually not silly now that we've entered the multicore era.

That's a pro, but there are cons too :/
- this kind of game engine has hardly anything runnable in parallel
- all the game globals need to be properly mutex'd
- or threads executions need to be serialized which defeats the point
Another pro though is that all of us masochists love debugging
multithread programs ;)


I'll try these solutions with my toy project and see how they fair
with performances/complexity :)

Thanks,

-- 
Sylvain

Re: Long-lived Guile scripts in a mono-threaded game engine

[Clinton Ebadi]

Sylvain Beucler <beuc@beuc.net> writes:

> Hi,
>
> Thanks for your answers Ludovic and Clinton.
>
>
>> An alternative approach could use a thread per script.
>
> By the way, I have a question about threads: is there a way to kill a
> running thread? For example when the current game screen changes, all
> current scripts are terminated. Or does this need to be implemented
> manually?

cancel-thread / scm_cancel_thread should do what you want

-- 
<captain_krunk> ntk is currently using "telnet fyodor 25" to send email

Re: Long-lived Guile scripts in a mono-threaded game engine

[Neil Jerram]

[-- Attachment #1: Type: text/plain, Size: 1523 bytes --]

2008/5/27 Clinton Ebadi <clinton@unknownlamer.org>:

> You are pretty much doing what call/cc does, and so could
> straightforwardly rewrite the functions that cause scripts to freeze
> to capture the current continuation and schedule an event to resume
> this continuation when needed. So something like:
>
> (define (say-stop message)
>  (call/cc (lambda (k)
>             (%say-stop message k))))
>
> This might be worth trying and might perform well enough, but Guile's
> call/cc is fairly slow and heavyweight as it must copy the entire C
> stack.


The amount of the stack that needs copying could be reduced, though, by
putting a continuation barrier (scm_c_with_continuation_barrier) in the C
code shortly before it calls out to Guile.

Personally, I'd try the continuation approach.  I did something just like
this for a dayjob-related project, where a key objective was to make the
Scheme scripts as friendly-looking as possible to non-Scheme people.  I used
continuations to make it possible to write a script as a sequence of
apparently synchronous operations that were really asynchronous (i.e. send a
request somewhere, and wait for an asynchronous response).  It can be done
in such a way that the call/cc is hidden down in the infrastructure, and
script-writers never need to see it.

A complication in my case was that the C code was sensitive to unusual
return patterns.  So I also needed to use a continuation to protect the C
code; I can provide more detail about that if needed.

Regards,
        Neil

[-- Attachment #2: Type: text/html, Size: 1917 bytes --]