Method and Apparatus for Game Development Using Correlation of Time Sequences and Digital Video Data

The present invention relates to a method and apparatus for computer game development, and more particularly, to a method and apparatus which correlates digital video data to time sequences providing for ease of manipulation by the operator.

Film editing has always been a part of film production. Historically, films have followed a single sequence. Thus, in editing a film, editors cut and pasted film portions one after the other. With the advent of computer gaming however, different events take place depending upon the decision of the user. When the user is given a choice of possible decisions to make, and makes one, the computer's programming accesses certain video image data as a consequence of the user's choice. Thus, in video games, frames of video images are not compiled to be viewed in a simple single stream, but must include the ability to branch into at least one of two time-sequence-based directions depending upon the user input. Accordingly, depending on an event or decision of the user, the computer can access the video segment which corresponds to the chosen time path.

The notion of branching video sequences has been utilized previously, for example, in movie maps. In that application, a user can proceed through a data space which is correlated to a position on a map. When the user reaches an intersection of streets on the map which is represented by a branching node in the data space, the user can choose to take one of a plurality of presented paths. The user directional and/or speed input is provided by a track ball or joy stick.

In game development, a developer might establish a game plan in the form of branched time lines so that he or she may edit film or digital video data to correspond to those time lines. However, this process is cumbersome because the developer must cut and paste the digital video data in an ad hoc manner, since he or she does not have the ability to precisely match the time duration of a particular stream of video images to the time lines of the game plan.

According to the present invention, a method and apparatus for developing a game is provided. In an editing mode, a first display is used to develop a branched time line structure and a second display is used to view video image sequences. The two displays are coupled so that the structure of the branched time line developed by the user on the first display may be correlated with portions of digital video image sequences viewed on the second display. The branched time line structure developed on the first display includes a first single time line connected to a node which is in turn connected to two or more single time lines. The node represents a decision point in the game.

The second display includes a time indicator for showing the amount of real time a particular image sequence generated by digital video data occupies. The present invention includes the ability to block on the time indicator a portion of a digital video data segment so that it can be correlated with a single time line of the branched time line structure to form a data block which is stored in the computer's data store.

In the playback simulation mode, the combined video and time line data block can be accessed so that it is displayed simultaneously with the branched time line. A position marker which can move along the branched time line indicates the point along the time line which corresponds to a given displayed video image. Thus, the developer has the ability to either view displayed video images in real time or to control the rate at which the time line marker travels along the time line. In the latter configuration, the movement of the position marker is capable of causing the sequential video images to be displayed in a manner that is slower or faster than real time.

FIG. 1 shows a computer and two displays according to the present invention;

FIG. 2 shows a first time line embodiment of the present invention;

FIG. 3 shows a second time line embodiment of the present invention;

FIG. 4 shows another time line embodiment;

FIG. 5 shows yet another time line embodiment;

FIG. 6 shows still another time line embodiment according to the present invention;

FIGS. 7a-7j show still shots taken from a video image sequence according to the present invention; and

FIG. 8 shows a flow chart of a method according to the present invention.

A computer 11 used in accordance with the present invention preferably includes a sufficient data store to store video data, for example, a hard drive, a video laser disk or a CD-ROM. Peripheral devices and/or equipment can be used as a data store as well or alternatively. The video data is preferably digital rather than analog to enable precision in editing it and manipulation in translation between files by the computer. Any one of various digital video compression schemes can be utilized to condense the amount of storage space required for the video data. Initial unedited digital video data is stored in a first computer file, so that it can be manipulated in accordance with the present invention.

Two displays 12 and 13 are shown in FIG. 1. Each is connected and is responsive to the computer 11. The user uses the two displays 12 and 13 to coordinate the game development process. On the first display 12 the user develops a branched time line structure (see FIGS. 2-6). On the second display 13, the user views the video images and blocks portions so that the video images can be correlated to the branched time line structure created by the user on the first display 12. The correlated data block generated is stored in computer 11. Instead of being separate monitors as shown in FIG. 1, the video data and time line images can be displayed in the form of overlays or windows on a single computer screen. In such a manner, a first window is a first display and a second window is a second display.

A typical operating system such as that used by Apple Computers or Microsoft's Windows program is sufficient to develop the programming to manipulate and combine data to develop a game according to the present invention. Typical word processing or graphical user interface computer programs include programming techniques suitable for programming a computer to perform in accordance with the present invention. The ability to click and drag are most helpful to carrying out the method described herein.

The user input module is the track ball 14. Alternatively, key strokes or other such commands, e.g., voice, can be used for user input depending on the operating system's capabilities. To begin the use of the method and apparatus for game development according to the present invention, a simple graphics program is initiated. Turning to FIG. 2, a branched time line structure developed on a grid of points is shown therein. Attention is turned to point 18 at which the user began to draw a first time line portion 19a. (The arrows 16 and 17 will be discussed in detail below.)

To start the development of the branched time line structure, the user double clicks at point 18 and drags the cursor up to another point where the user inserts a node 22a to form a single time line. The user then drags the cursor to form separate lines 22a and 23a one after the other, so that they connect to node 21a. The user can repeat the process forming another line 19b, node 21b, lines 22b and 23b, and so on. Other types of user graphical interfaces can be used to develop the branched time line structure such as drawing it by hand and scanning it to generate a computer data file. Moreover, a branched time line structure can be drawn in any other manner, such as using machine language or postscript.

The present invention provides for any number of different types of branched time line structures to be formed such as those shown in FIGS. 3, 4 and 5. FIG. 3 shows an example of an intertwined branched time line structure having lines 24a-24g connected via nodes 26a-26e. Note that lines 24a-24e are shown as bi-directional so that the user can move along each of the time lines in the forward or the backward direction. FIG. 3 also includes an expanded view of node 26b to show that a branched time line can reside within a node. There, secondary nodes 25a, 25b and 25c are connected by time lines 24h, 24i and 24j. The structure of a node within a node developed in accordance with the present invention is used to create intricate levels of hierarchy in a game plan's structure.

While FIGS. 2 and 3 show a branched time line having time lines connected to nodes, FIGS. 4 and 5 show different types of node configurations. For example, a perspective type of node 27 is shown in FIG. 4. A perspective node is configured so that when a game player reaches a perspective node, the game player can pivot on one or more points within the node to view different time line portion options before embarking thereon. For example, were a game player to advance along a path and then reach a room having five windows, doors, portals or exits, the player would need to decide which to proceed through. In this way, the perspective node maps out in a physical sense the directions one can take from a position inside a perspective node. Alternatively, the perspective node can present time based options only or in combination with physical or directional options, giving the game player the opportunity to pick a time path as he pivots within the node.

Turning to FIG. 4, the user could pivot to the right or to the left, such indicated by lines 28a-28e which also demonstrate the perimeter of the perspective node 27. Along the perimeter are windows, doors or exits 29a-29e which lead to the aforementioned time line portion options. If the game player were to choose to advance through exit 29a, the user would follow time line 31 having an arrow point at one end and an arrow tail at the other end, in this case, indicating the direction of advancement. Alternatively, the game player could have advanced through exit 29b, 29c or 29d to follow paths 32, 33 or 34 respectively.

FIG. 5 illustrates a similar perspective node to that shown in FIG. 4 showing that advancement by the game player can be made from any window, door or exit 36a-36d along path 37 or 38, for example. Within node 39, a decision node 41, like nodes 22a and 21b shown in FIG. 2, is positioned. Node 41 can act as a decision point or can contain yet another node such as the hierarchical structure containing secondary nodes 25a-25c as shown in FIG. 3.

Turning now to FIG. 6 and FIGS. 7a-7j, a simple branched time line having starting point 46, nodes 47a-47c and lines 48a-48d is shown to illustrate the time line and video image correlation feature of the present invention. Lines 48a-48d are broken into two lines to show the forward and backward directions more clearly. FIGS. 7a-7j show frames of video images 51a-51j generated in response to data signals corresponding to digital video data stored in computer 11. Each display screen is capable of containing other information, such as the time bar 52.

In practice, the branched time line structure is developed to generally map out the sequence of events of the game. When an initially unedited video sequence is viewed, and a portion is chosen or edited portions are extracted to be correlated to the branched time line structure, the single time line portion to which it is correlated will grow or contract in accordance with the length of the chosen video sequence. This is achieved by simple programming means. Alternatively, if data storage space is a concern or for any other reason, the duration of the single time lines in the branched time line structure can be adhered to fully or in part so that video sequences can be edited, slowed down or speeded up, to match the allowable time duration.

FIGS. 7a-7j illustrate video sequences which have been correlated with the branched time line structure of FIG. 6. FIG. 7a generally corresponds to point 46 on FIG. 6, which is essentially the starting point of that branched time line structure. FIG. 7b is a frame which roughly corresponds to half way up line 48a. FIG. 7c is a frame taken approaching node 47a while FIG. 7d is taken beyond the decision node 47a. FIG. 7e is at decision node 47a and shows a video image of the decision transition from line 48a to 48b. FIG. 7f shows the decision transition continuing. FIG. 7g shows the decision transition completed so that the path defined by line 48b can be embarked upon. Alternatively, FIG. 7h shows that instead of following a turn to the right, the game player's decision at node 47a was to continue in a linear manner and proceed along time line 48d. FIG. 7i shows the progress along time line 48d, nearing decision node 47c. FIG. 7j shows the position of the image after node 47c as if one were to pursue a path to the end at point 49.

The sequence of flames of film footage shown in FIGS. 7a-7j is illustrative of the correlation between the branched time line structure and a video image sequence because its geographic layout generally matches that of the branched time line shown in FIG. 6. However, any type of sequence of flames of video images having any type of content can be used in accordance with the present invention. The present invention is directed to correlation of a branched time line structure with any sort of time based medium, such as animation, audio, text data or any other type of data which changes over time. For example, time-based information such as which direction a camera is pointing, such providing annotations for interactivity, is also considered within the scope of the present invention.

Returning specifically to FIGS. 7a, 7b and 7c, there, the filled-in portion 53 of time bar 52 which is bracketed is illustrative of the length of real time occupied by that sequence of video images. Clearly, any type of time indication icon can be used such as a conventional clock, a digital read-out, an hour glass or a sundial. If the video sequence shown in FIGS. 7a, 7b and 7c had been unedited (ignoring, for now, FIGS. 7d-7j), then the game developer could see that the real time of the video sequence was, for example, 5 seconds because the filled-in portion 53 of the time bar 52 corresponds to five seconds of real time. For example, clock 54 shows that the time corresponding to the bracketed filled-in portion 53 is 5 seconds. The little marker 55 shows how far along in the video image sequence the frame currently displayed on the second display 13 is. For example, marker 54 is one quarter along portion 53 and therefore at the 1.25 second point of the video image sequence.

Moreover, additional read-outs such as a frame indicator (not shown) can be provided. A frame indicator shows, for example, the number of frames in a particular video sequence, and includes an indicator as to which frame is currently being displayed. Typically, video images are displayed at a rate of 30 frames per second. Thus the time bar 52 and a frame indicator can be lined up so that 30 frame segments are matched to one second on time bar 52.

As discussed above, in order to correlate a chosen video sequence to a single time line, the length of a single time line portion is adjusted to correspond to the real time duration of the chosen video sequence. Returning to FIG. 2, for example, arrows 16 and 17 show a portion 56 of the entire branched time line structure designated. This can be done by changing its color relative to other portions of the branched time line on the screen to highlight it or any other suitable means. Time line clock 57 shows that the designated time line portion has a length of 4 seconds. Therefore, in correlating the video sequence of FIGS. 7a-7c, which is 5 seconds, to time line portion 56, which is four seconds, several options are available.

One option is to use a part of the video sequence equalling 4 seconds. FIG. 7a shows blocking markers 58 and 59 blocking the equivalent four out of the five seconds of the video image sequence. The video data corresponding to the blocked video image sequence is then correlated with time line 56 and stored in a computer data store. Another option is to speed up the video image sequence so that the 5 second sequence takes only 4 seconds and then correlate it to the branched time line 56. These options are available if there are time constraints imposed, such as limited disk space, or market reasons.

However, as mentioned above, it is easier to simply change the length of the time line portion to correspond to the length of the video sequence the user wishes to insert at the point on the branched time line.

The next step is to correlate a video image sequence with the node. This is done in essentially the same manner as the time line. Turning to FIGS. 7d-7g, there, the bracketed filled-in portion 61 on the time bar 52 is shown. The video image sequence represents the images which would appear had a game player chosen to turn right at the node. A perspective node like that shown in FIGS. 4 and 5 could be used to generate the turning effect of the images at node 47a.

Backing up, FIG. 7h, which is nearly identical to FIG. 7d, shows the video image which would be displayed had the game player chosen to continue in the same physical direction as the initial path shown in FIGS. 7a-7c. In FIGS. 7h through 7j, the bracketed filled-in portion 62 of time bar 52 also depicts a certain amount of time.

FIG. 8 shows a flow chart of the sequence of steps a game developer uses in accordance with the present invention. As mentioned above, in step 66 the user starts the development with a double click of the input device. The branched time line is developed in step 67 on the first display 12 as shown in FIGS. 2-6 or in any other suitable manner. On the second display 13, a video image sequence is generated in step 68 from digital video data contained in the data store of computer 11. Simultaneously in step 69, the video time monitor is started. As the video image sequence is displayed in step 71, the video sequence's real time continues to be monitored. On the other hand, a mechanism may be in place to provide the real run-time of the video image sequence without needing to in fact display the data. In any event, at the end of the video sequence, which is step 72, the time monitor ends in step 73. With reference to FIG. 2, a piece 56 of the branched time line is then selected in step 75. Then as shown on the time bar 52 of FIGS. 7a-7j, a portion of the video data is blocked in step 74. The time line piece 56 (see FIG. 2) from the branched time line structure, that is its relative position to other pieces of the time line, and the video image data are then correlated in step 76. Certain parts of the process shown in FIG. 8 are repeated until the game developer has decided that enough correlations have been made. When the game developer is through, the process ends in step 77.

To correlate the video data with the branched time line, the process involves setting up a new file to which to copy chosen video data in an order or arrangement which best provides data access defined by the branched time line structure. In the simplest case, the game developer starts at the bottom of the time line, correlating a first video sequence with a first time line portion. In a linear manner, a second video sequence is correlated to a second time line portion, such second video sequence being copied from the video data file to be read after the first video sequence. After a node is reached, the branching makes correlation more complicated in the sense that the storage in the database or a disc, for example, of the video sequences becomes more random, making access to them slow, at times. Preferably, a data storage scheme provides the ability for quick access to the data upon simulation or actual play. For example, using two data disks, one poised for access to certain data when a decision node is reached, is a method of storing the correlated data. Another method, described in co-pending patent application Ser. No. 08/331,214, entitled Video Game Porting Compiler and Method of Operating a Video Game, naming Bruce Leak, Sean M. Callahan, and George Cossey as inventors, filed Oct. 28, 1994, is preferable.

While FIG. 8 shows a flow chart wherein the steps are performed in a parallel manner, that is, the video image is blocked while the time line portion is selected, the same process can be achieved in a serial manner. For example, after the video image sequence is selected, then the time line portion is selected.

The present invention also includes a simulation mode wherein the user can advance through the time line to view the video sequences to which portions have been correlated. Above, the edit mode of the present invention has been described. Therefore, once the selected video image data and the branched time line has been correlated, the game developer can return to the branched time line structure on the first display screen, for example, like that shown in FIG. 6. As mentioned previously, FIG. 6 generally correlates to FIGS. 7a-7j after the process of the present invention has been completed. The ability to cursor along the branched time line structure and view the video images which correspond to given points along the branched time line structure in simulation mode can be done with a joystick to simulate actual game play. In this manner, the game developer can move through the decision nodes at any speed, thus verifying or validating the decision nodes. Of course, any other user input device, such as a trackball or keyboard can also be used during simulation mode. For example, the circular cross-barred cursor 81 can be used to move through the branched time line structure to view the compiled video sequences. The cursor does not need to be directly coupled to the branched time line structure, but needs to be coordinated therewith to provide an indication of which frames are being viewed with respect to the structure. The arrows 82a in both vertical directions show which directions the cursor 81 can move along the branched time line structure to cause the video image sequence on the second display 13 to change in accordance therewith. When the cursor reaches a node, the game developer can toggle to the left or to the right to control the time path taken. To reverse direction, the user can move the joystick back. This allows the game developer to watch the sequences, advancing through and backtracking through nodes in order to determine if they are satisfactory. If the developer wants to edit data which has already been correlated, the game developer can return to edit mode so that the data can be moved out of the compiled game file and new or revised data can be inserted.

When the cursor 81 is temporarily in a fixed position on a particular point on the branched time line, the video sequence will freeze-frame on a particular frame. Thus, if the cursor is moved slowly, the user can view each frame, stopping at each one.

The present invention also provides the ability to jump around the branched time line structure without having to move along it by cursor 81. Turning again to FIG. 1, the dotted line 82 indicates that a cursor such as cursor 81 of FIG. 6, can be moved to any position along the branched time line.

In the simulation mode, the game developer has the option of viewing the branched time line at its highest level or at a lower level. At its highest level, the nodes within nodes would not be revealed. At a lower level, the time line image would reveal the nodes within other nodes. Simple programming means can provide the ability of the game developer to toggle between hierarchy levels.

In simulating game play at the highest level (that is, not viewing nodes within nodes), the present invention provides the ability for the computer to calculate the shortest path through the node having nodes residing therein. Therefore, the present invention provides the ability for the cursor to pass through a node in as seamless a manner as possible. In so doing, the time durations of each complete path of the branched time line structure within the highest level nodes, are calculated and compared to find the shortest time path.

The foregoing description of the preferred embodiment of the present invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Obviously, many modifications and variations will be apparent to practitioners skilled in this art. The embodiment was chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.