Hierarchical Nodal Logic for Blender 2.5

This project is the continuation of the Robotics iTaSC project. iTaSC produces an instantaneous response to a set of constraints but this is not sufficient to obtain a complex behavior. There is a need for a logic layer that selects and controls the constraints so that the robot performs a complex task. This project consists in allowing the easy implementation of such task layer.

Logic is not specific to Robotics, so we can leave the robotic domain for a moment and try to address the problem of creation of a logic setup in the most general case.

Current Situation

The game engine in 2.49b has a GUI for logic creation: the Logic Bricks system. But it has several limitations:

It is very difficult to see the logic as a whole when it gets a little complicated. Also the logic is not presented in a confortable form: the sequence of actions are not easily visible.
The state system is the only level of hierarchy available and that's insufficient for complex logic.
A game is always a dodgy mix between Bricks and Python:
- Python access to game engine features is incomplete; you cannot get away from using some logic bricks, possibly inefficiently, if you want to create a 'only python' application.
- Logic brick access to game engine features is incomplete; you cannot get away from using some Python code if you want to implement a complex logic.
Logic Bricks are not easily extendible: you must code in C and modify Blender to create a custom brick.
Logic graphs are not reusable: you cannot create a library of logic graphs and apply them to multiple objects. This is because Logic Bricks are closely attached to objects.

The goal

This project will try to address all the limitations of Logic Bricks by providing a system that's easy to use, extensible, hierarchical, efficient, complete and reusable.

Let's explicit these requirements:

Easy to use: We want a graphical logic editor. The strength of graphical logic programming versus coding is sufficiently well established to justify the use of a graphical editor. To limit the development effort, our choice goes to the Blender's Node editor.
Reusable: This means that the creation of a logic graph is independent of the object or group of objects on which it will be used. Ultimately this allows to build, distribute and use libraries of logic graphs.
Hierarchical: We want nested logic graphs. This is a fundamental requirement if we want to maintain clarity in the logic setup at different levels. The lack of hierarchy in logic graphs is a typical limitation of the existing graphical logic editors.
Complete: We don't want to limit the programming model to one particular style. To be future proof, this system should allow any type of programmation: imperative programming, dataflow programming, state engine, hierarchical state engine, protocol stack, etc.
Extensible: It must be accessible to everyone to create new nodes, for their own use or for distribution. The creation of new nodes should not require the recompilation of Blender or any change in the .blend file format.

Although the primary target is the game engine, we want to keep it sufficiently general so that it can be applied with minimal efforts to Blender for a variety of tasks such as animation, scene creation, etc.

Conceptual Example

A simple example is shown below. This example closes door 5 if it is open with a swish when the player is walking close to lever 5 and presses the spacebar. If the door is closed, it opens it and changes the status of the lever. In addition, the little noodle can easily be made into a group, and thus copied and modified for other levers and doors in the same or future games. Yes, I love TombRaider, and even have the old Blender Sphinx model.

Concept Example

Please note that this concept of the nodes used may not be the most efficient, and my behind-the-scenes description may not be accurate. My intent is to show how a node-based network may work and allow game engine programming via nodes, instead of solely relying on text-based code. Behind the scenes, when gameplay starts, the value 5 is fed to a string concatenate node that converts the 5 to a string and makes the string "Lever5", and feeds that to three other nodes: a PropertyGet node as the Object name, a PropertySet, and another PropertyGet. These nodes take the value but don't actually do anything until asked for a value. Similar processing happens to make "Door5" which is fed the PlayAction node as an Object name.

The OnChange node sets up an Event monitor that watches the Avatar Location. When the Avatar Location changes, it sends that location to the Proximity node. The Proximity node asks the PropertyGet for a value, and it gets the current location of Lever5, and returns that to the Proximity node. If the two locations are within +/- 4 X units and +/- 3 Y units and have the same Z value, Proximity sends a Logic True pulse to the And. The And asks PropertyGet for a value. PropertyGet gets the current Status value of Lever5 and returns it to the And function. And also requests the current keypress to be processed. If the key is a space and the Status=="Open", it sends a Logic True out to PlayAction, PlaySound, and PropertySet. PlayAction causes the BGE to play back the Door Close action. PlaySound plays back the DoorSwish sound (was this preloaded when gameplay started? probably so if resources permit). Lastly, the Status of Door5 is set to Closed.

Why Nodes?

After reviewing some of the most popular graphical logic editors in the market and consulting with other Blender devs and users, we came up with a Nodal Logic design. Various well-established analogies include: flowcharting, data flow diagrams, and integrated circuit design methods. The pattern we want to use is Blender's Node Editor, where we have a set of connected nodes in a tree-type of structure (a "noodle"). Inputs feed data and events into the noodle, where it is processed and results in changes relayed out through output nodes. Inputs can be taken from, for example, a Wii remote, a joystick, the keyboard or motion sensors. Processing can include any number of math functions, scene functions (object create/destroy, play actions and animations, get/set a variable or property). Outputs can be relayed to set a property, write to a file, or send a value to an output port (for example, controlling a robot), or write to a log file through a file output node.

This is not the only possibility but a well-designed Nodal Logic system can fulfill all the requirements stated above better than any other system. The key features are re-usability and hierarchy. If well used, the hierarchy of Logic graph will provide the separation of tasks, programmatic capability and state engine support that is needed for a complex logic development. We should be able to group nodes into logical processing units, and be able to append/link node groups as well.

Using Blender Node Editor

Since this is a node-based system, it makes sense to re-use Blenders Node Window, and just grow the Mat-Tex-Compo list to include a Game Logic context.

The current Node Editor doesn't support many of the requirements stated above. Quite a lot of modifications will be necessary before it can be used for Game Logic but we think that the existing code base is sufficient to justify its use.

Re-using Node Groups

In the concept example above, notice how easy it would be to group most of those nodes together into a "Close Door" group that takes a general Value in. We could then re-use that same group for Door 1, 2, 3, 4, 6, etc just by feeding a different value. Presumably, we can thus process door actions when enabled via an additional AND node (when other achievements are accomplished), and re-use this group across games.

Node Graphs Scope across the whole Blend file

Whereas the old brick way was pretty much object specific with messaging to communicate between objects, a node graph has no such limitation. Any number of objects can interact within the same noodle just by being connected. Since the old brick way was also scene-dependent, there is no such restriction here. This node graph can exist in any scene within the blend file, and is actively evaluated while game is in play. This could be the "Logic.Doors" scene. If this window was active while the game was in play, we could show realtime execution of the graph by flashing the connectors and annotating data values transmitted, or turning the node a different color while it is executing.

Maybe some Conventions

In laying out that crappy image, I discovered a hybrid of the current nodes and flowcharting. Logic pulses generate from the bottom of a node, and nodes are triggered by logic true pulses into their top. Data is transmitted via regular socket connectors on the side. Different colors for different kinds of nodes, many just header colors. Threads are solid, and can be highlighted by clicking on them to show solid shading (for tracing connections). Directional arrowheads help too in showing the flow of processing.

The Concept

If we want the node system to be extensible, we must have a generic node which can be configured to have any number of inputs and outputs of any type and perform any operations. With the other requirements in mind, our choice goes to a python node with the following structure:

A Python script that declares one Python class. The runtime engine will instantiate the class so that the node's methods can execute in the instance context at runtime.
Comments with a special format will provide the meta information that's necessary to display the node in the GUI and execute it in the engine. The meta information will tell the GUI how to render the pins, what parameters must be displayed, the node documentation, etc. The meta information will tell the runtime engine how to process the inputs and outputs, how to execute the node, etc.

So the Nodal Logic system will be made of 3 parts:

A set of python nodes available in libraries
A GUI that allows to place those nodes in a graph and connect them by links. The graph information will be stored in a standard binary format inside the blend file.
A runtime engine that takes the graph information, compiles the nodes, instantiate them and executes the graph by calling nodes methods and passing data between them.

A consequence of this design is that the data exchanged between nodes will be Python objects. The engine will be agnostic to the type of objects, it's entirely up to the nodes to define what data they want to exchange. To standardize things, libraries of data types can be recommended (ex: MathUtil for vectors and matrices).

Another consequence is that all Game Engine functionality will need to be available to Python. This is not the case for the moment, especially for sensors.

Although C implementation can be considered for certain nodes, we believe that this generic script node will be sufficient to implement efficiently most of the nodes. For complex computation, it is always possible to call a C function from a python script.

The generality of the generic script node is achieved by means of options at pin level, node level and link level. Here is the list, yet incomplete, of pin options that will be supported:

array of pin: Y/N
pin direction: input/ouput
pin type: push/pull
push input options:
- trigger node for execution: Y/N
- queue data: Y/N
- immediate function on data delivery: Y/N
- reset after node execution: Y/N
push ouput options:
- automatic pulse generation after node execution: Y/N
pull data input options:
- set to constant value: Y/N
- caching: Y/N
pull data output options:
- data source: object/function
- update data inputs before evaluating the function: Y/N
- caching: Y/N

Here are some options at node level:

type of node: DAG node, push logic, variable, I/O port. Only the types that have an impact on how the node is instantiated and executed need to be distinguished.
execution on each frame: Y/N
UI parameters

The Node Editor will also provide certain options at link level:

delay of transmission
filtering script
queuing (certain pin options can be supported at link level for greater generality)

All these considerations are from an implementation perspective. We try to answer the question: What generic object do we need to implement at node level to get the greatest generality at application level. It is an important aspect of this project: due to limited time and manpower it is the only viable approach to the highly complex task of developing a graphical programming system. For example, implementing ad-hoc C nodes for all the possible tasks is completely impractical within the time-frame that we have. Once the generic script node is ready, the GUI and the run-time engine implemented and a complete set of Python functions available to access GE functions, we expect that an army of generous developers will implement all the possible nodes for all the possible tasks.

In this project we will concentrate on implementing the generic script node, the GUI, the run-time engine and adding all the missing GE functionality to Python. Of course we will do our best to implement a basic set of nodes.

As a guide to node developers, the following sections describes what kind of nodes will be needed.

A very "smart" event detection and notification system must underlie the whole system. Perhaps nodes need to "register" themselves in some sort of list fashion, stating what type of event they want to be notified of. In the example above, the Proximity node needed to be notified when the avatar location got within a certain range bound; it certainly did not need one iota of CPU time any other time.

Development Support

To support the workflow of development, some tools and features are needed:

Real-time display: perhaps in a special display/debug mode (where we don't expect real-time performance), the node tree shows execution.
- When a node receives processing time, it highlights itself. Before it suspends processing, it displays updated values.
- When a pin (socket) gets a pulse or data to send on, it highlights
- When a thread (connection) transmits data in response to a push or pull request, it highlights, showing the data being transmitted.
Breakpoint: the user may need to freeze execution at some point in the game in order to debug issues (such as why a door doesnt open). When suspended, they can then either resume execution or break execution. Maybe this can be a special node that is put into the graph, and it suspends execution when it is triggered and the debug mode is enabled.
- They can designate a node to suspend overall game execution either before or after it processes
- a pin can be designated to suspend overall execution when it either receives or after it transmits its information (depending on whether it is an input or an output socket)
Logging and Inspection: As the game executes, certain key information can be designated to display in a window (replaces the Statistics overlay now). When logging is enabled, the user will be able to see a list of the nodes which have changed that property value.

Scripting Custom Nodes

A standard set of nodes will be available to cover all the functionality of the game engine and basic programming functions. The system can be extended by creating compound nodes and by scripting. New nodes can be implemented in Python source code as explained in the general concept section.

Creating New Nodes

It seems useful to provide a GUI API to simplify scripting:

the user brings a generic script node in the graph. By opening a property window, the user can customize it:
the inputs/outputs pins can be names.
the options of the pins can be selected: push/pull, etc.
the name of the node can be changed.
node parameters can be specified with data type, limits and render options but it is not strictly necessary as we can use data input for parameters.
the node function can be written in Python in a text field.

From this information the GUI creates the node source code, saves it in a text datablock or an external file which is then reloaded to update the display of the node in the graph. This process can be repeated to update the node definition. In the event where the new node definition is not compatible with the graph (pins have disappeared) the faulty links will be deleted.

Scripting a New Node

To present the node in the graph, the script needs to create its presentation in an __init__. the functions used to draw the node, the pins, etc. could be an extension of the current Panel API used to configure and present the UI of Blender itself.

Then the main processing would actually be executed each time the node is pulsed. The script uses the Blender Py API to do, well, whatever can be done in Python inside Blender. The script would be dynamically executed like a scriptlink:

Script node: points to a text object or py file, and executes that script when activated.

Node Types

In a somewhat similar fashion to Compositing nodes, there will be various families of nodes, arranged according to general function:

Input: get data from the outside world into the graph (noodle) and trigger logic processing
Logic: make decisions and set output values based on input values
Output: send data to the Blender rendering engine, or to the outside world.

In general, each node should provide a precise, well-defined function, and implement that function in a robust, error-free, and tolerant manner. It should protect itself from errant data received, and provide bounded, expected results. In addition, each node should be provided with a set of test cases that demonstrate the nodes functionality. Nodes should be tolerant of data types, for example, if a numeric value is expected, accepting both integer and floats as input values to a socket, and character string values are converted to a number, and lists of numbers are processed as well.

When the game engine is initialized, each node will be instantiated and the constructor called for initialization. Initialization code may reset ports, flush input buffers, or check for required files. As a minimum, a node should report its name and license summary to stdout.

Nodes may be coded in C or Python. Source code for nodes must contain a license.

Nodes may be distributed via the standard Blender install, or through open source libraries, or as closed-source licensed routines from vendors.

Nodes will be connected with threads from one node's output sockets to another's input socket. This connection will transmit data values from one node to another. Depending on the type of pin, the data may be pushed from the output to the inputs, with optional latency and queuing, or pulled from the input. The first type of connection allows to implement dataflow graphs or sequential logic graph. The second type of connection allows to implement a Dependency Acyclic Graph (DAG).

Each node will also receive a shutdown command, for example, when the user presses ESC. This will allow the game engine to make a graceful exit, by closing any open files, returning any external devices to a rest state, prompting for and saving game progress, and so on.

Event Detectors

Event Detectors bring information to the node graph during its execution. Data can be extracted from GameEngine functions: keyboard input, physics collision, etc. These nodes will havily depends on the GameEngine API to extract data from the game environment. The GameEngine will provide registration functions to avoid polling whenever possible.

Once extracted, the data is fed through a thread to other nodes.

They roughly correspond to the old "Sensors" logic bricks or WM Event-KeyMapItem-EventHandler.

They are evaluated (executed) when they are either triggered by a synchronous event such as the game clock (the heartbeat tick), an asynchronous interrupt system event (such as a mouse click), or triggered by receiving a pulse/input from another node, or in response to a pull or poll event from a downstream node.

Input nodes should be state-aware and be able to initialize and change their own state. Therefore a timer node could determine when the system time seconds digit changes, and send off a pulse to the game countdown timer display node for it to change the display. The countdown timer would be able to remember the current time remaining, and in turn send off a trigger to the game end logic when the value reaches zero. This "cpu-starved approach" has the potential to make better use of compute resources, in that logic only needs to be executed when needed. In dealing with lag, nodes such as keyboard input nodes would be able to catch up and flush the keyboard buffer, if, for instance, two or three keys had been hit since the node last got execution priority. Being state-aware means that a node can remember internal variable values since the last time it was invoked and determine what state it is in, and pick up processing right where it left off.

A suggested starter list of Event Detector nodes includes:

Keyboard Keypress: monitors the keyboard input port and does a keymap translate - that option allows the detection of ctrl-a as either one or two events.
Mouse click
Mouse Move
Serial Port: polls a numbered serial port for data received, if any. Keyboard is just a specific user-friendly implementation of this node.
USB Port: reads data from the indicated USB port
- Controller Event (Wii, Xbox controller, multi-axis Joystick, etc).
Midi Event Notification (person presses key on midi keyboard, or robot sensor sends midi data)
Sensor Poll: Polls a sensor every specified interval for the current value

Note that today, the BGE doesn't have anything like an event queueing system. This is because it runs synchronously with the physics engine and the render pipeline. It seems impractical to change this architecture but a event system could be implemented anyway for internal events like mouse and keyboard. It could be used by certain sensors that would start a separate thread in which they perform the detection task and feed events through this system.

Note that the BGE is designed to be "real-time", and event detection should occur as near to real-time as possible. Subsequent event processing, however, may get backed up and result in lag. Lag can be annoying (you get shot before you can move) or even dangerous (robot servo exceeds operating range). Therefore, we need a node:

Queue Monitor: monitors the queue of events stacked up, waiting to be processed, and raises a logic true if the monitored Event queue holds more than the indicated events.
Queue Filter: monitors the queue for specific values of events received (e.g. heartrate > 150 bpm, breathing rate < 10 bpm)

While these nodes are input only, don't forget their writing equivalent where applicable.

Soft Detectors

While you can think of the Event Detector nodes as being hardware-related, these Data Input nodes are more soft in nature, and are triggered when BGE processing changes some value:

Timer Value: when triggered, this node starts counting real-world seconds and outputs the time value. Required values are a starting and finishing values. It stops when the finish value is reached. If start > finish, it connotates a countdown timer.
Random Number: based on a seed (so testing is repeatable), gives a random number.
Curve: outputs a stream of values according to a curve. X is based on a game clock input and is in seconds, and Y output is based on the interpolated curve value. Options are to loop or just play once. Output starts being generated when the node is triggered by a logic pulse.
Duration / Elapsed Time (Count up timer)
Property Value Change Event: monitors some object's property and pulses when it changes.
Collision Event (bounding box collision)

Therefore, the system (on game startup) will have to set up data/memory location monitors that hook into any change made to the value. Output Sockets include:

Pulse
Value
Image
String

Logic Nodes

These nodes will help determine the context, or applicability in processing events. A suggested starter list of Logic Input Nodes includes:

Logical And: takes two or more inputs and, when all have been supplied, generates an output pulse/value. Input can be just a pulse or a value.
Logical Or: routes one or the other value (of an array of inputs) on its way.
Logical XOR: (Exclusive Or - one or the other input socket, but not both). When am input socket is pulsed, the node checks to see if the other socket has been pulsed, and if so, does not trigger an output, but instead resets state.
Clock: sends a pulse x times per second (x is set on the node's face). This could be used to trigger AI processing, movement/action replay so that actions replay at a known frame rate, etc
System Event - Lose Focus: The BGE plays inside of an application window and hogs system resources (like CPU). If the application loses focus, it should nicely stop being such a hog, possibly by suspending play. This node gives it that awareness.
System Event - App End: the user has indicated they want to stop the game play via the close the application window X button.
Game Start: The user has requested the game to start. Sends out the initial pulse to get the party started. Options include play mode (real, debug).
Comparitor: Raises true if two input values are equal within the proscribed tolerances, or Less Than is A < B and Greater if A > B.
Breakpoint: when activated by a logic pulse, it suspends gameplay in debug mode. Any values fed to it (like from PropertyGet nodes) are dumped to the console.

Getters/Setters

These node either get or set data values, and are the means by which the node graph is aware in in-game changes, and saves data for later use. A suggested list includes:

Fixed value getter/setters include:
- Value: provides the specified value (logic pulse, logic level, value, string, or array) the specified number of times.
- Random: based on input seed, provides a value between 0 and 1 (use the Math nodes to expand the range to whatever you may want)
- Color Generator: puts out an RGBA color
- Material: brings in the indicated Material
- Texture: brings in the indicated texture
In-memory nodes include:
- Property Get: reads some property of some object. The name of the object and the name/selection of the property should be entered/selected on the face of the node.
- Property Set: sets the value of some property of some object. This can be a user-defined property, or a standard property like rotation.
Serial File I/O include:
- File Open
- File Line Input (File Open happens during initialization processing)
- File Write: writes a string out to a file
- File Close
Socket I/O:
- Ping: tests to see if an IP address is live on the indicated port
- Pong: responds to a ping on the port.
- Packet Read: accepts a packet received from the indicated IP address
- Packet Send: sends off data to the ip/port
Database (MySQL) I/O include:
- DB Session: establishes a session with the database; login
- Table Read: reads a value in from the indicated table, providing a list of (column, value) pairs for the selected rows. Needs an input SQL select statement
- Unpair: For each (column, value) pair, outputs the property in one socket and the value in another
- DBPair: For each property name received in one socket, and value in the other, makes a pair
- Table Write: Changes values (column) in the database table for the indicated row (a Where clause needs to be entered) based on the supplied (column, value) pairs.
- DB Commit: Writes changes out to the database when all Table Writes are successful

Action Nodes

You can think of it as these nodes generate data for the game engine to process, by sending data or commands out of the node graph to the engine. They are roughly similar to the actuators of the the old system.

These nodes can be told explicitly to process by a logic pulse to their input socket or can run at each frame until stopped explicitely.

When a node operates on an object, an object reference must be passed on the dedicated node input. By default, the node executes on the object that owns the graph. Such retargetting capability is the key for reusability. A graph can be made to work on various objects or group of objects provided it receives or has the logic to get the references.

A suggested list of Action nodes includes:

Motion: Simple: sets the new Location and Rotation of an object by allowing the user to specify the Delta xyz distance/angle to be changed every tick, locally to its orientation, or globally within the game world.
Port Write: outputs a value to a port
Controller Write: flashes a light or triggers a shaker in a controller
Scene update: forces display update
Sound Play: plays a sound once. Same controls as Play Action for looping, pingpong, and complete.
Sound Loop Start: causes a sound loop to start. Control on the face of the node specify how many loops to play
Sound Stop: aborts the playback of a sound or loop.
Video Start and Loop Start and Stop: same as sound, but with video file
Play Sound: plays back a sound file. Options to loop and pingpong. Works within a memory management framework that tries to pre-load the main sounds, so this node should have some kind of a priority or importance/frequency of use indicator for the sound file. A feature of the Node Window would be to create one of these nodes for each sound file in a directory, or have some kind of inventory pallette
Play Video: plays either a video file or image sequence as a texture on the specified object. Options to loop, pingpong a sequence. If a sequence, you have to manually specify the framerate.
Snapshot: take a snapshot of the screen and send the image out through the output socket
Create Object: instance a mesh (like a grenade) at the specified coordinates into the game. Mesh name is specified on the node, and coordinates are input sockets with default values you can set on the node.
String function: provides the indicated string function on the two inputs supplied. For example, the Append function takes a keyboard input node (which supplies the letter "n") while a PropertyGet node for Player.Name provides the string "Be"; this node outputs the string "Ben" to a PropertySet node for the value of Player.Name, thus updating the Player.Name from "Be" to "Ben"

Motion Nodes

These nodes make objects move, and include:

Motion: Servo: somewhat similar to a driven key, this node changes one object's loc/rot based on the changes in another object's loc/rot. For example, a lever position opens a door. Using the node tree, you connect an Object Property input node for the lever to this node (for the door) to specify the controlling object and to establish that signal.
Play Action: A true input pulse triggers the specified action to start playback for the indicated object (armature or object). Raises the logic output true while the action is playing. If "Loop" is true, the action will loop around and play again (forward) if it finishes while the pulse is still true. If "PingPong" is true, the action will reverse when the last frame is played while the Play pulse is still true. If both Loop and PingPong are both false, the action will play once, and then stop. The action will end if at any time the Play logic trigger becomes false. If "Finish" is true, the action will finish out its cycle when the Play logic trigger is false; otherwise it will immediately end. The output "Playing" logic output socket is true while the action is playing back, either forward or backward. It momentarily goes false when the endpoint (start or end) of the action cycle is reached.
- Note: need to check the latest dope sheet ideas for current terminology

Morphing Nodes

Shape (note this term might change to Morph): Over the specified time interval (using an ipo curve?) this node applies a shape key (morph target) to the object, changing its shape by changing the influence. Again, like with sounds, it would be nice to have an inventory of these created for each object. Options are to loop or pingpong the shape key's influence.
- Note: Time/duration is either in seconds or in ticks. This brings up an interesting design question, as to when the game designer keys say an action, it may be a series of poses to be played back at a certain frame rate. At work, we use a JSON string to specify which frame to play and how long to hold that pose for (in milliseconds). Might want to incorporate that idea in this node as a parameter to control playback.

--Roger/PapaSmurf 05:17, 7 November 2009 (UTC)

Constraint Nodes

These nodes moderate, or constrain, the values that pass through them. Examples include:

Location: Limits motion to within a bounding box
Rotation: Prevents objects from spinning out of control
Scale
Distance: range between a reference object. Parameters allow elasticity within a boundary range
Orientation: ensures a relative location within a ray angle
Value: generic value limiter. Limits it to be in a range, with a limit of infinity (+/-). Use two feeding an OR node to ensure values do NOT fall into a continuous range.
FilterList: removes unwanted items from a list, constraining it to only include specified items
Color: limits the material color of an object to an HSV range

Scene/Display Nodes

These nodes operate to trigger or modify gameplay:

Select: Chains gameplay to the named scene. After the scene has been changed, a logic true pulse leaves this node to start initialization processing
Load: Chains gameplay to a new blend file and starts processing all the node grpahs in that file.
Camera: Changes the active camera to the indicated object
Layers: Establishes which layers are actively rendered
Filter: used to put a filter in front of the camera or distort the camera view. Examples include DOF, water a la BioShock, heat waves, luminosity/glow.
MatChange: Changes the indicated property value of the indicated material name. Also needs an index for multiple materialized objects, and an index for texture if it affects the way a texture is applied to the object. For example, if you have a blood splatter texture, use this node to increase the Color influence of that texture channel.
TexChange: Changes the indicated property value for the indicated texture
MatGet: This handy node gets the material used by an object in the game
MatSet: This node changes the material used to color an object. Option is to make it single user as well after applying. Allowing you to color say, an army, but then make individuals change color

Messaging/Communication

These nodes send/receive messages.

Machine Port Read: polling type interface, reads the port when requested
Machine Port Write
TCP/IP Port monitor: receives incoming IP packets from the specified port (8080, etc) and sends out the TCP/IP Packet Received

TCP/IP Packet Send: Sends out a packet to a TCP/IP Port

Message: Sends a message to a distribution list with a Subject. e.g. notify ARMY to ATTACK with message {{DIRECTION,"45"},{SPEED,2.5}}
Listen: Reads and filters messages on the specified distribution list for a specified subject. When one is received that meets the message criteria, it sends on the message

Port Interrupt: Any port can be directly monitored, such as for custom robot controllers, weather/real world monitors (as was demonstrated at BlenderCon 09 - the heart rate monitor, breathing monitor)

We could possibly add a DBus interface here as well (when available). It would open a lot of new possibilities (like... easy integration of chat application from within a game!) --Skadge 10:40, 9 November 2009 (UTC)

(Linux) Jack Events for audio device connection and message reception (such as midi event)
(Linux) Audio output via Jack

Object Interaction

These nodes allow the game designer to control how and when an object interacts with another object or the system in general.

Create: Creates an instance of the object.
Layer: Moves the specified object to be part of the layer list.
Parent: Makes the object have the indicated parent.
Path: Makes the object follow the path.
Delete: Removes the object from the game.
Follow: Primitive AI following. Attempts to reduce the distance between it and the reference object.
Seek: AI path finding. Attempts to reduce the distance between it and the reference object.
Proximity: More of a general vector comparitor under the sheets, but it pulses true if two tuples are within limits of each other.

--Roger/PapaSmurf 05:39, 7 November 2009 (UTC)

Runtime Engine

This section goes over some design details of the runtime engine that will execute the logic graphs.

Execution of nodes

A node is triggered for execution when it receives a data (can be a pulse) on one of its push inputs. A triggered node is put on the current frame run list and executed in turn. The execution of the graph continues until there are no more nodes in the run list. A node is removed from the run list before its execution but it can be put back in later if the graph contains a logic loop.

Several mechanisms are provided to ensure timely execution of graph:

Delay on logic connection: to avoid that a logic loop becomes an infinite loop, a delay expressed in number of frames can be specified on the logic connection. A data traveling on this link will be delayed by this many frames, allowing to spread the execution of the graph over time. While any node with an input and output can be used in a loop, some nodes (e.g. a linear progression node) might be specifically designed for use in loops. Such nodes might have the following connections: two inputs: reset and continue; and two outputs: continue and end, with end being triggered when the progression is complete.
Synchronization nodes: if the graph splits in several parallel execution paths, synchronization nodes can create a barrier that emits an output pulse only when all parallel paths have reached it.
Persistent nodes: a node is persistent if it is put on the next frame run list during the execution of the graph. This method is complementary to creating loops with a delayed logic connection (above). A persistent node might have the following connections: two inputs: start and stop; and two outputs: continue and exit (note: no loop). It can be useful to have both methods of repeated execution:
- Nodal loops provide a flexible execution path. One can see which node will be activated in which order, but it requires additional connections that can make the graph less readable. To exit a loop, extra nodes are required to check for an exit condition (with an if/else node for example).
- Persistent nodes encapsulate the loop, making the graph more readable. The exit condition is set as a property of the node.
Examples of nodes that could be persistent include countdown timers and sensors. Note that, since there are use cases for both types of repeated execution, some nodes might be configurable to work in loop mode or persistent mode.

(some changes in this section by Z0r 12:35, 6 November 2009 (UTC))

Nested node graphs

A fundamental feature is the possibility to encapsulate a graph of nodes inside a compound node. This new node can be used as an ordinary node in a graph, which can itself be encapsulated in another compound node, etc. This node grouping is not done in a casual way (such as selecting some nodes in a graph and grouping) but in a very explicit way: the entire graph must be declared compound, inputs and outputs must be declared (by means of special I/O nodes), a unique name must be given to the graph and it becomes only available as a node and not as a graph anymore. Of course, editing the compound node remains possible. Using an explicit mechanism to create a compound node has key advantages:

It forces the user to think of what is the purpose of the node and clearly define the inputs and outputs.
It allows to create reusable logic: the compound node can be used several times.

Note that next to this explicit compound node creation process, we can still give a grouping/ungrouping GUI option for the clarity of the graph layout. This will have no effect on the execution of the graph.

Compound nodes cannot be saved in source code because they contain graph information. Practically, it means that compound node must be a new type of datablock in Blender. This datablock will provide the same information as ordinary nodes so that they can be used in graphs.

A compound node can make use of other compound nodes, creating a hierarchical Logic graph.

Compound node will have an explicit state: the node becomes active when it received a pulse on one of its inputs, it remains active until a special 'return' node is executed. This node automatically removes all nodes from all run lists and perform certain shutdown functions such as deregistering sensors. This definition of compound node matches quite well the concept of state in a state engine.

Reusable Logic

An important aspect of the new system is the ability to reuse Logic graph. This is already the case for compound node but it should also be possible for whole Logic graph. This means that Logic graphs must be created independently of game objects. In blender terminology, a logic graph will be a new type of datablock (different from compound node).

The dissociation with the game objects is possible because the nodes will carry their own data and will not rely on the game object properties. A logic graph is assigned to a game object simply by setting a pointer and incrementing a use count like any other datablocks.

For greater flexibility, it will be possible to assign more than one Logic graph to a game object. Prioritization of their execution will be possible.

Implementation Details

Let's apply the general concept to practical questions and see how we can solve them.

How to get object references?

With Logic bricks, object references can be obtained from:

sensors reporting interacting objects
the owner of the brick
global list (scene object list, application list)
object's children
links to bricks of other objects of the logic group (a logical group is formed by objects having cross connections between bricks)

The first 4 methods are certainly applicable to the new system but the last method is not directly possible as a logic graph is assigned as a whole to one object and all instances of the nodes will belong to that object only.

It seems inpractical to have mixed ownership in a Logic graph: if an object is deleted that owned certain nodes of a graph, these nodes will have to be removed, causing holes and possibly breaking loops. This is less important in a Logic Brick setup as there are no explicit loops.

If we decide nevertherless to have multiple ownership in a graph, the question of the assignment of nodes to object comes up since there is no ownership at the creation of the graph. This can be solved by a 'linking' stage: when a logic graph is instantiated in the game engine, the nodes are assigned to different objects based on matching the names that has been setup during creation phase. This method goes strongly against the reusability of Logic graph since the name of the objects would have to match.

The best approach seems to be a targetting method: a node can be explicitely targetted to another object by passing an object reference as a data input. A reusable graph can get object references in various way:

by digging the owner children's tree and getting children reference by name, type or property (e.g. find the child with 'armature' type)
by scanning the group reference during group instantiation. Such local reference list will be available to Logic graph via special group nodes.
by scanning the global object list.

In addition to these 'intra graph' methods, it seems useful to provide an 'inter graph' method by allowing connections between graphs. Such connection would be displayed as a shortcut and created with a copy-paste operation: copy an output in one graph and paste it on an input in another graph.

Such inter graph links create a problem during instantiation: if the destination graph of a shortcut is instantiated multiple times, each instance will get a copy of the shortcut without problem: multiple inputs can be connected to one output. But the opposite is not possible because an input can be connected to one output only (note that it's possible with logic inputs)

Specific problem with sensor nodes

With Logic Bricks, sensors are special bricks that run on each frame as long as they are active. The activation is done implicitely as soon as there is at least one link to an active controller. For some sensors, the activation involves a registration process in the Bullet physics engine (collision sensor, etc).

In order to open up this functionality to Python, explicit registration function will be provided. This will go together with an event system: the registration generates events and the sensor simply checks if events have occured or better, is activated by the engine when an event has occured. Deregistration will be done automatically in case of compound node going to inactive state or explicitely by stopping the sensor.

Performance analysis

With all the previous points in mind, we can define the execution steps of a node and analyse the interactions with Python.

Activation of the node

Activation happens when another node sends a pulse or a data on one of the push input. The push input will be implemented as an elaborated Python class that provides an API to follow the link backward (in case the script wants to scan through the links arriving on the input). The push input will have a true/false status for simple check in the script. The C++ engine will access the push input objects directly by index (without having to do a name lookup) and will store the data. It will also put the node on a specific run list based on the link delay. Doing that requires a few pointer manipulation. If the node was already on a run list, the frame number of that run list is compared with the delay of the link. If the delay is shorter, the node is moved to a shorter run list. A node can only be on one run list at a time.

The number of run lists can be high without impacting the performance: each run list is a tiny double linked list head in an array indexed by number. The logic engine advances through the run lists in a round robbin manner.

The priority system will be implemented as a series (not too many) of run lists for each frame. The engine executes all the nodes on the high priority list before checking the lower priority lists.

When the node gets on the top of the list, its execution commences.

Execution of the node

Before execution the node function, the inputs and outputs must be set as follow:

push inputs are already set right based on activation process, nothing must be done for them.
Optionally, push outputs are flagged to generate a pulse after execution. Other option is to let the node execute function set a pulse (or data) on the outputs so that selective output are triggered. Logic outputs are also elaborated objects that allow the script to follow the output links if necessary.
Optionally, pull inputs are evaluated. The evaluation involves following the data link and getting a python object from the other end. It can involve executing a DAG node, which in turns evaluates its inputs, etc, until the data path is evaluated recursively. The pull inputs are simple Python bindings that are assigned to the python object obtained from the evaluation.

Then the node function is called. The instance context gives access to inputs and outputs and the global context to system-wide game data.

During the execution of the node, the pull outputs can be assigned (for later retrieval by a pull input) and optionally the push outputs can be set.

If the node is set for implicit looping, the function can return True or False to trigger the automatic activation of the node on next frame or not. If the node is set for explicit looping, it must provide a pulse on a 'running' output to allow the user to loop the logic.

When the function has returned, the C++ framework performs the following operations:

All inputs are cleared unless the node is set for 'cumulative' mode. In that case, it is up to the script to clear the input.
Optionally all pull inputs are set to None. This is useful to release the memory used by temporary objects returned by functions.
The push output are scanned for values. For each output set, the links are followed to activate the nodes on the other end as explained above.
The pull outputs are left unchanged, they will be used by other node as input values.

With this execution framework, it seems possible to use Python as a scripting language without impacting the performance. Even if some nodes are implemented in C++, they will have to provide Python objects on their inputs and outputs to let other python nodes access them.

Dev:Source/GameEngine/Projects/NodalLogic

目次