Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Coroutines

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Coroutines
David Couzelis
Member #10,079
August 2008
avatar

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. ;D

Does C or Allegro provide an easy way implement coroutines? Or, more generally, how do you go about scripting an enemy or event?

kenmasters1976
Member #8,794
July 2007

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.

bamccaig
Member #7,536
July 2006
avatar

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. :P

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).

Peter Hull
Member #1,136
March 2001

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)

David Couzelis
Member #10,079
August 2008
avatar

bamccaig said:

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.

Quote:

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

Erin Maus
Member #7,537
July 2006
avatar

Coroutines are great. ;D

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

---
ItsyRealm, a quirky 2D/3D RPG where you fight, skill, and explore in a medieval world with horrors unimaginable.
they / she

RmBeer2
Member #16,660
April 2017
avatar

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.

🌈🌈🌈 🌟 BlackRook WebSite (Only valid from my installer) 🌟 C/C++ 🌟 GNU/Linux 🌟 IceCream/Cornet 🌟 🌈🌈🌈

Rm Beer for Emperor 2021! Rm Beer for Ruinous Slave Drained 2022! Rm Beer for Traveler From The Future Warning Not To Enter In 2023! Rm Beer are building a travel machine for Go Back from 2023! Rm Beer in an apocalyptic world burning hordes of Zombies in 2024!

David Couzelis
Member #10,079
August 2008
avatar

Erin Maus said:

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'.

RmBeer2 said:

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?

bamccaig
Member #7,536
July 2006
avatar

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? :P Or it would be if it wasn't buggy. r1() returns 0 so the while exits after just the one call. :D 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.

Audric
Member #907
January 2001

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.

bamccaig
Member #7,536
July 2006
avatar

RmBeer2
Member #16,660
April 2017
avatar

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. :)

🌈🌈🌈 🌟 BlackRook WebSite (Only valid from my installer) 🌟 C/C++ 🌟 GNU/Linux 🌟 IceCream/Cornet 🌟 🌈🌈🌈

Rm Beer for Emperor 2021! Rm Beer for Ruinous Slave Drained 2022! Rm Beer for Traveler From The Future Warning Not To Enter In 2023! Rm Beer are building a travel machine for Go Back from 2023! Rm Beer in an apocalyptic world burning hordes of Zombies in 2024!

Erin Maus
Member #7,537
July 2006
avatar

bamccaig said:

Erin: The code for ItsyRealm is also amazingly well organized and clean. :o 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. ;D

---
ItsyRealm, a quirky 2D/3D RPG where you fight, skill, and explore in a medieval world with horrors unimaginable.
they / she

bamccaig
Member #7,536
July 2006
avatar

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...

#SelectExpand
1#include <stdio.h> 2#include <stdlib.h> 3 4typedef enum { 5 CO_ERROR = -1, 6 CO_DEAD = 0, 7 CO_SUSPEND = 1, 8 CO_RUNNING = 2 9} costatus; 10 11struct coroutine_t; 12typedef struct coroutine_t coroutine_t; 13 14typedef void * (*coroutine_f)(coroutine_t *); 15typedef void (*destroy_userdata_f)(void **); 16 17struct coroutine_t { 18 coroutine_f routine; 19 destroy_userdata_f destructor; 20 costatus status; 21 int step; 22 void * retval; 23 void * userdata; 24}; 25 26void * start_coroutine( 27 coroutine_t ** coroutine_p, 28 coroutine_f routine, 29 destroy_userdata_f destructor, 30 void * userdata) 31{ 32 coroutine_t * coroutine = *coroutine_p = 33 (coroutine_t *)malloc(sizeof(coroutine_t)); 34 35 if (coroutine == NULL) 36 { 37 return NULL; 38 } 39 40 coroutine->routine = routine; 41 coroutine->destructor = destructor; 42 coroutine->status = CO_RUNNING; 43 coroutine->step = 1; 44 coroutine->retval = NULL; 45 coroutine->userdata = userdata; 46 47 return routine(coroutine); 48} 49 50void * yield_coroutine(coroutine_t * coroutine, void * retval) 51{ 52 if (coroutine->status <= CO_DEAD) 53 { 54 return NULL; 55 } 56 57 coroutine->status = CO_SUSPEND; 58 coroutine->retval = retval; 59 60 return retval; 61} 62 63void * resume_coroutine(coroutine_t * coroutine) 64{ 65 if (coroutine->status <= CO_DEAD) 66 { 67 return NULL; 68 } 69 70 coroutine->status = CO_RUNNING; 71 coroutine->step++; 72 73 return coroutine->routine(coroutine); 74} 75 76void * end_coroutine(coroutine_t * coroutine, void * retval) 77{ 78 if (coroutine->status <= CO_DEAD) 79 { 80 return NULL; 81 } 82 83 coroutine->status = CO_DEAD; 84 coroutine->retval = retval; 85 86 return retval; 87} 88 89void * error_coroutine(coroutine_t * coroutine) 90{ 91 coroutine->status = CO_ERROR; 92 coroutine->retval = NULL; 93 return NULL; 94} 95 96void destroy_coroutine(coroutine_t ** coroutine_p) 97{ 98 coroutine_t * coroutine = *coroutine_p; 99 100 *coroutine_p = NULL; 101 102 if (coroutine != NULL) 103 { 104 if (coroutine->destructor != NULL) 105 { 106 coroutine->destructor(&coroutine->userdata); 107 } 108 109 free(coroutine); 110 } 111} 112 113const char * status_str_coroutine(coroutine_t * coroutine) 114{ 115 switch (coroutine->status) 116 { 117 case CO_ERROR: 118 return "error"; 119 case CO_DEAD: 120 return "dead"; 121 case CO_SUSPEND: 122 return "suspend"; 123 case CO_RUNNING: 124 return "running"; 125 default: 126 return "undefined"; 127 } 128} 129 130void * r1(coroutine_t *); 131void * r2(coroutine_t *); 132 133typedef struct { 134 coroutine_t * r2p; 135 long args[2]; 136 long result; 137} r1state; 138 139void cleanup_r1state(void ** userdata) 140{ 141 r1state * state = *(r1state **)userdata; 142 143 *userdata = NULL; 144 145 if (state != NULL) 146 { 147 destroy_coroutine(&state->r2p); 148 149 free(state); 150 } 151} 152 153void * r1(coroutine_t * coroutine) 154{ 155 r1state * mystate = NULL; 156 long * args = NULL; 157 long arg = 0; 158 long ret = 0; 159 160 //fprintf(stderr, "DEBUG\tExecuting r1 step %d\n", coroutine->step); 161 162 switch (coroutine->step) 163 { 164 case 1: 165 arg = (long)coroutine->userdata; 166 mystate = (r1state *)malloc(sizeof(r1state)); 167 168 if (mystate == NULL) 169 { 170 return error_coroutine(coroutine); 171 } 172 173 coroutine->userdata = mystate; 174 175 args = (long *)&mystate->args; 176 args[0] = arg; 177 args[1] = 10; 178 179 ret = (long)start_coroutine(&mystate->r2p, r2, NULL, (void *)args); 180 181 if (mystate->r2p == NULL || mystate->r2p->status == CO_ERROR) 182 { 183 return error_coroutine(coroutine); 184 } 185 186 fprintf(stderr, "DEBUG\tr2(%ld, %ld) yielded %ld\n", args[0], args[1], ret); 187 188 mystate->result = ret * 3; 189 190 return yield_coroutine(coroutine, (void *)mystate->result); 191 case 2: 192 mystate = (r1state *)coroutine->userdata; 193 194 args = (long *)&mystate->args; 195 args[0] = mystate->result; 196 args[1] = 10; 197 198 ret = (long)resume_coroutine(mystate->r2p); 199 200 if (mystate->r2p->status == CO_ERROR) 201 { 202 return error_coroutine(coroutine); 203 } 204 205 fprintf(stderr, "DEBUG\tr2(%ld, %ld) yielded %ld\n", args[0], args[1], ret); 206 207 mystate->result = ret * 5; 208 209 return end_coroutine(coroutine, (void *)mystate->result); 210 } 211 212 return error_coroutine(coroutine); 213} 214 215void * r2(coroutine_t * coroutine) 216{ 217 long * args = coroutine->userdata; 218 219 //fprintf(stderr, "DEBUG\tr2 args: [%ld, %ld]\n", args[0], args[1]); 220 221 long result = args[0] * coroutine->step + args[1]; 222 223 return yield_coroutine(coroutine, (void *)result); 224} 225 226int main(){ 227 coroutine_t * coroutine = NULL; 228 229 long result = (long)start_coroutine(&coroutine, r1, cleanup_r1state, (void *)5); 230 231 if (coroutine == NULL) 232 { 233 fputs("Failed to start r1 as a coroutine! Out of memory?", stderr); 234 return 1; 235 } 236 237 while(1) 238 { 239 if (coroutine->status == CO_ERROR) 240 { 241 fputs("Failed to execute r1 as a coroutine! Out of memory?", stderr); 242 return 1; 243 } 244 245 printf("r1(5) yielded %ld\n", result); 246 247 if (coroutine->status == CO_DEAD) 248 { 249 break; 250 } 251 252 result = (long)resume_coroutine(coroutine); 253 254 fprintf(stderr, "DEBUG\tResumed coroutine now has status '%s'.\n", status_str_coroutine(coroutine)); 255 } 256 257 destroy_coroutine(&coroutine); 258 259 return 0; 260}

(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'.

Erin Maus said:

Haha, you're being too nice. But I like to think it's pretty good code, especially for a video game. ;D

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. :P

dthompson
Member #5,749
April 2005
avatar

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.

______________________________________________________
Website. It was freakdesign.bafsoft.net.
This isn't a game!

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

{"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"}1522023_690817180949038_1062062659_n.jpg
Just use a f'ing thread and be done.

_jagged
Member #17,124
September 2019

I'm no expert, by any means, but couldn't all this be done with pthreads? Mutexes, condition variables?

dthompson
Member #5,749
April 2005
avatar

_jagged said:

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. ;)

______________________________________________________
Website. It was freakdesign.bafsoft.net.
This isn't a game!

bamccaig
Member #7,536
July 2006
avatar

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.

amarillion
Member #940
January 2001
avatar

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.

#SelectExpand
1#!/usr/bin/env node 2function *fibonacci() { 3 let a = 1, b = 1; 4 while(true) { 5 yield a; 6 [a, b] = [b, a + b]; 7 } 8} 9 10console.log("It's planning poker time!") 11let i = 0; 12for (const f of fibonacci()) { 13 if (++i > 8) break; 14 console.log(`Team member ${i} estimates: ${f}`); 15}

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 :P

bamccaig
Member #7,536
July 2006
avatar

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.

Polybios
Member #12,293
October 2010

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.

bamccaig said:

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 ???

bamccaig
Member #7,536
July 2006
avatar

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.

Erin Maus
Member #7,537
July 2006
avatar

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.

---
ItsyRealm, a quirky 2D/3D RPG where you fight, skill, and explore in a medieval world with horrors unimaginable.
they / she

bamccaig
Member #7,536
July 2006
avatar

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.

 1   2 


Go to: