Archgrove - Implicit Definition

After Windows Update toasted my Vista install last week (Twas impossible to login as the console,I could only recover by RDCing in and using System Restore), I bit the bullet and bought an iMac to use as my primary desktop. I’ll keep the Windows machine around for games and some development work.

Overall, I’m very happy (but then, I’ve been a Mac laptop user for years). The only problem is the TN panel screen, which has an annoying top to bottom gradient (some colours get very desaturated as you move down the screen). It’s not ideal, and less than I’d expect from Apple. However everything else is perfect, and as I’m no graphic designer, I can afford to live with it.

My first tiplet (which is no doubt very obvious to most people, and maybe even in the help files) is that you can save Automator workflows as application bundles. It’s significantly easier to achieve some small tasks (which don’t have control structures) with this mechanism - I currently use it to read me the RSS news headlines when the machine alarm goes off. Yes, this could be achieved with more traditional programming methods, but occasionally, graphical workflow tools are useful.

As mentioned, some spare time at the moment is being spent investigating the mistakes other people make using the W3C DOM API. Having now looked at literally hundreds of separate bugs, I’ve begun to construct a coarse categorization for each. I don’t claim there’s anything novel here - in fact, most of us have these internal categories well defined. All I’m doing here is spitting out a semi-minimal collection of them, and giving each a title.

Some types of errors can be argued to fall into multiple groups - this is no bad thing. The idea, eventually, is to speak of how effective certain techniques are at preventing certain types of error.

Errors of ignorance
When you don’t know what you’re doing

A remarkable amount of bugs just boil down to raw incompetence. Harsh words, but in reality, we’ve all been there. Using languages and frameworks before we’ve actually performed some experiments, being thrown into fixing a problem in a system we’ve never seen before, being forced to render comment on a project before we’ve even seen a spec - all old stories for even the most talented developers. Errors of ignorance capture the problems you introduce in this state - using the wrong constructs, not knowing what frameworks actually do, and generalised language idiom failures.

Errors of expectation
When the outside world intrudes.

Most of the time, we’re dealing in some form with input in our programs. If we expect input in a certain format, and receive it in another, this is our fault - we need to be more robust. We might also think we’ll get input in a given format, but it’s subtly different.

We can also have expectations on what other people will provide for us, or the side effects they will have on the world. Any problems induced by our expectations differing from reality, I’m currently calling “Errors of expectation”.

Errors of omission
When you forget to handle something

Often, we know what we’re doing, we intend to do it, and then just forget - perhaps to handle an edge case, perhaps to release a resource. Our natural forgetfulness leads us into “Errors of omission”.

NB: This is currently my least favorite category, which I hope to kill off, but some bugs just fall into this group very naturally.

Errors of intention
When you just got it wrong.

These are what most people would call bugs - when the we, the programmer or designer, just get it wrong. Perhaps we thought the algorithm worked when it didn’t, perhaps our mathematics is just wrong, perhaps our expectations are mutually inconsistent. The code is doing exactly what we wanted - it is, in it’s way, flawless work. It just doesn’t do the right thing because, even having missed all the above classes of errors, we still didn’t know what the right thing was - we’ve committed an “Error of intention”.

This is my first attempt at a concise set of names to concepts I’ve been dealing with for years - it will be interesting to see how they evolve as I try and put it to use.

At the moment, I’m spending spare moments collecting and collating idiomatic failures in Javascript (specifically, failures of DOM manipulation in Javascript). This is, alas, proving harder than I expected – bug database trawling is about as fun as it sounds and, more importantly, the bug databases don’t keep track of developmental bugs.

By idiomatic failures, I’m referring to common mistakes and patterns that cause errors. Suitable examples from other languages would be

• In C, failing to account for the null string terminator
• Buffer overruns, in C and C++
• Off by one errors in pretty much every language
• With C++, delete’ing a new[]’d resource
• In PHP and many other scripting languages, failing to account for the weakly typed comparisons (so you forget that 0, null and the empty string are treated as semantically the same under comparison, but are distinct in your program logic).

These are the building blocks of certain types of program failure –often, when debugging, one of these type of error is the cause.

Of course, I’ve run into these many times myself, but that doesn’t really say much about the commonality of the problem; I may be a particularly poor programmer. So, I’ve been spelunking around bug databases for long running open source projects (i.e. the Javascript libraries behind Ruby on Rails); this is proving somewhat fruitful, but it’s a statistically invalid sample. As mentioned, the bug databases only tend to get populated by bugs in release versions, and then only the bugs that people have bothered to report. If a developer finds a bug whilst he’s developing, these are often not added – even if it took days to track down. Moreover, if they find a bug in a release version themselves, they often quietly fix it. Bugs that only occur rarely and are not repeatable are added almost never.

In a way, this is quite good – the failures I’m seeing are the ones that escaped testing, escaped the eyes of the developers, yet blew up in a users face. These are the hard to see bugs – the most annoying of the species. On the other side, this is quite bad – I miss a huge subset of bugs that fall into my class of interest.

Of course, these types of problems could be considered language defects – stupid mis-features that bite people again and again specifically because they are so artificial. After I have a relatively complete map of these failures, I’m going to move onto logical failures and failures of design that are common within Javascript/DOM – i.e. conceptual black holes that people are repeatedly sucked into, the actual failures of programmers.

Right, we left off (a long while ago), having looked at the basic dungeon layout. The question was, how do we turn the geometry of a dungeon cell into a two dimensional map? Let’s look at a (badly, hand) drawn section of a dungeon wall. It’s got a floor, some obvious wall, and a little “hump” – some kind of rock, or bizarre architectural anomaly (it is a dungeon, after all).

We can see the raw triangles in 3D, and we’d like to get this down to a set of lines in 2D (we can draw lines very easily using the APIs available to us). To accomplish our goal, we’ll need to think about what we actually want to see on the map – showing the floor, and little lumps and bumps is not really useful information for people. The only real obstructions that they’ll want to see mapped are the extents of the dungeon – the walls.

How can we distinguish a wall from the geometry? Well, the distinguishing fact I used in my simple algorithm was that it’s vertical – everything within a certain tolerance of the vertical axis is a “wall”, and would appear on the map.

On this diagram, we see the tolerance region – all polygons that are upright enough to be contained within the triangle are going on the map. Let’s remove everything that’s outside the verticality acceptance region, and see what we’ve got left.

Not bad – everything remaining looks pretty damn wall like to me. All we’ve now to do is turn this into a set of lines, discard the vertical components, and we have a reasonable 2D representation of the dungeon block we can use to map.

That’s pretty much it for Magellan 2 – once these line blocks are collected, they’re simply transformed (by some simple mathematics) to deal with the translation and rotation of the dungeon relative to the current viewpoint of your character. Rendering them to the screen is just a case of taking each line, transforming it, and then telling Decal “draw this line starting here and ending here”.

There are plenty of problems with this approach (some of which manifested themselves in the released version); however, this explains the basic concept (which was all I set out to do). One day, if there’s interest, I might write about these design faults, and the potential improvements that could be made.

Just to clear up some misconceptions, the point of this article is not to recreate the plugin, or repair it for the modern Asheron’s Call. The plan is to write a set of articles on how it was created, and why it (in general) worked. Those looking for a replacement would do well to visit http://www.flynn1179.me.uk/ac/?minimap and see the impressive looking work that Thorfinn Sigurdssen has been doing (Disclaimer: I have neither personally tested this, nor been contacted by the author).

Last time, we left off having made a series of educated guesses about how the dungeon system in AC works. From our observations, we’ve noted that every dungeon seems to be laid out in a giant 3d grid of cubes – assembled as if from lego bricks, prefabricated elements of dungeon.

We can see the prototypical dungeon template above – each little cube is ready to be filled with a one of a choice of dungeon blocks by an eager designer. A template block might look as follows.

This one is taken from my Asherons’s Call 2 archives (so don’t go looking for it in game), but it illustrates the point. The player walks around on the interior (the complex looking set of triangles), and the rest of the cube is filled with virtual nothingness – in this fashion, we can make our big cubes look like caves, temples, whatever is needed (rather than a boring apartment block).

We could take four of the above dungeon elements (that we call dungeon cells), rotate them around and put them into adjoining cubes in the template to create a donut dungeon – a giant loop. Obviously, it’s up to the designer to ensure that there’s no corridor or tunnel that leads into an unfilled cube (and hence into the void).

This is all well and good, but now that we’ve made a plausible (and in this case, rather educated) guess at the dungeon structure, how does it help us? Our task is to draw a map of the walls of the dungeon, not big wireframe meshes stuck around the place! So, tune in next time to see a little bit of simple mathematics that will transform the above into something more useful for our purposes.