Re: Game Logic

[Pierre Phaneuf <pp@ludusdesign.com>]

Chris Purnell wrote:

> > A directed graph is good for runtime optimization. The same thing can be
> > done with an array of instructions, just slower (moving blocks of
> > instructions around instead of just changing pointers).
> 
> What run time optimization are you talking about?
> 
> I know about pruning constant expressions form parse trees.

That's the kind of things it does, but it does others. I don't have the
Advanced Perl book handy, but it discuss the various optimizations done.

> If I were writing it I would parse the source script into a tree
> structure, then do the optimization.  If I wanted to execute it then
> and there I do a tree walk executing using recursion.   If I wanted
> to save some sort of byte code for execution later I would save the
> nodes in reverse polish order.  Later they would be executed using
> iteration and some sort of evaluation stack.

Perl executes in a similar way. Recursion is not a good idea by the way,
you should try to avoid it, at least during execution. I think Perl
works this way: there is an execute_node kind of function, which returns
a pointer to the next node to execute. No recursion this way and very
nice, simple code (this execute_node function could be a virtual method
in a C++ object for example).

I would store nodes using serialization (using a visitor pattern to
avoid recursion, parse trees are often quite deep!), and reload them
back as a tree structure (wouldn't require two different executors).

> Others may do things differently.

Of course.

> But the point is that the discussion will be based upon the following:
> 
> 1. Do I want to include the parsing of the script source into my game
> or do I want to have external "byte code" compiler.

You might way to have parsing in the game if you want to support an
"eval" function or a lambda function (to do closures for example).

> 2. Will the easier to implement iterative solution cause problems later.
> Such as stack usage or trying to break out from the execution (eg on an
> error).

Funny, I don't really see the iterative solution as easier to implement.
Or do you mean iterative as in non-recursive? (I am thinking "array of
instructions") See this:

void run_tree(ParseNode* tree) {
   while(tree) {
      tree = tree->execute();
   }
}

(simplified, of course, but not that much)

> > Also, higher level instructions generally have a greater chance of
> > having complex parameters (Pentium instruction is high level enough for
> > that!), so this is longer to decode, and when optimizing you have to
> > find out the length of all the instructions before doing the (expensive
> > by itself) move.
> 
> No, those a low level instructions. The high level instructions
> appropriate for the execution of a scripting language would get
> their parameters in a simple and constant way.  Such as from
> the child nodes of your directed graph or from the top of an
> evaluation stack.

What? Pentium instructions are low level? Did you look at the
instructions in the Java VM or the Quake VM? The Quake VM is x86-like,
and the Java VM is even worse, being RISC-like! I mean low and high
level for machine instructions like RISC and CISC. "Perl high level"
would be "ultra CISC"! ;-)

Yes, from the nodes of directed graph is what I'm suggesting as easier.
But some people suggest using blocks of VM code similar to blocks of
executable binary x86 code. If the VM operators are high-level enough,
the instructions will most probably be complex (CISC-like) and would
require more complicated decoding because of the varying length.

As for stack-based vs. register-based executors, consider these two
implementations of "c = a + b":

push a
push b
add
pop c

and:

load a, #1
add b, #1
store #1, c

The first one has 9 memory access (the "add" has two fetchs and one
store, and push/pop have one fetch and one store) and the second one has
3 (and one less instruction). Can you guess which one is faster? ;-)

> > A directed graph executor benefits a lot from having
> > same-sized nodes, but it can shove a pointer to additionnal parameter
> > information without copying stuff around or being variable-sized itself.
> 
> The same is not only true of virtual machines but of many real RISC
> processors.

Yes, but the same-sized instruction/node and the tree vs. instruction
list things are two separate things. RISC processors have this
same-sized instruction advantage, but do not have the tree advantage
(would be really useful for out-of-order processors, they could save
their reordering information for later!). Some very old machines had a
pointer attached to every machine instruction, telling where the next
instruction was. I think Intel's IA-64 has something similar (ohh, the
innovation).

> Anyway this all implementation.  This is something I know about.
> What I don't know is what language I should use.  I have ruled
> out using an existing script interpreter.  Not only because
> their languages don't have the one feature I know I need
> (A native vector type) but also because I want to execute
> the script in a controlled and secure environment.

Controlled and secure environment? What do you mean exactly? Beside the
fact that you can add a high-performance vector type that would look as
native as anything else to Perl, you can also block out some operations.
I think you can even redirect them to your own code (if you want to do
checking before execution).

This is all discussed in the Advanced Perl book (the panther book). I
heartily recommend this book even if you're not going to use Perl as
your interpreter. It discusses the internal workings of a real (and
really good) interpreter, and it very well written.

> How should the scripting language relate to the actual objects
> in the game?  I'm of the opinion that any OO aspects of the
> language should relate directly to the objects in the game
> but how should this be done?

For your other questions, and more particularly the OO ones, check out
UnrealScript:

http://unreal.epicgames.com/UnrealScript.htm
http://unreal.epicgames.com/Network.htm (related to UnrealScript)
http://unreal.epicgames.com/CppObjects.htm (also related)

That said, while Tim Sweeney is quite brilliant most of the time, he has
some strange ideas about a few things (that's why IMHO Quake3 is
(arguably) faster and better, Carmack is more pragmatic: he tries out
all the ideas he can think of or "get his mind on" and keep the good
ones, Sweeney has good ideas and some bad ones and just uses them).

-- 
"If you want to travel around the world and be invited to speak
at a lot of different places, just write a Unix operating system."
 -- Linus Torvalds

---------------------------------------------------------------------
To unsubscribe, e-mail: linuxgames-unsubscribe@sunsite.auc.dk
For additional commands, e-mail: linuxgames-help@sunsite.auc.dk