Fractured Foundations

Just as this past weekend was starting I came across a GDC presentation made by one of the guys from Ensemble Studios.  Specifically it was about making their final game Halo Wars.  It was a technical presentation with some very cool stuff, such as how they used multi channel heightmaps to give their landscape a 3D mesh rather than just a verticle offset for each vertex.  However, the thing that caught my eye was the screen shots from their editor.  It was all C# based.  Ok I suppose it could just be generic managed Windows Forms, but I doubt it.  Combining this with both the comments I’d overheard about how “nice” the interface was for one of the other dissertation projects and the fact I’ve been dying to have a go at C# tool dev and bridging native and managed libraries I went a head and did just that.

The first real step was putting into place the managed wrapper classes for my unmanaged library.  After some looking around and not really finding anything that could help me much I decided to amalgamate all I’d seen and could assume into a best guess implementation.  It turned out it was quite simple.  Since I relied on a lot of interfaces already as well as my main library interface being bridged it worked quite well.

With the first manged library built and running I patched it into a simple C# frame that would list all the available nodes in a loaded module.

First Pass C# Interface

Next up was a little organisation.  Modules are referenced within the library by a provided name.  The loaded file itself is abstracted away.  So if you load a module with the name ‘Core’ and it contains a module called ‘time’ you would create that node by using the name ‘Core::time’ where the ‘::’ is used to show a reference into a module is made.  I figured the simpilest way to break that down visually was just a tree view.

Organised Node Libraries

With a proof of concept type implementation taken care of with regards to actually proving it works I started messing around with layout ideas.  Naturally this ment snazzing it up a little with file menus, work spaces and of course an about box.

Fleshing out the Interface

After playing around with default items in the work space I set about actually showing the procedures, both the current one being edited and a list of “grouped” procedures.  The editor window is fairly straight forward in concept, it’s where the “nodes” will be for connecting up to make procedures.  I had to use the property grid just because it seems everyone uses it these days.  There are 2 types of visual nodes.  The IO node and the Bound Node.  IO Nodes are the first I started with.  These just represent the inputs and outputs of procedure so.  The bound nodes are those associated with a specific node in the procedure, these I didn’t get round to finishing as there’s some back end editing stuff I have to adjust to let them play a bit more nicely.

First Interactive Procedure

With the nodes floating about I spent time getting dragging to work a bit nicer as well as investigating how to make the nodes a bit more visually appealing.  I hadn’t really thought about how they would look when I began so I just messed around and decided upon something fairly plain, simple but pleasant.

Custom Drawn Nodes

I finished off the weekends work for this by iterating again on the design of the node controls.  These are now fully custom elements with no more hacked in place windows components that do nothing.  The sockets are now more obvious as well as showing their connecting points.  I also went back over the whole UI and rejigged it a bit to use it’s space better, offer more feedback to the user and try to provide more command buttons on the UI so the user can use them or the ones provided through the file menu.

Last UI Iteration for the Time Being

I have to admit I enjoy working with C#.  How quickly you can put together a UI is just one of it’s strengths.  Setting up meaning full interactions between objects and over all structuring for happy interface development is quite straight forward.  It’s not my beloved C or C++ but the tools Microsoft have provided for it inside of Visual Studio are excellent.

Alas as I created this editor I started tinkering with the notion of creating a second interface for my library.  Essentially splitting the Application interactions into 2 logical parts.  The original interface refered to just as “ProcLib” would be simple and straight forward, load procedures and run them, not much more.  That would be for the runtime aspect.  For editors the library provides a more flexible and open ended interface that can be used more for modifying and creating procedures.  This proved to be some fun, but since it is back to C++ and technically after the weekend has finished I shall talk more about it in days to come.

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.