Destiny Project Notebook, Folio 10

It spreads, it leaks, things bubble up!
letter from Chris to Bill and Michæl

29 May 1999

I had hoped to have a nice visual simulation of spreading activation of associative memory working in NNITE by now. Thwarted by the vagaries of BCB3, however, I was compelled to make the associative memory itself behave more like a neural network. Pursuing the "reservoir" idea, I added reservoirs to the memory, then added methods for injecting the initial stimulus and for performing cycles of the recall process. A new dialog for the memory test driver and I was off and running!

A sticky point, as you may recall, was the distribution of an item's output "energy" among related items. I proposed to divide an item's output among its subjects, then divide each subject's output among the items associated with it, allowing a recurrent single-layer network of knowledge items to feed back to itself. At some point, my mind cycled back to the input/output question and I realized that I did not want to start the recall process by being reminded of a small set of items, but rather by being reminded of a small set of subjects. It also occurred to me that while the main thing I wanted was a set of items that had been recalled by the process, it might also be useful to know which of the subjects were most favored and the recall process proceeded. This led to the thought that I could create an equivalent two-layer network composed of a layer of subjects, connected to a layer of items, which then fed back to the subject layer. The output distribution model is much simpler this way: each subject contributes to its associated items while each item contributes to its component subjects. The initial input is also simple: deposit a certain amount of energy into each of the appropriate subject reservoirs. (Alternatives include depositing a certain amount of energy into each reservoir for a certain number of cycles, or until the result stabilizes.)

The processing model in my present simulation is much as I described it at our last meeting, with the exception that I have not included a sigmoid (or any other function) between the summation of inputs and the reservoir. Instead, all inputs to a neuron are summed directly into the reservoir. Next, leakage (if any) is applied, removing a fixed amount from the reservoir. If anything is left in the reservoir, that amount is multiplied by a flow factor which determines how much of the reservoir will flow out to the output in this cycle. This flow is then limited so that it does not exceed some maximum flow. The flow thus limited is the output of the neuron, and the reservoir is reduced by the output flow.

As a matter of computational efficiency, I didn't exactly make a reservoir for each item and subject in the memory, and my processing doesn't loop through all subjects known to the memory, then through all items known to the memory. That would be prohibitively impractical as the memory of our characters approaches 2 to the 30th items. Instead, I maintain STL maps of object id and reservoir value. The maps start out empty. The initial inputs assign values to a few subject reservoirs, creating these map elements. Because a map element is automatically created and initialized each time a previously unknown key is used for a map reference, the maps automatically grow as energy is added to previously uninvolved items or subjects. In addition, each time an object's reservoir is reduced to zero by leakage, I remove it from its map. In this way, when I process the reservoirs and the connection of each output to the inputs of the other layer I process only the reservoirs for items and subjects that have been made active by the recall process. The use of the map to focus storage and computation should be a significant advantage (well worth the overhead imposed by the map objects) when performing recalls from large memories.

To enhance visibility into the process, I create two priority queues (one for items, one for subjects). The element of each queue is actually a pair of the reservoir value for the associated object (whether item or subject) and the id of that object. This allows my test interface to extract a list of the active items and the contents of their reservoirs, ordered by reservoir content. Naturally, it decodes the ids using the knowledge and vocabulary elements of the memory under test into readable strings.

Other elements of the interface for my test driver include a list of vocabulary words (subjects known to the memory) from which to pick, an area to display the subjects picked, entry fields for setting the initial stimulus, leakage, flow rate, and maximum flow, and buttons to control the recall process (Start deposits the initial stimulus in the reservoirs of the chosen subjects and processes recall for one cycle and displays the results, Continue processes recall for one cycle and displays the results, End cleans up, erasing the reservoir maps and emptying the priority queues). Another button clears the list of chosen subjects (in case of error, or to start a new test).

Using the test driver with the processing model I have described, I have explored the algorithm's ability to deposit energy along chains of items connecting indirectly associated subjects. Leakage proved to be critical to keeping the process focused; without it the energy spread itself rather indiscriminately throughout the memory. Also critical was the strength (or duration) of the initial stimulus. An initial stimulus of 10.0 (with max. flow of 1.0, flow rate of 0.5, and leakage of 0.02) is enough to ensure that the output from the initial subjects remains saturated for at least 8 or 9 cycles, but I found that this was not usually enough (depending on how directly related, through items in memory, the subjects were) to recall item chains connecting the initial subjects. I am currently favoring stimuli that last from 20 to 30 cycles to recall relationships 3 times removed.

When initial subjects are stimulated for long enough, the relevant items gradually acquire more energy, eventually "bubbling up" in the priority queue display to become the top items in the queue. Usually, there is a point somewhere in the first 30 cycles where a complete chain of items connecting the subjects can be picked off the top of the priority queue, and this arrangement of the queue persists quasi-stably for several cycles (anywhere from 3 to 15 in the cases I tested). Even with the initial subjects at saturation, however, there is a tendency for the quasi-stable queue state to degenerate again into items strongly related to secondary subjects for which few items exist.

When initial subjects are no longer outputting at saturated values, the memory transitions to free association. (Yes, with the test interface I can actually observe this!) Each item sparks other items, the uppermost items changing more frequently, wandering further off of the original track. The reservoir values (intensity? relevance?) steadily decline through this period until at last all of the energy has been claimed by leakage.

I have tried variations on processing order, exploring the idea of simulating the leakage at different points in the processing cycle. I haven't found a variation yet that fails to perform the expected recall, though some arrangements result in more subjects and items being considered simultaneously than others. I have more aesthetic interest in the variations which allow leakage to perform as a minimum threshold for producing an output, merely because I know that biological neurons behave as though they have thresholds. For similar reasons, I have set the maximum flow at a normalized output level of 1.0 because I know that biological neurons also have a saturation level beyond which they cannot respond more strongly.

There are some questions to be answered and details to be worked out. What is the right approach for the initial stimulus (high until done?). What is the stopping rule? What factors govern an appropriate choice of leakage? Can flow rate, leakage, and max. flow vary among populations of neurons? What about connection strength? Surely the equal division model I've adopted for distributing energy isn't the best way to go. How to address issues of relevance (How strongly associated is a subject's identity with a particular item that references it? Is the strength of this association different depending on the direction in which one traverses it?), of credibility (Do I believe this item? Disbelieve it? How extremely do I believe or disbelieve it?), of usefulness (Is there a preference for items (or subjects!) that have proven useful in the past? Are they somehow easier to activate?)? What about amplification (Maybe more connections should give rise to more total signal? Surely biological neurons are not passive devices?)? What about inhibition (so far, only positive connections have been considered)?

There's also a meta-issue about biology. My own personal opinion is that biology should inform, but not dictate, our developmental efforts. Biological neurons have proven adaptable and useful in the context of biological entities, but a slavish simulation of them may not be the best approach for endowing computers with some of their attributes.

These few issues aside, the fact that we have achieved some plausible behaviors from our initial model for both directed association and free association is highly encouraging. I look forward to demonstrating the process in action to you at our next meeting on the night of 2 June.


Project notebook now online
letter from Chris to Bill and Michæl

31 May 1999

Well, I didn't get out to smell the flowers much, nor did we go anywhere exciting this weekend, but I did put a prodigious amount of effort into converting my principal project notebook for Destiny into HTML, drawings and all. It is now available for viewing on the Draigsffau website.


Comments from demonstration of spreading activation and its test interface

2 June 1999

What if we separate the output threshold from the leakage. If we made this change and leakage was considerably lower than minimum flow, little-used nodes could accumulate energy until they had enough to fire.

Bill suggests that the display show energy per fan-out connection, or perhaps fan-out factor times energy. Another suggestion is to use the cost information from an ordinary map as a "knowledge base" and see whether the algorithm can identify paths between points of stimulus.

We agreed that we should probably vary the connection strength, instead of treating all connections equally, but there was no agreement on what the basis of the variance should be.


Toward a first game engine

16 June 1999

Things we need to determine

Inventory control factors

Environment

Environment objects (Swords, vases, Snertlings)

Event Manager (translate to STL C++)

Map & Map Manager

Responsibilities of the environment

Responsibilities of objects in the environment

Is the map + almanac the environment, or is there more to the environment? Tentatively, we decided that the map, almanac and map manager encompass the environment, and will be extended as necessary.

Entity characteristics

Object characteristics

Sapience characteristics (In what ways can intelligences differ?)


Destiny Navigational Testbed

2 July 1999

Map display with overlays for

Difference between the real map and the map as the guided creature knows it (assuming unfamiliarity). Process line of sight to acquire new map knowledge.

Path planning based on creature location and location of selected aimpoint

Even perfect map knowledge shouldn't imply knowledge of location of things which have moved since they were last seen.

Path replanning

When lowest-cost path cannot be extended because of unknown territory, planning is done: time to move and find out more (if two heads in path plan, continue until both are stuck).

What a map needs to know about a creature

What a map needs to know about an obstacle / barrier


Determining Map Cell from Cursor on Isometric Map Display

2 July 1999

For display without relief,

x = ( x' sin B - y' cos B ) / sin (A + B )

y = ( x' sin A + y' cos A ) / sin (A + B )

where A is positive angle of map x with respect to display x and B is negative angle of map y with respect to display -x.


 

5 July 1999

Relief Correction for Cursor on Isometric Map Display

Because different map cells can have different elevations, and thus different relief offsets, the best solution seems algorithmic. "Draw" a vertical line from top to bottom of the map display at the x position of the cursor. Use existing functions to determine cell on a flat map. For each cell that the line enters, correct the cell center (in display coordinates) for elevation, then compute the distance (in display coordinates) from cursor to corrected cell center. The cell whose center is nearest the cursor is the cell that best corresponds to the cursor position.

Map Methods Concerning Creature Movement

Human Paces
walk
2 miles / hour
~1.0 m/sec
run
1 mile / 9 minutes
~3.0 m/sec
sprint
~5.0 m/sec
cautious / sneaky
~0.3 m/sec

Movement Management

7 July 1999

For each creature / object / entity: If it has a path, take the difference between the current clock time and the clock time the thing was last moved. Multiply by timeFactor (rate at which time is moving). Multiply by movement speed (creep, walk, run, sprint, etc.). Adjust for terrain, change in elevation, etc. (map movement cost) for mode of travel (foot, mounted, wheeled, etc.) Move along the path (in world units) according to permitted movement. If movement cost changes before the end of the permitted move, recompute the remaining allowance. Replan path as necessary.

Alternatively, one can create a "movement plan" for the animation manager to carry out: in pixel coordinates, with activity mode and orientation.

Separate Animation Manager (separate from the event manager)

When in motion, orientation should be in direction of motion, as a first approximation. Want eventually to be able to cover case of backing away, etc., though.

For Robin

Path Support for Motion Manager

Animation, indexed by creature species, mode of motion, speed. Each animation may have one or more frames. If one, then static image. If more, then can be either continuous (loop), as in running, or one-time, as in spear-cast.

Each creature can also have sounds, indexed similarly (at rest, running, etc.).


Game Elements for a Simple Game

7 July 1999

With Michæl

Game Elements

Group Play

Central personality (player) gives directions to other (NPC) entities whose abilities are not perfect. Characters should operate mostly autonomously, but take directions to approximate the extent that verbal directions can be given.

With Bill and Michæl

Most players won't want to train their party in detail, but could get into deciding which skills, attributes to assign to which party members.

Entities in opposition.

Appropriate level and means of control (i.e. interface should not require managing the individual affairs of a cast of thousands (or even hundreds) in a major battle).

Layout generator for dungeon floor plans.

Inventory Objects

Walls / Barriers (binary terrain)

Creatures

Damage determined by

Armor

Initially, can assume no gain in skill with time or experience.


Detail Regions Triggering Change-of-Map

8 July 1999

Each map has a list of cells of especial interest. These can be event triggers. They can also be cells used to define a region for which another map has the detail. A cell of interest is associated with a list of codes indicating what kind of interest the cell holds.

A detail region is a region on a layer map with / for which a detail map registers itself.

Objects crossing into a detail region may be placed on and managed by the detail map (depending on granularity / fidelity of game play).

Objects leaving a detail map are placed on and managed by the larger map. For this, we will need "exit regions" on the detail map.

Come to think of it, there's no reason why associated maps cannot be peers, rather than heirarchical. Separate maps of the floors of an office building could be considered peers, with exit regions at stairwells and elevators.


Player Character Movement

8 July 1999

In solo games there is typically one creature that represents the player. This is the only creature controlled by the player. Their location governs map scrolling and whether the display generation is handed off to another map. (example: Diablo)

In other, more strategic, games, there can be many creatures allied with the player's character, controlled (more or less) by the player. Map scrolling then has to be part of the player's game actions since there is no foolproof basis for determining what the player might want to be looking at.

Elementary Game Actions and their Variations

Possible mapping of activities to mouse actions:

Mouse Action Single Click Double Click Right Click
normal location: go to (normal speed)
creature: approach and attack
object: approach, pick up, and place in inventory
location: go to (fast speed)
creature: keep attacking
object: approach and take in hand
location: orient toward
creature:attack without approach
object: examine
shift creature: approach and talk....    
control      
alt      

Need to stay flexible about assignment of mouse actions. Some games might reqire a lot more approaching and talking than attacking, or vice versa, and we want to be able to make most common actions easiest.


Implementation Notes

9 July 1999

Created entityInfo and entityLayer classes. Each entityInfo contains data about a particular entity, while the entityLayer references entities to map locations.


Implementation Notes

10 July 1999

Created an entityType to hold information about a type (race/occupation/class) of entity. This class includes mean and deviation for entity statistics (e.g. height, speed). Entity constructors allow a random draw on these characteristics when a new entity is created.

Animations are indexed by

A Boolean is indexed by entity type and activity to indicate whether the animation sequence for that type and activity should loop continuously (until stopped).

Developed and incorporated into the display generator an algorithm for movement along a map path:

effort = base movement * speed factor * delta time * time factor
while effort > 0
   distance = effort / cost factor of first leg of path
   if distance > length of first leg of path, 
      effort -= length of first path leg * cost factor of first leg of path, 
      remove first leg from path
   otherwise, take distance off of first leg of path

Developed a file format for representing one or more animation sequences in an "Animation Palette" file. This file specifies the entity type, activity, and orientation(s) to which a sequence of images applies.


Separate Animation Controller

12 July 1999

Separation of world timeline from display timeline. Separate animation controller from event manager. User interaction interface vs. world internals.

Net game architecture: world on server (or server net), animation and user interface on client.

What is the future of the current activity mode? A big bitmap? A set of modes? A map of activity to boolean?


Back to the Destiny documents

Back to the Previous Folio of the Notebook

Onward to the Next Folio of the Notebook