One Million Bytes

A slight aside today while I play with futuristic skyscraper shapes.  I'm not going to talk about cities, instead this post is about an interesting technical aspect of the synthesis engine; the use of the call stack.

The Stack

Typically the stack is something that most programs and programmers don't need to worry about, ever.  Programs tend to rarely have a call graph that goes even remotely near the stack depth limit.  Of course we have all hit stack-overflow situations, but these are usually due to either:

1. A function accidentally calling itself (either directly or indirectly).
2. A recursive algorithm not terminating properly.

Both of these are just bugs you would hit during development, fix, and move on.  Sometimes though you may be explicitly using recursion to solve a problem and need to be wary of how deep the recursion goes.  Usually in this case you would just tweak the code to stop it running out of stack space, or perhaps your data-set is of limited complexity and it just works, so you can ignore it and again just move on.  With Apparance however we have to be a bit more careful.

Tree Evaluation

The synthesis process in Apparance is implemented as an operator-tree evaluation.

Simple tree evaluation example

This means that starting at some root procedure we evaluate its output, triggering this sequence of events:

1. The graph inside the procedure is instantiated and connected up.
2. We find what the procedure output is wired to, and evaluate its output (recurse to step 1).
3. At some point we reach a fundamental operator instead of a procedure.  Evaluating its output results in some code being executed to perform its intended function.  In order for it to be able to do this though it needs input data, which it requests (another function call) as required until it can return with the calculated output result.
4. We find out what the operator input is wired up to (this happened in step 1 for its containing procedure).
1. Usually this will be another output and we will evaluate that (step 2).
2. If our input is actually wired to a procedure input, then in a similar way to 4 we have to see what that is wired up to and recursively follow it until we either reach another operator output (step 2 again), or we reach a constant value.
5. On reaching a constant value we now have data to pass back up the call graph and we can return.  There are a couple of ways constant values can appear in a procedure:

1. Embedded in a procedure itself as a constant input.
2. As an input parameter supplied to the root procedure.
3. Output-only operators that obtain the value from outside systems, e.g. mathematical constants like Pi, or useful synthesis state like the current block size.

The upshot of all this is that as we dig deeper into our procedure graph, and at every step towards some constant data value, we are making deeper and deeper function calls.

Data Driven Code

Normally the execution call graph is largely hard-coded into a program; conditional branching changes the exact shape of this graph, and recursion can cause chains of similar shaped sub-branches to push it deeper, but it is still largely predetermined in behaviour.  During development, the stack usage may increase, but this maximum will largely not change during the execution of the program.  As a consequence, for most programs it is impossible to blow the stack in every-day use.

For a data-driven situation however, you can no-longer make this assertion; we don't know how deep our procedures will end up going when we are building them in the editor.  It is very simple to accidentally create a procedure that recurses for-ever and instantly overflows the stack.

Simplest procedure that overflows the program stack.

This is a problem since these crashes happen at edit time, when the application is in the hands of the end user, and not during its development where a debugger and developer are at hand.

A Walk In The Dark

In some senses, every program is a ticking time-bomb.  Are you really aware of how close your program runs to the stack limit?  Do you just ignore the problem since you've never hit it?  Do you even know how much stack space is available to your program?  It's a bit like taking a night-time stroll on the cliff-tops, everything is fine, until it suddenly really isn't.

It's a bit of an odd situation because languages don't really acknowledge the existence of a stack limit and it seems a little talked about point.  There don't seem to be any ways to query the stack, or work out the current depth, using standard library calls.  This may be because there are ways to hand code this and it's such a rare use case that it's just not worth the effort supporting it, or alternatively it is acknowledging what should be entirely an implementation detail that the programmer should make no assumptions about.  Anyway, I need to know the limit and I need to monitor the depth as procedure evaluation is performed and so in the absence of any library support for this it's down to a hand-rolled approach. 

Get A Tape Measure

First, how deep are we?  A few searches online reveal what I suspected; that the simplest way to measure how deep you are in function calls is to take the address of a local variable (or function parameter) at the start of the program and compare it with the address of a local variable in your current function.  I created a macro to do this:

 #define CURRENT_STACK_LOCATION(a) ((uint64_t)(void*)&(a))

Used like this:

 int a;

 uint64_t stack_pos = CURRENT_STACK_LOCATION(a);

During synthesis this is evaluated each time we dig deeper, and compared to the initial stack position.  If we go too deep, we flag the error and abort the synthesis, unwinding the stack with returns triggered by an error check.

How High Can You Get?

The other important question is "how big is the stack?".  There doesn't appear to be a way to measure this in code and some investigation reveals that this is something you can set in your EXE project settings (for C++ project), or via some EXE fiddling (with EditBin.exe) for C#.  In both cases though, the default seems to be one megabyte.

Assuming this 1 MB is actually 1,048,576 bytes (2^20) I decided a 1,000,000 byte threshold would leave a nice safety margin after triggering an abort of the synthesis run.  This seems to work fine, and you can see the results of this with the simple test case (proposed earlier).

Results of simple stack overflow test procedure running.

We managed to get to an evaluation depth of 15,624 and it was a final stack frame of (at least) 96 bytes that pushed us over the million byte limit.  This is plenty of space for very complex procedure evaluation, but with the safety net of knowing you aren't going to crash.

Engineering

It's quite likely that I have missed some useful API call or technique that could have saved me some time or prevented various assumptions here, but I guess this is an engineer's approach to the problem; measure, try stuff, get something that works, and test it.  It seems to work, and until I find a platform/machine/OS/scenario where it doesn't (or a suggestion to improve it)  I will consider it solved for now.  If you have any suggestions, or concerns, please chip in below.

Thanks

A quick thank-you to those that came up for a chat and see me demo some of Apparance at last weeks Tuesday Night Gamedev Pub gathering in Guildford.  There were many good questions and interesting conversation, and I could see that the whole project was making people think, hard (either that or the beer was making it hard to think).  Your questions and chatter prompted the writing of this post.  I hope to demo again next time for those that missed it.

What is project "Apparance"?

Videogames

I have been making videogames for over twenty years, and the process always seems to go something like this:

1. Design game
2. Create assets
3. Write code
4. Test game
5. Repeat above in various combinations until done (ship or bust)

These steps are quite separate, mostly performed by different people (or groups of people), and the bigger the game the more of all this you need.

Some time ago I came to the conclusion that above a certain project size this model isn't very efficient for a variety of reasons. Firstly, because assets need to be worked on by multiple people, the friction associated with moving them around (conversion, source control, management, communication, builds, deployment, and loading) can mean lots of additional effort and add up to long and frustrating iteration times.  Secondly, as projects have become more ambitious, with larger scopes and game-play areas where the work involved in creating them increases exponentially (with area/volume), the cost also ramps up this way because the work a team puts in can only, at best, grow linearly with size.  In addition to this, a natural consequence of growing teams is the need for increasing communication, management, and support.  All of these pressures usually mean compromises being made to the game's detail, richness, variety, polish, quality, or seemingly low priority support work is neglected, in order to get it to fit within the budget.

Pondering this problem for several years I have formed a vision of how I think we can improve this construction and authoring process, and what the technology and tools it requires would look like.  I'm fed up with conventional approaches, the waste, the sluggish pace, the repetition, the tighter squeeze on the more fuzzy aspects of creativity like experimentation, play, fun, emergence, and instinct. I want to try working a different way, using novel and interesting techniques, powerful technology and tools, to empower smaller teams to create bigger things.  I believe we can do better, and whilst it won't be everyone's cup of tea, it's something I believe passionately in.

"I'm fed up with conventional approaches, the waste, the sluggish pace, the repetition, the tighter squeeze on the more fuzzy aspects of creativity like experimentation, play, fun, emergence, and instinct."

I've been working on this project in my spare time for around five years, with the original concept rolling around my brain for about five years before that.  As I described in my previous post I am now in the fortunate position to be able to invest all my time in this project.  So, what exactly is it I am proposing?

Vision

I want to enable rapid creation of rich and varied worlds through fully dynamic procedural generation.  I want to encourage play and exploration through fully interactive live editing of content and behaviours.  I want to make games in creative and exciting ways:

• Rich worlds full of the variety that parameterisation and procedural techniques can enable.
• Vast structures with intricate detail from highly scalable dynamic modelling.
• Endless continuous worlds with no loading and no transitions required.
• Don't repeat to save time, every instance can be unique in design and appearance.
• Instant feedback and fast iteration from rapid and responsive tools.
• The play and exploration that real-time control systems with live editing allows.
• Freedom from bulk assets and offline asset pipelines by going fully run-time procedural.
• Increasing the efficiency of creating content through asset modularity and easy reuse.
• Making extensive use of visual editing paradigms (data-flow, node-graph).
• Removing hard coded content, everything data driven.
• Small footprint applications yet with all the richness of today's larger titles.

There is nothing out there that does all this, the technology just don't exist. I see this project as an adventure where we are specialising in procedural generation and real-time interactive experiences that can be applied to a variety of applications; especially games, education, and interactive visualisations. If we aspire to travel to new lands but the vehicles to do so do not exist, we must first build them.

"If we aspire to travel to new lands but the vehicles to do so do not exist, we must first build them."

What it is

This is an authoring environment in which to create your worlds, populate them, and bring them to life. The real-time synthesis engine uses procedural definitions, their input parameters, and the surrounding environment to dynamically fill out the world in more and more detail as you explore.

Apparance Editor - Procedure graph for roof section of an old house

The editor provides authoring and testing of the world through a visual flow based editing model (nodes and wires) to create the procedure definitions describing the geometry, texturing, effects, physics, behaviour, logic, and much, much more.

A standalone player application provides a non-editable view of world, for test, play, and release.
The underlying engine contains the technology driving both editor and game, using highly concurrent operation, with dynamic detail management, largely stateless data-flow control and AI systems, and all with live editing/monitoring during authoring and play.

What it is not

It is not a silver bullet and won't solve everyone's problems; Some games won't fit the development model and technology being created here.  It may be that a game relies heavily on areas that are a particular weakness for this technology. Some games are based on very tightly controlled and designed environments and behaviours. But I believe that working toward its strengths and away from its weaknesses is no different to any existing games development, more so historically as hardware and software capabilities have applied their own unique constraints on possibility.

I don't see it as a plugin for other engines; using a lot of unique techniques to achieve its aims means it may not work well in more conventional engine scene graphs and rendering.  The lack of scalability in many existing systems can cause problems too as non-scaling systems 'crowd-out' the scalable ones as a project grows.  This is a disruptive technology, and relies a lot on the interaction between the various novel techniques at play.

It is not finished yet.  This is a project that I've been working on in my spare time, and whilst showing great promise already, there is still a lot to do to.  I see many stages to its development and I will be building demonstrations and even games to show-case it at various points in the future.

Direction

This is an ongoing project and I want to involve people as it develops.  Through blogging and sharing the results of my work I hope to involve like-minded and creative people to help shape the tech and tools into something that many developers could benefit from.  I am working towards releasing versions of the tools for you all to play with to see what we can create together.  If you are interested in these ideas and the prospect of trying something different please get in touch via email, via my Twitter feed, or just follow progress here on my blog.

The Name

Logo design idea - featuring one of the first models built with the system.

Apparance (or often Apparence) refers to the outward manifestation of a person or thing, the act of being visible, what others see, the process of creating this external impression. The original inspiration for this comes from "Against A Dark Background" by Iain M Banks; The Solipsists don't subscribe to the concept of the individual with no use of the word 'me', referring to, and in a way justifying, the existence of other members of their group as 'apparences'.

Next

Next time I will bring you a full project status report, showing the current state of play and what I'm working towards at the moment.  It should be a very visual post as there is lots to see.

What's it all about?

Ok, so, enough preamble, what is this all about you ask?

For a long time I've dreamed of having a way to make the creation of electro-mechanical, electronic, electrical and purely software devices easier by replacing all the custom control electronics with a computer. This is a fairly obvious approach, nothing new there you say, but I am after something more powerful, I want to be able to construct the controlling software with the same methods and techniques used when creating the physical parts. Designing, inventing, and creating a physical system or machine is a process of experimentation, testing, iterating, and trial-and-error. It involves wiring up motors, switches, lights, sensors, modules, relays, solenoids, valves, and more to IO ports of a computer or microcontroller, fiddling with wiring, tweaking controls, watching the effects, plugging them together in a way you have never before to create something new. I want the same process for the software that runs them. I want to be able to drag virtual components and circuits around the screen, plugging them together this way and that, tweaking values and watching the results, a fully interactive control system working with the hardware, all in real-time. I have so many projects that could work like this, so many things I want to experiment with, so many ideas, so much that could be done with a system like this, that it has become a project to preceed all other projects. Every time I think of a new idea it rapidly degenerates into 'how much easier this would be if my control system idea existed', and then to 'there's no point investing any time in hard wiring/coding my idea when I could be working on this general solution that will benefit all projects so much...'.

And so, we have my project, a technology I am calling Virtual Information Circuitry Engineering, or V.I.C.E. for short. I'll expand on what it entails next.