Destiny Project Notebook, Folio 7

Describing Paths

7 January 1999

Path

originTerminus <PLACE>
destinationTerminus <PLACE>
directionList list<DIRECTION>
viaList list<PLACE>
distance <DISTANCE>
followingPath ("along") <PATH>
subpathList list<PATH>
orientation <ORIENTATION>
manner (shape, urgency, etc.) <MANNER>

Additional Locations

Directions (instructions for path traversal)

Display Order (language specific?)

If subpath list not empty, display each path in subpath list.

Otherwise, describe in this order:

Descriptive Phrases

<DIRECTION>

  1. operator (toward, away from)
  2. <PLACE>

<DIRECTION>

  1. operator (up, down)
  2. <THING>

<DIRECTION>

  1. operator (forward, backward, left, right)
  2. <ORIENTATION>

<DIRECTION>

  1. <DIRECTION> (north, south, east, west)

<PLACE>

  1. operator (at, beside, behind, in front of, near, under, over, on, above, beneath, below, inside, outside)
  2. <THING>

<PLACE>

  1. between
  2. <PLACE>1
  3. and
  4. <PLACE>2

<PLACE>

  1. across
  2. <PATH>
  3. from
  4. <PLACE>

<PLACE>

  1. intersection
  2. <PATH>1
  3. <PATH>2

Describing Paths, cont'd

16 January 1999

Origin is often implicitly "here".

Straight-line path

  1. originTerminus
  2. directionList
  3. (distance)
  4. (viaList)
  5. destinationTerminus

Path coincident with another path

  1. originTerminus
  2. followingPath
  3. (distance)
  4. (viaList)
  5. (distance) [If present, distance is either in position 3 or 5 but not both.]
  6. destinationTerminus

For segmented paths, the origin and / or destination of a segment (or subpath) is often a via place of the whole path.

Critical Questions

What places are important as via points?

How to determine whether a path is coincident with another (known) path, such as a road?

A Path Description

  1. North 3 miles.
  2. North until you reach the lake, then around the lake until you reach the town.
  3. North until you reach the lake, then follow the shore of the lake, keeping the lake to your right, until you reach the town.
  4. North until you reach the lake, then follow the shore of the lake clockwise until you reach the town.

The Great Rules for Describing Paths

Path descriptions are approximations to paths. Places where the path deviates from the described approximation are places worthy of one or more separate path segments, if the deviation is "significant".

Follow the Great Road east out of The City, around The Peak, to the town of Titipu.

 

Describing Paths, cont'd

17 January 1999

Location can be a path from a known landmark location: "Genghis' workshop is 4.3 km southeast of Ulan Bator."

PLACE( Genghis' Workshop ) IS PLACE( PATH( FROM PLACE( Ulan Bator ) DIRECTION( southeast ) DISTANCE( 4.3 km ) ) )

Question and Answers

Question

"Pardon me. Where is the best inn in town?"

Answers

123.7 yards south-southwest.

Keep following this road until you reach the corner with the pie-maker's shop. Turn left and look for the sign with the parrot with the wooden leg.

In that thing? You can't even get there! You'll need to go back the way you came and park in the big field on the left. When you've parked, there's a footpath along the stream that leads back toward the center of town. Follow the footpath until...

Right across from the cabinet maker's house.

Beats me. I'm new in town myself.

Why the hell should I tell you?

Describing Paths, cont'd

30 January 1999

Description modes for describing paths (the three Great Rules mentioned on 16 January 1999) compete on how much of the path they describe accurately, simplicity of expression (number of segments), and the degree to which they fail to accurately describe portions of the path. Going back to our Great Road example, here are three ways of describing the path:

  1. Follow the Great Road east from The City to the town of Titipu.
  2. From The City, go east to the foot of The Peak. Proceed clockwise around The Peak for 175 degrees of arc, then go east to the town of Titipu.
  3. Go east from The City to the town of Titipu.

Clearly, description 1. is the best description. It covers all of the path and is accurate for the whole path. Description 2., while accurate, requires more segments to describe the path well. Description 3., while as simple as description 1., is significantly inaccurate for the middle portion of the path.

More subtly, descriptions also compete on which subsets of them can be combined to cover the whole path with minimal overlap. In addition, formation of sets that use the same description mode may be favored; having already described some segments of a path in terms of following known paths, I may prefer to describe the remaining segments similarly, even if it would require additional segments or entail some inaccuracy.

Inaccuracy can be characterized as an error between the described segment and the path that the description would generate.

Path generated by the description "Go east from The City to the town of Titipu."

A first-order check for suitability of a description can compare the length of the path segment described (the "true" path) and the length of the path segment as described. Merely going east from The City has a path length of only 86% of the true path length. In general, descriptions of paths which differ by more than 5% from the true path length should probably not be considered accurate enough.

A more detailed analysis of the deviation between two paths (true and as-described) would compare the distance between parametrically equivalent points along the two paths (e.g. the point 10% of the way along the true path is compared with the point 10% of the way along the path generated from the description. It seems reasonable to characterize the difference between the paths by a mean square error term; if evidence comes to light that the square of the error is not much like what humans use to evaluate difference between paths we can adapt to the new evidence. Perhaps error should be relative to the path length (advantage of being unitless).

One point I have not touched on in our little example is that going East from The City does not actually get one to the town of Titipu, but passes to the north of the town. For the purpose of comparing path segments, we can assume that the path ends at its point of closest approach to the actual terminus of the true path. In practice, if the simple description were chosen, one would want to add a segment describing the travel necessary to "bridge the gap", if the distance was "significant".

Describing Paths, cont'd

31 January 1999

To be able to give "follow" innstructions requires additional information about named / known paths as they relate to the path to be described. This information could either be developed during the path planning process (in which case an overhead would be levied on all possible paths being explored) or after a single path has been determined. The necessary information would be an entry / exit list for the known paths along the planned path. For example, here is a partial list from a path that follows The Great Road through its intersection with the Southern Caravan Road:

path step index
enter / exit
known path
path id
0
enter
The Great Road
260057
218
enter
Southern Caravan Road
212305
219
exit
Southern Caravan Road
212305
521
exit
The Great Road
260057

With information like this, it would be fairly easy to construct descriptions like "Take the Great Road from The City to the town of Titipu, passing through the intersection with the SouthernCaravan Road."


Road Layer (current implementation)

31 January 1999

The current road layer is derived from a map< ulong, short >, which contains the road number, indexed by map cell id. The other data members of the road layer include:

Problems with Road Layer Implementation

Each cell of the road may have different material and / or movement advantage than other cells of the same road: cobblestones give way to Macadam, and sometimes there are patches of loose gravel in construction zones.

A road, as a sequence of map cells, may overlap other roads, so a partiicular map cell may participate in zero, one, or more roads. Sometimes, as with intersections, this represents a point of connection. Under other circumstances, roads may occupy the same terrain but not connect, as in the case of an overpass or underpass, or parallel roads that happen to fall in the same map cell. In the non-connecting case, each road may have its own material and movement advantage too, as with a freeway crossing over a footpath, or over a railroad track. These roads in the same cell may obviously have different bridge / tunnel attributes as well: when the freeway passes over the footpath, the freeway is on a bridge while the footpath is probably not.

Bridges and tunnels are often worth mentioning as waypoints, so it's important to know to which road a bridge properly applies. In addition, the movement advantage that applies within a map cell properly depends upon which road one is traversing through the cell (if any).

View of a map cell's roads View of a road's map cells

number of roads in cell

properties of road 1

  • material
  • movement advantage
  • bridge flag
  • tunnel flag

properties of road 2

  • material
  • movement advantage
  • bridge flag
  • tunnel flag

etc.

ordered list of map cells through which the road passes

properties of first map cell

  • material
  • movement advantage
  • bridge flag
  • tunnel flag

properties of first map cell

  • material
  • movement advantage
  • bridge flag
  • tunnel flag

etc.

Bridges and tunnels could also use information about how far they are above or below the elevation of the local terrain. In fact, this is applicable to level paths as well. Railroads and highways, for example are often placed on embankments, especially in areas subject to flooding.


Situation-dependent factors in path description evaluation

2 February 1999

Why Path Description is Important

Path description is inherently important because it is an element of conversation, espeically in cases where an NPC denizen of a town must interact with a character player new in town. As Jackendoff's work makes clear, however, the mind also uses place and path information as metaphors in many situations, including explanations and instructions in general. One could also view an explanation as a segmented path toward the replication of a subset of knowledge in the receiving entity, or a recipe as a segmented path toward a goal of a baked cake.


Re-engineering the Road Layer

3 February 1999

There may be many roads. Change the road index from a short to an unsigned integer.

Each cell may contain several roads. Instead of mapping from a cell to a road index, map from a cell to a set of road indices.

Material, bridge, tunnel, movement advantage, and height above terrain may all vary along a road. Provide for usual (normal, standard, nominal) values indexed by road index, but also allow exceptions to be indexed by map cell for any particular road which would override the usual values.

May want the ability to specify alternate descriptions. For example, one (often shorter; a name or nickname) for entities familiar with the path, another for entities to whom it is strange.

As an alternative to the road index, make this a subject index with reference to an associative memory containing map knowledge, such as the Almanac (see entry for 7 February 1998). Alternatively can map one to the other (better) instead of using one in place of the other.

Implementation Notes

4 February 1999

Began implementing the road layer changes described above on the night of 4 February 1999. Created a RoadInfo class to hold information about one road; it is implemented except for the ReadFromFile and WriteToFile methods.

Could implement map layer files as XML documents. This would divorce them somewhat from the specifics of the read / write functions, allowing greater portability to / from other game engines or editors.

Implementation Notes

5 February 1999

Finished implementing the RoadInfo class. Began re-implementing the map road layer as a map of cell indices to a set of road indices. Information about the roads would be carried in a vector of RoadInfo objects indexed by the road index.

Typedef'd the index classes MapCellIndex and RoadIndex, to abstract them from whether they are integers, unsigned integers, long integers, etc.

Compiler couldn't handle map of unsigned long to string. Something about names of templated functions not being distinct, so changed MapCellIndex to unsigned integer instead and the compiler was "happy".

Road Layer Editor

6 February 1999

Functionality

Choose road from drop-down list of roads.

Build / clear road from cell.

Bridge / tunnel road in cell (toggles)

Set up new road

Per-cell overrides

Bridges and tunnels are really per-cell overrides too, with implied usual values of false.

Segmenting and Splicing Paths

Segmenting divides one path into two or more paths. When segmenting paths, how to partition knowledge in memory about the variaous path segments?

Splicing combines previously-separate paths into a single path. How to combine knowledge in memory about the paths? How to determine and handle disparate "usual" characteristics among the paths to be combined?

Implementation Notes

Today I finished the re-implementation of the road layer class and re-worked the isometric map display class to use the new functions and structures. Began design work toward changing the map editor program for the new map layer.

Hint line is: Description[ over bridge][ in tunnel] when map editing cursor is over a road cell.

Road Layer Editor, cont'd

7 February 1999

Spent today re-working the map editor to take advantage of and provide control over the new road layer class.

The map editor is now 2,883,067 lines and compiles in 3,482 seconds.

Want to redo edit display controls:

Layer display to modify Layer display to use as model
Water Elevation
Points of Interest Road
Terrain Road

New web site & changes to roads
letter from Chris to Bill

8 February 1999

I finally did something I've been meaning to do for at least a year: I dumped my old Compuserve account (customer since 1980) and got an earthlink account (incl. 6MB for web pages). You can now send mail to draigsffau@earthlink.net. Of course, you'll still get a faster response sending to me at work.

Nothing on the web page yet, but I was thinking of including a bit about the destiny engine project. General objectives and principles. Eventually it might serve as an exchange ground among the few game programmers that want to explore the limits of intelligent computer-run characters, but I'm not sure I'm ready for that yet.

I was starting to work out some algorithm details for describing paths that follow "known" paths (e.g. driving directions use highways and streets as known paths). I realized that the road layer of the map didn't support the kind of knowledge I needed to "feed" the description algorithms. Naturally, I re-engineered the road layer (Thursday and Friday night). As in the adage "Two wrongs are only the beginning" I then found that I needed to adjust the map display classes so that they could accurately display the road information (all day Saturday). That wasn't enough yet, of course, because I couldn't create roads in the new road layer with the old map editor displays and classes, so I spent still more time (all day Sunday) re-working the map editor. There are still some lingering problems with combo boxes, but its all basically working (again).


Semantic categorization rules and neural networks
letter from Bill to Chris

9 February 1999

Cool thing on the new account! I don't think that we're ready yet to start the possible feeding frenzy that will occur if we open up our world to the onslought of the web community.

After having read more of Jackendoff, I have come to the conclusion that his categorization rules that he seems to imply everywhere but never defines, are in fact the results of a neural network. (Imagine that: the brain using a neural network!) I say that mainly because of his argument about the bowl-cup-vase series of pictures. The network has some features that distinguish it from a standard back-prop however, in that it can "grow" new categories. The results of the network however, are definitely competitive. People will attempt to categorize the results as a "cup" or "bowl" or "vase" even when they're not completely sure about the division, and respond with a definite answer. Perhaps it's related to a combination of a back-prop and a Hopfield net?? (Back-prop because external feed-back into the system is possible, Hopfield because of it being self-organizing at least to some degree).

I forget, what was the additional road information that you needed to add in order to allow the use of known paths?


Knowledge about the world that could be in an associative memory (Almanac)

10 February 1999

Knowledge of seasonal variations

Political information


Combo Box Woes

13 February 1999

The combo boxes used to select road or terrain type do not display correctly all the time. Sometimes the descriptive text for the item is blank, even though the accompanying material bitmap is displayed correctly.

When the application is started or the window is re-drawn (in response to an expose event, for example) the combo box is correctly displayed. This is also true immediately after a map is loaded.

When the combo box is first "pulled down", the text of the choice corresponding to the current choice is blank (but not in the display of the current choice, which is still okay).

When a new choice is made from the combo box, the box collapses and the pattern for the new choice appears in the current choice area, but not the text.

When the combo box is pulled down again, the text appears in the current choice area, but the corresponding choice in the lower area is without its text (as when the box was first pulled down).

Perhaps it is a weird highlighting effect, rather than a failure to print the text or to refresh the display.


Back to the Destiny documents

Back to the Previous Folio of the Notebook

Onward to the Next Folio of the Notebook