Procedural navigation graphs for identifying a route for a virtual object

Techniques to automatically generate a navigation graph for a given environment and agent are disclosed. The environment may include an arbitrary number of polygonal obstacles arbitrarily arranged, concave or convex, static or dynamic. The disclosed operation extrudes (in a specified manner) the vertex of each obstacle. The extruded vertices comprise the navigation graph's nodes. Each object's extruded vertices may be joined to form a corresponding extruded object. Paths may then be identified by attempting to connect every extruded vertex with every other extruded vertex. Those paths intersecting any of the extruded objects are rejected as possible paths. In some embodiments, paths that are oriented in approximately the same direction having approximately the same length may be removed as being redundant.

BACKGROUND

One challenge in the design of computer games is agent movement—the motion of an entity or object through its environment. Pathfinding strategies have the task of finding a path from any coordinate in a game world to any other (possible) coordinate under a given set of constraints. Pathfinding systems take as input a starting point, a destination point, knowledge of its environment (e.g., where obstacles are located), and information regarding the agent if relevant; they then find a series of points that constitute one or more paths the agent can follow to navigate from its starting point to its destination point.

A game's world geometry is often stored in a structure referred to as a “map” and usually contains all of the polygons that make up the game's environment. To reduce the amount of computation required, a game's map is often simplified. The pathfinder uses these simplified representations to determine a path from start to end. The most common forms of simplified representations are navigation meshes and waypoints. A navigation mesh is a set of convex polygons that describe the walkable surface of a three-dimensional (3D) environment. Waypoints are a collection of nodes with links between them. Waypoints are useful for creating efficient obstacle free paths through static maps but are generally unable to deal with dynamic worlds.

SUMMARY

In one embodiment the disclosed concepts provide a method to automatically generate a navigation graph. The method includes receiving a scene or environment having two or more polygonal obstacles and information concerning an object that is designated to move through the scene or environment. Next, extruded vertices are generated for each vertex of each polygonal obstacle by: extending, for each edge adjacent to a vertex, a rectangle for a distance based on the object's characteristics, wherein the rectangle's two sides extending from the edge are perpendicular to the edge, a third side of the rectangle is parallel and coincident with the edge and a fourth side is parallel to the edge; identifying, when the extruded rectangles of adjacent sides of the vertex intersect, a top-most intersection point as the extruded vertex; and identifying, when the extruded rectangles of adjacent sides of the vertex do not intersect, that point at which two lines intersect, wherein a first of the two lines is a line parallel and coincident to the fourth side of the extruded rectangle on one of the vertices two adjacent edges and the second of the two lines is a line parallel and coincident to the fourth side of the extruded rectangle on the other one of the vertices two adjacent edges. Each of the extruded vertices of each polygon may be identified as a node in the navigation graph. Next, each extruded vertex of each polygon may be connected to the polygon's adjacent vertices to form or create an extruded object or boundary. Possible paths may be generated by connecting each extruded vertex with each other extruded vertex by straight lines. Possible paths that intersect an extruded boundary may be rejected. The remaining paths comprising the edges of the navigation graph. In another embodiment, redundant edges may be removed. In yet another embodiment, weights or any desired function may be assigned to the navigation graph's edges or paths. In still another embodiment, program code to implement the disclosed techniques may be prepared (in any language) and stored in any media that is readable and executable by a computer system.

DETAILED DESCRIPTION

This disclosure pertains to systems, methods, and computer readable media to improve the operation of a graphics system. Techniques disclosed herein may be used to automatically generate a navigation graph for a given environment and agent. The environment may include an arbitrary number of polygonal obstacles arbitrarily arranged, concave or convex, static or dynamic. The disclosed operation extrudes (in a specified manner) the vertex of each obstacle. The extruded vertices comprise the navigation graph's nodes. Each object's extruded vertices may be joined to form a corresponding extruded object. Paths may then be identified by attempting to connect every extruded vertex with every other extruded vertex. Those paths intersecting any of the extruded objects are rejected as possible paths. In some embodiments, paths that are oriented in approximately the same direction having approximately the same length may be removed as being redundant.

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed concepts. As part of this description, some of this disclosure's drawings represent structures and devices in block diagram form in order to avoid obscuring the novel aspects of the disclosed concepts. In the interest of clarity, not all features of an actual implementation are described. Moreover, the language used in this disclosure has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter, resort to the claims being necessary to determine such inventive subject matter. Reference in this disclosure to “one embodiment” or to “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the disclosed subject matter, and multiple references to “one embodiment” or “an embodiment” should not be understood as necessarily all referring to the same embodiment.

It will be appreciated that in the development of any actual implementation (as in any software and/or hardware development project), numerous decisions must be made to achieve the developers' specific goals (e.g., compliance with system- and business-related constraints), and that these goals may vary from one implementation to another. It will also be appreciated that such development efforts might be complex and time-consuming, but would nevertheless be a routine undertaking for those of ordinary skill in the design and implementation of graphics systems in general and game systems in particular, having the benefit of this disclosure.

Referring toFIG. 1, system100in accordance with one embodiment includes client105that uses agent110and either provides or generates scene115through which agent110must be able to navigate. Scene115may contain an arbitrary number and arrangement of obstacle polygons. Navigator120uses a novel technique to automatically and rapidly generate navigation graph125(a structure identifying those points and paths within scene115that agent110may assume) for any given scene115that guarantees there is no region within scene115that agent110cannot reach. Client105may use navigation graph125to plan agent110's movement through scene115. In one embodiment client105and navigator120may be different aspects of a common application executing on the same computer system. In another embodiment client105may be one or more applications and navigator120another one or more applications executing on the same computer system. In general client105may be any application that needs to track an object (e.g., agent110) through an area (e.g., scene100) without itself needing to determine where in the given area the object may traverse. Similarly, navigator120may be any application or procedure that provides the disclosed functionality. By way of example navigator120may be a user-level application or functionality accessed through a an application programming interface (API). In still another embodiment client105may execute on one computer system while navigator120executes on another computer system. In implementations taking this approach, path130may represent one or more networks, each of which may take any form including, but not limited to, local area networks and wide area networks such as the Internet. Further, path130may use any desired technology (wired, wireless or a combination thereof) and communication protocol (e.g., TCP, or transmission control protocol and PPP, or point to point).

Referring toFIG. 2, navigation graph operation200in accordance with one embodiment may begin with navigator120obtaining agent descriptor information105′ and scene115(blocks205and210). One type of agent descriptor information may include the agent's bounding radius. Another type of agent descriptor information may include a structure identifying the agent's perimeter. Scene115may contain an arbitrary number and arrangement of obstacle polygons, any of which may be concave or convex, static or dynamic: a concave polygon is a polygon having one or more interior angles greater than 180°; a convex polygon is a polygon whose interior angles are all less than 180°; a static polygon has a fixed position within scene115; and a dynamic polygon may change its position during the time navigator120generates navigation graph125. The vertices of all polygons within scene115may then be extruded by an amount based on the agent's bounding radius (block215). As used herein the term “extrusion” means to extend a polygon's vertex in such a fashion as to minimally encompass a given agent subject to constraints applied by the vertices two adjacent edges (see below). From each polygon's extruded vertex an extruded object may be generated (block220). In one embodiment this may be done by connecting each polygon's extruded vertex to each of its adjacent extruded vertices. The obstacle polygon's extruded vertices comprise the nodes in navigation graph125. To identify paths, an attempt may be made to create a connection between all of the vertices of all of the extruded obstacle polygons. Any connection that intersects any of the extruded obstacle polygons (even self intersection) may be removed (block225). In one embodiment, this may complete the generation of navigation graph125. In another embodiment a simplification operation may be applied to eliminate redundant paths. For example, connections between different nodes having approximately the same direction and/or approximately the same length may be removed as effectively being redundant. What constitutes the “same” or “approximately the same” will, of course, vary from implementation to implementation, dependent upon the needs and purpose of a given implementation. In one embodiment length and orientation thresholds may be specified so that if two paths have lengths differing by less than the specified length threshold they may be considered to be the “same” length. Similarly, if two paths have orientations (e.g., are pointed in the same direction) that differ by less than the specified orientation threshold they may be considered to point in the same direction (e.g., have the same orientation).

Referring now toFIGS. 3 and 4, a more detailed description of how extruded vertices may be created is provided (e.g., block215). To begin, a first node of a first obstacle polygon may be selected (block300): vertices B and E inFIG. 4A. A first edge of the selected vertex may be chosen (block305): edges AB and DE inFIG. 4B. An edge normal to the selected edge can then be made (block310): normal NABand NDEinFIG. 4C, with the length of the edge normal equal to the agent's bounding radius. Next, a rectangle extending perpendicularly from the selected edge and having a depth equal to the edge normal may be created (block315): seeFIG. 4D. These actions may be repeated for the selected vertices other edge (blocks420-430): seeFIG. 4E. Referring now toFIG. 3B, a check may now be made to determine if the selected vertices edge rectangles intersect (block335). As shown inFIG. 4E, those edge rectangles corresponding to the concave polygon do intersect (the “YES” prong of block335), so the top-most intersection point B′ may be taken as the extruded vertex (block340): seeFIG. 4F. Also shown inFIG. 4E, edge rectangles corresponding to the convex polygon do not intersect (the “NO” prong of block335), so the top surface of each edge's rectangle may be extended in toward the selected vertex until they intersect (block345): seeFIG. 4G. The intersection point E′ of the extended rectangle edges may be taken as the extruded vertex (block340); seeFIG. 4H. If the polygon has at least one more vertex to extrude (the “YES” prong of block350), the next adjacent vertex that has not yet been extruded is selected (block355) where after vertex extrusion operation215continues at block325. If all of the polygon's vertices have been extruded (the “NO” prong of block350), the polygon's extruded object may be created by connecting each of the extruded vertices to each of its adjacent extruded vertices (block360).

Referring toFIG. 5A, a navigation graph operation in terms of illustrative environment or scene500having polygonal obstacles505,510and515, and agent520will be described. As shown inFIG. 5B, each of the three polygonal obstacles505,510and515first have their vertices extruded525. With each obstacle polygon's extruded vertices known, so too are the final navigation graph's nodes as they are the same (see above). Referring now toFIG. 5C, each polygon's extruded vertices may be connected to form extruded objects505′,510′ and515′. Operationally, extruded objects define regions in scene500through which agent520cannot pass. Referring toFIG. 5D, and by way of example, extruded vertex525extends a possible path530from itself to every other extruded vertex in scene500. Some paths535intersect one of the extruded objects meaning they are not viable and should be removed as shown inFIG. 5E. Referring now toFIG. 5F, extending paths530for each of the other11extruded vertices may result in navigation graph540.

Turning now toFIG. 5G, consider a case where agent520begins in scene500as shown and wants to move to node or position545. Agent520could, for example, move first to node550and take path555to end at point545. Alternatively, agent520could move first to node560and take path565to end at point545. As shown inFIG. 5G, there are a number of different paths agent520may take to get from node550to node545. In one embodiment each edge in navigation graph540may have assigned to it a weight or any desired function, and agent may move from start to finish so as to minimize a cost based on edge weight. By way of example, a weight or cost may be assigned to each edge in navigation graph540based on its length. In this way minimizing a cost may facilitate agent520taking the shortest path between any two locations.

Referring toFIG. 6, the disclosed embodiments to generate a navigation graph in accordance with the above may be performed by representative computer system600(e.g., a general purpose computer system such as a desktop, laptop, notebook or tablet computer system). Computer system600may include one or more processors605, memory610(610A and610B), one or more storage devices615, graphics hardware620, device sensors625(e.g., 3D depth sensor, proximity sensor, ambient light sensor, accelerometer and/or gyroscope), communication interface630, user interface adapter635and display adapter640—all of which may be coupled via system bus or backplane645which may be comprised of one or more continuous (as shown) or discontinuous communication links. Memory610may include one or more different types of media (typically solid-state) used by processor605and graphics hardware620. For example, memory610may include memory cache, read-only memory (ROM), and/or random access memory (RAM). Storage615may include one more non-transitory storage mediums including, for example, magnetic disks (fixed, floppy, and removable) and tape, optical media such as CD-ROMs and digital video disks (DVDs), and semiconductor memory devices such as Electrically Programmable Read-Only Memory (EPROM), and Electrically Erasable Programmable Read-Only Memory (EEPROM). Memory610and storage615may be used to retain media (e.g., audio, image and video files), preference information, device profile information, computer program instructions or code organized into one or more modules and written in any desired computer programming language, and any other suitable data. When executed by processor(s)605and/or graphics hardware620such computer program code may implement one or more of the methods described herein. Communication interface630may be used to connect computer system600to one or more networks. Illustrative networks include, but are not limited to, a local network such as a USB network, an organization's local area network, and a wide area network such as the Internet. Communication interface630may use any suitable technology (e.g., wired or wireless) and protocol (e.g., Transmission Control Protocol (TCP), Internet Protocol (IP), User Datagram Protocol (UDP), Internet Control Message Protocol (ICMP), Hypertext Transfer Protocol (HTTP), Post Office Protocol (POP), File Transfer Protocol (FTP), and Internet Message Access Protocol (IMAP)). User interface adapter635may be used to connect keyboard650, microphone655, pointer device660, speaker665and other user interface devices such as a touch-pad and/or a touch screen (not shown). Display adapter640may be used to connect one or more display units670which may provide touch input capability. Processor605may be a system-on-chip such as those found in mobile devices and include one or more dedicated graphics processing units (GPUs). Processor605may be based on reduced instruction-set computer (RISC) or complex instruction-set computer (CISC) architectures or any other suitable architecture and may include one or more processing cores. Graphics hardware620may be special purpose computational hardware for processing graphics and/or assisting processor605perform computational tasks. In one embodiment, graphics hardware620may include one or more programmable GPUs and each such unit may include one or more processing cores.

Referring toFIG. 7, a simplified functional block diagram of illustrative mobile electronic device700is shown according to one embodiment. Electronic device700could be, for example, a mobile telephone, personal media device, a notebook computer system, or a tablet computer system. As shown, electronic device700may include processor705, display710, user interface715, graphics hardware720, device sensors725(e.g., proximity sensor/ambient light sensor, accelerometer and/or gyroscope), microphone730, audio codec(s)735, speaker(s)740, communications circuitry745, image capture circuit or unit750, video codec(s)755, memory760, storage765, and communications bus770.

Processor705, display710, user interface715, graphics hardware720, device sensors725, communications circuitry745, memory760and storage765may be of the same or similar type and/or serve the same function as the similarly named component described above with respect toFIG. 6. Audio signals obtained via microphone730may be, at least partially, processed by audio codec(s)735. Data so processed may be stored in memory760and/or storage765and/or output through speakers740. Image capture circuitry750may capture still and video images. Output from image capture circuitry750may be processed, at least in part, by video codec(s)755and/or processor705and/or graphics hardware720, and/or a dedicated image processing unit incorporated within circuitry750. Images so captured may be stored in memory760and/or storage765.

It is to be understood that the above description is intended to be illustrative, and not restrictive. The material has been presented to enable any person skilled in the art to make and use the disclosed subject matter as claimed and is provided in the context of particular embodiments, variations of which will be readily apparent to those skilled in the art (e.g., some of the disclosed embodiments may be used in combination with each other). The various embodiments have been described, for the most part, in terms of a game application and a single agent. The disclosed techniques are no limited in either of these aspects. Consider for example a mobile robot (agent), a room with a number of objects (environment) and a motion control system (application) that must move the robot through the room. Such a problem may be ideally suited to the disclosed techniques. In addition, multiple agents may be addressed by multiple uses of a single basic implementation, the use of different threads for different agents or graphs. Other uses will be apparent to those of ordinary skill having the benefit of this document. In addition,FIGS. 2 and 3show flowcharts illustrating different aspects of how to generate a navigation graph in accordance with the disclosed embodiments. In one or more embodiments, one or more of the disclosed steps may be omitted, repeated, and/or performed in a different order than that described herein. Accordingly, the specific arrangement of steps or actions shown should not be construed as limiting the scope of the disclosed subject matter. Further while all of the above described embodiments were two-dimensional in nature, navigation graphs of the type described herein may be implemented for any dimensional space. The scope of the invention therefore should be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled. In the appended claims, the terms “including” and “in which” are used as the plain-English equivalents of the respective terms “comprising” and “wherein.”