Jump to content





Cruisin' On Auto-Pilot - Part II

Posted by DZ-Jay, in Christmas Carol, Game Development, Intellivision 17 November 2018 · 90 views

In our first part of this series on the P-Machinery Auto-Pilot, we reviewed the general circumstances that prompted its creation, how and why it was created, and an overall idea of the infrastructure that supports it.  Central to that infrastructure was the concept of a Sprite Object Record, the data structure representing a game sprite, which is the very thing on which the Auto-Pilot operates.
 
Now it's time to talk about the technical design of the Auto-Pilot itself and go a little deeper into its inner workings.
 
Technical Overview
As mentioned before, the Auto-Pilot itself is very simple.  Its brilliance comes from the versatility and flexibility this simple design affords the game program.  At its core, there are three main components to the Auto-Pilot:

  • Script - An Auto-Pilot script is an ordered list of statements that operate on a particular sprite object.  Each individual statement represents a command that alters the behaviour or state of the sprite, or changes any of its internal attributes.
     
  • Dispatcher - As the name suggests, the Auto-Pilot dispatcher's job is to dispatch commands as necessary. On every invocation, it fetches the statement corresponding to the current step of the object's script, decodes it using a look-up table, and calls the appropriate command with any arguments given.
     
  • Command Executor - Each command supported by the Auto-Pilot has a corresponding executor function, which is the actual sub-routine that performs the work to fulfill the command.
Below is a simple flow diagram depicting the architecture of this system, and the general way in which the various components interact.  A full description of each component follows.
  +===============+
  |               |
  |               |
  |  P-MACHINERY  |<------------------------------------------------------------------,
  |               |                                                                   |
  |               |                                                                   |
  +===============+                                                                   |
          |                                                                           |
          | 1. Call Auto-Pilot         +==============+                               |
          |    Dispatcher              |  AUTO-PILOT  |                               |
          |                            |    SCRIPT    | 3. Decode & execute           |
          |                            +==============+    step command               |
          v                     ,----->|    Step 1    |------------------,            |
  +===============+             |      +--------------+                  |            |
  |               |             |      |    Step 2    |                  |            |
  |               |             |      +--------------+                  v            |
  |  AUTO-PILOT   |-------------'      |    Step 3    |          +===============+    |
  |  DISPATCHER   | 2. Dispatch        +--------------+          |    COMMAND    |    |
  |               |    current step    |    Step 4    |          |    EXECUTOR   |    |
  |               |                    +--------------+          +===============+    |
  +===============+                    |    Step 5    |                  |            |
          ^                            +--------------+                  |            |
          | 6. Return to               :     . . .    :                 / \           |
          |    dispatcher              .              .               /     \         |
          |                            +--------------+             /         \  No   | 4. Return
          |                            |    Step n    |            (   Done?   )------'    to game
          |                            +--------------+             \         /
          |                                                           \     /
          |                                                             \ /
          |                                                              | Yes
          |                          +==================+                |
          |                          |      SPRITE      |                |
          `--------------------------|   OBJECT RECORD  |<---------------'
                                     +==================+
                                        5. Increase
                                           step counter 
 
As you can see in the diagram, the P-Machinery framework (actually, any part of the game program) invokes the Auto-Pilot dispatcher (1), typically in a loop.  The dispatcher dispatches the current step in the script (2) by decoding the statement and calling the appropriate command executor (3).
 
When the executor completes one cycle of its work, if the target state of the command has not been fulfilled (e.g., the sprite has not reached the given destination, or a set timer has not yet expired, etc.), control is returned to the game program (4) and the statement will be continued on the next invocation.
 
If the parameters of the command have been fully satisfied, the object's step counter is increment (5), and control is passed to the dispatcher (6), which will then dutifully do the same thing again for the next statement; and so on. 
 
 
The Auto-Pilot Script
An Auto-Pilot script is a list of operational statements, each comprised of a command and its parameters.  There are no requirements pertaining to which commands can be called, or in which sequence -- every command supported by the Auto-Pilot is available for any statement.
 
The only actual functional requirement of a script is that the very last statement must be a Stop command.  This tells the framework that the script is fulfilled and that the Auto-Pilot is no longer needed.  Technically, it clears the AutoPilot flag in the Sprite Object Record, disabling the Auto-Pilot.
 
Script statements are stored as program data and contain no executable code.  All work is performed indirectly by the command executor invoked for each statement.
 
Script Statement
The anatomy of a script statement is as follows:
    DECLE  <command-code>,  <parameter-1>,  <parameter-2> 
 
The <command-code> is a symbolic constant representing the command.  These constants are conveniently defined by the Auto-Pilot library as an enumerated list of values, and serve essentially as an index into the command-executor dispatch table.  Command codes will be described in full later on.
 
As shown above, each statement is afforded up to two parameters.  These are passed along by reference to the command executor, which is then responsible for using them as necessary.
 
Design Limitations
At the very beginning of design, I thought it made great sense to define scripts in a purely deterministic way, structurally, so that the execution of commands could be simplified by not having to figure out how many arguments were available.  Also, by making all statements the same size (three data words), individual steps within the script could be singled out and referenced externally, merely by giving a step number and computing their offset from the top.
 
However, in practice, none of that special functionality was ever needed nor desired.  In fact, the actual implementation of the command executors was such that each one could in theory consume as few or as many parameters as it needed.
 
Moreover, it turned out that different commands had different parameter requirements, but that even these were rather constants.  For instance, setting the screen position required always X and Y parameters; while setting the speed required only ever a single velocity parameter.  This made the two-argument requirement simultaneously an onerous restriction to some potential commands, and a wasteful consumption of resources for others.
 
Yet, this restriction on statement structure was built-into the Auto-Pilot engine and as much as it bugged me sometimes, I never took the time to go back and change it -- even when faced with the stark reality of dwindling ROM space.  The fact that I am complaining about it right now should serve to illustrate how much I regret not rectifying this.
 
 
The Auto-Pilot Dispatcher
The Auto-Pilot dispatcher is a simple dispatcher module whose sole purpose is to get the next statement from the script, decode its command code, and jump to its corresponding command executor.  It performs no context-switching, except to save the return address of the caller so that the ensuing executor can return accordingly when done.
 
The dispatcher uses a simple look-up table with pointers to each available command executor.  The decoded command code then serves as an index into this table.  The full command table is shown below:
    ; -------------------------------------------------------------
    ; Dispatch table for the Auto-Pilot commands
    ; -------------------------------------------------------------
    DECLE   CMD_DELAY               ; Command: AP_CMD.Delay
    DECLE   CMD_STOP                ; Command: AP_CMD.Stop
    DECLE   CMD_STOP_DIS            ; Command: AP_CMD.StopDisable
    DECLE   CMD_EXEC                ; Command: AP_CMD.Exec
    DECLE   CMD_EXEC_DELAY          ; Command: AP_CMD.ExecDelay
    DECLE   CMD_EXEC_WAIT           ; Command: AP_CMD.ExecWait
    DECLE   CMD_GOSUB               ; Command: AP_CMD.Gosub
    DECLE   CMD_SUBRET              ; Command: AP_CMD.Return
    DECLE   CND_MOVE_TILE           ; Command: AP_CMD.MoveToTile
    DECLE   CMD_MOVE_X              ; Command: AP_CMD.MoveToX
    DECLE   CMD_MOVE_Y              ; Command: AP_CMD.MoveToY
    DECLE   CMD_MOVE_XY             ; Command: AP_CMD.MoveToXY
    DECLE   CMD_MOVE_TARGET         ; Command: AP_CMD.MoveToTarget
    DECLE   CMD_MOVE_PIX            ; Command: AP_CMD.MovePix
    DECLE   CMD_SET_POS             ; Command: AP_CMD.SetPos
    DECLE   CMD_SET_POS_X           ; Command: AP_CMD.SetPosX
    DECLE   CMD_SET_POS_Y           ; Command: AP_CMD.SetPosY
    DECLE   CMD_SET_POS_OFS         ; Command: AP_CMD.SetPosOffset
    DECLE   CMD_SET_TARGET          ; Command: AP_CMD.SetTarget
    DECLE   CMD_SET_SPEED           ; Command: AP_CMD.SetSpeed
    DECLE   CMD_SET_DIR             ; Command: AP_CMD.SetDir
    DECLE   CMD_SET_DIR_X           ; Command: AP_CMD.SetDirX
    DECLE   CMD_SET_DIR_Y           ; Command: AP_CMD.SetDirY
    DECLE   CMD_SET_DIR_WAIT        ; Command: AP_CMD.SetDirWait
    DECLE   CMD_SET_VISIB           ; Command: AP_CMD.SetVisib
    DECLE   CMD_SET_STATE           ; Command: AP_CMD.SetState
    DECLE   CMD_SET_FLAG            ; Command: AP_CMD.SetFlag
    DECLE   CMD_CLEAR_FLAG          ; Command: AP_CMD.ClearFlag
    DECLE   CMD_FLIP_FLAG           ; Command: AP_CMD.FlipFlag 
 
Invocation Interface
The dispatcher is invoked by the game program via a subroutine call, with a pointer to the Sprite Object Record as its only argument.  The interface to the subroutine is described in the source code as follows:
;; ======================================================================== ;;
;;  AP_DISPATCH:                                                            ;;
;;  Procedure to execute the next command in an auto-pilot script sequence. ;;
;;                                                                          ;;
;;  There are two entry points to this procedure:                           ;;
;;      AP_DISPATCH         Receives the data record and a return address   ;;
;;                          as input parameters.                            ;;
;;                                                                          ;;
;;      AP_DISPATCH.Next    Same as AP_DISPATCH, but no return address is   ;;
;;                          expected.  This entry point is intended for     ;;
;;                          command handlers to chain their execution by    ;;
;;                          recursively calling the dispatcher.  The return ;;
;;                          address is expected on the top of the stack.    ;;
;;                                                                          ;;
;;  INPUT for AP_DISPATCH                                                   ;;
;;      R3      Pointer to Object Record.                                   ;;
;;      R5      Pointer to return address.                                  ;;
;;                                                                          ;;
;;  INPUT for AP_DISPATCH.Next                                              ;;
;;      R3      Pointer to Object Record.                                   ;;
;;      SP      Pointer to return address.              1 DECLE             ;;
;;                                                                          ;;
;;  OUTPUT                                                                  ;;
;;      R3      Pointer to Object Record.                                   ;;
;;      R4      Trashed.                                                    ;;
;;      R5      Pointer to param1 of current step.                          ;;
;; ======================================================================== ;;
 
 
Basic Algorithm
Rather than posting the source code, I shall describe the functional algorithm instead:
  • Save the return address in the stack (only applicable when called externally by the game program).
  • Using the given Sprite Object Record, check the AutoPilot flag.
  • If the AutoPilot flag is set then
    • Get the pointer to the active script.  Note that this address actually points to the current statement, and is incremented after every successful statement execution.
    • If we have a non-zero pointer then
      • Fetch the first data element of the statement.  This is the command code.
      • Use the command code as an index into the look-up table and retrieve a pointer to the command executor.
      • Jump directly to the command executor routine, passing along the current statement pointer and the return address in the stack.
    • Else it means that the Auto-Pilot was disengaged (asynchronously) after it was queued for execution.  So, we skip it.
  • Else it means the Auto-Pilot is not engaged, so skip it.
  • Return to caller.
 
In pseudo-code, it looks like this:
// Alternative entry point is
//    ap_dispatcher.next(obj)
procedure ap_dispatch(obj) {

    // Only process if the Auto-Pilot is active
    if (obj.Flags(AutoPilot) == True) {
        curr_statement = obj.ScriptSeq

        // Only execute if we have a valid statement
        if (curr_statement != null) {
            // Fetch and decode command from statement
            cmd_code = curr_statement[0]
            cmd_exec = DISPATCH_TBL[cmd_code]

            // Invoke command executor
            call cmd_exec(obj, curr_statement)
        }
    }
    
}
 
The fact that there are two entry points, one which stores the return address and one which expects a return address on the stack, allows the Auto-Pilot engine to execute multiple statements in sequence, and only return to the game program  when done or when a command needs to wait before continuing.
 
This simple yet elegant design affords a simple multi-tasking mechanism in which statements are executed sequentially, and yet able to yield to the rest of the game program (or Auto-Pilot scripts for other objects) when execution of a statement requires longer than a single game cycle to complete.
 
 
The Statement Command Executor
As mentioned before, each supported command has a corresponding command executor, a sub-routine which implements the command functionality.  In this way, each executor contains code specific to its function.  That said, they all follow the same basic structure and general algorithm:
  • Fetch the parameters needed by the function from the current statement (passed on by reference by the dispatcher).
  • Do the necessary work needed to fulfill the command.
  • If the command has fulfilled its purposed completely then
    • Increment the step counter by advancing the current statement pointer in the Sprite Object Record to the next statement.
    • Jump back to the dispatcher using the alternative entry point.
  • Else return to the caller by retrieving the return address from the stack.
 
We can express that in pseudo-code as follows:
procedure cmd_exec(obj, curr_statement) {
    // Fetch one or two parameters,
    // as needed by the command.
    param1 = curr_statement[1]
    param2 = curr_statement[2]

    // ...
    // Perform the command work here
    // ...

    if (cmd_done == True) {
        obj.ScriptSeq++
        call ap_dispatcher.next(obj)
    } else {
        return
    }
} 
 
As you may imagine, very simple commands such as SetSpeed, SetVisib, FlipFlag, etc. -- which are very quick to execute and require almost no time at all -- can all be executed in series within the same game cycle.  Thus, each one jumps back directly to the dispatcher when done, without further processing.  This allows you to set multiple flags or update multiple aspects of the sprite's state in a single go, even though they are all described as discrete script statements.
 
A script composed only of such state-management statements, can then be executed all at once, although it may not be very interesting at all.  The most interesting part of the Auto-Pilot is how it handles longer running commands such as those that require a sprite to move from one place to another at a specific speed, or delay the execution of the next statement by a specific length of time.
 
We will dig into the gory details of all command executors in the next installment of this series.
 
     -dZ.
 
 
 
 
 
 






December 2018

S M T W T F S
      1
2345678
9101112131415
16 171819202122
23242526272829
3031     

My Gallery Albums

Recent Comments

Tags

    Latest Visitors