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

1. A system configured for providing a single polygonal navigation mesh in a virtual space by which objects of varying size can traverse, the system comprising:

one or more processors configured to execute computer program instructions, the computer program instructions comprising:

a navigation mesh component configured to provide a navigation mesh associated with the virtual space, the navigation mesh formed from polygonal tiles, adjacent ones of the polygonal tiles being joined along adjacent polygonal tile edges, outer boundaries of the navigation mesh confining 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;

a constraint initialization component configured to determine constraints associated with the navigation mesh based on a given object size, the constraints being 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; and

a mesh traversal component configured to determine whether the 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;

wherein the constraints include one or both of one or more edge constraints or one or more corner constraints;

wherein an object having two spatial dimensions in the virtual space is modeled as a circle, the circle having an object radius defining the associated object size, and wherein an object having three spatial dimensions in the virtual space is modeled as a cylinder, the cylinder having an object radius defining the associated object size; and

wherein individual ones of the one or more edge constraints correspond to individual polygonal tile edges that form at least a portion of the outer boundary of the navigation mesh, a given edge constraint defining a line parallel to a corresponding polygonal tile edge and spaced a distance equal to the object radius associated with the given object from the corresponding polygonal tile edge.

2. The system of claim 1 , wherein the computer program instructions further comprise a constraint validation component configured to validate individual ones of the constraints by determining whether one or more constraints adjacent to a given constraint completely encompass an area of influence associated with the given constraint, invalidated constraints being excluded as constraints associated with a corresponding object size.

3. The system of claim 1 , wherein the computer program instructions further comprise a split constraint component configured to determine one or more new constraints associated with a choke point in the navigation mesh, the choke point being a region of the navigation mesh that is narrower than adjacent regions of the navigation mesh.

4. The system of claim 3 , wherein individual ones of the one or more new constraints are portions of one or more preexisting constraints.

5. The system of claim 3 , wherein the split constraint component is further configured to determine a largest object size that can traverse through the choke point.

6. The system of claim 1 , wherein determining whether the given object can traverse from a first polygonal tile of the navigation mesh to a second polygonal tile of the navigation includes determining whether there are any valid positions for the given object in the second polygonal tile.

7. A system configured for providing a single polygonal navigation mesh in a virtual space by which objects of varying size can traverse, the system comprising:

one or more processors configured to execute computer program instructions, the computer program instructions comprising:

a navigation mesh component configured to provide a navigation mesh associated with the virtual space, the navigation mesh formed from polygonal tiles, adjacent ones of the polygonal tiles being joined along adjacent polygonal tile edges, outer boundaries of the navigation mesh confining 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;

a constraint initialization component configured to determine constraints associated with the navigation mesh based on a given object size, the constraints being 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; and

a mesh traversal component configured to determine whether the 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;

wherein the constraints include one or both of one or more edge constraints or one or more corner constraints;

wherein an object having two spatial dimensions in the virtual space is modeled as a circle, the circle having an object radius defining the associated object size, and wherein an object having three spatial dimensions in the virtual space is modeled as a cylinder, the cylinder having an object radius defining the associated object size; and

wherein individual ones of the one or more corner constraints correspond to individual corners of the outer boundary of the navigation mesh having an internal angle greater than 180 degrees, a given corner constraint defining an arc centered at a corresponding corner and having a corner constraint radius equal to the object radius associated with the given object.

8. A method for providing a single polygonal navigation mesh in a virtual space by which objects of varying size can traverse, the method being performed by one or more processors configured to execute computer program instructions, the method comprising:

using one or more processors to provide providing a navigation mesh associated with the virtual space, the navigation mesh formed from polygonal tiles, adjacent ones of the polygonal tiles being joined along adjacent polygonal tile edges, outer boundaries of the navigation mesh confining 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;

using one or more processors to determine constraints associated with the navigation mesh based on a given object size, the constraints being 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; and

using one or more processors to determine whether the 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;

wherein the constraints include one or both of one or more edge constraints or one or more corner constraints;

wherein an object having two spatial dimensions in the virtual space is modeled as a circle, the circle having an object radius defining the associated object size, and wherein an object having three spatial dimensions in the virtual space is modeled as a cylinder, the cylinder having an object radius defining the associated object size; and

wherein individual ones of the one or more edge constraints correspond to individual polygonal tile edges that form at least a portion of the outer boundary of the navigation mesh, a given edge constraint defining a line parallel to a corresponding polygonal tile edge and spaced a distance equal to the object radius associated with the given object from the corresponding polygonal tile edge.

9. The method of claim 8 , further comprising validating individual ones of the constraints by determining whether one or more constraints adjacent to a given constraint completely encompass an area of influence associated with the given constraint, invalidated constraints being excluded as constraints associated with a corresponding object size.

10. The method of claim 8 , further comprising determining one or more new constraints associated with a choke point in the navigation mesh, the choke point being a region of the navigation mesh that is narrower than adjacent regions of the navigation mesh.

11. The method of claim 10 , wherein individual ones of the one or more new constraints are portions of one or more preexisting constraints.

12. The method of claim 10 , further comprising determining a largest object size that can traverse through the choke point.

13. The method of claim 8 , wherein determining whether the given object can traverse from a first polygonal tile of the navigation mesh to a second polygonal tile of the navigation includes determining whether there are any valid positions for the given object in the second polygonal tile.

14. A method for providing a single polygonal navigation mesh in a virtual space by which objects of varying size can traverse, the method being performed by one or more processors configured to execute computer program instructions, the method comprising:

using one or more processors to provide providing a navigation mesh associated with the virtual space, the navigation mesh formed from polygonal tiles, adjacent ones of the polygonal tiles being joined along adjacent polygonal tile edges, outer boundaries of the navigation mesh confining 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;

using one or more processors to determine constraints associated with the navigation mesh based on a given object size, the constraints being 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; and

using one or more processors to determine whether the 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;

wherein the constraints include one or both of one or more edge constraints or one or more corner constraints;

wherein an object having two spatial dimensions in the virtual space is modeled as a circle, the circle having an object radius defining the associated object size, and wherein an object having three spatial dimensions in the virtual space is modeled as a cylinder, the cylinder having an object radius defining the associated object size; and

wherein individual ones of the one or more corner constraints correspond to individual corners of the outer boundary of the navigation mesh having an internal angle greater than 180 degrees, a given corner constraint defining an arc centered at a corresponding corner and having a corner constraint radius equal to the object radius associated with the given object.