Destiny Project Notebook, Folio 3

Barrier Implementation

27 July 1997

type -- index into display palette (e.g. 3 = stone wall)

height -- barrier height in meters

thickness -- barrier thickness in meters

closure -- (BarrierOpen, BarrierClosed, BarrierLocked, BarrierBarred)

permeability -- bits indicate the Game Agents which pass through the barrier: None (=0), Physical Force, Magical Activity, Physical Energy (e.g. light, vision), Fire Activity (generalize to chemical reactions), Fluid Activity (water, other liquids, gasses pass through), Physical Pressure (e.g. sound, force of explosion), and Missiles (arrows, thrown rocks, etc.)

susceptibility -- defined as for permeability, but indicates the types of Game Agents which can damage the barrier.

integrity -- the barrier-ness of the barrier, reduced by damage and weathering. Could be increased by maintenance. At integrity = 0 the barrier closure becomes BarrierOpen.

damageDeflection -- the fraction of damage which does not affect the barrier but is instead deflected into the immediate area of the barrier (on the side from which the damage was attempted).

weathering -- the amount of integrity lost during each weathering period. [Not sure what period should be but intent is for it to be in the 5 to 10 day range.]

visible -- normal barriers are visible, but some could be invisible (either because they are magical in nature, or for some special gaming purpose like preventing a planned route from going over a cliff edge).

Door bool is needed to indicate if barrier can be opened without destroying its integrity, or use a different subset of states.

Tiling bitmaps for barrier in isometric views

28 July 1997

Distort bitmaps per surface orientation, combined with isometric transformation (nearest neighbor to avoid color distortions). Align bitmaps on fromt corner.

Perhaps barriers should be vectors or splines instead of being map cell based. This would require that doors not be barriers, but rather a mechanism for getting from one side of the barrier to another.

If a barrier is a long line we will also have to handle damage differently. Integrity might ogiginally be per unit length. After damaging portions of a barrier to differeing degrees, an array of integrity numbers might be needed to describe the state of the barrier. Could assign states in fixed units of 1 meter in length (number of required states in the array could be set as soon as the length of the barrier was known). A side benefit of the vector / spline approach is that a barrier "layer" is not really needed, just a barrier "list"; it is not necessary to specify all the blank cells where a barrier isn't.

Hmm. How about Bezier curves w/ control points that have optional handles, as in Corel Draw or Ray Dream? Editor should have grid with adjustable spacing and line every n grid intervals with option of snapping point locations to the grid. Control points would have no handles (sharp corners), locked handles (each side directly opposite the other), or freely rotating handles. Control point options would be add node, delete node, change node type.

Curvy barriers would have to be faceted if surface normal illumination model is to be used.

29 July 1997

Bezier editing in Ray Dream

Bezier editing in Corel Draw

3 August

The map editor is now at 1,883,058 lines compiled in 906 seconds.

16 August

Bezier curves of order 3, specified with 4 points (for display, transform the points, then use 2-D Bezier interpolation / blending), n = 3, i from 0 to 1 (2D) or to 2 (3D).

The parameter u varies along the length of the curve from zero at x(0) to one at x(3).

When drawing, step size applied to u determines the coarseness of the representation. Ideally, one wants the step size as large as possible as long as the step length along the curve remains less than one pixel (or possibly up to 1 1/2 or 2 pixels?) We can use the fact that the Bezier curve will not exceed the bounds of the convex hull of its defining points.

By computing the longer or the two paths from x(0) to x(3) around the convex hull in pixels length, then dividing one by that length to obtain the step size for u:


Then again, one could compute (more simply) the length of the line 0-1-2-3 and use that distance to determine the step size.

Drawing a thick Bezier curve presents other challenges. One first thought is to make second and third curves with control points displaced cross-tangentially by a half-width.

This provides rather absurd results for sharp curvatures.

And breaks down completely in some circumstances.


A more conventional oval. We can think of the control points of the inner and outer surfaces as being on lines that bisect the angles between adjacent control lines.

Doubling of handles


Palette Problems

1 Nov 1997

Current palette implementation consumes vast amounts of system resources. Results in long delays when starting and stopping the map editor or map display applications (5 minutes, sometimes more). After implementing barrier display (w/ barrier palette) has to modify editor application to share palette copies between layer displays and the whole map display, otherwise Windows 95 would crash due to exhaustion of graphics resources. (July - August 1997)

Could reduce problem by

  1. Having a single "materials" palette w/ patterns for terrain, barriers, and (later) textures for character animation.
  2. Allowing palettes to have less than 256 patterns, preferably only as many as are filled (i.e. actually in use).

In addition, restricting the palette pattern to two colors in unnecessarily restrictive, since patterns have to be converted to 24-bit color to be used for the brushes.

Further, 8 x 8 patterns for textures seem to be too small (except on low-res displays). Separately managed texture bitmaps could be used with some of the special painting modes, instead of relying on the brush's "pattern" mechanism, allowing different texture pattern sizes.

May also want to allow several patterns for each material. For building materials, these could represent textures as seen from different directions, e.g. from front / back, from the side, and from above. For terrain, could depict some terrain under different seasons or weather conditions (winter, spring, summer, fall; parched, soggy, normal, snowy; leafy, blooming, seeded or fruited, dormant).

A patch of similar terrain might seem more natural in transitions were graded. i.e. the whole meadow doesn't bloom all at once. The same probably goes for parched or soggy vs. normal, although snowy does tend to happen all at once (but melts patchily).

Seasonal lakes would be a rather extreme example. For those, we would also want movement modes and costs to change. To a lesser extent we may want to change more normal terrain to be more difficult to traverse when soggy or snowy, and less difficult when parched.

Palette Implementation, etc.

14 Dec 1997

Combined terrain and barrier palettes into a materials palette (as suggested 1 Nov 1997), finishing the main work on the classes on 6 Dec.

Retrofitted the game map display class, the terrain display class, and the barrier display class to use the materials palette instead of the terrain palette and the barrier palette on 7 Dec.

Also on 7 Dec, improved the interface for the elevation editor, providing a separate level set mode instead of using the mouse down at leveling time. Provided windows to change & display the magnitude of effect and focus -- in addition to and in conjunction with the sliders I had before. I even played with showing the focus as a focusRectangle, redrawn at mouse move, but couldn't size correctly because zoom information wasn't available. [Because I was using the vcl_view classes instead of the more direct display I had adopted for the barrier display class.] (I retrofitted the terrain display classs to use the more direct technique, but not the other layer display classes.)

Today, I retrofitted the elevation display class to use the direct display access, permitting proper sizing of the focus rectangle. In the course of things, I improved the breakpoint LUT class: instead of merely storing the breakpoints, it now has a Color function to return the appropriate color for any data value.

At 3 PM, the map editor stood at 1,770,878 lines compiled in 933 seconds.

Also today, retrofitted roads and water displays for direct access. Established LUTs for road and water displays in the map editor. May now be at the point where the ap_view / map_view / vcl_view classes can safely be removed from the project.

20 - 22 Dec 1997

Removed the ap_view / map_view / vcl_view classes and source files from the project. Changed terrain display and section of map file to refer to materials (i.e. patterns) by name, rather than assuming palette elements would always be in right order.

Terrain Layer Editor

31 Dec 1997 - 1 Jan 1998

Designed the editor functions for the terrain layer. In addition to the new-layer and zoom buttons, there are "mode" buttons for Paint and Fill functions, a drop-down owner-draw combo box for choosing terrain types by name (which shows the patterns just to the left of the strings) and a place for showing the movement cost of the currently-selected terrain type. The combo box was difficult (the example in the manuals was just plain wrong); the fill implementation was also challenging. (These problems have been solved by others, but it keeps the work interesting.)

The map editor stands at 1,636,345 lines, and compiles in 944 seconds. This is fewer lines than earlier because I removed the abstract view classes -- see notes of 14 and 20 - 22 December.

Next, I need a dialog box for editing / augmenting the set of choices for terrain types and their patterns and movement costs. (Note: this was completed 1 Jan 1998.)

Roads and Water on Map Display

10 Jan 1998

I've adapted the isometric map display to be more flexible about which map layers are present. I have also added logic to over-ride the terrain pattern with road, water, and / or barrier patterns where appropriate.

The roads layer has been changed to a "type" model (as the terrain was earlier). The display pattern, movement advantage, and a description are provided for each "type", and the main array is an array of type indices. Index value of 0 is no road. Movement advantage is a multiplier for terrain movement cost, so 1.0 represents no advantage.


Index Movement Advantage Description Pattern
0 1.0 Unimproved Void
1 0.2 Macadam Surface Blacktop
2 0.4 Cobblestone Road Paving stones
3 0.7 Footpath Dirt

The water layer has been changed somewhat to include something like a type. The main array is still water depth, but a set of patterns is also provided, along with maximum depth for the pattern -- sort of a small lookup table.

In operation, a pattern is selected as the first pattern for which the depth of water in the map cell does not exceed the maximum depth assigned to the pattern. Essentially depth takes the place of direct indexing.

Index Maximum Depth Pattern
0 1.0 Passable water
1 10.0 Shallow water
2 200.0 Deep water

If cell depth is greater than any pattern's maximum depth, the last pattern is used. Water patterns are used for the whole-map dispaly, not the display used by the water layer editor which still uses a piecewise lookup table with (generally) much finer color gradations to distinguish depth relationships more easily.

With the incorporation of road and water layers into the map, the question of precedence has come up. Terrain should be visually superceded by roads -- unless the roads are in tunnels. Water covers both terrain and roads -- unless the roads are on bridges. Barriers should be displayed as above terrain, over roads -- unless they are in tunnels -- but tunnels can be blocked too. Barriers might be submerged below water -- unless they are floating -- but may be visible if they are higher than the water is deep. (Also, water is not strictly opaque.)

Implementation notes

11 Jan 1998

Now that there is more to do per map cell in the displays (especially the whole map display), I have moved the small tile / large tile branch of the drawing loop further into the loop. I had previously had two variants of the loop in the two tile size branches, but now there's enough logic that it's a maintenance headache to keep up two copies of the logic.

Wrote WriteToFile functions for each savable map layer type. Now each layer knows how to write itself to a file and how to read itself from a file, rather than requiring the map class to know how to read and write each of its layer types.

Modified standard movement cost computations to account for water depth. If depth is > 1 meter, foot, mounted, and wheeled travel are not possible. If depth is zero, water has no effect. If depth > 0 and < 1 meter effect is a linear factor which depends on depth. Water has no effect on land movement if there is a road or bridge in the water cell.

Redefined from-file constructors for saveable layers to use the ReadFromFile function.

Thought and Memory

17 Jan 1998

For the past two weeks, Bill and I have been discussing the structure of knowledge, the nature of memory, and computer implementation of learning, recalling, forgetting, and using knowledge to derive more knowledge.

Memory is a matter of capacity and importance. If the acquisition of knowledge is uninhibited, new facts will either crowd out old ones, or will fail to be remembered because the capacity is already filled. Humans exhibit both of these characteristics: Newly-acquired 'facts' can drive out old facts, but it is also true that humans have some limit to the rate at which they can learn. It as though at some point the 'pipeline' becomes stuffed and they must rest before learning more or risk forgetting some of the recently-acquired knowledge.

There is enough evidence to suppose that when old facts are pushed out, that age (i.e. the time since the fact was acquired) is not the primary criterion for determining which facts are forgotten. This is where the admittedly vague notion of 'importance' enters the model. Less important facts are more easily forgotten, in general. There is also a re-inforcement of memory each time a fact is recalled, whether for direct use or to derive other needed facts. Indeed, frequently used facts (e.g. a childhood telephone number or address) are retained with clarity decades after they have ceased to be useful or relevant in any conventional sense. Thus, we will use 'importance' to measure the degree to which a memory will be retained, not its relevance or fitness for any particular purpose.

We would also like to distinguish between long-term and short-term memory. In our model, short-term memory is where newly-acquired facts are stored. Short-term importance decays linearly over a short period of time, and is many orders of magnitude smaller in capacity than long-term memory. Long-term memory represents "permanent" storage. Long-term capacity is very large. Long-term importance is non-linear in its dacay -- our model represents the slow decay over time as being a logarithmic function of elapsed time.

When a fact's short-term importance decays to some threshold (probably zero), it is removed from short-term memory. If it has acquired enough long-term importance, it is retained in long-term memory.

While knowledge can be quite complex, our model describes knowledge as

Data in this model can be of differing structures. Some of the simplest are noun - relationship - noun and noun - attribute - value. E.g. Bill - loves - Julie and Bill's jacket - color - black.

Originally, we had considered a subject, or perhaps a subject list as part of the structure of a knowledge itme. At my suggestion, we will try a more associative structure, which taken together with the knowledge structure will provied the basis for a functioning associative memory and reasoning process.

In this approach, each noun or relationship (we could probably say datum part, but exclude high-cardinality items) is associated with a list of all the data that reference that noun (or whatever). The restriction against high cardinality is mostly practical; if one recalls that a certain building is 5.2 km distant, knowledge about other things that are 5.2 km distant is probably not helpful unless there are other associations with these other things as well. Thus, when considering (i.e. having recalled) that Bill's jacket is black, a reasoning or conversation engine would have immediate access to other knowledge about Bill's jacket (e.g. that it is owned by Bill) and to knowledge about other things that have the color black.

Implementation notes

19 Jan 1998

Converted road layer from a full array of road types (i.e. one per map cell) to a sparse layer implementation which will be the model for other sparse layers (points of interest, etc.). Instead of being derived from vector and map layer, sparse layers are derived from a STL map of map cell numbers to the data (in this case, road type indices). Put simply, we need only store the data for places where there are roads (i.e. where the roads lie) augmented by the location id (map cell number) corresponding to each datum.

Implemented bridges and tunnels as Booleans in auxiliary maps (by map cell id) which are data members of the road layer class. I.e. only cells where the roads are on bridges or in tunnels need be stored in the maps. Modified whole map display to overwrite terrain with road only if the road cells are not also tunnel cells, and to cover roads with water only if the road cells are not also bridge cells.

21 Jan 1998

Added code to road layer display to distinguish tunnel cells by framing them in black, and bridge cells by framing them in white.

Implementation notes

25 Jan 1998

Today I provided full editing capability for both the water and road layers.

Water layer functions are modeled on the elevation editor functions: Deeper, Shallower, Level, and Set Level. As with the elevation layer, decreasing or increasing water depth is controlled by the scale (magnitude) and focus (area of effect) parameters which can be specified in edit fields or by the use of sliders, and the magnitude of the effect is tapered to neighboring cells using a Gaussian weighting. One problem I encountered was that deepening any portion of the map covered the entire map with a very thin layer of water. In this case, thin means micrometers. Because the map display logic said to display water patterns over terrain if the water depth was greater than zero, the effect was to innundate the entire map. I solved this by arbitrarily suppressing (setting to zero) all depths less than 0.1 meters.

Road layer editor functions are based on the terrain editor functions. I added mouse functions to toggle the bridge and tunnel flags which are special to the road layer. Instead of Paint and Fill, the other mouse functions are Build (set road type) and Clear (remove road elements).

Implementation notes

27 Jan 1998

I redefined the barrier layer today to reflect several improvements. First, I defined it as a sparse layer (as I did for the road layer on 19 Jan), so only the places where barriers are need be stored, not the fact of their absence where they are not.

Second, I applied the LUT approach, i.e. that each layer element is really an index into a list of barrier types (as was doen previously for the terrain and road layers), and that most barrier properties are properties common to that type of barrier, not location-specific properties. Under the previous structure, the layer was a vector of barrier nodes, where the barrier node was a separate class which stored damage deflection, susceptibility, weathering, etc for a particular map cell. Thus one had to instantiate a class for each map cell. The new structure does away with the barrier node class (substantial performance gains) in favor of maps and vectors in the layer class. The one property that isn't related strictly to the barrier type is the integrity -- this is still maintained for each barrier location because of the possibility that specific sections of the barrier can be damaged.

Implementation notes

28 Jan 1998

Implemented editor functions for the barrier layer. These are mostly drawn from the road layer editor: Build / Clear, combo box to select barrier type, and Setup button for establishing the characteristics of the barrier types via the barrier type setup dialog. The setup dialog is the most complex so far. A barrier type has eleven attributes (compared with four for terrain types), two of which are bit flags requiring 6 checkboxes each.

The map editor stood at 2,204,350 lines, compiled in 1138 seconds.

Back to the Destiny documents

Back to the Previous Folio of the Notebook

Onward to the Next Folio of the Notebook