Fractured Foundations

Everything to do with this project can be summed up with “if I’d just done it like that from the start.”

I spent most of this week going back to what had been my rough research papers.  I am rereading them with a good deal more perspective in what I am doing and why.  Where originally I tried to ignore what some of the papers had done as I wanted to do it, I am now finding a lot of gaps and areas that appear to be fairly untouched.  I’m not under the dellusion I am the first, but it definately seems my area of choice is growing and under a lot of research so my goal and approach may turn out to be something worth while.

I don’t think my time was miss spent over the last month or so, it’s just that I’m now on my third ground up build and would prefer to have done it properly the first time.  There’s a lot of work I’ve put in that will never see the light of day because it was trying to be a global problem solver rather than a focused piece of software.

My current itteration of the library entitled “ProcLib” is quite light weight and while there’s still a fair bit to do, I think it’s certainly benefited from the previous attempts.  Some parts of it are better designed now, such as my eventual implementation of actual node links will be threadable.  The way developers extend the nodes is a lot more elegant as well as much more abstract.  Still bits to do but it’s the most complete version yet.  It’d just have been nice to be here 4 weeks ago and have loads of time to do clever stuff.  At the moment I’m just driving to create the specific demos I’d had in mind and whether I have the time to finish them and a write up is very unilikely.

Tommorrow, if I get enough done I think I’ll put up a blog with the papers I am most interested in using in my report or as a basis of a demo.

Today I spent a while outlining the format of my graph storage files.  There were a couple concerns I wanted to tackle in terms of both functionality and data types.  The first one I solved was the storage medium which I decided to just go with XML.  I suppose that decision meant the rest just became an XML schema definition but I know very little about the high level concepts so just refer to it as “making a file to hold my graph data.”

The XML formatting gave me an idea that had been working it’s way through my head for a while.  Originally I was building graphs with the concept of 3 node types, generators, operators and exporters.  The important note for these is that the applications would have had to retrieve the specific nodes from my library and manually set and get data values from the nodes.  What I have come up with for the redesign is input and output elements that are fixed tables with named parameters.  This means the application only ever deals with the input and output tables and nodes internal to graphs can retrieve values or set values in those tables.   This I believe makes the procedures that the graphs represent much more application friendly.

On top of the new IO tables I’ve designed in a simple name space system.  This is done in an attempt to allow extension modules a fair bit of freedom with their data types and functions without clashing too badly with other modules.  When registering a module to the system it is given a name or a title which becomes it’s root level namespace.  This name will be guaranteed by the system to be unique, I intend to ensure that the system has a way of avoiding loading the same module under a different name as well.  Once the module is loaded with it’s title, the node and data types it contains are referenced using the title followed by a ‘::’ symbol.  So a module named ‘Maths’ with a node called ‘Add’ would reference that node as ‘Maths::Add.’

So with the conceptual components mostly done I tackled the actual design of the XML itself.  I tried to keep it fairly simple, clean, understandable and ideally flexible.  For the purposes, I am quite happy with the results.

The first part is the “graph” element that wraps the entire definition.  It contains a “name” attribute which will be used to reference the graph within the engine.

The first sub section is the “modules” section.  This is where the graph identifies to the system what modules it references or needs loaded.  There are sub elements within this tagged as “module” each of which contain the attributes “name” and “file.” The “module” elements are loaded based on their file attribute and use the name attribute as that modules namespace.

Following this are the “input” and “output” elements.  These represent the named input and output tables associated with the graph. The sub elements in these sections are tagged “parameters” which contain a “name”, “type” and “default” attribute.  The name attribute identifies the parameter for referencing by both the system and the nodes withing the graph.  The type attribute identifies what kind of data the parameter holds and the default attribute is able to pass an initial value to the parameter.

The next section of the file is the “nodes” element.  It is what identifies all the nodes that will exist in the graph.  Individual nodes are handled by the “node” element handle, which contains “name” and “type” attributes.  Nodes can also contain “parameter” elements to initialize internal data.  Declaring parameters in this section means that are most likely not going to change for the life span of the graph.

The final element in the file is the “connections” element.  This is where the links between nodes are made to define data flow when a graph is operating.  The sub element that defines a single connection is tagged “connection.” The connection element contains sub elements tagged “to” and “from.” These sub elements contain the attributes “node” and “socket.”  Essentially they define which output parameter on a node gets connected to which input parameter on another node.

At the end of the post is a simple example of a stored graph, however first I want to have a brief conclusion.  I believe this format is fairly portable and quite simple to manage.  The user interface for creating them isn’t as big a priority as I had originally thought so I believe any developer application would be able to create an exporter to this format.  I also believe the new system design will benefit any user applications and games since it gives them a cleaner interface with the graphs and also hopefully allows for more straight forward management of various types.

My next step will hopefully to be recode bits of the engine that need to be changed to match this new design, possibly a little redesign of the engine as well, and to get a parser written for this file format.  The parser will need to generate the run time graphs with loaded modules, connected inputs and outputs and all that good stuff.

This final section will probably be quite long due to the formatting but here it is.  This is an example graph saved out to my format.  It is a simple graph that has 2 named inputs of type “Float” which the graph uses with 2 other constant float values to create 2 addition functions and the results of those get multiplied and output to a named output parameter.

<graph name=”" >
<modules>
<module name=”Maths” file=”PrEditorMaths.dll” />
<module name=”Noise” file=”PrEditorNoise.dll” />
</modules>

<input>
<parameter name=”value1″ type=”Maths::Float” default=”0.0″ />
<parameter name=”value2″ type=”Maths::Float” default=”0.0″ />
</input>

<output>
<parameter name=”value1″ type=”maths::Float” default=”0.0″ />
</output>

<nodes>
<node name=”node1″ type=”Maths::Float::Constant”>
<parameter name=”value” type=”Maths::Float” value=”23.7″ />
</node>

<node name=”node2″ type=”Maths::Float::Constant”>
<parameter name=”value” type=”Maths::Float” value=”5.0″ />
</node>

<node name=”node3″ type=”Maths::Float::Add” />
<node name=”node4″ type=”Maths::Float::Add” />
<node name=”node5″ type=”Maths::Float::Multiply” />
</nodes>

<connections>
<connection>
<from node=”inputs” socket=”value1″ />
<to node=”node3″ socket=”input1″ />
</connection>
<connection>
<from node=”node1″ socket=”output” />
<to node=”node3″ socket=”input2″ />
</connection>
<connection>
<from node=”inputs” socket=”value2″ />
<to node=”node4″ socket=”input1″ />
</connection>
<connection>
<from node=”node2″ socket=”output” />
<to node=”node4″ socket=”input2″ />
</connection>
<connection>
<from node=”node3″ socket=”output” />
<to node=”node5″ socket=”input1″ />
</connection>
<connection>
<from node=”node3″ socket=”output” />
<to node=”node5″ socket=”input2″ />
</connection>
<connection>
<from node=”node5″ socket=”output” />
<to node=”outputs” socket=”value1″ />
</connection>
</connections>
</graph>

Realizing something or finding out hours were spent developing something minor or irrelevant seem to be a common trend when working on research projects.  I’ve got a few pictures and some updates to talk about that I’ve gotten done since the last update but those will be put off a little but as the last few days have really altered my perspective on this project.

The first step in getting this whole issue straight is to identify just what I’d been focusing on and the areas I thought would be most important.  Specifically this area was giving artists and designers an easy to user interface to create generation procedures.  This really focused on the interface and how the artists used it to do new things and create content in new ways.

This original intention is very broad but also doesn’t really put into perspective the projects goals.  The way I outlined it was really this radical new  way of interacting with users and making the underlying technology a minor player in the whole thing.  In my head I had that as the appropriate prioritization of the project.  However as I’ve progressed it’s been far more obvious that my true intentions were to make a middleware type library that was capable of loading user created graphs and generating assets for use in a game engine.

You may now be asking: “Woah there, that’s the same thing really isn’t it?” To which my answer is: yes on the surface and at either end of the pipeline it sort of is.  However when it comes to scope and being able to say what’s “new” about my project it really brings the obvious answers to the surface.  My use of node graph and visual programming style interfaces aren’t new, they’re directly inspired by existing paradigms and even specific tools.  The state of the art would point out that these are infact very succesful ways of doing things and why I wanted to use them.  At the other end of the spectrum using procedurally generated content in game isn’t new at all either.  There are plenty of examples of assets being generated in external applications to be imported into games, there are also examples of features within game using procedural methods to create elements that they will use.  My real contribution is this middle ware library that takes as it’s input a formatted generation description that it then parses and runs to provide a defined output that is an asset a game can understand and use.

So, where’s the huge change?  Well it feels a bit like designing the first ever car and slapping a body together, popping a comfy seat and a steering wheel in for the driver, assuming the engine will go up front and the putting shiny wheels on it.  I’ve been praising the wheels, both steering and rolling, designing them as being the important feature to it, no wheels, no rolling, no control, no car.  However the fact of the matter is I just assumed mechanical details and that the engine would just happen.  Taking a step back I can see the engine itself is the crucial piece of technical detail.  It’s the true heart of the car, the steering wheel may allow the driver to control the car and the wheels on the road may let it travel about but both of those have been done before, it’s the combustion engine that drives it all.  The pistols firing away turning the crank to push power to the drive wheels to make it go and the throttle pedal giving the driver control over just how much power the engine should put out.

The analogy is rough around the edges, but the point is there.  What I want to do is really delve into the specifics of how my “PrEditor Engine” will work, define the inputs and outputs so the Editors can control the procedures and the games know what they’re getting.  I had intended the Engine to be an implementation detail, mostly ignored with the “usability” factor being the key selling point.  Well that’s turned out to be jumping the gun hugely.  Yes a node based editor is really cool and I’m not ditching that, as well as the demo frame work it’s hanging about, it’s just I’m going to have to REALLY put a lot of effort in to make up the lost time on the Engine.  It’s where I’ve wanted to be, it’s not something to be thought up after the Interface is created.  It’s got to be the key stone in all of this.

I wanted to try and approach this as a Rapid Application Development but the very thing I was trying to avoid was the most important detail.  I don’t have a system in place that needs to accessed, I don’t have a team of artists waiting for an easier way to create procedural content, I’m on the very tip of the technical side trying to create a reusable and expandable library that can be used to do all that with.

So, back on track, not all the old work lost, but certainly not what I am going to focus on as my key development goals.  They are ultimately just a way of facilitating generation of and rendering the outputs from the core engine.  From here on out the PrEditor Engine might need a new name, so it’s a Procedural Generator rather than a Procedural Editor, the editor is merely part of the toolkit used to create the inputs to the system.

This means for this week I’m going to try and wrap up to some degree my work on the editor and demos and really have to get to the drawing board with this engine implementation.  What was a fairly straight forward and thrown together system to create the means to an end will have to be come a strongly defined process.  By the end of the week I hope to have the structure of the input data, the parsing and graph generation process, the node definitions, the graph execution and the setting of input data and retrival of output data atleast in the research phases if not early definitions outlined.  I plan on sticking to the avoidance of over engineering and keeping it straight forward but I also want to tackle head on the crucial points I’ve uncovered about where and how to define data types that will be extensible but still be able to run as part of a generalised node graph.

Today was spent early on debugging the STL vector replacement I wrote.  Originally I had thought it quite clever with a double linked list that stored extra nodes off the tail,  so it didn’t have to always create and delete elements as they were used.  It turned out a simple thing like reordering head and tail pointers can be quite complex when handled in various ways at different points.  I’d end up fixing an issue in a stack style function and realise the issue went unfixed in a queue type function.  However after walking through it all and nailing down some of the lose ends it’s up and working and actually doing it’s job in some areas.  For example my mesh loading library has a few objects that stores of thousands of faces but uses a swap buffer that is cleared after each use.  With some of the list entries stored off for later use this means the swap buffer only actually allocates the highest number of  verticies used by a face.  I’m sure the STL vector class does this too so not amazing per se but it’s nice to have written my own just to see if I can and how it’s done.  No fun using something someone made for you if you don’t know how it works.

So actual progress on the project was also achieved.  I’ve got a simpler and hopefully more solid implementation of the nodes in place.  One of the biggest issues I think I’m going to face is figuring out how to balance the data types of inputs and outputs.  I want to be able to set it up so that I can explicitly make sure I’m passing a input data type to a node and that it will be outputting a specific type that can then be used.  The current system in place is quite lenient in that it’s up to the implementation to define the storage medium.  The interface only defines a method to retrieve an integer value to represent a mnemonic value for it’s type and the a get and set method that return and take pointers of type void, respectively.  It’s not the most impressive interface nor do i think it’s very professional. I had tried a templated version and extremely overloaded version but the former is a tough nut to crack with an application running through interfaces and the later got very messy and wouldn’t have supported data types beyond what I supported.  The reason I want this kind of flexibility is the fact that there are so many different data types to deal with and so many are going to be defined by the intended use. Things like a mesh of spatial Vectors that are manipulated to create a terrain aren’t even as simple as I had hoped, a company might use mere bytes to represent the data where others might use full blown double precision floating point values.  String types may vary accross libraries, where I use a lot of STL strings others might have their own custom built ones.  At the end of the day I want to support as much as possible and inhibit as little possible.  I think I’ll be looking into this a fair bit but I’d like to find a soloution that can leave it fairly flexible without requiring me to code handlers for every possible permiation of data structures.

So, on to a slightly more successful part of the day. I got the UI running with the new node structures as well as getting in the base frame work for handling the different types.

Colour Coordinated Node Types

Now when a node module is loaded and registers the UI creates a new GUI for it and adds the availabel nodes to the lists.  These can then be selected and placed by the user.

Organised Nodes. Tabbing for Modules and Lists for Node Types

While placement, selection and movement are all in place the connection creater is still in need of some work.

Input and Output System becomes a colourful messy graph

Tomorrows task will be to get the outputs listed on the node elements, setup the connections so you can only drag connections from an output to a valid input(ensuring inputs only have 1 link) and I would like to make a rudamentry pass at running the graph.

Other areas I’ll be keeping in mind or having a think about will be a properties editor for nodes so that I can use the GUI to edit the values inside generator and output nodes.  I also plan on having a think about how to load and store pre built graphs, as well as the possibility of some real time preview windows or nodes.