🔒 Locked

Making Coroutines "wait"

Started by KainS Apr 13, 2009 at 7:46 PM 13 replies 3.5k views

Original Post

Apr 13, 2009 at 7:46 PM

Hey folks! I'm just delving into working on my RPG in earnest, but I find myself paralyzed by a design issue. I'm using Lua coroutines for my NPCs, as well as the introductory cutscene in each chapter of my game's plot. Any of those coroutines can do things like play sounds and music, make an NPC move, or direct text to the dialogue controller. For the purpose of this problem, I'll focus on the latter case. The dialogue controller gets updated in each frame with the amount of time that's passed, and adds text to the dialogue box accordingly. This gives the game that old school type of dialogue box, where text appears letter by letter at a consistent pace instead of all at once. Let's say right now that I have an NPC script that's just a series of these text instructions, like so: ----- say('Hello!') say('How are you doing?') playSound('fanfare.wav') ----- "say" merely enqueues a string in the dialogue controller and then returns. This script will run to completion with no yields. It enqueues both lines of text in the controller. Immediately afterwards, a sound will play. The sound does not necessarily play after the text is on screen, but will most likely play while the text is slowly appearing on the screen. This kind of concurrent action might be desired in some cases. But now let's say I'd like an NPC to *wait* for certain time-consuming operations to complete. For example, if I wanted the NPC to wait until some speech is on screen, I would want to implement a say-then-yield(string) function that yields the coroutine until the string is entirely on screen (which will likely take multiple iterations through the game loop). It's the engine-side implementation of "say-then-yield" that stumps me. I can't think of an implementation that wouldn't result in an awkward design on the engine side. Do I pass the dialogue controller the information necessary to resume a coroutine when it is finished (i.e. an ID or structure pointing to the particular lua_State), and rely on it to resume the script when the text appears, like a signal/block construct? If so, then won't I have to implement that kind of functionality in *every possible component* that the NPC script may ever possibly wait for? Playing sounds, fading music, moving from point A to point B... it seems like a lot of repeated code to put into every component that the script would interact with, and I see no simple way to abstract it out across components for easy extension or maintenance. I currently see no other way to implement this, unfortunately. Ultimately, I might be stressing out over nothing; sometimes there are situations where no design decision can be perfect. But before I go on with a design decision that I already have a bad feeling about, I'd like to know if there are smarter ways to implement this kind of functionality. :) If anyone has any suggestions on how to nicely implement coroutine waiting and resuming in an engine, I would really appreciate any insights.

ddn3

Apr 14, 2009 at 9:55 AM

This is a common problem with NPCs. There are many ways of doing this, but Lua does offer coroutines which suits this problem well. You can implement various behavioral objects which encapsulate their stateful execution thread in a coroutine, to eliminate the need to explicitly store state ( in the C++ paradigm you would create objects with internal state and perhaps a switch statement and callbacks or events to push the states ). In Lua the simplest way is to have each NPC have a coroutine stack which they execute when given time to "think".

Something like this..

NPC = { } -- Create a table to hold the class methods function NPC:new() -- The constructor   local object = {		mTasks={}	--stores active corotuines in here   }   setmetatable(object, {     -- Overload the index event so that fields not present within the object are     -- looked up in the prototype parent class table     __index	= NPC   })   return object end  --simple npc think funciton, gives CPU time to runable tasks function NPC:onThink()	if (#self.mTasks==0) then		return;	--nothing to do	end	for k,v in pairs (self.mTasks) do		local status = coroutine.resume(v);		if (status~='dead')			v=nil;		end	end end --simple function creates a say task with msgfunction NPC:onSay(msg,sndFX)	local sayFunc = function()		--initate the speech get ID back from game to check its state		local speakID = GAME:say(msg);				--once speak state is done we can progress to next line,		while not(GAME:isSpeakDone(speakID)) do			coroutine.yield();		end				--check if speech was finished or interruted, good pratice here.		if (GAME:getSpeakState(speakID)~='done') then			return;	--we can exit without playing sound		end				--play sound at end of speech		GAME:playSound(sndFX);	end		self:pushTask(sayFunc);end--pushes runable functions onto the task stackfunction NPC:pushTask(func)	if (func==nil) then 		return;	end		local co = coroutine.create(func);		table.insert(self.mTasks,co);end

This code is unchecked, i'm sure there are syntax errors and what-not, but you'll get the idea.

Good Luck!

-ddn

rmtew

Apr 15, 2009 at 4:08 PM

Quote:
Original post by KainSUltimately, I might be stressing out over nothing; sometimes there are situations where no design decision can be perfect. But before I go on with a design decision that I already have a bad feeling about, I'd like to know if there are smarter ways to implement this kind of functionality. :)

If anyone has any suggestions on how to nicely implement coroutine waiting and resuming in an engine, I would really appreciate any insights.

An advantage of coroutines like these, is that you can make calling the function which blocks them and hands them off for resuming look like any other natural function call. No boilerplate. This is one of the main reasons I work on Stackless Python, which also provides coroutine-like functionality. It's worth the work to "pass the ... information necessary to resume a coroutine when it is finished" in my opinion.

Reawakening the calling function and expecting it to judge whether what it asked to be done was actually completed, is something I would warn against. It adds redundant processing which wouldn't even factor in if the resource being wrapped just took care of reawakening the calling coroutine when whatever event that signifies completion happened.

Kylotan

Apr 16, 2009 at 7:45 AM

How are people handling the synchronisation issues here? If the character is deleted before a coroutine associated with it is resumed, it's probably easy enough to destroy the coroutine object. But what if another character is deleted, one referred to within a coroutine?

I have thought about making all objects within such scripts be proxies to their authoritative C/C++ representation, and for them to observe that representation in such a way that a flag can be set when it's deleted, allowing it to raise an exception (Python) or do something similar in Lua (presumably set an error) when any attribute of that object is next accessed. However, I'm not sure how well such a strategy fits with the popular automatic binding generators that many people use. (I tend to roll my bindings by hand, personally.)

Is anybody doing this or something similar in practice?

ddn3

Apr 16, 2009 at 10:33 AM

The way complex systems deal with those kind of dependencies is either through automated resource management ( such as garbage collection, reference counting, etc.. ), so a resource is guaranteed to be not freed until all references of it are destroyed so operating upon it is guaranteed, but it's state of course can be 'dead' vs 'alive' which will not allow it to affect anything. But it's bad practice to operate upon dead entities either way, the other method I've seen is to use a decoupling event system where events are sent to the target entity through a broker and that broker decides if the entity is alive or dead and delivers that message.

Such an asynchronous event scheme needs an equally asynchronous programming paradigm otherwise you'll be bogged down by writing tons of event handling code, state trees and temporary state variables.

Lua does GC of both it's objects and bound objects from C++, so as long as you let Lua manage the lifespan of the objects, within Lua they are guaranteed to be existent as long as there are still references too it. Makes programming easy enough and for most games that's adequate.

If your ambitious, you can implement the asynchronous event driven schemes, which has it's benefits too. That's more similar to the stackless programming paradigm popular these days ( ie stackless phython, Erlang.., etc.. )

Good Luck!

-ddn

rmtew

Apr 16, 2009 at 6:42 PM

Quote:
Original post by KylotanHow are people handling the synchronisation issues here? If the character is deleted before a coroutine associated with it is resumed, it's probably easy enough to destroy the coroutine object. But what if another character is deleted, one referred to within a coroutine?

You can create complicated systems where it is possible to reason what coroutines should be killed in response to what changes in game state. But this just gives you custom boilerplate. It's moving away from the paradigm of natural calls and the easily readable code that allows.

The simplest approach is the best approach. Kill coroutines where it is possible to do so in a straightforward manner, and otherwise, check state after the operation blocking the coroutine completes.

It might be that you can find an event to listen to, in order to detect things like the removal of other characters. Then you can take the simple approach and kill the coroutine.

class Character:  def __del__(self):      self.AbortActivity()  def OnObjectRemoved(self, ob):      if ob.itemID == self.targetID:         self.AbortActivity()

Unfortunately, it is not always the case that you have suitable events. Sometimes I am too lazy to even look, it's easy enough to hook up a generic function to gauge coroutine relevance.

class Character:  def Attack(self, targetID):      activityState = self.StartActivity(ACTIVITY_ATTACK, targetID)      if targetID:          self.Approach(activityState.targetID)          if not self.ActivityStillValid(activityState):              return

Quote:
Original post by Kylotan
I have thought about making all objects within such scripts be proxies to their authoritative C/C++ representation, and for them to observe that representation in such a way that a flag can be set when it's deleted, allowing it to raise an exception (Python) or do something similar in Lua (presumably set an error) when any attribute of that object is next accessed. However, I'm not sure how well such a strategy fits with the popular automatic binding generators that many people use. (I tend to roll my bindings by hand, personally.)

Is anybody doing this or something similar in practice?

Not that I know of. IMO the scripting code should work properly and deletion should just be handled cleanly. This solution sounds like the kind of approach you take to debug when you don't know your code well enough to know why something hasn't been deleted properly.

Kylotan

Apr 17, 2009 at 6:02 AM

Quote:
Original post by rmtew
The simplest approach is the best approach. Kill coroutines where it is possible to do so in a straightforward manner, and otherwise, check state after the operation blocking the coroutine completes.

It might be that you can find an event to listen to, in order to detect things like the removal of other characters. Then you can take the simple approach and kill the coroutine.

I don't see how that helps anything but the most trivial scripts.

eg.:

friend = nearestFriend() # friend1 is now a Character object/proxyenemy = acquireTarget() # enemy1 is also a Character objectmoveTowards(enemy) # this yields until you get close enoughsayTo(friend, "He's over here!")attack(enemy)

Imagine that while moveTowards is paused, the C++ object that enemy refers to is killed by a different coroutine or the C++ engine. That's easy to spot, because the existence of the enemy character is likely to be part of the predicate that decides when to resume the coroutine. But now imagine what to do if the friend character is killed in that time. Something either has to know to invalidate the coroutine, or has to put boilerplate 'still existing' checks into the sayTo command and any other similar command.

Quote:
IMO the scripting code should work properly and deletion should just be handled cleanly. This solution sounds like the kind of approach you take to debug when you don't know your code well enough to know why something hasn't been deleted properly.

Not at all. It's just a classic concurrent programming problem where multiple processes want to access one remote resource, ie. the C++ object referred to by the script-side character objects. Even if you can guarantee it's not deleted that just moves the problem, from "check the object still exists in memory" to "check the object is allowed to be operated on". Some languages get around this by completely forbidding shared references, such as Erlang, but that's not how we expect to work in Python, Lua, or game programming generally.

Kylotan

Apr 17, 2009 at 6:15 AM

Quote:
Original post by ddn3
But it's bad practice to operate upon dead entities either way, the other method I've seen is to use a decoupling event system where events are sent to the target entity through a broker and that broker decides if the entity is alive or dead and delivers that message.

Yes, keeping dead entities around and flagging them doesn't fix the problem, just changes it from a crash bug to a maintenance nightmare. It's easy to ensure the script entities get flagged but not so trivial to ensure every single method checks that flag before operating. Doubly so, if the flag can itself be set during operation of such a method.

Message systems seem fine but I wonder how cleanly you can implement them in scripts written in a typical imperative and object-oriented language. Suddenly the idea of simply taking a C++ object and automatically generating bindings for it becomes useless, the way I see it. You can't store much entity state in script, which in turn means your scripting becomes limited.

ddn3

Apr 17, 2009 at 10:15 AM

The problem isn't much different from the problem in C++/C with lingering references, how do you design a system where objects can be cleanly removed from a complex system which can hold ptrs to that data. It's a question of design here, you'll have to have a clean object hierarchy, well defined relationships between objects and known sinks for ptrs which you'll have to be sure to flush of the object when the need arises. A lot of work, but people have been doing these things in unmanaged languages for along time.

Mixing a managed and unmanaged language you'll have to negotiate ownership of objects. Personally I would let the script own all the objects and let it's GC manage it and if the need arises create a scheme for one off cases like corotuines which can have problematic lingering references.

It just boils down to how you design and use it. I'm sure you can create novel solutions in script where you explicitly register all objects and their relevant usage and when the time comes you can cleanly flush references of it from the system, much like how you'll have to do in an unmanaged language.

Good Luck!

-ddn

rmtew

Apr 17, 2009 at 4:42 PM

Quote:
Original post by Kylotan
I don't see how that helps anything but the most trivial scripts.

eg.:
friend = nearestFriend() # friend1 is now a Character object/proxyenemy = acquireTarget() # enemy1 is also a Character objectmoveTowards(enemy) # this yields until you get close enoughsayTo(friend, "He's over here!")attack(enemy)
Imagine that while moveTowards is paused, the C++ object that enemy refers to is killed by a different coroutine or the C++ engine. That's easy to spot, because the existence of the enemy character is likely to be part of the predicate that decides when to resume the coroutine. But now imagine what to do if the friend character is killed in that time. Something either has to know to invalidate the coroutine, or has to put boilerplate 'still existing' checks into the sayTo command and any other similar command.

When I read this paragraph, I feel like there's a point missing with regard to why these two things in your last sentence are non-trivial. I can quite easily implement a workable solution for "invalidate the coroutine" in your given scenario with Stackless Python. I can have that sequence of code in a coroutine terminated, when friend is "deleted".

Of course, the language the coroutines are provided by, and the framework you've built on top of that language determine the limiting factors in the solutions you can implement.

Kylotan

Apr 20, 2009 at 8:25 AM

Quote:
Original post by rmtew
I can quite easily implement a workable solution for "invalidate the coroutine" in your given scenario with Stackless Python. I can have that sequence of code in a coroutine terminated, when friend is "deleted".

I think the problem here is that you've been doing this stuff for years and it seems obvious to you, whereas it is new to most people. That's why this thread or some variant of it gets posted here at least once a week for the last 2 years. The people who know how to use coroutines effectively are saying, "to do do this, use coroutines", but aren't explaining how they do it. There's no simple document to direct people to, especially not when it comes to this sort of issue.

There is a typical expectation on this forum - not necessarily a good one - that you can code an object in C++, then use an automatic bindings generator (eg. SWIG, Boost::Python, LuaBind, etc) to create proxy objects in the language being used for scripting, eg. Python, Lua, &#106avascript, etc. The underlying object can be used as-is.<br/><br/>But this doesn't work well with a naive approach to coroutines. If I have 2 routines that refer to the same C++ object and the C++ object is deleted by one of them, the other coroutine needs notification of this as its proxy object is now likely to be broken. But the original C++ object has no notion of the scripting system or existing in multiple places or any of that. So I'm interested in knowing what people are doing here in practice. Where is the tracking of an object's usage across coroutines taking place?<br/><br/>And is terminating the whole coroutine always acceptable? I can imagine wanting to do something more elegant like raise an exception when a proxy object is no longer valid, but again that requires a bit more sophistication in the proxy object than people are used to having.<br/><br/><blockquote><span class="smallfont">Quote:</span><table border="0" cellpadding="4" cellspacing="0" width="95%"><tr><td class="quote">Of course, the language the coroutines are provided by, and the framework you've built on top of that language determine the limiting factors in the solutions you can implement.</td></tr></table></blockquote><br/>Most people on this forum will be attaching a scripting language to a pre-existing native-code engine, so the framework will be non-existent. That's why we could do with knowledgeable people sharing their approaches, to know what sort of intermediate structure would be useful.

Kylotan

Apr 20, 2009 at 8:37 AM

Quote:
Original post by ddn3
The problem isn't much different from the problem in C++/C with lingering references, how do you design a system where objects can be cleanly removed from a complex system which can hold ptrs to that data.

The difference is the language barrier. If I delete an object in C++, I can iterate through whichever structures I need to in order to decouple any references. However, given a lua_State or a runnable PyObject, I can't imagine having to examine them manually to find any object that looks like it might refer back to my C++ object via something like a Lua light-userdata or a Python PyCObject. That's quite an opaque interface. So I don't think you'd do it that way at all - you'd have some sort of bridging system mapping C++ objects to the coroutines they're used in, presumably registering themselves at the point of creation. Or perhaps via a lazy system where these proxy objects only look up the C++ object when a method is invoked and can return an error if the object is no longer there. Or something. The problem is that nobody seems to be talking about their particular brand of 'something'. ;)

Quote:
Mixing a managed and unmanaged language you'll have to negotiate ownership of objects. Personally I would let the script own all the objects and let it's GC manage it and if the need arises create a scheme for one off cases like corotuines which can have problematic lingering references.

I think life is a lot easier if your main game logic is done in Python or Lua and you just use C++ for efficiency and the like. Sadly most of the people on this forum won't be coming at it from that angle, so I'm trying to collect information on how you can effectively use coroutines for simulated NPC parallelism while still allowing you to have a game written primarily in C++ and making use of the binding tools available.

ddn3

Apr 20, 2009 at 6:06 PM

This is true, this problem is one of the harder ones in scripting and also very proprietary to your scripting solution. Personally if i was to implement a shared object scheme between Lua and C++ for complex objects like entities, I would use the resource handle approach.

Within a runable script, for it to operate upon any entity or complex object it must explicitly grab it from a given handle. This handle function can throw an exception ( or a Lua assert ) which will cease the execution of the script in a safe and consistent manner. The C++ environment can guarantee that any entity or rsrc grabbed through a handle during the script execution scope will be valid. Once the scope exits it has to regrab it on the next iteration. A little overhead but its worth it.

So several things to note, user doesn't have to write error handling code, that's done automatically through assert and exception handling which wraps the scripts execution. Performance is good since the user can grab an entity/rsrc and operate upon it directly through function bindings, no need for complex asynchronous logic associated with a message based scheme.

For this scheme to work the scripter has to maintain discipline enough to not store raw pointers around but rather use handles, which can be deference through a global manager which can guarantee the objects existence or throw an error to stop the execution of the script in a consistent fashion.

That will probably get you 90% of the way there, but it's hard to say if this scheme will scale. I think it's robust enough for most purposes.

Good Luck!

-ddn

rmtew

Apr 20, 2009 at 8:14 PM

Quote:
Original post by Kylotan
Quote:
Original post by rmtew
I can quite easily implement a workable solution for "invalidate the coroutine" in your given scenario with Stackless Python. I can have that sequence of code in a coroutine terminated, when friend is "deleted".

I think the problem here is that you've been doing this stuff for years and it seems obvious to you, whereas it is new to most people. That's why this thread or some variant of it gets posted here at least once a week for the last 2 years. The people who know how to use coroutines effectively are saying, "to do do this, use coroutines", but aren't explaining how they do it. There's no simple document to direct people to, especially not when it comes to this sort of issue.

But it's not obvious. It's all about knowing the functionality provided by the tools you have available so that you can see how to apply it to suit whatever the situation is. I just thought about what the Python language can do, and ways to apply it.

Quote:
Original post by KylotanThere is a typical expectation on this forum - not necessarily a good one - that you can code an object in C++, then use an automatic bindings generator (eg. SWIG, Boost::Python, LuaBind, etc) to create proxy objects in the language being used for scripting, eg. Python, Lua, &#106avascript, etc. The underlying object can be used as-is.<br/><br/>But this doesn't work well with a naive approach to coroutines. If I have 2 routines that refer to the same C++ object and the C++ object is deleted by one of them, the other coroutine needs notification of this as its proxy object is now likely to be broken. But the original C++ object has no notion of the scripting system or existing in multiple places or any of that. So I'm interested in knowing what people are doing here in practice.</td></tr></table></blockquote><br/><br/>I don't know anyone who is doing this particular thing. I've never done it before in practice. Just because it is possible and it might be the most easily usable approach, does not mean that anyone is actually using it.<br/><br/>Again, the key in my opinion is just knowing what range of functionality you have available and working about how to apply it to suit your needs.<br/><br/><blockquote><span class="smallfont">Quote:</span><table border="0" cellpadding="4" cellspacing="0" width="95%"><tr><td class="quote"><i>Original post by Kylotan</i><br/>Where is the tracking of an object's usage across coroutines taking place?<br/></td></tr></table></blockquote><br/><br/>Make your own tracking or not. Maybe take the easiest approach and just use some sort of tracking system built into your language of choice? It's just knowing what you need and knuckling down and doing it.<br/><br/><div class="source"><pre><code>import gcimport typesimport sysimport stacklessdef FindSomeEnemy(): return otherCharclass SomeObject: def __init__(self, objectName): self.objectName = objectName print "Created object", id(self), objectName def StartApproachAndAttackSummoningAid(self): t = stackless.tasklet(self.ApproachAndAttackSummoningAid)() print "Starting tasklet", id(t) # Do some fake shit where we get the tasklet into # a blocked position holding a reference to some # other object. t.run() def ApproachAndAttackSummoningAid(self): enemy = FindSomeEnemy() print "char found enemy", id(enemy), enemy.objectName print "char blocking" stackless.schedule()def DeletingObject(obj): print "Deleting object", id(obj), obj.objectName # Find all the refering frames. for v1 in gc.get_referrers(obj): if v1 is locals() or v1 is globals(): continue if type(v1) is types.FrameType: for v2 in gc.get_referrers(v1): if v2 is locals() or v2 is sys._getframe(): continue if type(v2) is stackless.tasklet: print "Killing referring tasklet", id(v2) v2.kill()otherChar = SomeObject("otherChar")char = SomeObject("char")char.StartApproachAndAttackSummoningAid()# Take that char, otherChar is getting deleted.DeletingObject(otherChar)</code></pre></div><br/><br/><blockquote><span class="smallfont">Quote:</span><table border="0" cellpadding="4" cellspacing="0" width="95%"><tr><td class="quote"><i>Original post by Kylotan</i><br/>And is terminating the whole coroutine always acceptable? I can imagine wanting to do something more elegant like raise an exception when a proxy object is no longer valid, but again that requires a bit more sophistication in the proxy object than people are used to having.</td></tr></table></blockquote><br/><br/>This is an implementation detail. Discussing this is something that depends on how you want your framework to work more than technical limitations, assuming that the above solution isn't unsuitable or you come up with something else to the same effect.<br/><br/><blockquote><span class="smallfont">Quote:</span><table border="0" cellpadding="4" cellspacing="0" width="95%"><tr><td class="quote"><i>Original post by Kylotan</i><br/><blockquote><span class="smallfont">Quote:</span><table border="0" cellpadding="4" cellspacing="0" width="95%"><tr><td class="quote">Of course, the language the coroutines are provided by, and the framework you've built on top of that language determine the limiting factors in the solutions you can implement.</td></tr></table></blockquote><br/>Most people on this forum will be attaching a scripting language to a pre-existing native-code engine, so the framework will be non-existent. That's why we could do with knowledgeable people sharing their approaches, to know what sort of intermediate structure would be useful.</td></tr></table></blockquote><br/><br/>I would argue there aren't necessarily any such approaches. Just because I can chime in here and say, yes I can come up with an implementation to solve a scenario you describe, does not mean that I've done anything resembling it before. Sure I've used the same tools in different ways, but that's not necessarily related.<br/><br/>Then there's the time requirements. It takes a lot of time and energy to construct a forum post. Do you know what I do when I want to procrastinate? I go read web pages and post on forums. And correspondingly, a lot of the posts on forums like these come across as procrastination to me. Any solution I come up with, anyone who spent the time to learn the functionality available to the Python language and knows a nominal high level amount of Stackless Python should also be able to come up with. If I was one of those knowledgable people, I'd probably veer away from getting involved and knuckle down on my own projects avoiding finding a forum to post questions about it to.

Kylotan

Apr 22, 2009 at 9:04 AM

For many people posting here is an attempt to get assistance from someone more educated or experienced than oneself, in order to avoid wasting lots of time and to learn something, just as if you were to stop programming to read a programming book or take a programming class. Concurrent programming is definitely an area that is far better to learn through education than through trial and error, and cooperative concurrency is an under-taught area as it is. Accordingly, some concrete examples will help people learning about this approach, and I hope to be able to share more with the community in future.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.