System and methods for intelligent movement on computer displays

• US 5,287,446 A
• Filed: 10/15/1990
• Issued: 02/15/1994
• Est. Priority Date: 10/15/1990
• Status: Expired due to Term

• Current Assignee: Sierra Entertainment, Inc. (Vivendi SE)
• Original Assignee: Sierra On-Line, Incorporated (Vivendi SE)
• Inventors: Williams, Kenneth A., Scott, Larry L., Iden, David C.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/598,174
• Time in Patent Office: 1,219 Days
• Field of Search: 395/88, 395/90, 395/141, 395/142, 395/143, 395/152, 364/461, 364/457, 273/85 G, 273/DIG. 28
• US Class Current: 345/474
• CPC Class Codes: A63F 2300/66 for rendering three dimensional images
• CPC Class Codes: G06F 3/04845 for image manipulation, e.g. dragging, rotation, expansion or change of colour
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: Y10S 345/958 Collision avoidance

Abstract

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.

Claims

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.