 |
Claims  |
|
|
We claim:
1. An apparatus for rapidly processing data records representing moving and
non-moving objects on a playfield to determine which objects to display on
a portion of the playfield being displayed on a video display comprising:
means for organizing all of the data records for moving objects to be
displayed as a single linked list in memory, said single linked list
organized by the locations where the objects would be displayed if the
whole playfield were to be displayed;
means for processing only that portion of the single linked list for
objects positioned near said portion of said playfield to be displayed;
wherein the data records for said objects include positional information
expressed as x and y coordinate offsets from a reference point on the
playfield.
2. An apparatus for rapidly processing data records representing moving and
non-moving objects on a playfield to determine which objects to display on
a portion of the playfield being displayed on a video display comprising:
means for organizing all of the data records for moving objects to be
displayed as a single linked list in memory, said single linked list
organized by the locations where the objects would be displayed if the
whole playfield were to be displayed;
means for processing only that portion of the single linked list for
objects positioned near said portion of said playfield to be displayed;
wherein said means for processing includes means for generating a slip
indicating where on said linked list to begin processing to determine
which moving objects are to be displayed said means for processing also
for using said slip to control where processing on said linked list should
begin so as to process only those data records for objects which are
positioned on said playfield near said portion of said playfield to be
displayed.
3. The apparatus of claim 2 wherein said video display includes means to
scan a plurality of raster scan lines comprised of a plurality of pixels
with raster addresses expressed in terms of a position along a y axis
which is perpendicular to the direction of scanning of said raster scan
lines, the position of the scanning at any particular time expressed as a
current raster address, and wherein positions of objects on said playfield
are expressed in terms of positions along said y axis and positions along
an orthogonal x axis which is parallel to the direction of scanning of
said raster scan lines, and wherein said playfield includes a playfield
reference point and wherein said means for generating a slip includes
means to track at least the current raster address as a y offset of the
current raster scanning position from a reference point on the playfield
and wherein said slip is generated from data including the y offset of the
current raster scanning position.
4. The apparatus of claim 3 wherein said means for organizing further
comprises means for adjusting the position data of moving objects which
have been moved relative to said playfield reference point such that the x
and y coordinate offsets in the data records of those objects which have
been moved are altered relative to said playfield reference point and for
reorganizing said linked list such that said moved objects are on said
list in the proper position corresponding to the new position of each
object on said playfield.
5. The apparatus of claim 4 wherein said means for organizing further
comprises means for storing both moving and non-moving object data records
in said memory in an ordered, two-dimensional array where each array
location maps to a specific area on the playfield.
6. The apparatus of claim 5 wherein said two-dimensional array is a
collision detect array and further comprising means for collision
detection between an object to be moved and other moving and non-moving
objects in the vicinity of the object being moved on said display by
checking the position data of the data record corresponding to the object
to be moved against the position data of objects having data records
stored in adjacent locations of said collision detect array, said adjacent
locations of said collision detect array being limited to those adjacent
positions of said collision detect array which lie in the general
direction of movement of the object to be moved.
7. The apparatus of claim 6 wherein said means for collision detection
checks for collisions with the objects, if any, of the three next adjacent
collision detect array locations in the direction of movement if the
direction of movement is along either the x axis or the y axis on said
display or in the five nearest array locations forming a right angle
blocking the movement if the direction of movement is not on the x or y
axes.
8. An apparatus for determining which of a plurality of motion objects
positioned on a playfield to display on a video display in a window
portion of said playfield, said window portion defined by a plurality of
sequentially scanned raster scan lines including a current raster scan
line defined as the raster scan line being processed at any particular
moment:
first means for determining the current positions of said motion objects on
said playfield and for storing in memory a data record for each motion
object said data record for each said motion object including position
information expressed in playfield relative terms as an offset from a
known reference position on said playfield, said data records organized as
a single linked list organized in the order the motion objects would be
displayed if the entire playfield including all the motion objects thereon
were to be displayed;
second means for determining the position of said window portion of said
playfield on said video display by determining in playfield relative terms
as an offset between a point in said window and said playfield reference
point;
third means coupled to said second means for generating a slip from the
position information of said window on said playfield, said slip defined
as a pointer to the address in said memory of the data record which
corresponds to the first motion object on said linked list through which
said current raster scan line would pass if said current rater scan line
extended completely across said playfield;
fourth means coupled to said first, second and third means for using said
slip to begin processing data records for motion objects on said linked
list starting at the motion object data record identified by said slip to
determine which said motion objects to display.
9. The apparatus of claim 8 wherein at the start of each raster scan line
said fourth means uses said slip as a link address pointing to a data
record on said linked list to begin processing to determine which of said
motion objects having records on said linked list are to be displayed.
10. The apparatus of claim 9 further comprising a counter and a scanning
circuit for generating said plurality of raster scan lines which define
said window portion, each said raster scan line having a number, said
scanning circuit also generating and end-of-line signal signifying when
each new raster scan line is to be scanned, said counter being coupled to
receive said end-of-line signal from said scanning circuit, said counter
also being coupled to said second means to receive data defining the
current position of said window portion in terms of the scan line number
of the first scan line in said window portion said counter counting said
end-of-line signals starting from the scan line number of said first scan
line in said window portion to generate a current scan line number,
thereby defining the position of the current scan line in playfield
relative terms from the scan line number which locates the current window
position, and wherein said third means receives said current scan line
number and selects said slip address pointer using said current scan line
number at the end of each raster scan line.
11. The apparatus of claim 10 further comprising means in said first means
for reading player operated controls and causing corresponding movement on
said display of a plurality of associated player controlled, movable
characters, said characters being motion objects whose position and
appearance is defined by data records by adjusting position data in the
data records of said movable characters and for, from time to time,
determining the positions of said player controlled characters and for
adjusting the position of said window on said playfield so as to keep all
characters visible in said window at all times.
12. The apparatus of claim 11 wherein said first means further comprises
means for performing collision detection processing between motion objects
being moved and other motion objects or other objects on said playfield in
a neighboring area of said window, including means for collision detection
as to objects located only in predetermined adjacent areas relative to the
movement path.
13. An apparatus for displaying selected ones of a plurality of moving
objects located in a window portion on a playfield, said window portion
comprising a plurality of raster scan line which are sequentially scanned
including a current raster scan line, each said raster scan line having a
scan line number and comprised of a plurality of sequentially scanned
pixels including a current pixel defined as the pixel being scanned at any
particular moment, comprising:
means for reading user inputs and other data regarding the movements of
said moving objects and for determining the position on the playfield of
said moving objects in playfield relative terms with respect to a
reference point on said playfield;
means for storing data records regarding said moving objects including
their playfield relative positions in a random access memory and for
linking the data records of said moving objects as a linked list ordered
approximately by the order in which said moving objects would be displayed
if all the moving objects on the playfield were to be displayed in raster
scan order instead of only the moving objects located within the
boundaries of the current window portion;
means for generating a playfield relative slip pointer from the scan line
number of the current raster scan line indicating the address of the data
record of said linked list for a predetermined moving object;
means for comparing said playfield relative position information of said
moving objects on said linked list starting with the moving object
indicated by said slip pointer to the current raster scan line number and
the position of the window portion to determine which moving objects on
said linked list are to be displayed; and
means for displaying the moving objects that are visible in said window
portion.
14. A method of determining rapidly which of a plurality of moving objects
on a playfield are to be displayed in a movable window displaying a
portion of said playfield, said window comprised of a plurality of
sequentially scanned raster scan lines including a current raster scan
line, and for displaying said moving objects comprising the steps of:
organizing data records recording positions of each moving object on said
playfield as a linked list ordered by the sequence in which all the moving
objects would be written on a video display if the entire playfield were
displayed in raster scan fashion instead of only the portion of the
playfield visible in said window portion;
storing said linked list in memory;
generating a slip pointer address based upon said current scan line number,
said slip pointer address pointing to the address in said memory of the
data record on said linked list corresponding to a moving object
positioned on said playfield near or within said window where processing
should start; and
processing the data records on said linked list starting with the data
record pointed to by said slip pointer address to determine which of said
moving objects are at least partially visible in said window;
displaying those objects on said linked list which have position data
indicating that said objects are at least partially visible within said
window.
15. The method of claim 14 wherein said raster scan lines comprise a frame
and further comprising the steps of updating said slip pointer address
after a predetermined number of scan lines are displayed and continuously
updating said slip pointer address throughout each frame of scan lines and
updating the current position of said window at predetermined times and
updating the slip pointer address to reflect the new window position at
predetermined times.
16. The method of claim 15 further comprising the steps of organizing all
data records of objects on said playfield into a two dimensional array
where each array location maps to a particular area on said playfield, and
wherein each data record corresponding to a moving object is stored in an
array location corresponding to the playfield relative position of said
object where each data record includes position offset data indicating the
position of the associated moving object on said playfield relative to a
reference point on said playfield and further includes a link field
containing a pointer to the address of the data record for the next object
on said linked list, and further comprising the steps of reading user
controlled inputs regarding the desired movements of said moving objects
and adjusting the data records for the objects to be moved by changing
said position offset data for each moving object so moved and, if
required, reordering said linked list to reflect the new positions of the
moving objects so moved by changing the contents of said link field in the
data records for objects which have moved and changing the positions in
said array of the data records corresponding to moving objects which have
been moved to correspond to their new positions on said playfield.
17. The method of claim 16 wherein said playfield also has non-moving
objects positioned thereon and further comprising the steps of organizing
said non-moving object data records for non-moving objects on said
playfield in said two-dimensional array such that the data records for
said non-moving objects are stored in the appropriate array locations
corresponding to the positions of said non-moving objects on said
playfield and comparing the position data for each moving object being
moved against the position data of other moving and non-moving objects, if
any, in a predetermined pattern of array locations in the path of desired
movement to determine if a collision has occurred.
18. The method of claim 17 wherein the steps of comparing the position data
further comprises the steps of comparing the position data of the moving
object sequentially to the position data of the objects having data
records stored in said predetermined pattern of array locations and
stopping the comparisons upon locating the first data record indicating a
collision has occured where a collision has occurred if the positions of
two objects are within a predetermined distance of each other. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
The invention pertains to the field of processing of data records for
objects to be displayed on a video display. More particularly, the
invention pertains to the field of video game processing of a plurality of
objects on a playfield to determine which objects are visible on the
portion of the playfield being displayed and which objects have collided
with other objects.
As video games have become more complex and sophisticated they have
progressed to multiple player games with multiple characters in conflict
with multiple other entities with the battle taking place on ever more
complex playfields. Because standard video display circuitry is used to
display all this action, and because there are a large number of moving
and non-moving objects on such playfields there have developed severe
limits on the complexity of the game than can be depicted. This is because
the amount of time in which to decide which objects are to be displayed on
a particular scan line and which objects have collided with other objects
is limited by the amount of time the video processing circuitry takes to
scan the raster lines in the image. Since this scanning is a fast process,
the amount of time to process the data describing each object to make
decisions about it is limited. Ultimately, this limits the number of
objects that a system can handle and thereby limits the number of objects
and players that the system can successfully cope with.
Accordingly, a need has arisen for a video game processing system that can
rapidly handle large numbers of objects and player inputs to cause motion
in desired directions of some of said objects and which can rapidly detect
collisions between many such objects and many other objects on the
playfield.
Further, a need has arisen for a video game system which can gracefully
handle multi stamp motion objects which are larger than one stamp wide and
one stamp tall. A stamp is a group of pixels and lines, generally
rectangular and generally 8 pixels wide and 8 scan lines tall, which is
used to provide the shape of the motion object. The pixels are written
with data words which define the color or shade of gray at each location
in the stamp to define the identity of the motion object by its shape.
Heretofore, motion objects have been only one stamp wide. This limits the
size and complexity of character shapes which could be drawn on the screen
because the number of pixels available for coloring was too small to
define truly complex character shapes. Thus, as the sophistication of game
users has increased, there has arisen a need to be able to provide them
with more colorful and complex character shapes.
SUMMARY OF THE INVENTION
According to the teachings of the invention there is provided a video
system which can process a large number of moving objects under the
control of multiple users and a large number of non-moving objects within
the timing constraints imposed by the video image producing circuitry. In
the preferred embodiment, the video game system comprises a central CPU
which runs the main game program implementing the rules of the game and
which reads user control inputs indicating desired movements of the
characters and which controls other objects displayed on the screen. The
action takes place on a playfield of which only a portion is displayed.
The various moving objects and non-moving objects which are part of the
game are all placed on the playfield. The moving objects are moved in
response to either user control inputs or in response to commands from the
computer under the control of the main program to move the objects to
create the conflict in the game. The conflict in the game is irrelevant to
the invention and may be between the main characters and monsters or
between the objects which the players control and other objects that the
main processor controls or non-moving obstacles. The CPU continuously
evaluates the positions of the moving objects and stores data records
describing both the moving and the non-moving objects, including their
positions relative to a reference point on the playfield, in a two
dimensional array in a random access memory which will hereafter be
referred to as the array RAM. Each location in the array maps to a certain
area on the playfield. Contiguous array locations map to contiguous areas
in the playfield. The non-moving objects such as walls on the playfield
are also stored in the two dimensional array as dummy motion object
records which are not on the linked list but which are stored at array
locations corresponding to the position where they would appear on the
playfield. Hereafter, the portion of the playfield which is displayed will
be referred to as window. The dummy motion object records only contain the
x and y locations of the non-moving objects and may or may not contain a
dummy picture pointer. The actual picture pointer for the non-moving
object is stored in another array in the array RAM which is accessed
during a time slot devoted to painting the playfield picture (hereafter
called the playfield picture array). The picture pointer is the address in
read only memory where the actual graphic information defining the
appearance of the object is stored. In the preferred embodiment, each
array location for the motion object and dummy motion object data records
(hereafter called the collision detect array) maps to a box on the
playfield that is 16 pixels wide and 16 lines tall.
The moving objects in the collision detect array are linked by an ordered,
linked list but this linking is not relevant to the collision detect
feature of the invention. It is only an element of the invention that
increases the speed of display processing which determines which of the
motion objects will be visible in the window. The ordering of the list is
such that the objects appear on the list in the order they would be
displayed if the entire playfield was displayed in raster scan fashion
from left to right and top to bottom. In embodiments where raster scanning
is not used, the linked list need not be ordered in this fashion. When the
moving objects move, the linked list is reordered by the computer during
its time slot for access to the array RAM to maintain the proper order in
the linked list.
The video game system processes the data records in the array RAM in time
multiplexed fashion. A time slot will be given to the CPU to read records
from or write records to the array RAM. During this time slot the CPU does
any of the following things: it builds the array databases (there is a
collision detect array, a playfield picture array, an alphanumeric array
and a slip table or array), it moves objects per user commands by changing
the position offset field in the record to reflect the object's new
position relative to a playfield reference point (usually the upper left
corner of the playfield), it updates the array entries to change the links
on the linked list and change the slip table entries or to move object
records to the proper locations in the collision detect array when the
objects have moved, or it reads data records of objects that have been
moved and neighboring objects for collision detect processing. The term
"slip" as used herein, means a starting link pointer or link to the
correct object data record on the linked list where processing for any
particular raster scan line is to start.
Another time slot is devoted to access of non-moving objects for purposes
of displaying the walls and or other non-moving objects which form part of
the playfield landscape. Another time slot is devoted to access of the
alphanumeric data for display of information on the screen regarding the
score or other textual material.
Another time slot is dedicated to linked access to the next motion object
on the linked list either through use of the link from the last object
processed or by use of a slip. The slip table lists the places on the
linked list where "hit" processing should start on each raster scan line
to determine which motion objects are in positions to appear on the scan
line. The slip table is updated by the CPU during its time slot whenever
the order of the linked list is changed. Access into the slip table is
generated by decoding data including the current scan line number being
processed in the current window. The slip data is accessed from the slip
table in the array RAM and latched into a link register at the beginning
of the scan of each new raster scan line.
The last described time slot is devoted to accessing data records from the
linked list describing the y positions for the motion objects. This data
is used to do y hit processing to determine if there is a possibility that
the object will appear on the current scan line. If a y hit is found, the
pointer to the graphic data for the motion object is retrieved and the x
position of the object is examined to determine if there is an x hit,
i.e., the object is located along the visible portion of the x axis on the
playfield which is currently being displayed. Each data record has x and y
coordinate data describing the position of the motion object relative to a
reference point on the playfield. Each data record also has a link field
containing a pointer to the next record on the linked list. To avoid
needless processing of data records for objects that will not be visible,
access to the data records at the correct point in the linked list is
gained by using the slip pointing to the first motion object on each scan
line, and, thereafter until the end of the line, by using the links to
continue processing. At the end of each line, a signal is generated by a
state machine/sync generator controller logic to cause the slip address to
be updated to its new value and to be latched into the link register for
use in access to the linked list at the proper point for processing the
next line.
Every time a motion object is to be moved, a collision detect process must
be performed to determine if the movement would result in a collision with
either another motion object or a non-moving object on the playfield. The
CPU performs this process in a rapid manner by comparing the position of
the object to be moved to the positions of only and at most the nearest
objects in the path of movement since the motion object obviously will not
have collided with any objects not in the path of movement. To do this the
CPU uses a two dimensional collision detect array of data records
describing the relative positions of the moving and non-moving objects on
the playfield and accesses the records of only the closest objects in a
specific pattern that lies in the path of movement and which will
intersect said path of movement. The position data in the data records so
accessed are then compared record by record to the position data of the
object to be moved.
Both the x and y coordinates of all the objects in the array are expressed
in offsets from the reference point on the playfield so that the
comparison process does not have to wait for the whole array to be
rewritten every time the window changes position.
The comparison is done by subtracting the x position of the first record in
the pattern from the proposed new x position of the object to be moved and
testing the absolute value of the result to determine if the result is
smaller than a specific, constant number. If the result is not smaller
than the specific constant, then the y position comparison is skipped, and
the next record in the pattern is retrieved and the comparison is started
on the new record. If the result of the x comparison for the first record
is smaller than the constant, the y positions are compared in the same
manner. If the absolute value of the result is smaller than the constant,
a collision has occurred and all further record comparisons are stopped
since the moved object need only collide with one thing to trigger
collision processing. If the absolute value of the result is not smaller
than the constant, the next record for an object in the pattern is
retrieved and the position comparison process continues.
Once a collision has occurred, the CPU determines which motion object has
collided with which other object and the proper course of action to take
for that type of collision. For example, if a laser blast motion object
has collided with an attacking monster, the proper course of action may be
to make the monster disappear. If a monster motion object has collided
with the character being manipulated by a player, the proper course of
action may be to make the character die or lose health, power etc. If the
collision was between a character and a wall on the playfield, the proper
course of action may be to make the character's motion in the direction of
the wall stop at the wall. The proper course of action may differ in
different embodiments to implement different rules of play.
According to the teachings of the invention, multi stamp motion objects are
provided. Motion objects may consist of an array of stamps up to 8 stamps
wide and 8 stamps tall. Each motion object record on the linked list
consists of four words, one of which is the address of the first stamp in
the array of stamps. The other words of the motion object's data record
contain the motion object's vertical and horizontal size, the horizontal
and vertical positions and the link to the next motion object. During each
scan line, a chain of motion object data records are examined by logic
that compares the y position of the motion objects to the y position of
the current scan line, both positions being expressed in playfield
relative terms. The comparison circuitry delivers a number which is the
row number for the stamp in the motion object array containing the current
scan line. The row number of the stamp and the horizontal size information
is used to look up or calculate a motion object stamp offset number. This
is the stamp number of the first stamp in the array on the row containing
the current scan line. Each array of stamps is numbered with the stamps in
row 1 numbered 1, 2, 3 . . . up to 8. The first stamp in the second row
will then be numbered as the next number in the sequence following the
number for the last stamp in row 1. A counter then counts as each stamp is
processed to provide the relative address of succeeding stamps in the
current row. The motion object picture field also contains a field which
is the actual address in the graphics ROM of the first stamp in the array.
This address is added to the offset from the first stamp number of the
current stamp number.
The comparison circuitry also delivers a number which represents the actual
scan line in the current stamp which is being scanned. This information
plus the actual address of the current stamp in ROM derived from the above
described circuitry is used as an address to access a ROM where the
graphic data in the form of a pixel pattern for that type of motion object
is stored. The correct pixel pattern is then latched into a shift register
and shifted bit by bit into the line buffer being loaded in preparation
for scanning the next line. All the foregoing process is done one line
time ahead of the time of actual scanning of the line and is stored in one
of a pair of "ping pong" line buffers in waiting for the actual scanning
process. The other ping pong buffer stores the pixel pattern that is
actually being scanned at any particular moment.
According to another aspect of the teaching of the invention there is
provided a lookahead feature for processing the linked list of motion
objects to determine which will be visible in the current window. In the
preferred embodiment of the invention, a synchronous state machine in the
form of a ROM coupled to a sync generator and to several status signals is
used to generate the control signals which control the time slots for
multiplexing of addresses for the array RAM and the latching of output
data from the array RAM. The status signals which are input to the state
machine indicate the match or no match condition for the vertical and
horizontal position comparisons between the current motion object's
position and the scan line being painted in the current window. These
status input signals to the state machine also indicate several other
things: when the end of processing of all the stamps on one row of a
motion object has occurred; when the end of each scan line is reached; and
when the state machine is entering its first cycle of 7 basic time slots
which are used in looking for hits and doing other things. The state
machine has a foreground cycle of 7 time slots where various addresses are
selected and various data is written to or read from the RAM. The
foreground cycle is generally for the purpose of processing the linked
list records to determine which motion objects at or beyond the slip
pointer address are to be displayed on the current line. Each motion
object is processed first for a y hit. This means that for an object which
is a "hit," i.e., will be visible, the y position is such that part of the
object is supposed to appear on the current scan line. If there is a y
hit, the motion object is processed for an x hit in another time slot of
the foreground state machine cycle. This x hit processing is to determine
if the x position of the object and the x position of the window and the
horizontal size of the object are such that the object is supposed to at
least partially appear on the current scan line.
Since the process of processing a multistamp motion object to retrieve the
graphic data for several stamps on the current line takes some time to
complete, the state machine also has a background cycle. This cycle is
entered each time a status signal indicating that the stamps of a previous
motion object are still being processed to load the graphic data into the
line buffer. The purpose of the background cycle is to continue processing
of the next motion objects on the linked list following the motion object
last processed in the foreground states. The background processing however
is limited to determination of which motion object on the linked list has
both a y hit and an x hit. No picture pointer is retrieved for any motion
object having a y hit an x hit found in the background state. Only the
foreground states retrieve picture data.
To perform its function, the background cycle continues processing the
motion objects further down the list from the motion object which is
currently having its graphic data loaded into the line buffer so as to
implement a lookahead function. When the background states find the next
motion object with both an x and a y hit (in some cases, one foreground
state is also involved in the lookahead function), processing goes into a
hold mode where the background states continue to cycle in looking at the
horizontal position of the motion object which was found, but no new
motion objects are processed. This holding continues until the foreground
states and the associated circuitry finish loading all the picture data
from the original motion object into the line buffer as signaled by one of
the status signals. The foreground cycle is then re-entered, and the
picture pointer is retrieved for the object so located in the background
states. This pointer is used to access the graphic data from the graphics
ROM for the new motion object. If this motion object is more than one
stamp wide then, as soon as this graphic data loading process commences,
the status signal indicating that the graphics ROM and shift registers are
busy with the graphic data loading process is, and the background cycle is
re-entered to continue the lookahead process. A motion object which is
only one stamp wide can be processed and loaded to the line buffer in one
complete foreground cycle of 8 time slots, at the rate of one time slot
per pixel. The background cycle is entered only if the motion object to be
displayed has more than one stamp horizontally which will be visible.
BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1A and 1B are a block diagram of the circuitry implementing the
teachings of the invention.
FIG. 2 is an illustration of the conventions used in describing the
positions on the playfield of motion objects and playfield objects, the
current window position and the stamp arrays of the objects on the
playfield.
FIG. 3 is an illustration of the collision detect array in the array RAM.
FIGS. 4A and 4B are block diagrams of the vertical and horizontal match
circuits and the stamp offset calculation circuits.
FIG. 5 is a state diagram of the foreground cycle.
FIG. 6 is a state diagram of the background cycle.
FIG. 7 is a flow diagram of the collision detect algorithm.
FIG. 8 is a symbolic diagram of the conventions and tests used to determine
the presence of collisions between objects on the playfield.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
Referring to FIGS. 1A and 1B, there is shown a block diagram of a system
according to the teachings of the invention. For convenience, the reader
may wish to cut both FIGS. 1A and 1B along the cut line and assemble them
as one figure. These two figures will be hereafter referred to as FIG. 1.
Such a system has utility in a video game or other application where large
numbers of moving objects must be displayed on a screen and/or where
collisions among them during the movements must be detected.
A computer 20 runs a main program stored in working ROM 22 to do various
functions for the system. The main program implements the particular rules
of the game, and causes the computer 20 to perform input/output operations
to read user control input data from user controls and interface unit 24
and is given in Appendix A. The user control interface unit is of known
design and is not critical to the invention. It provides one or more user
control sets such as joysticks, fire buttons, magic buttons etc. In the
preferred embodiment, four user control sets are provided, and the
computer 20 reads data from them either by interrupt vector processing or
by polling of the controls. In the preferred embodiment, polling is used.
The particular rules of the game implemented by the main program such as
what happens when a monster collides with a character or what happens when
a character's shot or other form of assault collides with a monster are
not critical to the invention. The teachings of the invention are broadly
applicable across the video game market and, in fact, may be useful in
other fields such as processing radar or sonar images with large numbers
of moving targets where collision or proximity must be detected.
In the preferred embodiment, the system of FIG. 1 is used in a video game
involving four main characters which move and fight against multiple
moving monsters. Some of the characters shoot rays or bullets and these
also are displayed as moving objects. All this action takes place on a
playfield which is essentially a maze with walls, treasures, food, keys
and other stationary and nonstationary objects placed therein. All of
these moving and nonmoving objects have data records stored in a database
comprised of several arrays in the array RAM. Each of the records in the
database describes certain attributes of the object. Among these
attributes for each object are the horizontal and vertical position on the
playfield.
In the preferred embodiment, the playfield has multiple levels each of
which are different. The information as to the configuration of each level
and the locations of the various nonmoving objects on each level is stored
in a working ROM shown as part of memory 22. The computer uses data from
this ROM to build a two dimensional playfield array in the array RAM 32.
Each nonmoving object record in the playfield array also has a dummy
motion object entry in the collision detect two dimensional array in the
proper array location that corresponds to the position of the object on
the playfield. This dummy entry has the x position and y position data of
the object and may or may not have a picture pointer. The presence or
absence of the picture pointer is irrelevant to the invention. The purpose
of this dummy entry is to complete the collision detect array with all the
moving and nonmoving objects on the playfield so that collision detect
processing can be done from one array. The nonmoving objects in the
collision detect array may or may not be part of the linked list.
In the preferred embodiment, only a portion of the playfield is displayed.
This portion of the playfield will be hereafter called the window. The
playfield has a reference point which can be anywhere but which is usually
its upper left corner. The window also has a reference point, and it also
can be located anywhere in the window but is usually located in the upper
left corner. There may be as many as 1024 moving and nonmoving objects
scattered about the playfield at any particular time, but only some of
them will be visible in the window. The positions of the moving and
nonmoving objects are expressed in terms of their offsets from the
reference point on the playfield. In the preferred embodiment, the window
location is moved to keep the four main characters visible at all times.
In other embodiments, the window may remain stationary or may follow the
movements of some but not all the main characters. A major function of the
system of FIG. 1 is to determine which of the moving and nonmoving objects
on the playfield will be visible in the window. The system is aided in
this process by the fact that the positions of all the objects on the
playfield are expressed as playfield relative offsets.
The computer 20 is responsible for creating the database for all the
objects and updating the database when the position of the objects change.
| | |
