One month later, and we’re still working on the editor backend — it’s actually going really well, aside from the fact that it’s taking much longer than we anticipated!
As you may have noticed, this is a recurring theme with Robotology: our scheduling estimates are based on the known hardest task, however the actual effort required to complete a specific goal is inevitably determined by a task which was undiscovered during the planning phase.. resulting in a state of perpetual under-estimation. Frustratingly, it seems like the very nature of what we’re trying to do — developing new ideas for which there are no known or established solutions — results in us frequently running into unforeseen issues.
The editor is a perfect case-study of this phenomenon; re-reading our previous post, we seemed to be convinced that most of the hard work was done. Sadly, this turned out to be a bit optimistic. 😉
First, some background: the basis of the editor is a Doubly-Connected Edge List data structure, which is a lot like a 2-dimensional doubly-linked-list (lists being inherently 1-dimensional). The world is described as a 2D graph — a set of nodes connected by edges — and the DCEL is how we represent this graph. We then generate surface geometry by assigning a “thickness” to each halfedge in the DCEL, in essence inflating the graph to generate polygonal shapes.
This approach is similar to metaballs (not to be confused with meatballs!) except that while metaballs use points as the fundamental primative, we use lines; the result is that where metaballs produce smooth, rounded surfaces, we produce angular, faceted surfaces.
Here are a couple of screenshots: one, two.
Getting back to our previous topic — why the editor backend is taking much longer than anticipated — we had anticipated that development of the DCEL would be the main task. We made sure to carefully plan our implementation, because we knew from experience in school that writing linked-lists is often trickier than you’d think — and not at all fun to debug! It took us a couple days to implement the basic DCEL and iron out all the kinks. We then tried to take the next logical step, which was using the DCEL to generate a set of polygonal shapes.. and it was here that our plan fell apart.
While DCELs themselves are fairly straightforward and well-documented, the way we’re (ab)using them is unorthodox — rather than making a graph which explicitly describes polygons (nodes and edges representing the vertices and line segments which define a set of polygons), our graph is treated as a “skeleton” which is then inflated to generate polygons. During planning (before the DCEL was written) we had prototyped this inflation process, however once we created the proper version using the DCEL several holes in the prototype method became clear. And so, contrary to our initial assumptions, the actual hardest part of creating the editor backend wasn’t the DCEL itself, but the surface-generation algorithm.
We then spent several weeks trying to find a solution that worked.. this was a fairly harrowing ordeal which warrants a post or tutorial of its own. The short version is that we eventually got it all working. While it definitely sucks that it took almost a month to complete a task we didn’t think would take more than a day, we’re just happy that in the end we managed to find a good solution. Barring any further roadblocks, the remaining bits should be finished in the next week or two, and we can then get to work on the front-end/UI.
So far we haven’t found a good name for the editor.. candidates such as “The Line King” have been dismissed as too silly, while others such as “Inflated Polygonal Graph” are clearly not silly enough. Hopefully by the time it’s all done we’ll have hit upon a suitable title — or better yet, a clever and/or punny acronym.
That’s about all that’s new around here. For the past couple weeks, we’ve been judging IGF entries during our spare time; as usual there are tons of great games this year. In N+ news, we’ll be choosing winners for the third Contesque any day now, so keep those entries coming!
With any luck it won’t take another month for us to write the next post 😉
It would make logical sense if the editor was called “Red” for Robotology Editor. Nice link to N and Ned, and Red is a pretty cool acronym.
>>So far we haven’t found a good name for the editor.
“Inflated PyG”?
“REd PyG”?
pyg coming from “PolYgonal Graph”
True — the problem there is that Raigan keeps insisting on going one step further and calling it “Big Red”, which sounds like a trucker or a lumberjack!
‘Big Ned’ sounds pretty crazy too, you know!
Edit
Robotology
Levels
Utilizing
Graphs
Which
Are
Both
Inflated
And
Polygonal
Erlugwabiap. … You know what, never mind. I was onto something but that is certainly not the order to use >_>;
(I support Red, maybe!) Additionally I don’t exactly understand everything (I understand it a little!) but it does sound like good things are happening. One day you’ll realize you really ARE done the hardest task! 😀 Yay!
A quick grep gives me 825 words with the letters DCEL in that order, and 56 of those start with D and end with L. But most of them suck. Of them all, I kind of like “dacelo”, which is the genus of the Kookaburras, and “deckel”, an alternate spelling of deckle, which has something to do with edge treatment in paper manufacturing.
Incidentally, it’s hard for me to figure out the rules that the inflation is using, by looking at the examples. Some edges are in the center of their inflation, some are not. Inflations vary in width. Some corners are beveled, others not. I’ll be interested to read the developer tutorial.
1st thing first: Thanks for the update, it sounds like you’re making progress. I like how it seems you’re going for quality over quantity and avoiding the quick and dirty solutions. Keep up with the good work!
Could you maybe tell us some more about the concept of robotology? Gameplay? Maybe some idea of the gameplay and character functions will promote some ideas.
And yes, that is both a suggestion to come up with a name as well as a sneaky way to ask for more Robotology information.
he’s right. Christmas is thursday after all…
@AlliedEnvy: It makes a lot more sense when it’s in motion.. one thing to note is that DCELs are based on halfedges, which means each side of each lineseg can have individual properties — like thickness/inflation. We don’t know if this is useful enough to leave, or if it’s better to hide it and make both sides always have the same inflation (so that the interface is simpler/more streamlined), but for now the thicknesses can be set independently.
The “inflater” tries to bevel any acute corners, convex or concave, however it’s not 100% (it gets really complicated, for instance when two bevels interact they may generate an acute corner, so you then need to bevel the bevels, etc). Additionally, in order to support variable thickness platforms, adjacent segments with different thicknesses are beveled so that they meet.. otherwise, there are unsolvable situations (imagine two horizontal lines where one is inflated more than the other — there is no natural intersection, so we add a diagonal bevel to bridge the two surfaces). And there are several “endcap” styles, though this is still in-development (you can see in the screens that all shapes are using the same endcap, later this won’t be the case).
The rules were actually the difficult part, we finally gave up on trying to use an explicitly rule-based solution because there were so many different combinations of cases (like beveling the bevels), the solution we ended up using was to frame the rules as geometric contraints, and feed the whole thing to our physics solver.. this seemed like a brilliant jump at the time but later we realized it should have been the obvious solution from the start — when we were researching the physics solver we came across a lot of papers on solving systems of geometric constraints in CAD/CAM apps!
The biggest challenge with the editor is going to be figuring our which of the functionality should be exposed, and which should be hard-coded for simplicity.. we _really_ don’t want things to be as complicated as e.g Soldat PolyWorks, we want to retain the simplicitly and constrained-ness of Ned, but using a different sort of building block rather than tiles.. because tiles become a lot less fast+fun when you’re trying to make multi-screen levels! Maybe it’s just that the # of primitives you need to manage increases exponentially with the level size.
We’ll probably post more about the game itself once it’s more fully realized, we have specific things we want to do with the visual style and the technology, but in terms of how it’s framed it will probably be whatever ends up working — for instance, we don’t know if it will be “field-based” like Mario/Umihara or a more area-based coherent world like Castlevania/Metroid. Similarly, we don’t know yet how well our physics-based animation will work; this will have a pretty profound impact on the final game.
We actually just came across this developer blog, it’s someone who’s also in Toronto and is doing similar stuff with physics and animation (and also made Polyworks coincidentally!), pretty interesting: http://polycube.blogspot.com/2008/09/yet-more-physics-animation.html
Big Red is a gum’s name Raigan…Not to mention is does sound ridiculous. In all honestly, whatever you name it N players who convert will call it Ned or Red even if you name it something extravagant or different. We are a) lazy and b) creatures of habit.
Red sounds like a good name to me. Short, snappy, simple and it fits in with Ned.
Wow, I totally forgot the gum — to be fair I don’t think we have that in Canada, but I do buy a pack everytime we’re in the US..
I don’t mean to change the subject, but what language do you guys use for programming this Robotology stuff?
We have prototypes in Actionscript 1 and 3, but we moved over to C# a while ago. We don’t know yet if we’ll need to port to C++ at the end, but for now we’re sticking with “plain” C# (i.e no XNA/non-cross-platform stuff). We still use AS1 sometimes to quickly try stuff though.
Ahh man, I was hoping you guys used C++, and were willing to give me a lesson in DirectX programming…
Hehe.
On a relevant note: Why would you have to port to C++ from C#? Doesn’t C# work fine?
C# is working fine so far, but (a) we might need to squeeze every last drop of performance we can get, we have no idea yet how slowly things will run in a regular game scene since currently we don’t have everything up and running (b) C# isn’t as nice to deploy as C++, it requires .Net or Mono.
We’ve been judges for the IGF for a few years, and the number of C#/.Net games that run properly is _very_ small; it’s sort of like pygame — great for developing but basically you can only guarantee it’s going to run properly on your computer, it’s not really a good solution for releasing to the public.
Possibly the real problem with games we’ve been exposed to is XNA and not C# itself; this would be great if it was the case, since we’re not using XNA. Once we get the OpenGL parts written we’ll be testing it on different systems to see if it runs properly.
Definitely we’d like to stay in C# permanently, Visual Studio in C# is a really great tool; it just comes down to whether we can manage to get things running quickly and how easy it will be to get things working cross-platform.
One problem with C# is that there’s actually no good way to get a proper stable game loop going without resorting to unsafe/C++ code.. it’s pretty stupid! And we’re pretty anal about having things run smoothly.
I see…
So why’d you choose C# in the first place?
Well, it’s a lot easier and faster to work with than C++, especially for us (since it’s very similar to AS3/Java which we’re familiar with).
We’re trying to get a bunch of complicated stuff working (physics-based walking, geometry editing, etc), we thought it best to keep the language as simple as possible 🙂
How about “Reddit”- Robotology Editor? 😛
Red. It’s catchy. ^^.
Got one, F.I.G.U.R.E
Fully Integrated Greatly Used Robotology Editer!
I know, it’s not that great, but the word “Figure” is a the perfect thing for it, seeing as the letters end with Robotology Editer