Providing a navigation mesh by which objects of varying sizes can traverse a virtual space

A single polygonal navigation mesh in a virtual space by which objects of varying sizes can traverse may be provided. This may allow the navigation mesh to be used in determining appropriate paths for objects having a wide range of object sizes. The objects may include objects having a continuous range of possible object sizes. The use of a single navigation mesh for a range of object sizes may reduce the amount of storage needed to store separate navigation meshes for different object sizes. According to some implementations, constraints at outer boundaries of the navigation mesh may be determined based on a given object size allowing a single navigation mesh to be used for objects of any size.

FIELD OF THE DISCLOSURE

This disclosure relates to constraining movement of objects through a virtual space using a single polygonal navigation mesh for objects of varying sizes, rather than using meshes that are object size-specific.

BACKGROUND

Generally, navigation meshes may be used to define where objects can move and/or be located within a virtual space. Such navigation meshes may be constructed from polygonal tiles joined at their edges, and can be two- or three-dimensional. Conventional navigation meshes may not be visible within the virtual space. That is, a navigation mesh may be separate and unique from meshes that define visible surfaces within the virtual space. In some cases, however, a navigation mesh may track or correspond to a portion of a mesh that defines visible surfaces within the virtual space.

Traditionally, separate navigation meshes may be predefined for each one of a set of discrete object sizes. As a result, a virtual space may only accommodate objects of discrete sizes and/or certain sized objects may be over restricted in the virtual space. For example, if a virtual space has two navigation meshes—one for objects of size 1 (e.g., an object radius and/or another measure equaling one length unit) and another for objects of size 5, then an object of size 2 may utilize the navigation mesh for object of size 5. Thus, even though an object of size 2 is smaller than an object of size 5 and should be able to traverse areas where the object of size 5 cannot, the object of size 2 may have the same positional restrictions as the object of size 5. Additionally, memory usage associated with storing several predefined navigation meshes may be a drawback of existing approaches to navigation meshes.

SUMMARY

One aspect of the disclosure relates to a system and method for providing a single polygonal navigation mesh in a virtual space by which objects of varying sizes can traverse. This may allow the navigation mesh to be used in determining appropriate paths for objects having a wide range of object sizes. The objects may include objects having a continuous range of possible object sizes. The use of a single navigation mesh for a range of object sizes may reduce the amount of storage needed to store separate navigation meshes for different object sizes. According to some implementations, constraints at outer boundaries of the navigation mesh may be determined based on a given object size allowing a single navigation mesh to be used for objects of any size.

The system may include a virtual space platform. The virtual space platform may be configured to communicate with one or more other computing platforms via any one of a number of communication channels. The virtual space platform may be configured to execute one or more computer program modules. The computer program modules may include one or more of a space module, a navigation mesh module, a constraint initialization module, a constraint validation module, a split constraint module, a mesh traversal module, and/or other modules.

The space module may be configured to provide one or more virtual spaces to users via the virtual space platform and/or one or more other computing platforms. As used herein, a “virtual space” may include one or more of a virtual space, a video game, a virtual world, and/or other virtual spaces.

The navigation mesh module may be configured to provide a navigation mesh associated with the virtual space. The navigation mesh may correspond to a surface on which an object travels in the virtual space. The navigation mesh may be formed from polygonal tiles. Adjacent ones of the polygonal tiles may be joined along adjacent polygonal tile edges. Outer boundaries of the navigation mesh may confine paths by which the objects can traverse a surface or volumetric region in the virtual space such that the objects cannot breach an outer boundary of the navigation mesh. Portions of a surface in the virtual space may be planar and/or non-planar. A volumetric region in the virtual space may include a three-dimensional space in the virtual space. A navigation mesh corresponding to a given volumetric region may include a surface mesh that encompasses some or all of the volumetric region.

According to some implementations, a navigation mesh provided by the navigation mesh module may include a volumetric navigation mesh. A volumetric navigation mesh may include one or more volumetric units. A volumetric unit may be a closed shape defined by a plurality of polygonal tiles. The polygonal tiles forming a given volumetric unit may be planar and/or non-planar polygonal tiles. In a volumetric navigation mesh, the one or more volumetric units may be joined at the faces (i.e., polygonal tiles) of the volumetric units. The outer boundary of a volumetric navigation mesh may include a plurality of polygonal tiles. The outer boundary of a volumetric navigation mesh may establish a volumetric region within which positions and/or movements of objects are confined. As such, object positions and/or movements may be confined in three dimensions, in accordance with some implementations.

The constraint initialization module may be configured to determine constraints associated with the navigation mesh. Such a determination may be made based on a given object size. Constraints may be located within the outer boundaries of the navigation mesh. Constraints may be configured to confine a position of a center of a given object (or other point associated with the given object) having the given object size to prevent the given object from breaching the outer boundary of the navigation mesh.

According to various implementations, an object having either two spatial dimensions in the virtual space or an object that is restricted by a navigation mesh in two-dimensions may be represented or modeled as a circle. Such a circle may have an object radius defining the associated object size. An object having three spatial dimensions in the virtual space or an object that is restricted by a navigation mesh in three dimensions may be represented or modeled as a cylinder. Such a cylinder may have an object radius defining the associated object size.

Constraints determined by the system may include one or both of one or more edge constraints or one or more corner constraints. An edge constraint may correspond to an individual polygonal tile edge that forms at least a portion of the outer boundary of the navigation mesh. An edge constraint may define a line parallel to the corresponding polygonal tile edge. That line may be spaced a distance equal to the object radius associated with the given object from the corresponding polygonal tile edge. A corner constraint may correspond to individual corners of the outer boundary of the navigation mesh having an internal angle greater than 180 degrees. A corner constraint may define an arc centered at a corresponding corner. That arc may have a corner constraint radius equal to the object radius associated with the given object.

In implementations where a volumetric navigation mesh is utilized, constraints determined by the constraint initialization module may include surface constraints that correspond to the outer boundary of the volumetric navigation mesh. A surface constraint corresponding to a polygonal tile of the outer boundary may include a planar and/or non-planar shape. In some implementations, points on such a surface constraint may be equidistant from a corresponding polygonal tile of the volumetric navigation mesh. A surface constraint corresponding to an internal corner having internal angles greater than 180 degrees may include a spherical shape centered at the internal corner. The distance between a surface constraint and corresponding outer boundary of the volumetric navigation mesh may be based on a given object size.

The constraint validation module may be configured to validate individual ones of the constraints. This validation may include determining whether one or more constraints adjacent to a given constraint completely encompass an area of influence associated with the given constraint. An area of influence associated with a constraint may include the area on the navigation mesh between the constraint and a corresponding outer boundary of the navigation mesh. Invalidated constraints may be excluded as constraints associated with a corresponding object size.

The split constraint module may be configured to determine one or more new constraints associated with a choke point in the navigation mesh. A choke point may be a region of the navigation mesh that is narrower than adjacent regions of the navigation mesh. According to some implementations, individual ones of the new constraints may be or may be equivalent to portions of one or more preexisting constraints. The split constraint module may be further configured to determine a largest object size that can traverse through the choke point.

The mesh traversal module may be configured to determine whether a given object can traverse from a first polygonal tile of the navigation mesh to a second polygonal tile of the navigation mesh based on the constraints. Such a determination may include determining whether there are any valid positions for the given object in the second polygonal tile. In some implementations, the mesh traversal module may be configured to determine, when an object enters the navigation mesh, the nearest valid point on the navigation mesh to a starting location of the object and/or the nearest valid point on the navigation mesh to a desired target location of the object. In general, to traverse the navigation mesh, the object must cross shared interior polygonal tile edges between polygonal tiles. As such, the mesh traversal module may be configured to determine whether crossing a particular interior polygonal edge is allowed for a given object size.

DETAILED DESCRIPTION

FIG. 1illustrates a system100configured for providing a single polygonal navigation mesh in a virtual space by which objects of varying sizes can traverse, in accordance with one or more implementations. The virtual space may be provided by a local platform and/or by a remote platform over a network. In some implementations, system100may include a virtual space platform102. The virtual space platform102may be configured to communicate with one or more other computing platforms104. Such communication may be according to a client/server architecture. According to various implementations, users may access system100and/or the virtual space via virtual space platform102and/or computing platforms104.

The virtual space platform102may be configured to execute one or more computer program modules. The computer program modules may include one or more of a space module106, a navigation mesh module108, a constraint initialization module110, a constraint validation module112, a split constraint module114, a mesh traversal module116, and/or other modules.

The space module106may be configured to provide one or more virtual spaces to users via virtual space platform102and/or computing platforms104. As used herein, a “virtual space” may include one or more of a video game, a virtual world, and/or other virtual spaces.

A virtual space may comprise a simulated space that is accessible by users via local platforms (e.g., virtual space platform102) and/or clients (e.g., computing platforms104) that present the views of the virtual space to a user. The simulated space may have a topography, express ongoing real-time interaction by one or more users, and/or include one or more objects positioned within the topography that are capable of locomotion within the topography. In some instances, the topography may be a 2-dimensional topography. In other instances, the topography may be a 3-dimensional topography. The topography may include dimensions of the space, and/or surface features of a surface or objects that are “native” to the space. In some instances, the topography may describe a surface (e.g., a ground surface) that runs through at least a substantial portion of the space. In some instances, the topography may describe a volume with one or more bodies positioned therein (e.g., a simulation of gravity-deprived space with one or more celestial bodies positioned therein). The instance executed by the computer modules may be synchronous, asynchronous, and/or semi-synchronous.

The above description of the manner in which views of the virtual space are determined by space module106is not intended to be limiting. The space module106may be configured to express the virtual space in a more limited, or more rich, manner. For example, views determined for the virtual space may be selected from a limited set of graphics depicting an event in a given place within the virtual space. The views may include additional content (e.g., text, audio, pre-stored video content, and/or other content) that describes particulars of the current state of the place, beyond the relatively generic graphics. For example, a view may include a generic battle graphic with a textual description of the opponents to be confronted. Other expressions of individual places within the virtual space are contemplated.

Within the instance(s) of the virtual space executed by space module106, users may control characters, objects, simulated physical phenomena (e.g., wind, rain, earthquakes, and/or other phenomena), and/or other elements within the virtual space to interact with the virtual space and/or each other. The user characters may include avatars. As used herein, the term “user character” may refer to an object (or group of objects) present in the virtual space that represents an individual user. The user character may be controlled by the user with which it is associated. The user controlled element(s) may move through and interact with the virtual space (e.g., non-user characters in the virtual space, other objects in the virtual space). The user controlled elements controlled by and/or associated with a given user may be created and/or customized by the given user. The user may have an “inventory” of virtual goods and/or currency that the user can use (e.g., by manipulation of a user character or other user controlled element, and/or other items) within the virtual space.

The users may participate in the instance of the virtual space by controlling one or more of the available user controlled elements in the virtual space. Control may be exercised through control inputs and/or commands input by the users through virtual space platform102and/or computing platforms104. The users may interact with each other through communications exchanged within the virtual space. Such communications may include one or more of textual chat, instant messages, private messages, voice communications, and/or other communications. Communications may be received and entered by the users via virtual space platform102and/or computing platforms104.

The navigation mesh module108may be configured to provide a navigation mesh associated with the virtual space. The navigation mesh may correspond to a surface on which an object travels in the virtual space. The navigation mesh may be formed from polygonal tiles. Adjacent ones of the polygonal tiles may be joined along adjacent polygonal tile edges. Outer boundaries of the navigation mesh may confine paths by which the objects can traverse a surface or volumetric region in the virtual space such that the objects cannot breach an outer boundary of the navigation mesh. Portions of a surface in the virtual space may be planar and/or non-planar. A volumetric region in the virtual space may include a three-dimensional space in the virtual space. A navigation mesh corresponding to a given volumetric region may include a surface mesh that encompasses some or all of the volumetric region.

FIG. 2illustrates valid and invalid object positions on a portion of a navigation mesh200, in accordance with one or more implementations. Objects202and204may have respective object sizes associated therewith. In some implementations, objects202and204may be modeled or otherwise represented by circles in two dimensional configurations and/or cylinders in three dimensional configurations, as discussed further below. When determining whether a specific point in a navigation mesh is a valid position for an object to reside in or move through, the size of the object and/or other spatial measures (e.g., the object radius) may be taken into account. Any position that would result in overlap between the object and an outer boundary of the navigation mesh is invalid. An invalid position may be adjusted so that the object lies fully on the navigation mesh. InFIG. 2, the position of object202is valid, but the position of object204is invalid because object204breaches outer boundary206of navigation mesh200.

According to some implementations, a navigation mesh provided by navigation mesh module108may include a volumetric navigation mesh. A volumetric navigation mesh may include one or more volumetric units. A volumetric unit may be a closed shape defined by a plurality of polygonal tiles. One example of a volumetric unit may be a cube formed by six polygonal tiles, however other shapes may be used as volumetric units. The polygonal tiles forming a given volumetric unit may be planar and/or non-planar polygonal tiles. By way of non-limiting example, a non-planar polygonal tile may include a convex shape and/or other non-planar shapes. In a volumetric navigation mesh, the one or more volumetric units may be joined at the faces (i.e., polygonal tiles) of the volumetric units. The outer boundary of a volumetric navigation mesh may include a plurality of polygonal tiles. The outer boundary of a volumetric navigation mesh may establish a volumetric region within which positions and/or movements of objects are confined. As such, object positions and/or movements may be confined in three dimensions, in accordance with some implementations.

The constraint initialization module110may be configured to determine constraints associated with the navigation mesh. Such a determination may be made based on a given object size. Constraints may be located within the outer boundaries of the navigation mesh. Constraints may be configured to confine a position of a center of a given object (or other point associated with the given object) having the given object size to prevent the given object from breaching the outer boundary of the navigation mesh.

Objects in the virtual space may be represented and/or modeled by any shape for purposes of the navigation mesh. According to various implementations, an object having either two spatial dimensions in the virtual space or an object that is restricted by a navigation mesh in two-dimensions may be represented or modeled as a circle. Such a circle may have an object radius defining the associated object size. An object having three spatial dimensions in the virtual space or an object that is restricted by a navigation mesh in three dimensions may be represented or modeled as a cylinder. Such a cylinder may have an object radius defining the associated object size.

Constraints determined in system100may include one or both of one or more edge constraints or one or more corner constraints. An edge constraint may correspond to an individual polygonal tile edge that forms at least a portion of the outer boundary of the navigation mesh. An edge constraint may define a line parallel to the corresponding polygonal tile edge. That line may be spaced a distance equal to the object radius associated with the given object from the corresponding polygonal tile edge. A corner constraint may correspond to individual corners of the outer boundary of the navigation mesh having an internal angle greater than 180 degrees. A corner constraint may define an arc centered at a corresponding corner. That arc may have a corner constraint radius equal to the object radius associated with the given object.

FIG. 3illustrates constraints on a portion of a navigation mesh300, in accordance with one or more implementations. The navigation mesh300may have edge constraints302and corner constraints304. The edge constraints302may be parallel to corresponding outer boundaries306of navigation mesh300. A given edge constraint302and a corresponding outer boundary306may be separated by a distance equal to the radius of object308. The corner constraints304may be arcs centered at corners310of the navigation mesh300. The corners310may have internal angles greater than 180 degrees. The arcs of corner constraints304may have a radius equal to the radius of object308. The center position of object308may be constrained to the area within navigation mesh300defined by edge constraints302and corner constraints304.

In implementations where a volumetric navigation mesh is utilized, constraints determined by constraint initialization module110may include surface constraints that correspond to the outer boundary of the volumetric navigation mesh. A surface constraint corresponding to a polygonal tile of the outer boundary may include a planar and/or non-planar shape. In some implementations, points on such a surface constraint may be equidistant from a corresponding polygonal tile of the volumetric navigation mesh. A surface constraint corresponding to an internal corner having internal angles greater than 180 degrees may include a spherical shape centered at the internal corner. The distance between a surface constraint and corresponding outer boundary of the volumetric navigation mesh may be based on a given object size.

The constraint validation module112may be configured to validate individual ones of the constraints. This validation may include determining whether one or more constraints adjacent to a given constraint completely encompass an area of influence associated with the given constraint. An area of influence associated with a constraint may include the area on the navigation mesh between the constraint and a corresponding outer boundary of the navigation mesh. Invalidated constraints may be excluded as constraints associated with a corresponding object size.

FIG. 4illustrates invalidation of constraints on portions of a navigation mesh400, in accordance with one or more implementations. As an object radius forming a basis of a set of constraints increases, it may be possible for some constraints to become invalid. As mentioned above, when an area of influence associated with a given constraint is completely encompassed by neighboring constraints, the given constraint may be invalidated. InFIG. 4, constraint402in each portion of navigation mesh400may become invalidated by constraints404and406if a corresponding object radius increases because areas of influence of constraint404and406will completely encompass that of constraint402.

The split constraint module114may be configured to determine one or more new constraints associated with a choke point in the navigation mesh. A choke point may be a region of the navigation mesh that is narrower than adjacent regions of the navigation mesh. According to some implementations, individual ones of the new constraints may be or may be equivalent to portions of one or more preexisting constraints. The split constraint module114may be further configured to determine a largest object size that can traverse through the choke point.

FIG. 5illustrates new constraints determined at a choke point of a navigation mesh500, in accordance with one or more implementations.FIG. 5shows constraints for two different object sizes on navigation mesh500. According to some implementations, when constraint502touches constraint504, new constraints506and508may be determined. Based on constraints502and504, object510may travel between polygonal tiles512and514. Based on constraints502-508, object516may not travel from polygonal tile512to polygonal tile514.

The mesh traversal module116may be configured to determine whether a given object can traverse from a first polygonal tile of the navigation mesh to a second polygonal tile of the navigation mesh based on the constraints. Such a determination may include determining whether there are any valid positions for the given object in the second polygonal tile. In some implementations, mesh traversal module116may be configured to determine, when an object enters the navigation mesh, the nearest valid point on the navigation mesh to a starting location of the object and/or the nearest valid point on the navigation mesh to a desired target location of the object. In general, to traverse the navigation mesh, the object must cross shared interior polygonal tile edges between polygonal tiles. As such, mesh traversal module116may be configured to determine whether crossing a particular interior polygonal edge is allowed for a given object size.

FIGS. 6A and 6Billustrate considerations when determining whether an object can traverse between polygonal tiles of a navigation mesh600based on associated constraints, in accordance with one or more constraints. Determining whether crossing a particular interior polygonal edge is allowed for a given object size may be based on choke points. InFIG. 6A, travel by object602between polygonal tiles604and606is restricted by choke point608. The maximum object radius and/or object size that could possibly fit through choke point608may be determined. When determining a path for object602, travel between polygonal tiles604and606may be allowed if the object radius and/or object size of object602is less than the determined maximum.

Determining whether crossing a particular interior polygonal edge is allowed for a given radius may include determining a largest object radius and/or object size that has any valid position in a given polygonal tile. InFIG. 6A, object602represents the largest object radius and/or object size that can be positioned in polygonal tile606. Once that largest object radius and/or object size is determined, it may be used to determine if travel from one polygonal tile to another is valid. For example, if an object is in polygonal tile610, but its object radius and/or object size is greater than that maximum for polygonal tile606, then travel from polygonal tile610to polygonal tile606may not be allowed for that object. The maximum object radius and/or object size may be determined by identifying the object radius and/or object size for which the entire area of a given polygonal tile would be outside of the constraints of the navigation mesh. InFIG. 6B, that occurs when the intersection between constraints612and614cross the interior polygonal edge616separating polygonal tile606and polygonal tile610.

A given computing platform104may include one or more processors configured to execute computer program modules. The computer program modules may be configured to enable an expert or user associated with the given computing platforms104to interface with virtual space platform102and/or external resources118, and/or provide other functionality attributed herein to computing platforms104. By way of non-limiting example, the given computing platform104may include one or more of a desktop computer, a laptop computer, a handheld computer, a NetBook, a Smartphone, a gaming console, and/or other computing platforms.

The external resources118may include sources of information, hosts and/or providers of virtual spaces outside of system100, external entities participating with system100, and/or other resources. In some implementations, some or all of the functionality attributed herein to external resources100may be provided by resources included in system100.

The virtual space platform102may include electronic storage120, one or more processors122, and/or other components. The virtual space platform102may include communication lines, or ports to enable the exchange of information with a network and/or other computing platforms. Illustration of virtual space platform102inFIG. 1is not intended to be limiting. The virtual space platform102may include a plurality of hardware, software, and/or firmware components operating together to provide the functionality attributed herein to virtual space platform102. For example, virtual space platform102may include one or more servers and may be implemented by a cloud of computing platforms operating together as virtual space platform102. Additionally, virtual space platform102may include one or more of a desktop computer, a laptop computer, a handheld computer, a NetBook, a Smartphone, a gaming console, and/or other computing platforms.

Electronic storage120may comprise electronic storage media that electronically stores information. The electronic storage media of electronic storage120may include one or both of system storage that is provided integrally (i.e., substantially non-removable) with virtual space platform102and/or removable storage that is removably connectable to virtual space platform102via, for example, a port (e.g., a USB port, a firewire port, etc.) or a drive (e.g., a disk drive, etc.). Electronic storage120may include one or more of optically readable storage media (e.g., optical disks, etc.), magnetically readable storage media (e.g., magnetic tape, magnetic hard drive, floppy drive, etc.), electrical charge-based storage media (e.g., EEPROM, RAM, etc.), solid-state storage media (e.g., flash drive, etc.), and/or other electronically readable storage media. The electronic storage120may include one or more virtual storage resources (e.g., cloud storage, a virtual private network, and/or other virtual storage resources). Electronic storage120may store software algorithms, information determined by processor122, information received from virtual space platform102, information received from computing platforms104, and/or other information that enables virtual space platform102to function as described herein.

Processor(s)122is configured to provide information processing capabilities in virtual space platform102. As such, processor122may include one or more of a digital processor, an analog processor, a digital circuit designed to process information, an analog circuit designed to process information, a state machine, and/or other mechanisms for electronically processing information. Although processor122is shown inFIG. 1as a single entity, this is for illustrative purposes only. In some implementations, processor122may include a plurality of processing units. These processing units may be physically located within the same device, or processor122may represent processing functionality of a plurality of devices operating in coordination. The processor122may be configured to execute modules106,108,110,112,114,116, and/or other modules. Processor122may be configured to execute modules106,108,110,112,114,116, and/or other modules by software; hardware; firmware; some combination of software, hardware, and/or firmware; and/or other mechanisms for configuring processing capabilities on processor122.

It should be appreciated that although modules106,108,110,112,114, and116are illustrated inFIG. 1as being co-located within a single processing unit, in implementations in which processor122includes multiple processing units, one or more of modules106,108,110,112,114, and/or116may be located remotely from the other modules. The description of the functionality provided by the different modules106,108,110,112,114, and/or116described below is for illustrative purposes, and is not intended to be limiting, as any of modules106,108,110,112,114, and/or116may provide more or less functionality than is described. For example, one or more of modules106,108,110,112,114, and/or116may be eliminated, and some or all of its functionality may be provided by other ones of modules106,108,110,112,114, and/or116. As another example, processor122may be configured to execute one or more additional modules that may perform some or all of the functionality attributed below to one of modules106,108,110,112,114, and/or116.

FIG. 7illustrates a method700for providing a single polygonal navigation mesh in a virtual space by which objects of varying sizes can traverse, in accordance with one or more implementations. The operations of method700presented below are intended to be illustrative. In some embodiments, method700may be accomplished with one or more additional operations not described, and/or without one or more of the operations discussed. Additionally, the order in which the operations of method700are illustrated inFIG. 7and described below is not intended to be limiting.

At operation702, one or more virtual spaces may be provided for presentation to one or more users. Such presentation may be performed via one or both of virtual space platform102and/or computing platforms104. The space module106may perform operation702, in accordance with some implementations.

At operation704, a navigation mesh associated with the virtual space may be provided. The navigation mesh may be formed from polygonal tiles. Adjacent ones of the polygonal tiles may be joined along adjacent polygonal tile edges. Outer boundaries of the navigation mesh may confine paths by which the objects can traverse a surface or volumetric region in the virtual space such that the objects cannot breach an outer boundary of the navigation mesh. Individual ones of the objects having an object size associated therewith. The navigation mesh module108may perform operation704, in accordance with some implementations.

At operation706, constraints associated with the navigation mesh may be determined based on a given object size. The constraints may be within the outer boundaries of the navigation mesh and configured to confine a position of a center of a given object having the given object size to prevent the given object from breaching the outer boundary of the navigation mesh. The constraint initialization module110may perform operation706, in accordance with some implementations.

At operation708, individual ones of the constraints may be validated. This may include determining whether one or more constraints adjacent to a given constraint completely encompass an area of influence associated with the given constraint. Invalidated constraints may be excluded as constraints associated with a corresponding object size. The constraint validation module112may perform operation708, in accordance with some implementations.

At operation710, one or more new constraints associated with a choke point in the navigation mesh may be determined. The choke point may be a region of the navigation mesh that is narrower than adjacent regions of the navigation mesh. The split constraint module114may be configured to perform operation710, in accordance with some implementations.

At operation712, whether the given object can traverse from a first polygonal tile of the navigation mesh to a second polygonal tile of the navigation mesh may be determined based on the constraints. The mesh traversal module116may perform operation712, in accordance with some implementations.