Architecture Part I

Good Lord!  Is that the time?

I have neglected this blog shamefully for most of a year.  At least, it would be shameful if anybody were reading it, but I don't suppose anybody is.  At any rate, here we go again.

How will this thing all fit together?

The application is intended to take data stored on a back-end (Domino server), present it in a front-end (browser), and handle communication between the two. First the data for the map, and later the game state, needs to be loaded up, interpreted, and rendered in the browser. Then any changes made in the browser need to be fed back to the server. We have two platforms, and two communication channels. Let me deal with each in turn. This will take several posts - bear with me.

The Domino server provides a number of services that I need (plus a bunch of others that I am not using at this stage).

First, there is storage. All of the data are stored in a single Notes .nsf database file. This allows me to have multiple copies of the database in existence, and bring them into synch when I choose. It also allows me to take advantage of the flexible design structure inherent in Notes, as well as the various languages it supports. I am going to skate over the details of the .nsf file format here, and of the various design elements that it can contain. If you are familiar with it, well and good. If not, I trust I can remain intelligible anyway. The three things you need to know about at this stage are documents, views, and forms.

A Notes document is essentially a database record - a set of name-value pairs (fields), where the values can be any of several data types. Any of these fields can be multi-value - that is, a single field could contain the value "Red":"Green":"Blue", while the same field in another document might contain just "Purple". The set of fields on a particular document is not rigidly determined by a pre-existing schema, and need not necessarily be the same as the set in another document that is ostensibly of the same "form". .nsf files will happily scale to hold millions of records, but a few tens or hundreds of thousands will be quite adequate for my purposes. For the purposes of mapping alone, I have defined two document types - they are:

Map: has a map title (e.g. "Europe") and a list of variants available ( e.g. dates 410, 1618, 1805, 1914). It contains also a number of other parameters such as the dimensions of the map and the graphic to be used by the editor as a guide in building the map in detail. A map may be defined as having up to 100 rows and columns, for a maximum of ten thousand individual hexes. Row and column identifiers are two digit decimal numeric values, running from 00 to 99.

Hex: describes an individual map location. Originally, I had a single document containing all information concerning a single hex on a particular map. I later changed that scheme to have potentially two documents per hex. The reason for this is that a single map may now support a number of variants. I visualise these as being used for different historical periods, but of course other uses may be found later. Some aspects of the map - the shape of coastlines, the location of rivers, mountain ranges and so on, will not change appreciably over a few thousand years. One hex document describes these more-or-less permanent features - the base, or lithosphere. The second document describes the features that change over historical time, which I am calling the biosphere (I am playing a little fast and loose with the term, I know, but I have to call it something). The biosphere document records forests, marshes and human habitations. If I later represent roads and railroads, they will go here too.

A view is a collection of documents, defined by a selection formula as belonging together. It may be indexed on one or more keys, and will typically display a subset of the data contained in its member documents. All of the documents in a view need not be all of the same form or internal structure, although they often are. The main function of views in this application is to present a set of documents to the browser. When the browser calls for a particular map variant to be loaded, it first retrieves the details of the map itself, then the set of base hexes (10,000 of them for a 100×100 map), then the biosphere hexes (a substantially smaller number - maybe 20% of the base count). Each view shows the required information in JSON format, so that having been retrieved by an AJAX call the whole can be turned into a Javascript object with a single line of code. Domino actually has JSON built into it. A view can be defined to show certain data, and can be called on with a special parameter in the URL "&Outputformat=JSON". I can see that being really useful if you want to retrieve into Javascript a view built for other purposes, but the way it formats the JSON is necessarily somewhat generic - Domino has no way of knowing what I am going to do with the data. To be sure, I can turn the view content into a Javascript object, but its internal structure is not terribly convenient. Since my views exist for no purpose other than delivering data in JSON format to the browser, I can be a little more targeted, and roll my own. I will go into that in more detail another time.

A form is mostly used to define the user interface of a document. The UI is united at runtime with the data in a single document to produce an on-screen representation of the document for human beings to read. In this case I am not using it for that purpose, since what is represented on screen is an amalgam of hundreds, or thousands, of documents. I am using a form to lay out the entire application, defining what it will look like in the browser, and calling on code to fill in the details.

The last element I need on the server side is one or more languages for processing stuff - accepting orders, for example, or map edits, and executing them to change the state of what is stored. Notes has four languages built into it that can help with this.

Function Language is a simple declarative language rather like that found in spreadsheet functions. It is used for building view data out of stored data, and in Notes has a number of other applications for it that I won't touch on here. It is no good, though, for intricate processing (although you might be surprised how far it will take you even in that direction).

LotusScript is the scripting language that first appeared in Notes 4 in the mid-90s, It runs both in the Notes Client and the Domino server, and in the client can interact with and manipulate objects in the user interface as well as in the back end. It is object oriented (although not fully featured as an OO language) and uses a syntax much like Visual Basic. LS has been a workhorse of Notes development for many years, and although it obviously does not work in a browser, it remains convenient enough that I am using it at this stage for all of the server-side scripting. Alternatively, I could write all the server-side stuff in...

Java, which has become the mainstream language of choice for many programmers in the last decade or so. Notes developers have been slow to take up Java, for what seems to me one good reason. The Great Thing about Java, the Thing that got everybody all excited, and made them want to re-write everything in that language, is that you can write a program on any platform, and have it run without modification on any other platform that supports Java. No more porting, no more recompiling, no more platform-specific pragmas... sounds great, right? Well, yes, it does, but Notes already had that since the '80s. If you are writing on the Notes platform, your app will already run without modification on any platform that supports Notes. That means pretty much any operating system at all, on both client and server side. That is not to say that Java offers no advantage to the Notes developer, but the single advantage that made Java compelling to the rest of the world... we already had, ten years earlier.

Finally, content for the browser must be in HTML. In Notes there are basically four ways to generate HTML. You can:

1) hand-write it and pass it complete to the browser.

2) have server-side code generate it and pass it to the browser.

3) have Domino generate it automatically on the fly based on a WYSIWYG foundation.

4) pass data to the browser and process it there (using Javascript) into HTML.

In this application I am not using method 2. If HTML is being generated automatically based on a data set, the HTML is nearly always more verbose than the data. I prefer, then, to pass the data, and have the code run on the browser side to render it (method 4). This also allows me to parse the data in more than one way - once into HTML for display, and once (or more) into other formats for manipulation. I do, on the form opened in the browser, have a mixture of hand-coded ("pass-through") HTML to set out the major screen divisions, static text and so on, and elements for which Domino generates the HTML before serving it up. The latter is mostly used for fields, which are easier and more manageable to do in Domino Designer as regular Notes fields than to hand-code in HTML.

Post Lotusphere

Well, Lotusphere is over for another year.  The presentation was duly delivered, and you can find the slide deck in "File Resources", over on the sidebar.

The map editor is used as the chief example of a series of techniques that I thought might be of interest to people.  I have applied them to other, more business-oriented, applications also, but the map editor is the one that is most fun for me, and of course the focus of this blog.

Grid Conventions

Grid or Area?
In recent years board games based on area movement have been the vogue.  Areas have certain advantages - they:

• can be irregular in size and shape (indeed, they are so almost by definition.  Otherwise it's just a grid).
• minimise the number of discrete locations to keep track of.
• simplify movement, by making the size and shape of each area variable with the terrain (or other conditions) it contains.

The trouble is that the areas have to be tied to such local conditions, otherwise there is no point.  That, in turn, means that they have to be individually hand-crafted for each map.  That is not a problem, of course, for a commercial game representing a particular campaign.  For me, though, it is a problem.  What I want to build is not a game, but a platform, on which to build any map whatever (and ultimately, any game).  A grid it will have to be.

The Grid Having decided to use a grid to regulate map movement, the question that next presents itself is: what should be the shape of the tessellation?  Board wargames traditionally use hexagons (hexes), whereas most computer-based games use squares. Sometimes this is a simple grid, like a chessboard, but often it is disguised by being rotated and flattened.  In theory, there are three regular figures that can tessellate, the third being an equilateral triangle.  For our purposes that turns out to be equivalent to hexagons, so I will not discuss triangles further.

Squares
Squares have something of an advantage on computers in that it is easy to calculate the grid references of neighbouring squares in any given direction.  Also, the edge of a row or column of squares is a straight line. running either North-South or East-West (on a straight grid).  Movement can be either only diagonal, only straight, or both.  Only diagonal can't work in a non-abstract game, since a unit on any given square can only ever reach half the squares on the board.  Consider the bishops in chess - one moves on white squares, one on black, but they can never change.  Two practical choices remain, then.  I have written earlier that regulating the map by means of a grid involves some distortion.  The time has come to consider just how much distortion is introduced by our grid, so that we can keep it within acceptable bounds.

If a unit can move only along the axis of grid rows, each move to a neighbouring square covers one unit of distance in one unit of time.  Very good, if the intended destination lies along one of the cardinal compass points.  If it is in some other direction there will be a greater or lesser degree of distortion.  Assuming that  a unit takes one unit of time to move from one location to a neighbouring location, it should in that time cover one unit of ground (we are not yet considering the  effects of different terrain).  If it covers a greater or lesser distance in that time, movement is distorted along that direction.  This distortion is something we want to minimise, so we must first measure how great it is.

The maximum distortion occurs when movement is not through a face of the square grid cell, but through a corner, like the red path at left (the green path goes straight through a face).  If diagonal movement is permitted, a unit has a choice of eight locations to move to.  If it chooses to move to one of the four diagonally adjacent squares, the distance covered one unit of time is the square root of two (1.414).  A unit moving non-diagonally covers only one unit of distance in the same time.  The one moving diagonally is therefore about 41% faster.  Or to put it another way, the one moving EW or NS about 29% slower.

If diagonal movement is not permitted, the unit has only four neighbouring squares to move to.  A unit wishing to follow the red path must fist go east, A-B, along the green path, then north, B-C.  In the same time, one going due east also travels two squares A-B-D.  But how much ground has each covered?  The one moving east, A-B-D, has covered two units of distance.  The one heading North-East has covered 1.414 units (root 2).  Movement North-East, "through" (actually around) the corner is about 29% slower, or moving straight East through the face is about 41% faster.  It turns out, then (not very surprisingly) that whether you allow diagonal movement or not, one set of directions has a speed advantage of 41% over the other set.  The size of the distortion is not affected, just which directions are (dis)advantaged.  Can we do better than this?

Hexagons

A hexagonal grid is simpler in that there is no choice to make about whether or not to permit diagonal movement.  There are six possible directions of movement, all through a face of the hexagon.  The question remains, though, of how much distortion there is in heading for a destination that is off one of the six facial axes.  Again, the distortion is maximised by going straight through a vertex, so is similar to the second case above.  This time, we will compare moving two places straight East (through the faces) with moving 30 degrees north of east.  Each move passes through two hexes, so takes the same amount of time, but how much ground is covered by each?

If the distance between the centres of two neighbouring hexes is one unit, the distance from a centre to a face is .5.  The distance from the centre to a vertex (which is the same as the distance between vertices - the length of a face) is one third of the square root of three (1.732/3 =0.577).

Our two units each move through two hexes, taking two units of time.  The one moving directly east, along an axis of the grid, of course covers two units of distance.  The one moving 30 degrees north covers the equivalent length of a line that passes from the centre to a vertex of the first hex, from one vertex to the next of the middle hex, and from that vertex to the centre of the third hex.  Each of these distances is (square root of 3)/3, so the total distance is simply the square root of three (1.732).

We now have three scenarios in which to compare the advantage of the faster moving unit over the slower.

---

	Faster	Slower	Advantage	Penalty
Square (face movement only)	2	1.414	41.4%	29.3%
Square (face + diagonal)	1.414	1	41.4%	29.3%
Hex	2	1.732	15.5%	13.4%

---

The hex map has the clear advantage.  It does introduce a distortion to movement, but the maximum distortion is 15.5%, as against over 40% for the square grid.  That's acceptable.  15%, then, becomes my maximum tolerated deviation from spec. in other measurements.  I trust I can do a good deal better than that.