Source: http://www.google.ca/patents/US5287446
Timestamp: 2014-10-01 16:16:49
Document Index: 24146352

Matched Legal Cases: ['art 101', 'art 121', 'art 230', 'art 252', 'art 254', 'art 252']

Patent US5287446 - System and methods for intelligent movement on computer displays - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsControlling successive frames of video data displays the movement of an object between points on the display along natural or `intelligent` paths around obstacles, by establishing a locus of data points around each obstacle along which displayed movement of the object may proceed under conditions of...http://www.google.ca/patents/US5287446?utm_source=gb-gplus-sharePatent US5287446 - System and methods for intelligent movement on computer displaysAdvanced Patent SearchPublication numberUS5287446 APublication typeGrantApplication numberUS 07/598,174Publication date15 Feb 1994Filing date15 Oct 1990Priority date15 Oct 1990Fee statusPaidAlso published asDE69125565D1, DE69125565T2, EP0481286A2, EP0481286A3, EP0481286B1, US5425139Publication number07598174, 598174, US 5287446 A, US 5287446A, US-A-5287446, US5287446 A, US5287446AInventorsKenneth A. Williams, David C. Iden, Larry L. ScottOriginal AssigneeSierra On-Line, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (8), Non-Patent Citations (2), Referenced by (40), Classifications (14), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetSystem and methods for intelligent movement on computer displaysUS 5287446 AAbstract Controlling successive frames of video data displays the movement of an object between points on the display along natural or `intelligent` paths around obstacles, by establishing a locus of data points around each obstacle along which displayed movement of the object may proceed under conditions of the direct trajectory between points intersecting the locus of data points. `Freeway` paths are provided between remote sectors of the display to expedite `natural` movements over substantial distances around obstacles in a second embodiment.
What is claimed is; 1. A method for establishing a contiguous path of points between a beginning position and a selectable position for a movable object on a computer-controlled display showing at least one impassable object, said method comprising the steps of:providing coordinates for the beginning position and the selectable position; segmenting an area of the display into a plurality of sectors; providing at least one freeway between remote sectors of the display; detecting a position of any impassable objects; providing an avoidance path about each impassable object; calculating a direct trajectory between the beginning position and the selectable position; comparing the direct trajectory to the avoidance paths; analyzing the coordinate data at positions along the avoidance path to determine whether a sector includes any freeways in a direction of the selectable position; and establishing a locus of points intermediate the beginning position and the selectable position, said locus of points positioned along the direct trajectory where the direct trajectory does not have a same position as the impassable objects, along the freeway where the direct trajectory and the impassable objects have the same position and the freeway is in the direction of the selectable position, and along the avoidance path where the direct trajectory and the impassable object have the same position and no freeway is available. 2. A method for establishing a contiguous path of movement between a beginning position and selectable position for a computer-controlled display, said method comprising the steps of:providing coordinates for the beginning position and the selectable position; providing an avoidance path of coordinates about each impassable object; establishing a plurality of freeway areas; establishing at least one freeway providing a path of coordinates between two freeway areas; calculating a direct trajectory between the beginning position and the selectable position; comparing the direct trajectory to the avoidance paths for intersections therebetween and for each avoidance path determining a closest intersection and a farthest intersection from the beginning position; analyzing each avoidance path between the closest intersection and farthest intersection to determine whether any freeways are in a direction of the selectable position and provide a shorter path than the avoidance path; and for each avoidance path, establishing a locus of points intermediate the beginning position and the selectable position, said locus of points positioned upon the freeway where the freeway provides a shorter path to the selectable position than the avoidance path, else upon the avoidance path between the closest and farthest intersection for each avoidance path, and then upon the direct trajectory between the beginning position and the selectable position and between each farthest intersection of each avoidance path and the closest intersection of a next avoidance path. 3. A method for establishing a contiguous path of movement between a beginning position and a selectable position for a computer-controlled display, said method comprising the steps of:providing coordinates for the beginning position and the selectable position; defining an avoidance path of coordinates about each impassable object; segmenting the display area into a plurality of sectors; providing at least one set of freeway coordinates between remote sectors of the display; calculating a direct trajectory between the beginning position and the selectable position; comparing the direct trajectory to the avoidance paths for intersections therebetween and for each avoidance path determining a closest intersection and a farthest intersection from the beginning position; analyzing the coordinate data at positions along the avoidance paths between the closest and farthest intersections to determine whether a sector includes a freeway in a direction of the selectable position; and establishing a locus of points defined by a path traveled by:a) proceeding in the direction of the direct trajectory toward the selectable position until the closest intersection is reached; b) proceeding from the closest intersection toward the farthest intersection for any avoidance path encountered by following the avoidance path and entering, traversing and exiting any freeway in the direction of the selectable position substantially adjacent the avoidance path; and c) exiting the avoidance path substantially adjacent the farthest intersection along the trajectory toward the selectable position. 4. The method of claim 3 wherein the step of analyzing the coordinate data further comprises the steps of:analyzing coordinate data along the avoidance path between the closest intersection and the farthest intersection to identify all sectors in which the coordinates are positioned; identifying any freeways in the sectors identified; ascertaining whether the identified freeways are aligned in a direction of the selectable position; determining whether a distance along the freeway between two sectors is less than a distance along the avoidance path between the same two sectors. 5. The method of claim 3, wherein the step of proceeding from the closest intersection to the farthest intersection further comprises the steps of:proceeding along the avoidance path that is closest to the freeway; determining an access node along the avoidance path that is closest to the freeway; determining a departure node along the avoidance path that is closest to the selectable position; entering the freeway substantially adjacent to the access node; proceeding along the freeway to a position substantially adjacent to the departure node; exiting the freeway at the position substantially adjacent to the departure node; and proceeding along a trajectory toward the selectable point. 6. A method for establishing a contiguous path of movement between a beginning position and a selectable position for a computer-controlled display, said method comprising the steps of:(1) providing coordinates for the beginning position and the selectable position; (2) defining a polygon about each impassable object, where each of said polygons are closed and not intersecting; (3) calculating a direct trajectory between the beginning position and the selectable position; (4) comparing the direct trajectory to the polygon for intersections therebetween and for each polygon determining a first intersection closest to the beginning position and a second intersection closest to the selectable position; and (5) establishing a locus of points intermediate the beginning position and the selectable position by:a) forming a path of points along the direct trajectory until the selectable position or an intersection between the direct trajectory and a polygon is reached; b) forming a path of points along the polygon until another intersection between the direct trajectory and the polygon is reached; and c) returning to forming the path of points in accordance with the first forming step a). 7. The method of claim 6 wherein said step of defining a polygon further comprises the steps of:selecting a plurality of nodes about the polygon; and placing the nodes in an order to denote sides of the polygon. 8. The method of claim 7, wherein said step of defining a polygon further comprises the step of orienting the nodes about the polygons in a particular direction.
9. The method of claim 8, wherein the particular direction is clockwise.
10. The method of claim 6, wherein the step of calculating a direct trajectory between the beginning position and the selectable position comprises calculating a vector between the beginning position and the selectable position.
11. The method of claim 6, wherein said step of comparing the direct trajectory to the polygon for intersections therebetween further comprises the steps of:computing a vector for the direct trajectory; computing vectors between adjacent nodes in the polygon; and comparing the vector for the direct trajectory to the trajectory of each of the vectors between adjacent nodes of the polygons to determine whether any intersections within a domain of the display exists. 12. The method of claim 6, wherein the step of establishing a locus of points intermediate the beginning position and the selectable position, further comprising the steps of:determining the path of points about each polygon; calculating a distance along each path of points about each polygon; and selecting the path of about each polygon that has a shortest distance. 13. The method of claim 6, further comprising the step of optimizing the distance of the path of points between the beginning point and the selectable point by forming new paths of points between two nodes where the distance between the two nodes along the new path of points is less than the distance between the two nodes on the path of points, and the new path of points does not include points within any polygon.
14. The method of claim 6, further comprising the step of optimizing the distance of the path of points between the beginning point and the selectable point by:determining the paths of points about each polygon; calculating the distance from the beginning position to the selectable position along all combinations of paths about each polygon; and selecting the combination of paths about the polygons that has the shortest total distance from the beginning position the selectable position. 15. The method of claim 14, further comprising a second optimizing step which comprises:determining the possible paths about the polygons intersected by the direct trajectory; optimizing the possible paths about the polygons by forming new paths of points between any two nodes where the distance between the two nodes along the new path of points is less than the distance between the two nodes on the path of points, and the new path of points does not include points within any polygon; calculating the distance along the optimized possible paths; and selecting the path with the shortest distance from the optimized possible paths and establishing the locus of points along said shortest path. 16. The method of claim 6, wherein the step of establishing a locus of points intermediate the beginning position and the selectable position, further comprising the steps of:testing for overlap of one polygon with one or more other polygons; eliminating any polygons from intersections with the path of points which are completely overlapped by another polygon; performing the steps (1) through (5) recursively using an exit point from a polygon as the beginning position if the polygon is partially overlapped to generate an optimized recursive path from the exit point of the polygon to the selection position; and combining the optimized recursive path with the locus of points from the beginning position to the exit point. 17. The method of claim 16, wherein the step of testing for overlap comprises comparing an entry and an exit point of a previous polygon with an entry and an exit point of a next polygon to determine whether either of the entry and exit points of the next polygon lie between the entry and exit points of the previous polygon when traversing the direct trajectory from the beginning point to the selectable point.
18. The method of claim 16 wherein the step of performing the steps (1) through (5) recursively is performed by performing the steps (1through (5) with the exit point of the previous polygon as the beginning point and the selectable point the same, if the entry point of the next polygon lies before the exit point of the previous polygon and the exit point of the next polygon lies after the exit point of the previous polygon.
19. A method for establishing a contiguous path of points between a beginning position and a selectable position for a movable object on a computer-controlled display showing at least one impassable object, said method comprising the steps of:providing coordinates for the beginning position and the selectable position; defining a position of at least one impassable object by defining a polygon about one impassable object as a closed polygon that is not self intersecting and not intersecting any other polygon about other impassable objects, and a polygon is defined by selecting a plurality of nodes about the impassable object, and the nodes are placed in an order to denote sides of the polygon. calculating a direct trajectory between the beginning position and the selectable position; comparing the direct trajectory to the position defined for each impassable object; and establishing a locus of points intermediate the beginning position and the selectable position, said locus of points positioned substantially adjacent the direct trajectory where the direct trajectory does not have a same position as the position of each of the impassable objects and positioned about the impassable object where the direct trajectory and the impassable objects have the same position; where the locus of points intermediate the beginning position and the selectable position is established by forming a path of points along the direct trajectory until the selectable position or an intersection between the direct trajectory and a polygon is reached, and by forming a path of points along the polygon until another intersection between the direct trajectory and the polygon is reached, and by returning to forming the path of points in accordance with the first forming step; and optimizing the distance of the path of points between the beginning point and the selectable point by forming new paths of points between any two nodes where the distance between the two nodes along the new path of points is less than the distance between the two nodes on the path of points, and the new path of points does not include points within any polygon. 20. A method for establishing a contiguous path of movement between a beginning position and a selectable position for a computer-controlled display, said method comprising the steps of:providing coordinates for the beginning position and the selectable position; defining an avoidance path of coordinates about each impassable object; calculating a direct trajectory between the beginning position and the selectable position; comparing the direct trajectory to the avoidance paths for intersections therebetween and for each avoidance path determining a closest intersection and a farthest intersection from the beginning position; establishing a locus of points intermediate the beginning position and the selectable position, said locus of points defined by a path traveled by:a) proceeding in a direction of the direct trajectory to a point substantially adjacent the closest intersection; b) proceeding along the avoidance path from the point substantially adjacent the closest intersection to a point substantially adjacent the farthest intersection; c) exiting the avoidance path at the point substantially adjacent the farthest intersection along a trajectory toward the selectable position; d) repeating steps a-c until the selectable point is reached; e) analyzing an exit trajectory from the farthest intersection and the nodes that define the incremental trajectory which intersects the direct trajectory to determine if other impassable objects will be encountered; and f) selecting the exit trajectory that does not intersect with another impassable object. Description
Conventional video game systems commonly rely upon program information and operator controls to form displayable images of a movable person, vehicle, or the like, within a relatively static background field of objects such as trees, roads, rocks, walls, and the like. Such video game systems typically incorporate `joystick` controllers or cursor-control buttons for producing operator control signals that determine the position or direction of movement of the movable object within the background field. In such systems of contemporary design, the movable object as displayed is usually inhibited from moving through an impassable object or area such as a displayed wall, tree or rock, and the system operator is then required to manipulate cursor-control buttons or joystick controller to maneuver the displayed movable object around the displayed impassable objects. In this manner, a system operator maintains control over a movable object as it is continually repositioned and redirected along a desired path among impassable objects within the computer controlled display. If the movable object is maneuvered into an impassable object such as a rock or tree, then the movable object may not be advanced further in a direction through the impassable object, but will have to be controlled or maneuvered by the system operator in other directions away from the impassable object under computer control. Systems of this type are commercially available and commonly include a console unit to which manual controllers are connected, and to which various memory cartridges can be connected that configure the video game system for operation as a labyrinth game, race, sporting event, or the like.
However, in certain computer-controlled game systems, a conventional `mouse`-type controller may be utilized to position a displayed cursor at a selected position in a conventional manner. It also may be that the system operator wants the object he is controlling to keep moving in some general direction without having to maneuver the object around the impassable object that normally prevents the movable object from continuing on the desired direction. (i.e., A direction key is used to designate travel in an easterly direction and there happens to be an impassable object east of the movable object). When such a controller is arranged to designate a destination for a displayed movable object within a displayed field of impassable objects, a direct path, or trajectory, between where a movable object is positioned in the display and where the operator desires the movable object to be next positioned in the display may intercept an impassable object that inhibits further movement of the movable object toward the desired position without additional maneuvering by the system operator. With a mouse-type controller, such maneuvering may involve awkward repositioning of a displayed cursor, via the `mouse`, to overlap the position where the movable object is `stuck` against an impassable object, and thereafter redefine different path segments to maneuver the movable object around the impassable object toward the desired next position. This severely limits the speed with which a computer-controlled game sequence may progress through a sequence of scenes or events, and contributes to operator frustration in having to maintain continuous control over the movable object during even the most trivial repositioning maneuvers associated with a displayed scene or event.
The computational overhead of calculating each new trajectory for a movable object from its present displayed position to its desired destination position is reduced by incorporating a control or trigger profile around each displayed impassable object or area, and initiating independent control of a movable object along an avoidance path only in response to intersection of a movable object with the trigger profile around an impassable object or area. Avoidance paths are provided which surround certain impassable objects or areas to avoid such as trees, holes, ponds and rocks to facilitate controlling the displayed movement of a movable object along the shortest avoidance path around such impassable object or area. In this manner, a movable object may be displayed as exhibiting rudimentary `intelligence` in being able to maneuver independently around an impassable object in the path or trajectory of the movable object to its destination position without requiring the system operator to remain in continuous control of all movements of the movable object around an impassable object or area.
In a second embodiment of the present invention, a displayed field may be segregated into sectors over the area of the display, with avoidance paths associated with each impassable object or area and with `freeway` paths oriented between spaced sectors to serve as preferred trajectories for a movable object to follow in traversing major distances in the displayed field. This preserves the realism of `intelligent` movements exhibited by a movable object in response to major changes in desired position within a displayed field while significantly speeding up progress of the game through insignificant sequences that should not require the operator's continuous attention or control over the movement of the movable object.
FIGS. 4A and 4B are a flow chart of the process for determining whether there is an intersection between the direct trajectory and the avoidance paths;
FIGS. 6A, 6B and 6C are a flow chart of the process for displaying movement of objects along `intelligent` routes;
FIGS. 8, 8A, 8B, 8C and 8D are flow charts of the process for providing intelligent movement of a movable object in accordance with a third embodiment of the present invention;
FIG. 9 is a flow chart of the process in the third embodiment of the present invention for constructing a path between the two points from list of paths about polygons; and
FIGS. 10A and 10B are a flow chart of the process of third embodiment for optimizing a path between two points.
In accordance with the preferred embodiment of the present invention, an avoidance profile, or path 13, including a plurality of points or nodes 15 is located about the rock 9 (and about other impassable objects 11) at a slight spacing therefrom to represent a path or locus of points that designate varying trajectories about the impassable object. Specifically, as illustrated in the list of FIG. 2, the coordinates of each point 15, 16, in the path are listed in a memory look-up table to define the incremental trajectories from point to point around the impassable object 9. Thus, for a displayed movable object (such as a person or vehicle or the like) positioned at a beginning point (point A), an operator may elect to move the object to be displayed at a selectable point (point C). This may be accomplished in conventional manner using a `mouse`-type controller which controls the movement of a display cursor to the point C that can then be designated as the next position for the movable object by `clicking` the `mouse`-type controller on the point. Thereafter, displayable icons suitable for characterizing a displayed person, for example, in a walking or running stride are successively recalled from ROM or RAM and are interposed on the stream of pixel data for the displayed background per frame at different intervals per successive frame in a conventional manner in order to display the movable object as moving along the trajectory or direct path 12 between points A and C.
The displayed movement of a movable object along the avoidance path 13 continues to a position at or near an intersection of the direct trajectory 12 with a point, or with an incremental trajectory between adjacent points 23, 25 along the avoidance path 13. The movable object may then be displayed as leaving the avoidance path 13 at a point 23 which is nearest to the selectable point C to travel along the trajectory of path 27. Alternatively, the movable object may be displayed along a trajectory 29 as leaving the avoidance path 13 at the nearest end point 25 defining an incremental trajectory 25-23 which intersects with the direct trajectory 12. Of course, the movable object may also be displayed as traversing the direct trajectory 12 between point A and the interpolated intercept (or intercept at a point) of the avoidance path 13, along the avoidance path 13 to the interpolated intercept (or intercept at a point) with the direct trajectory 12, and then along the direct trajectory 12 to the target point C. Thus, the movable object is displayed as traversing a path around an impassable object along a line of travel that closely resembles the natural or `intelligent` choices that a live entity which is depicted by the displayed moving object would make.
The preferred embodiment of the present invention, also provides `intelligent` movement of an object that can pass in either direction around an impassable object. As illustrated in FIG. 1, a displayed tree 11 includes an avoidance path 17 completely around the base. Thus, displayed movement of an object from point D to the target point E may intersect the avoidance path 17 that could be traversed in either direction. Such avoidance path 17 is formed as the locus of points that are completely identified in a look-up table of coordinate data points similar to the coordinate data points illustrated in FIG. 2. Thus, the distances between sets of adjacent points can be accumulated between intercept points 35, 37 in each direction around a closed set of data points, and the shortest of the accumulated distances determines the direction of movement around the impassable object.
Referring now to FIG. 3, there is shown a pictorial representation of raster-type display of a background scene (for example, of a waterfront shoreline) including a meandering impassable object or boundary 41. The impassable object or boundary 41 includes an avoidance path 43 along, and in close proximity with, the boundary 41. Thus, displayed movement of a movable object from point F to point G would normally occur along the direct trajectory 45, to the intercept 47 with the avoidance path 43, and along such avoidance path 43 to the intercept with the direct trajectory 45, and then along the direct trajectory 45, to the target point G in the manner previously described. This would result in unintelligent meandering movement along the boundary 41 in place of expected, `intelligent` movement in more direct line toward the target point G.
In accordance with a second embodiment of the present invention, the display area is segmented into several sectors 51, 53, . . . 65 (for data analysis, but not for display of any sector boundary lines). In selected sectors of the display area, there are provided one or more auxiliary avoidance or `freeway` path(s) 67 which traverse the major spacings between remote sectors of the display. Therefore, the coordinate data associated with the display position of a movable object is analyzed to determine whether or not the position is in a sector that includes a freeway that traverses the display in a direction generally toward the target point G.
Thus, in the illustration of FIG. 3, a movable object displayed at point F that is to be moved to point G would be moved in the manner previously described along trajectory 45 to intersection 47 and then along the avoidance path 43 through various sectors of the displays. However, the coordinate data at points along the avoidance path 43 is analyzed for sector identification, and whether that sector includes a freeway 67 generally aligned in the proper direction toward the target point G. Thus, the coordinate data along path 43 and residing in sectors 51 and 57 would not initiate transition to the freeway 67. For example, if movement was from point F toward point H, analysis of the coordinate data would indicate no benefit to be derived from traversing along the freeway 67 that resides within sector 59. However, coordinate data along avoidance path 43 that resides in sector 59 can be analyzed for `intelligent` use of an available freeway 67. For movement toward point G, the analysis of the coordinate data for points along the meandering avoidance path 43 would indicate greater distance therealong than along freeway 67 to the sector 65 in which the freeway 67 and the point G reside. Therefore, a movable object is displayed as traversing direct trajectory 45 from point F to intercept 47, then along avoidance path 43 into sector 59 at which a transition occurs to freeway 67 along the shortest path 69 between the two paths 43, 67 within the sector, then along the freeway 67 into sector 65 at which a transition occurs along the shortest path 71 between the two paths 43, 67, to the intercept 49 and then along trajectory 45 to point G. Of course, the freeway(s) 67 need not be straight, but only substantially shorter between remote sectors than a traversing avoidance path between such remote sectors. In this manner, the movable object is displayed as having traveled along a route of natural or intelligent selection between points F and G without further control or intervention by an operator.
A flow chart 101 for the process of analyzing whether a freeway path is available, and moving the object along the established path of points is illustrated in FIG. 5. Once the object has been placed on an avoidance path 43, a determination of whether a freeway path 67 exists in the direction of the object's selectable position (Point 6) is made. A first step 103 is analyzing whether the object is moving from a freeway area. In a preferred embodiment, this step 103 is accomplished by determining whether any freeway path exists in the sector in which the object is positioned. For example, this determination may be made at each node along the avoidance path upon which the object is traversing. If there is no freeway path in the sector, the process is complete and the object continues to follow the avoidance path. If there is a freeway path in the sector, a next step 105 determines whether the object is moving to a freeway area. Preferably, this step evaluates whether either the selectable position or the intersection point on the avoidance path is positioned in a sector that includes a freeway path. Again, if there is no freeway path in the sector for the destination, the process is complete. Otherwise, a next step 109 in the process determines whether a freeway connects the sector in which the object is positioned and the sector in which the destination of the object lies. If no freeway connects the object's present position and the object's destination, then the process is complete, no freeway is utilized, and the object is moved with normal pathing. If there is a freeway path connecting the current sector of the object, the object is moved towards its destination. The process continues with a step 111 of finding an access node along the freeway path that is closest to the position of the object. Next, a step 113 of finding the node along the freeway path closest to the objects destination or selectable position is executed. The object is then moved from its present position to the access node in step 115. The freeway path is followed to the departure node in step 117. Finally, the object is moved from the departure node to the destination in step 119. While the process has been described as moving the object along a path from node to node, it should be understood that the movement involves establishing a locus of points between the nodes for each movement of the object therebetween.
If no freeway path is available then the object is moved from point A to point B using normal pathing. Referring now to FIG. 6, there is shown a flow chart 121 of the normal pathing process by which coordinate data for the points on the display and along avoidance paths are analyzed to produce displays of `intelligent` movement around impassable objects or areas without intervention of the operator. A first step 123 in analyzing the coordinate data to produce `intelligent` movement along the display is to determine whether there are any intersections between the object's direct trajectory and any avoidance paths 13, 17 and 43 on the display. The existence of any intersections can be accomplished as described above with reference to FIG. 4. If no intersections are found then the direct trajectory may be followed to the selectable position and the analysis is complete. However, if intersections are found to exist, then a step 125 of finding the avoidance path that is closest to the objected is performed. Additionally, in step 127 the intersection closest to the position of the object is located.
Next, the process determines whether the path found to be closest is a "sticky path" A sticky path is one that holds the object on the path until the object reaches the node of the path that is closest to the object's destination point and then releases the object to continue to its destination. If the path is "sticky," then the node closest to the object's destination is located in a next step 130. If, on the other hand, the path is not "sticky" then the next step 131 locates the intersection closest to the objects destination.
Once the route has been selected, the object is moved to the entry point (step 137). In a following decision step 139, the process checks whether the object reached the entry point. If the entry point was reached, then the process continues to step 151 where the object is moved to the next node along the path. However, if the entry point was not reached then the process attempts to get on the avoidance path at a point near the entry point in series of steps 141, 143, 145 and 147. In these steps, the process attempts to "backtrack" along a trajectory in a direction 180� from the object's previous trajectory. If a path is found on the backtrack trajectory, then the closest of the intersection and the node on the path will be accessed. This allows an object that is blocked from moving along the trajectory at its current position to move backward away from the blocking area onto a path around it. The process begins by searching for a backtrack point or intersection on the path behind the object in step 141. If the backtrack point was not found the process is complete and unsuccessful. If a backtrack point was found, the object is moved to the backtrack point in step 145. The process then tests whether the backtrack point was reached (step 147). If the backtrack point cannot be reached, the process is complete and unsuccessful as if no backtrack point had been found. If the backtrack point is found, the process continues using the backtrack point in place of the entry point and proceeds to step 151 where the object is moved to the next path node.
Referring now to FIGS. 7-10, the third embodiment of the present invention will be discussed. In a third embodiment, the present invention advantageously provides an alternate method for `intelligent` movement about any impassable objects. In FIG. 7, a raster type display shows a background including impassable objects such as a rock 200, a tree 202 and a mountain 204. As with the display of FIG. 1, the display area is identified by coordinates of points everywhere over the area of the display from (0,0) in the upper left corner to (200,200) in the lower right corner. The movement of an movable object, similar to the object described above with reference to the first embodiment, from a beginning position to a selectable position may be specified by an operator using either a mouse as described above, direction keys or a joystick. The third embodiment of the present invention advantageously provides intelligent movement of the object from beginning position to the selectable position with a method comprising the steps of: defining a polygon about each impassable object; calculating a direct trajectory between the beginning position and the selectable position; determining whether the direct trajectory intersects any of the impassable objects on the display; sorting the intersections according to their closeness to the beginning position; constructing a path from the beginning position, around the impassable objects intersected, to the selectable position; and optimizing the path. In addition, if more than one impassable object is intersected by the direct trajectory, further optimization is performed by selecting the path with the shortest distance from the possible paths about the impassable objects intersected.
In accordance with the third embodiment of present invention, a polygon 206, 208, 210 is defined about each of the impassable objects 200, 202, 204, respectively. Each polygon is defined by a plurality of nodes or points N1-N20. The nodes N1-N6 define the polygon 206 about the rock 200. Similarly, the nodes N7-N12 and nodes N13-N20 respectively define the polygons 208, 210 about the other impassable objects 202, 204. The polygons 206, 208, 210 are preferably closed, not self-intersecting (e.g. Jordan polygons) and do not intersect any other polygons about impassable objects. The use of nodes is advantageous because the polygons are automatically defined simply by specifying nodes that define the boundary of the impassable object. The nodes allow the polygons to be to conceptualized by programers defining polygons. It should be understood that while the polygons 206, 208 and 210 are illustrated in FIG. 7 for ease of understanding, the polygons 206, 208, 210 are provided for data analysis only and are not typically shown on the display. In particular, the nodes N1-N20 are preferably stored in memory and as lists of points, with each polygon specified by a pointer to a first node in a chain of lists.
The method of the present invention next establishes paths around the intersected polygons 206, 208, 210 and selects the path with the shortest distance. For movement of an object from X to Y, one path around the polygon 210 would be from Il to I2 through nodes N14, N15, N16, N17, N18, and N19. The other path around the polygon 210 would be through nodes N13 and N20. The distance of the path is determined by summing the distances between the adjacent nodes in the path from Il to I2. The path having the shortest distance is then selected for movement of the object from the beginning position to the selectable position. Where the trajectory between the beginning position and the selectable position intersects more than one polygon as with the direct trajectory 214, the shortest path is determined about each polygon individually. For the direct trajectory 214 between X and Z, a shortest path for polygon 206 between I3 and I4 is calculated separately from the shortest path about polygon 208 between I5 and I6. For example, the shortest path for polygon 206 is the path through nodes N5 and N6 and the shortest path about the polygon 208 is through nodes N7, N8, N9.
The distance between two particular nodes is preferably definable by the user. This is particularly advantageous where the polygon borders on the edge of the display such as with polygon 210. Since all impassable objects are defined by closed polygons regardless of their position, impassable objects which lie on the edge of the display will be defined by a polygon that has one side along the edge of the display. Even though the polygon has a side along the edge of the display, this side is not a clear path for movement about the impassable object and movement of the object along the side is not permitted. Thus, defining the distance between two nodes to be infinity or the maximum possible value will insure that the object always moves along the path that shown on the display rather than the path along the edge of the display. For example, the distance between nodes N13 and N20 is preferably defined to be the maximum possible value to insure that any trajectory that intersects polygon 210 takes a path about the mountains 204 on the portion of the screen displayed rather than along the edge of the display where the object is not permitted to travel and where the object would not be fully viewable. Therefore, in determining which is the shortest path about the polygon 210 between the intersections Il and I2, the path through nodes N14, N15, N16, N17, N18 and N19 would be selected.
The third embodiment preferably determines whether the direct trajectory intersects with any polygons as well as the shortest path according the process shown in a flowchart 230 of FIG. 8B. In step 232, the method tests whether the beginning position and the selectable position are the same. If they are the same, no comparisons are necessary and the method continues to the next series of steps. If the beginning position and the selectable position are not the same, the process determines if the end of the polygon list has been reached, in step 234. If the end of the list has been reach, either no polygons are in the display field, or all the polygons in the display field have already been compared to the direct trajectory. Otherwise, the direct trajectory is compared to the polygon noted in the list of polygons in step 136. If there is no intersection, step 238 gets the next polygon in the list and loops through the comparison step 236 so that the direct trajectory is compared to each polygon in the list. However, if the direct trajectory intersects the polygon, the intersection closest to the beginning point, and the intersection closest to the selectable point are determined in step 240. The shortest path between these two intersection points is then calculated in step 242, and the shortest path is stored in a PATHLIST in step 244. The paths stored in the PATHLIST are stored according to the distance from the beginning position to the closest intersection. Once the PATHLIST of shortest paths about polygons has been formed and the intersection nearest to the beginning position and intersection nearest the selectable position for each polygon is saved, the intersection points are analyzed to determine if any of the polygons entry and exit the intersections overlap any of the other polygons entry and exit points. By "overlap" it is meant the when viewed along the trajectory from the beginning position, no intersection saved for a polygon lies between the intersections saved for any other polygon. In step 246, a variable (pathnumber) which indicates the number of paths in PATHLIST, or the number of polygons intersected is incremented and the process continues by getting the next polygon in the list in step 238 and returning to step 234.
If no overlap was found, a path between the beginning position and the selectable position is created by linking the shortest paths, the beginning position and the selectable position together. For example, a path from X to Y around the intersected polygon 210 would include nodes X, Il, N14, N15, N16, N17, N18, N19, I2 and Y. A path from X to Z around the intersected polygons 206, 208 would include nodes X, I3, N6, N5, I4, I5, N7, N8, N9, I6 and Z. It should be understood that since the trajectory 214 intersects more than a single polygon, the path is created by forming a path along nodes starting with the beginning point, X, then proceeding to the closest intersection to X, namely I3. The intersection I3 and the shortest path from I3 to I4 about the polygon 206 are then linked to X. The next closest intersection I5 to the beginning point is then retrieved and linked to intersection I4. The path associated with intersection I5, the shortest path about the polygon 208 through nodes N7, N8, N9 and I6, is also appended to the path. It should be understood that this process could continue for any number of polygons that are intersected by a direct trajectory. After the intersection closest to the selectable position is linked to the path, the path is competed with by adding the node for the selectable position such as Z.
The process of constructing the path is a step 250 in a flow chart 252 of FIG. 8C for the avoidance pathing process, and will be detailed more specifically with reference to a flowchart 254 of FIG. 9. The process begins forming the path with the beginning point in step 256. In step 258, the process tests whether the PATHLIST is empty which indicates that no polygons are intersected, or the paths about the intersected polygons have already been added to the path. If the PATHLIST is not empty, then the first path in the list is retrieved in step 260. If there is no overlap between this polygon's entry and the previous polygon's exit then the retrieved path is added to the path by inserting the nodes representing the closest intersection to the beginning point, the shortest path and the closest intersection to the selectable point, in that order. Once these nodes have been inserted, the first path in the PATHLIST is deleted in step 264 and the process returns to step 258. If there was overlap detected during the analysis of the entry and exit intersection points of the polygons, then one of two alternatives is taken at each overlap. If the entry and exit point of a polygon lies between the entry and exit point of another then this polygon is not use in creating the a path from the beginning position to the selectable position. If the entry point of some polygon (polygon B) is between the entry and exit point of another polygon (polygon A) and the exit point of polygon B does not lie between the entry and exit point of polygon A then the path created will continue to exit point of polygon A and at that point the path is saved and a new path is generated by the method described herein with the beginning point being the exit point of polygon A and the same selectable point. (this is a recursion of the method generating the unoptimized path in that the method is calling itself. The two paths are then combined into one path). Thus, the process will cycle through all the paths in the PATHLIST and add them to the path being constructed between the beginning and selectable positions until PATHLIST is empty. Then the selectable position added and the entire path is returned in steps 266 and 268. However, if overlap is detected the program will call itself to generate the path starting at the exit point of the previous polygon to the selectable point. Then the path returned is appended to the current path (after removing the duplicate point generated , the exit from the previous polygon) and this path is returned.
As best shown in FIG. 7, once a path that avoids impassable objects between X and Y has been established, the path it is optimized. In other words, any nodes on the original path that can be eliminated are removed to create an optimized path between the beginning position and the selectable position. The optimized path does not intersect with any of the polygons and has a shorter distance than the original path. For example the path between X and Y is initially established along the points X, Il, N14, N15, N16, N17, N18, N19, I2, and Y. After one iteration of the optimization process, the path between X and Y is reduced to the path comprising the nodes X, Il, N14, N15, N16, N17, N18, N19, I2, and Y. The first iteration of optimization removes nodes Il, and N14, by replacing them with a direct path 270 between X and N15. Similarly, a second iteration of optimization eliminates nodes N16 and N17 by providing a direct path 272 between N15 and N18. The path is fully optimized after a third iteration of the optimization process which eliminates I2 from the path.
The third embodiment of the present invention also provides additional optimization where the path between the beginning position and the selectable position intersects more than one polygon. In such situations, as with the path between X and Z, the additional optimization calculates the optimal distance for all possible combinations of routes about the intersected polygons 206, 208 and selects the shortest. For example, the pathing would provide an optimized path from X to Z using the shortest distances about each polygon 206, 208. The optimized path is an optimization of the path through the nodes I3, N6, N5, I4, I5, N7, N8, N9, and I6. However, the additional optimization calculates the distance along three other paths between X and Z, namely: a path in opposite directions about the both polygons 206, 208 through nodes I3, N1, N2, N3, N4, I4, I5, N12, N11, N10, and I6; a path opposite in direction only about the first polygon 206 through nodes I3, N1, N2, N3, N4, I4, I5, N7, N8, N9, and I6; and a path opposite in direction only about the second polygon 208 through the nodes I3, N6, N5, I4, I5, N12, N11, N10, and I6. Therefore, such additional optimization would return the shortest path that avoids the polygons 206 and 208, namely, the path defined by the nodes X, N6, N11, N10 and Z. The fully optimized result is a path along the shortest path about the first polygon 206 and longer path about the second polygon 208.
The process for providing additional optimization is illustrated in the flowchart 252 shown in FIGS. 8C and 8D. First, the process compares the variable pathnumber to two, in step 320. If the pathnumber is less than two, one or fewer polygons are intersected by the trajectory between the beginning and selectable positions. Thus, normal optimization as discussed above with reference to FIG. 10, is performed in step 322 and will fully optimize the path. If the pathnumber is two or greater then the path OP between the beginning and selectable positions is constructed in step 250. This construction step 250 is preferably in accordance with the method described in FIG. 9. In step 324, the path OP is optimized using the same method as in step 320. The optimized path is also stored as path BP. In step 326, the length of the path BP is calculated and a variable BL is set equal to the length of the path BP. Next, in step 328, all the possible paths about each polygon and the possible combinations of those paths are determined. The initial direction is set to the direction about which the path BP traverses the polygons. Those skilled in the art will understand that the permutation of possible paths about n polygons will be 2n. Thus, for a L- path that intersects two polygons there are 22 or four different paths from the beginning position to the selectable position and about the polygons. The method of the present invention advantageously calculates each of the 2n path and selects the path with the shortest optimized distance. In step 328, a new path NP is created by changing the direction about which one of the intersected polygons is traversed. A determination of whether all possible paths about the intersected polygons is made in step 332. If all the possible directions have been examined, then the process returns the path BP in step 334 and the additional optimization is complete. However, if not all the directions have been examined the path NP is optimized in step 336 similar to the optimization in steps 322 and 324. The steps 338, 340, 342, and 344 define a loop that effectively optimizes all the possible paths about the intersected polygons and saves the shortest path in the path BP. In particular, step 338 sets the path ONP equal to the optimized path of NP. In step 340, the length of the path ONP is calculated. In step 342, the length of ONP is compared to the shortest length found, BL. If the length is less than BL, BL is set to be the length of ONP and the path BP is set to be ONP and the process loops to step 330. Finally, it should be noted that in the third embodiment the entire path from the beginning position to the selectable position is determined before any movement of the object along the path. Thus, the animation provided by movement in the third embodiment is very smooth and uniform because delays due to processor speed limitation and calculation the path during movement are eliminated. Therefore, the preferred embodiments provide intelligent movement from the beginning position to the selectable position in an automatic fashion.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4053740 *22 Dec 197511 Oct 1977Lawrence David RosenthalVideo game systemUS4089524 *18 Jan 197716 May 1978Gremlin Industries, Inc.Digitally controlled electronic gameUS4357014 *5 May 19802 Nov 1982Sanders Associates, Inc.Interactive game and control thereforUS4862373 *13 May 198729 Aug 1989Texas Instruments IncorporatedMethod for providing a collision free path in a three-dimensional spaceUS4905147 *15 Oct 198627 Feb 1990Logg George ECollision detection system for video systemUS4905168 *15 Oct 198627 Feb 1990Atari Games CorporationObject processing for video system using slips and linked listUS5047916 *24 Mar 198910 Sep 1991Kabushiki Kaisha ToshibaMethod and apparatus of free space enumeration for collision avoidanceUS5058024 *23 Jan 198915 Oct 1991International Business Machines CorporationConflict detection and resolution between moving objects* Cited by examinerNon-Patent CitationsReference1"Creating Arcade Games on the Commodore 64," 1984, Compute! Publications, Inc., Chapter 9: Collisions, p. 244, line 10, One of the ABC Publishing Companies, Greensboro, N.C., U.S.A.2 *Creating Arcade Games on the Commodore 64, 1984, Compute Publications, Inc., Chapter 9: Collisions, p. 244, line 10, One of the ABC Publishing Companies, Greensboro, N.C., U.S.A.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5515489 *17 Feb 19957 May 1996Apple Computer, Inc.Collision detector utilizing collision contoursUS5577185 *10 Nov 199419 Nov 1996Dynamix, Inc.Computerized puzzle gaming method and apparatusUS5596695 *13 Jul 199221 Jan 1997Matsushita Electric Industrial Co., Ltd.Interactive multi-media event-driven inheritable object oriented programming apparatus and methodUS5601487 *22 May 199511 Feb 1997Casio Computer Co., Ltd.Electronic game devices and methodsUS5621431 *29 Apr 199415 Apr 1997Atari Games CorporationAnimation system having variable video display rateUS5729458 *29 Dec 199517 Mar 1998Etak, Inc.Cost zonesUS5736991 *5 Apr 19967 Apr 1998Fujitsu LimitedAnimation editing apparatusUS5777628 *29 May 19967 Jul 1998Hewlett-Packard CompanyMethod and apparatus for detecting cache collisions in a two dimensional memoryUS5828369 *15 Dec 199527 Oct 1998Comprehend Technology Inc.Method and system for displaying an animation sequence for in a frameless animation window on a computer displayUS5892520 *26 Jun 19926 Apr 1999International Business Machines CorporationPicture query system using abstract exemplary motions of a pointing deviceUS5983190 *19 May 19979 Nov 1999Microsoft CorporationClient server animation system for managing interactive user interface charactersUS5999185 *30 Mar 19937 Dec 1999Kabushiki Kaisha ToshibaVirtual reality control using image, model and control data to manipulate interactionsUS6026384 *21 Oct 199715 Feb 2000Etak, Inc.Cost zonesUS6084588 *8 Apr 19974 Jul 2000Discreet Logic, Inc.Interaction between moving objects and matte derived from image framesUS6121981 *19 May 199719 Sep 2000Microsoft CorporationMethod and system for generating arbitrary-shaped animation in the user interface of a computerUS618135113 Apr 199830 Jan 2001Microsoft CorporationSynchronizing the moveable mouths of animated characters with recorded speechUS632999414 Mar 199711 Dec 2001Zapa Digital Arts Ltd.Programmable computer graphic objectsUS633186123 Feb 199918 Dec 2001Gizmoz Ltd.Programmable computer graphic objectsUS636982126 Feb 19989 Apr 2002Microsoft CorporationMethod and system for synchronizing scripted animationsUS6426752 *3 May 199730 Jul 2002Kabushiki Kaisha Sega EnterprisesGame device, method of processing and recording medium for the sameUS6437785 *30 Apr 199920 Aug 2002Intel CorporationMethod of conveying a relationship between objects in a sceneUS6833849 *20 Jul 200021 Dec 2004International Business Machines CorporationVideo contents access method that uses trajectories of objects and apparatus thereforUS7525546 *8 Feb 200828 Apr 2009Microsoft CorporationMixture model for motion lines in a virtual reality environmentUS7588497 *12 May 200615 Sep 2009Kabushiki Kaisha Square EnixMethod, an apparatus and a computer program product for generating an imageUS77058586 Oct 200427 Apr 2010Apple Inc.Techniques for displaying digital images on a displayUS774636029 Mar 200729 Jun 2010Apple Inc.Viewing digital images on a display using a virtual loupeUS7782324 *23 Nov 200524 Aug 2010Dreamworks Animation LlcNon-hierarchical unchained kinematic rigging technique and system for animationUS78045086 Oct 200428 Sep 2010Apple Inc.Viewing digital images on a display using a virtual loupeUS783942015 Jun 200523 Nov 2010Apple Inc.Auto stacking of time related imagesUS7889212 *7 Sep 200615 Feb 2011Apple Inc.Magnifying visual information using a center-based loupeUS792898519 Feb 201019 Apr 2011Dreamworks Animation LlcRigging for an animated character moving along a pathUS79652952 Apr 200921 Jun 2011Microsoft CorporationMixture model for motion lines in a virtual reality environmentUS8187094 *22 Sep 200529 May 2012Sega CorporationGame programUS819409924 Feb 20105 Jun 2012Apple Inc.Techniques for displaying digital images on a displayUS845647528 Dec 20054 Jun 2013Microsoft CorporationMotion line switching in a virtual environmentUS84564886 Oct 20044 Jun 2013Apple Inc.Displaying digital images using groups, stacks, and version setsUS848796017 Nov 201016 Jul 2013Apple Inc.Auto stacking of related imagesUS87759535 Dec 20078 Jul 2014Apple Inc.Collage display of image projectsUS20120324385 *30 Sep 201120 Dec 2012Nintendo Co., Ltd.Methods and/or systems for designing virtual environmentsWO1997024705A1 *20 Dec 199610 Jul 1997Etak IncCost zones* Cited by examinerClassifications U.S. Classification345/474, 345/443, 345/442, 345/958International ClassificationG06F3/033, G06T13/00, G06F17/50, G06F3/048Cooperative ClassificationY10S345/958, A63F2300/66, G06F3/04845, G06F17/509European ClassificationG06F3/0484M, G06F17/50RLegal EventsDateCodeEventDescription11 Aug 2005FPAYFee paymentYear of fee payment: 1212 Jan 2005ASAssignmentOwner name: SIERRA ENTERTAINMENT, INC., WASHINGTONFree format text: CHANGE OF NAME;ASSIGNOR:SIERRA ON-LINE, INC.;REEL/FRAME:015552/0771Effective date: 20011214Owner name: SIERRA ENTERTAINMENT, INC. 14205 SE 36TH STREET SUFree format text: CHANGE OF NAME;ASSIGNOR:SIERRA ON-LINE, INC. /AR;REEL/FRAME:015552/07711 Aug 2001FPAYFee paymentYear of fee payment: 815 Aug 1997FPAYFee paymentYear of fee payment: 41 Feb 1991ASAssignmentOwner name: SIERRA ON-LINE, INC., 40033 SIERRA WAY, OAKHURST,Free format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:WILLIAMS, KENNETH A.;IDEN, DAVID C.;SCOTT, LARRY L.;REEL/FRAME:005581/0805Effective date: 19901015RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google