The PROC system (AI in Games and Multi tasking, part 4)

So, to recap on what I have been saying so far in this series… the fundamental problem I have with the methods commonly used to implement behavior in games is that they all require, in some way or another, the creation of a virtual computer. And this reason they do this, is because we don’t have language solutions that handle multi tasking properly. It is for this reason that we hear terms such as Hierarchical Finite State Machine (HSFM), and somehow miss the point that your plain old computer system and the common languages used to program them are, in fact, Hierarchical Finite State Machines already. There is a supreme irony to this; we solve our behavior problems in games often using HFSMs, and talk about HFSMs as if they are something special. We also create rather fancy HFSM systems and then call them something else, such as “Behavior Trees”. But, I argue… we should all move along… there is nothing special to see here. All that is happening is that we are creating virtual computing units that are all HFSMs in one form or another. We make many of them in a single game, and figure out how they can influence each other. This is the grand picture of video game development. It’s all loops, switches and if statements, regardless of what fancy name you call them by. Each state is an operation that is no different from a line of code.  Every single line of code, every opcode of the CPU in fact, is just another state.

Because of this I want a programming language that simply allows what one might otherwise cleverly encode into a complex data structure as part of some virtual machine, to be represented directly as code. Alas such a language does not appear to exist; I could use scripting languages but they usually only go so far and anyway, I want to use one language for pretty much everything. If I choose C++ as my language in which to write a game, I want to be able to express the behavior in C++, using straightforward C++ code.  I shall now present my solution to this.

To help understand what I am trying to do here, it might be good to start with an example (I’ll explain what the various pseudo keywords such as _PROC_ and _END_ mean later).

void exec() {
   _PROC_ {
   } _END_;

If you show this to a programmer, they will immediately think of it as a scripting language. However, this is only because of the names of the ‘functions’. Otherwise, it’s just a list of function calls. Look, let’s look at a different example:

void exec() {
   _PROC_ {
   } _END_;

See how in the second example the function calls look like simple calls, simply because of what they are, er… called (ignoring the odd naming convention). The point is that the first example is implying an object that needs to work in its own thread in parallel to other threads because the names of the functions suggest the actions of a game object.

Anyway, looking at the first example concerning a simple action of going to a fridge and getting something to drink, it would seem that we simply can’t write things out that way in C++. Since none of the actions execute instantly, but instead take many frames to complete, we can’t create nice simple function calls. Or can we?  Well… actually we can, if we add a bunch of boilerplate to each of the function calls, using macros. That is why the calls have a specific naming convention, so that it is clear that these are what I call ‘PROCs’. Originally this was simply short for ‘process’, but if you like you can think of them as “Procedural Routines Operating Concurrently”.

I still find this fascinating to think about. My entire codebase is an HFSM which has the current state held in the program counter of the CPU. But then, in order to implement multi-tasking, I need a second program counter. This second program counter is specific to the software thread, and each thread has one. If you think about it, this is precisely what multi-tasking operating systems do; they create separate execution contexts and switch between them rapidly. This requires playing around with the stack, and this playing around has some performance cost. However, the approach here is different. Here we never play with the processor stack at all, but instead create a virtual program counter that magically remembers the current execution state of the thread. Hopefully you can make a connection to the concepts of coroutines I introduced earlier.

This is all fine an dandy, but we need to have a way to cause this virtual program counter to execute a particular line of code, and this is where C++ starts to show its limitations. To understand the problem, we need to consider how, for example, the execution of ‘_WalkToFirdge_()’ works. First of all, the function exec() of the entire listed code block is called every game tick. But while we walk to the fridge, we need to stop calling it. Instead we need to call the exec() of the _WalkToFridge_() proc until it is completed. When _WalkToFridge_() has completed, the exec() of the parent proc starts being called again… but clearly we do not want to execute it from the beginning anymore. If we do, we will be stuck forever walking to the fridge. Instead we need to execute _GrabSoda_(). We need to remember, somehow, to continue execution from the next line… we need to have something like a coroutine.

The experienced programmer out there will by now have figured out that to achieve what we need, we need a way of switching which code is executed according to the state of a variable. If you can’t see why, don’t worry I’m sure it will all become clear as you continue reading. There are many possible solutions to consider here:

  • We can use a switch statement
    • This is the way I standardized on. See below for how it works.
  • We can use function pointers
    • Actually we can’t. You need to change the execution point within a block of code, and that cannot be done by calling a function which takes you out of that code block
  • We can use a series of if statements
    • This is possible as an alternative to the switch statement, but switch statements are heavily optimized for a large number of cases, whereas a series of if statements has to perform a long chain of tests. If statements also reduce optimisation performance generally.
  • We can get the address of a goto label and store that
    • This would be lovely to be able to do. You can on gnu compilers in fact. You can take the address of a goto label and then store it, and later jump to it. Again a really simple idea that could have been in the original C standard, but was not.
    • Alas, this is not a standard C++ feature, for example it is not available on Microsoft compilers
  • We could use setjmp/longjmp
    • This could be used, but it is generally slow because its meant to be used for exception handling. Also, it suffers from the problem that it has to actually execute code at the jump point to get the address of the jump point. This becomes a problem when you want to cause a change in the execution state, for example on receipt of an event or message… you can’t jump to a point in the code you have not previously executed.
  • We could create our own custom inline assembler macros
    • I have played around with this, but clearly this is opening the door to major compatibility issues.
The switch statement is standard across all C++ platforms and compilers. It is the natural solution, but has some problems. The biggest problem is that every single state needs to be ‘named’ in some way and these names must be integers. The result:
switch(_state) {
 case eProcLine1: _state=eProcLine2;  _WalkToFridge_(); break;  
 case eProcLine2: _state=eProcLine3; _GrabSoda_(); break;
 case eProcLine3:
.... etc

We could get somewhere with this… but it would be great if we could get rid of the case labels. We don’t need them. Otherwise it feels like going back to something like programming in basic. Of course we can wrap the boiler plate in a macro… except that we then need to auto generate case labels. How on earth can we do that?

Well, on some compilers there is a macro that increments each time called __COUNTER__, but it is not standard. Originally available on Microsoft compilers, it is now also available on gnu compilers (gcc, etc) as of GCC 4.3.5. What this does is convert to an integer, and increment that integer by one each time it is called. Such a simple idea, but one that some people would ask “Why on earth would you need that”. Well… I can now create a simple macro to wrap all that boilerplate.

#define _WalkToFridge_() _state=__COUNTER__; \
/*--- stuff to add the substate----*/ ; break; \
case __COUNTER__-1:  // it increments even inside a macro call, need -1

switch(_state) {
.... etc

Alas, some issues with this. First, it is not standard C++. Second, we really want a unique ID for the whole macro. It’s not nice that the above solution depends on the order in which __COUNTER__ is, erm… encountered.

The solution I use is one that no doubt make many a grown (and not so grown) programmer weep. But after you get over how cranky it feels, it actually becomes not so bad. Honest. What I do is use the __LINE__ macro instead of __COUNTER__.

__LINE__ returns an integer that is the line number of the source code line in which __LINE__ appears. It is standard, and it will stay the same during a single macro call. It’s actually quite weird to use it this way, but it works without any problems. The only snag, if you can consider it really a snag, is that you have to put each proc call on a separate line.

OK that’s it for this part. In the next part, I will explain the “stuff to add the substate”, that is how a proc calls another proc. It is, after all is said and done, not actually that complicated. It requires, of course, the creation of a virtual stack,

9 Responses to “The PROC system (AI in Games and Multi tasking, part 4)”

  1. Yonathan Says:

    ” (I’ll explain what the various pseudo keywords such as _PROC_ and _END_ mean later) ”

    Will you explain this in a later blog entry or did you forget to add it to this one ? As soon as I’ve got access I’m going to study the PROC system as well but these blog entries are an easier way of understanding it.

  2. Vincent van de Pol Says:

    This post is very close to one of my main motivations for my dissertation. Because of the snapshot nature of a computer screen really, we need to iteratively execute the code, which is the exact opposite of how we would like to code it. We like to code more straightforwardly as you show with the use of Macros and Co-routines. I think this almost forces modularity, which uses ‘transitions’ to switch between them. Transitions in turn need to be managed again in all the fancy architectures we create today. It doesn’t really matter what you call your architecture, it’s all about dynamically transitioning between the states/behaviors/blocks/etc. Then again it’s usually the high level concept of an architecture that changes the mindset of a programmer, which is most likely a bigger contributor to the “better” code that is produced.

  3. gaz Says:

    This stuff is pretty easy to implement without the need for any macros.

    There’s no docs, I’m part way through writing an article that I’m going to submit to AltDevBlogADay

    But if you look in the examples dir all you need to do to hand control back to the tasker is call the sleep() function.

    That code works on the mac. There’s only 1 machine dependant routine you need to supply for it to work on other machines. The code has been used on released games for PC, PS1, Saturn, X360, PS3. I also use it myself on IoS

    It’s more up front cost macros but longer term a bit easier to write your code with.

    Cheers 🙂

    • Dino Dini Says:

      I will need to investigate your solution, but looking at it briefly your solution appears to rely on operating system threads. That has a few problems: 1) It is not portable, 2) Potentially it is inefficient 3) The sleep function causes a thread to sleep for a certain amount of time, so it seems to still be preemptive, not cooperative multitasking. It is unclear how you prevent the OS from switching between threads without “yielding”. The result will be non determinisatic behavior which is not good for game AI. Additionally, it is not clear to me how by itself this system allows for changes of the execution point of a thread on receipt of a message. So I do not think the solution you present and mine are comparable. I will write more on this topic later, I have not completed this series.

  4. gaz Says:

    It does not rely on OS threads.

    It’s a single thread co-operative tasker so there’s no issue with interfering with OS’s own scheduler.

    You can repoint a task to another routine pretty easily (though isn’t exposed to in the C++ wrapper class) but you have to be aware of the potential side issues of this.

    If you have an classes declared on your task’s stack they will not destruct.

  5. gaz Says:

    To be clear (which without documentation it isn’t) the sleep function is a member of the Taskable class, not the OS sleep function 😀

    • Dino Dini Says:

      I would want more information on how the sleep is implemented. It uses TSK_Sleep which I thought was a platform specific/OS call… I’ll look into it when I get the chance.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: