Methods for intelligent movement of objects on computer displays

• US 5,425,139 A
• Filed: 11/12/1993
• Issued: 06/13/1995
• 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: Iden, David C., Williams, Kenneth A., Scott, Larry L.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/152,309
• Time in Patent Office: 578 Days
• Field of Search: 395/152, 395/142, 395/143
• 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

A method and system for controlling the movement of an object between points on a display along natural or "intelligent" paths around obstacles includes 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 moving a movable object on a computer-controlled display showing at least one continually stationary impassable object, said path, positions and objects defined by Cartesian coordinates, 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 having a perimeter of line segments;

calculating a direct trajectory between the beginning position and the selectable position;

comparing the direct trajectory to the position defined for each impassable object;

establishing a locus of points intermediate the beginning position and the selectable position, said locus of points positioned between the beginning position and a line segment of an impassable object 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 and,

moving the movable object from the beginning position along the locus of points to the selectable position after the locus of points is established.

2. The method of claim 1, wherein said step of defining a position of at least one impassable object further comprises the steps of:

selecting a plurality of nodes about the impassable object, each node having coordinates; and

calculating an incremental trajectory between the coordinates of each node, each incremental trajectory defining one of the line segments of the perimeter of the impassable object.

3. The method of claim 2, wherein said step of comparing the direct trajectory to the position of the impassable objects comprises determining whether the direct trajectory intersects an avoidance path for each impassable object.

4. The method of claim 3, wherein said step of establishing a locus of points intermediate the beginning position and the selectable position further comprises the steps of:

forming a path of points along the direct trajectory until the selectable position or an intersection between the direct trajectory and an avoidance path is reached;

forming the path of points along the avoidance path until another intersection between the direct trajectory and the avoidance path is reached; and

returning to forming the path of points in accordance with the first forming step.

5. The method of claim 4, further comprising the steps of:

determining the paths of points about the impassable object;

analyzing whether there is more than one path of points about the impassable object and calculating the distance along each path of points; and

selecting the path of points about the impassable object that has a shorter distance.

6. The method of claim 1, wherein said step of defining a position of at least one impassable object comprises defining a polygon having line segments about each impassable object, where each of said polygons are continuously stationary, closed, and not self-intersecting any other polygon about other impassable objects.

7. The method of claim 6, wherein the step of comparing the direct trajectory to the position defined for each impassable object further comprises determining whether the direct trajectory intersects the polygon for each impassable object.

8. A method for establishing a contiguous path of movement for moving a movable object between a beginning position and a selectable position on a computer-controlled display showing at least one continually stationary impassable object, said path, positions and objects defined by Cartesian coordinates, said method comprising the steps of:

providing coordinates for the beginning position and the selectable position;

defining an avoidance path of a series of line segments having 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; and

establishing a locus of points intermediate the beginning position and the selectable position, said locus of points including at least;

a) a first set of points including the beginning point and points forming a trajectory to an attachment point along the line segment containing the closest intersection;

b) a second set of points including the avoidance path from the attachment point to a detachment point along the line segment containing the farthest intersection;

c) a third set of 5 points including the detachment point and points forming a trajectory toward the selectable position; and

moving the movable object from the beginning position along the locus of points to the selectable position after the locus of points is established.

9. The method of claim 8, wherein the attachment point is the closest intersection.

10. The method of claim 8, wherein the attachment point is the node of the avoidance path that is closest to the beginning position and is an endpoint of the incremental trajectory containing the closest intersection.

11. The method of claim 8, wherein the attachment point is the node of the avoidance path that is closest to the selectable position and is an endpoint of the incremental trajectory containing the farthest intersection.

12. The method of claim 8, wherein the detachment point is the farthest intersection.

13. The method of claim 8, wherein the detachment point is the node closest to the selectable position.

14. The method of claim 8, wherein the detachment point is the first node that is an endpoint of an incremental trajectory that intersects with the direct trajectory and is between the selectable position and the first set of points.

15. The method of claim 8, wherein the step of proceeding along the avoidance path further comprises the steps of:

determining whether the avoidance path is closed;

calculating the distance from the closest intersection to the farthest intersection along each path of the avoidance path; and

if the avoidance path if closed selecting the path from the closest intersection to the farthest intersection having a shortest distance.

16. A method for establishing a contiguous path of movement between a beginning position and a selectable position for moving a movable object on a computer-controlled display showing at least one continually stationary impassable object, said path, positions and objects defined by Cartesian coordinates, 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 polygon is closed, not self-intersecting and not intersecting any other polygon;

3) comparing a direct trajectory between the beginning position and the selectable position to each 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;

4) establishing a locus of points intermediate the beginning position and the selectable position by;

a) forming a first path of points from the beginning position along the direct trajectory until the selectable position or an intersection between the direct trajectory and a current polygon is reached;

b) forming a second path of points along the current polygon until another intersection between the direct trajectory and the current polygon is reached;

c) connecting the first and second paths of points to the beginning position;

d) testing for overlap of the current polygon with one or more other polygons by comparing an entry and an exit point of the current polygon with a last exit point of an other polygon to determine whether the last exit point of an other polygon lies between the entry and exit points of the current polygon when traversing the direct trajectory from the beginning point to the selectable point;

e) excluding any polygon from the path of points if the last exit point of the polygon lies at or before the exit point of the current polygon; and

f) performing the steps (1) through (4) recursively using an exit point from the current polygon as the beginning position to produce a recursive path around all polygons and;

g) moving the object from the beginning position to the selectable position along the locus of points after the locus of points is established.

17. The method of claim 16 wherein the step of forming a path of points along the current polygon until another intersection between the direct trajectory and the current polygon is reached further comprises the step of selecting the next intersection of the direct trajectory and the current polygon.

18. The method of claim 16 wherein the step of forming a path of points along the current polygon until another intersection between the direct trajectory and the current polygon is reached further comprises the step of selecting the last intersection of the direct trajectory and the current polygon.