Hi, all! So, I recently started trying game development in Lua. It's been fun! But when I learned about "coroutines" it absolutely blew my mind! I'd never heard of them before. I've been wanting something like this for decades!
For those who don't know, coroutines are best summed up as "functions with state". An example use is to script an enemy movement in a simple manner.
https://en.wikipedia.org/wiki/Coroutine
Even though Lua has been fun, C and Allegro are my true passion.
Does C or Allegro provide an easy way implement coroutines? Or, more generally, how do you go about scripting an enemy or event?
While Allegro doesn't have native support for coroutines, it supports threads and event loops so I think it might be possible to implement a coroutine system using these.
Or, more generally, how do you go about scripting an enemy or event?
In my game, I'm using a basic state machine system inspired by MUGEN. While it's not multithreaded, I guess it could be possible to adapt it to use threads and make it work in a coroutine fashion.
I failed to understand what coroutines even meant in the past, but I gave it another try and I think this time I get it. It sounds like the key idea of coroutines is that they are like functions/routines that can yield (surrender) control to another (presumably related) coroutine, and the other coroutine can yield control back again (but at its leisure and choice, or it can yield to a completely different one presumably).
There's no implicit threading/parallelism going on here. The switch can happen with jumps. However, synchronization is implied. If one coroutine is executing the other is either not running or suspended. And if you happen to implement coroutines in a way that does utilize parallelism them you may be sacrificing some of the qualities that made coroutines useful to begin with. Or something like that.
Obviously you can implement coroutines in C or C++, but I think you would face certain limitations, like either having a very verbose function call signature that varies or perhaps having some limited number of supported arguments implemented through C++ templates or only supporting arguments through some kind of dynamic type+data passing or something like that (really breaking out of a lot of the benefits of C to trade for other benefits).
Theoretically you could use regular C or C++ functions passed into a special "manager" function that interprets special return values as context switches, but they would have to be implemented sort of like a switch statement or else-if ladder I think (or just implemented as separate functions). It would probably be easiest to do this with a code generator that ran before you compiled your code. Either way, I think you end up having to implement some sort of new or extended language (if not going outright up a level of abstraction).
Sometimes coroutines are implemented with threads to keep things simple, but you pay for it in speed because yielding between coroutines requires overhead to unblock and block threads.
Append:
I guess the ideal coroutine would be implemented as a single function in C that could goto appropriate places while maintaining state all while running any of its coroutines.
I'm fuzzy on exactly how coroutines end, or if they necessarily do, and if coroutines can exist that interact with webs of others. This could obviously get very complicated regardless of how you implement it... But it is a neat concept. I think it only adds a tiny bit of value though so coming up with an implementation that is worth using would be challenging.
In fact, I'm sure if it could be done, it would have been by now so start by searching for existing solutions before hammering your own square wheel.
I'm also wondering whether multiple "invocations" of a coroutine are meant to be possible or if there can only be one instance in the entire application. You could easily accomplish the persistent state with static variables, but only if the coroutine is effectively a singleton (which to my mind makes it nearly useless, but perhaps its need is sufficiently rare to make it adequate).
The wikipedia entry is pretty thorough on descriptions and implementations.
Ages ago I used this one for C, if you look at the example, the API is pretty straightforward IMO.
I always thought coroutines looked like a great idea, and surely would be better than the "callback hell"/futures/async-await that we have in JS now, but I guess there must be some practical reason they haven't become widespread. They're even implemented natively in Windows (as Fibers)
how coroutines end
So, my only experience with coroutines so far is with Lua in the PICo-8 gaming environment. It involves sending the coroutine function that I create to "cocreate()", calling "coresume()" from outside the function when you want it to run, and calling "yield()" from inside the function when you want it to pause. A coroutine can be in one of three states: running, suspended, dead. If it gets to the end of the function it's dead, and trying to resume a dead coroutine will result in an error. Because of the nature of garbage collection in Lua, a dead coroutine / variable will eventually just be cleaned up.
whether multiple "invocations" of a coroutine are meant to be possible or if there can only be one instance in the entire application
Great question! Yes, multiple coroutines can exist! I created a test application here. It creates four Pac-man style "ghosts" that run in circles around the screen, each with their own instance of the same coroutine. See the function "control_coghost()".
https://github.com/drcouzelis/pico-8/blob/master/carts/coghosts.p8
Coroutines are great.
I use them in the dialog for ItsyRealm. Take this one for example: https://github.com/erinmaus/itsyscape/blob/master/itsyscape/Resources/Game/Peeps/Sailors/Nyan/NyanRecruit_en-US.lua
A message and select command both yield until the player interacts with the dialog. It's nifty!
You can use coroutines in C++ with Boost.Coroutine: https://theboostcpplibraries.com/boost.coroutine
My better answer:
#include <stdio.h> int(*fcall)(); int r1(); int r2(); int r1(){ printf("Routine 1\n"); fcall=r2; return 0; } int r2(){ printf("Routine 2\n"); fcall=r1; return 0; } int main(){ fcall=r1; while(fcall()); return 0; }
I haven't tried it yet, but it should work. The callback functions always is nice.
EDIT:
I'm using it all the time too, I guess. After all these years, just now I find out that it is called coroutines.
I use them in the dialog for ItsyRealm.
That's a perfect use for them! Just kinda waiting around for the "next thing" to happen, but gotta keep that game loop loopin'.
My better answer
I don't quite understand your example... A coroutine allows a function to "leave and come back" while preserving the state. Can that happen in your example?
No, RmBeer2's example isn't a proper coroutine because it cannot suspend and resume. It's really just a fancy infinite toggle I guess? Or it would be if it wasn't buggy. r1() returns 0 so the while exits after just the one call. That's kind of what I meant by "impossible".
Though I suppose if you were to resort to assembly perhaps you could implement your own stack handling to save the stack frame into the functor's state and then unwind the frame and jump out, but be able to restore the old frame afterward to continue where it left off? I guess theoretically something like that is possible. And very neat.
Coroutines are great for controlling sprites in a 2D game. I made the whole game behavior of Vigilante with them, and an incomplete platform shooter that I can't find at the moment.
There is a way to program this way in C (and better in C++, because then coroutines can access the instance's fields), but it's very hackish, so I'm not sure I'd recommend it. The limitations are :
- local variables will not be preserved between two yields. You'll have to use instance fields instead, or whatever storage you have for per-object data.
- loop structures for/do/while will "not work" if they contain a yield, because the hack makes use of the 'break' instruction, and the loop blocks will prevent those breaks to reach their intended target. You have to use gotos instead.
If you're curious, there is a "famous" article Coroutines in C, which builds up on a construct called Duff's device
Once again, it's probably more of a curiosity than a good practice. Coroutines are a good reason to move a lot of game behavior and data to a Lua component.
Erin: The code for ItsyRealm is also amazingly well organized and clean. You are a God among mortals.
Like I said, I haven't tried it.
This code can certainly keep the states, return the result, exit and return.
You just have to put more code in the middle. I have only created it with the intention that everyone already knows.
The function can keep itself or change to another function, it can return any value, and in the while() line it can continue or break the loop, or execute more series of lines inside the while.
States can be maintained with top-level variables, global variables or in static variables within the function.
And maybe much more.
Erin: The code for ItsyRealm is also amazingly well organized and clean. You are a God among mortals.
Haha, you're being too nice. But I like to think it's pretty good code, especially for a video game.
This is perhaps a more complete system. It sort of "works", but obviously the coroutine function needs to be carefully coded to save its state on the heap and (if necessary) change the logic each time it is executed. I think that's about as good as you can get in C without assembly to manipulate the stack...
(Fixed memory leaks, maybe!)
Output:
DEBUG r2(5, 10) yielded 15 r1(5) yielded 45 r1(5) yielded 500 DEBUG r2(45, 10) yielded 100 DEBUG Resumed coroutine now has status 'dead'.
Haha, you're being too nice. But I like to think it's pretty good code, especially for a video game.
Especially for a video game. That thing is better organized than 99.999% of projects of sufficient complexity, even counting business and popular open source projects.
I always thought coroutines looked like a great idea, and surely would be better than the "callback hell"/futures/async-await that we have in JS now, but I guess there must be some practical reason they haven't become widespread.
I'd imagine (but am by no means sure) this is because - like JS - you'd need (a) an event loop runtime, and (b) some new keywords (for less clunkiness).
That said - for an established language - I reckon Python's implementation is pretty neat.
{"name":"1522023_690817180949038_1062062659_n.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/2\/d24b1cc4287b7e49ccf832dbb4612fbe.jpg","w":960,"h":927,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/2\/d24b1cc4287b7e49ccf832dbb4612fbe"}
Just use a f'ing thread and be done.
I'm no expert, by any means, but couldn't all this be done with pthreads? Mutexes, condition variables?
I'm no expert, by any means, but couldn't all this be done with pthreads? Mutexes, condition variables?
Absolutely - but it's a very different way of programming. You might choose coroutines over threads because you don't want to worry about thread-safety or deadlocks. However, the latter's only going to go away if you remember to yield. Windows 3.1 anyone?
Or you may just be a JS programmer and have no choice.
Synchronizing threads is complicated and error prone. Coroutines have nothing to do with parallelism (threads). In general, they are not parallel, but still concurrent. In other words, they're synchronized with one another. One executes, and the caller doesn't continue until the first yields control.
You can implement coroutines with threads, but you essentially have to synchronize your threads in such a way that only one is awake and running at a time so it kind of defeats the purpose of threads. Threads are the expensive way to implement coroutines because the context switches and the threads themselves come at a cost.
The point of coroutines is that they can essentially return and resume where they left off to return again and again. This enables some design patterns that would be difficult to do otherwise.
JavaScript's callbacks are nothing more than function pointers to invoke when something happens. The same pattern exists in C or C++ and every other language... It's an essential part of functional programming too, and JavaScript is inspired in part by Lisp IIRC. It's a very useful and powerful feature of any language to support.
You don't have to do things with callbacks in JavaScript. JavaScript is just influenced by functional programming and its nature of having to synchronize and talk to the native UI code means that callbacks were just the best, if only, way to solve event handling in JavaScript.
Either you let your JavaScript engine run a damn slow event loop, or you register JavaScript functions to execute by the native code when an event occurs, blocking the UI until the JavaScript completes.
Same here - I've always thought co-routines are awesome! They make it much easier to code NPC logic.
In essence, co-routines have nothing to do with multi-threading at all. What co-routines are, is a nicer way to program a state machines. When a co-routine yields, the "state" of the NPC is saved on the stack until the co-routine is invoked again on the next update cycle.
In the end, the extra work to embed Lua never seemed to pay off, at least not during a game jam. I've always managed to make do with a regular state machine in C++. Using multi-threading to achieve this is definitely not worth the head-ache.
But, on a different note: lately I've been enamored with JavaScript generators, which are very similar to co-routines. Some of the games I make nowadays are in JavaScript, so I can enjoy all the co-routine goodness. E.g. look below at how the fibonnacci co-routine yields and is then re-invoked, potentially infinitely.
I always thought coroutines looked like a great idea, and surely would be better than the "callback hell"/futures/async-await that we have in JS now, but I guess there must be some practical reason they haven't become widespread.
So yeah.... JS already has them
Wikipedia describes generators as semi-coroutines, or a subset of coroutines. The claim made in the article is that generators cannot "yield" to a different generator/"coroutine". Though for all intents and purposes I'm not sure how invoking a generator from inside of another generator is any different. I suppose what isn't really possible is a set of cooperating generators that feed off of one another? I don't know, that part kind of lost me.
When a co-routine yields, the "state" of the NPC is saved on the stack until the co-routine is invoked again on the next update cycle.
I thought of coroutines as execution stacks. And yield is kind of a way to say "Leave this stack as it is and stop here", a weird inner meta-return. Like setting a breakpoint in a debugger and then continuing later.
I think that's about as good as you can get in C without assembly to manipulate the stack...
I've never used them, but could setjmp and longjmp help here
I don't think setjmp/longjmp can solve the problem on their own. There are local variables stored on the stack that will no longer exist after the function returns. These need to be carefully stored and restored later when you jump back into the function. It's not a simple thing to solve on bare metal. It's much easier to implement within the language/compiler/runtime itself. Perhaps it could be accomplished in part with preprocessor macros to generate code for copying/restoring data using some global store, but I think it would be flaky at best.
There's fibers & such for C++ (see Boost Coroutines or Win32 fibers), you can do it from C/C++ relatively easily. I used Boost Coroutines in a bot for a video game, they worked nicely.
Strictly speaking I think that the underlying setcontext family of functions used to implement fibers in Unix-likes is doing the stack manipulation internally (so nothing changed, except somebody else did the hard work?). Also, apparently the C standard has obsoleted features required by this library to achieve its goals.
It sounds like Windows might be implementing them on top of threads, which would again imply costs associated with their usage.
Nevertheless, it does look like these concepts would make coroutines much more feasible in C for platforms that supported the ucontext.h library or fibers in general. But I'm sure mileage will vary.
Windows doesn't implement them on threads.
I made that assumption based on the ConvertThreadToFiber function. And it sounds like that's the only way to execute a fiber, though I may be wrong about that. I don't care to delve too deep into the Windows library (gross). Nevertheless, they seem to have their fiber implementation tied to threads, even if not in the same way that I assumed.