Method and device for computing a path in a game scene
AssigneeNetease (Hangzhou) Network Co., Ltd.
InventorBing Luo
Life of this patent
Estimating the term…
Abstract
A method and device for computing a path in a game scene according to embodiments of the present disclosure, comprising: dividing the game scene into a plurality of first areas; dividing each of the first areas into a plurality of convex polygons, based on features of the game scene; combining adjacent convex polygons into a plurality of second areas; computing a first path from a first point to a second point, said first path passing through a group of second areas of said plurality of second areas; and computing, based on the first path, a second path from the first point to the second point, said second path passing through a group of convex polygons of said group of second areas.
Claims9
A method for computing a path in a game scene, the path being from a point to another different point in the game scene, the method comprising:
- dividing the game scene into a plurality of first areas;
- dividing each of the first areas into a plurality of convex polygons, based on features of the game scene, wherein the features of the game scene comprise:
- geographic features and character features, wherein the step of dividing each of the first areas into a plurality of convex polygons based on the features of the game scene comprises:
- determining unreachable areas and reachable areas in each of the first areas, based on the geographic features and character features of the game scene;
- and
- dividing the reachable area in each of the first areas into a plurality of convex polygons;
- for each of the first areas, combining adjacent convex polygons of said plurality of convex polygons within the first area to obtain a plurality of second areas in the first area, such that a set of second areas are obtained for the same scene;
- computing a first path, said first path starting from a first point to a second point and passing through a group of second areas of said set of second areas;
- and
- computing a second path based on the first path, said second path starting from the first point to the second point and passing through a group of convex polygons of said group of second areas.
A device for computing a path in a game scene, the path being from a point to another different point in the game scene, the device comprising:
- a first dividing module configured to divide the game scene into a plurality of first areas;
- a second dividing module configured to divide each of the first areas into a plurality of convex polygons, based on features of the game scene, wherein the features of the game scene comprise:
- geographic features and character features, wherein the second dividing module is further configured to:
- determine unreachable areas and reachable areas in each of the first areas, based on the geographic features and character features of the game scene;
- and
- divide the reachable area in each of the first areas into a plurality of convex polygons;
- a combining module configured to, for each of the first areas, combine adjacent convex polygons of said plurality of convex polygons within the first area to obtain a plurality of second areas in the first area, such that a set of second areas are obtained for the same scene;
- a first computing module configured to compute a first path, said first path starting from a first point to a second point and passing through a group of second areas of said set of second areas;
- and
- a second computing module configured to compute a second path based on the first path, said second path starting from the first point to the second point and passing through a group of convex polygons of said group of second areas.
A non-transitory computer readable storage medium for storing a program of instructions executable by a computer to perform a process, the process being used for computing a path in a game scene, the path being from a point to another different point in the game scene, the process comprising:
- dividing the game scene into a plurality of first areas;
- dividing each of the first areas into a plurality of convex polygons, based on features of the game scene, wherein the features of the game scene comprise:
- geographic features and character features, wherein the step of dividing each of the first areas into a plurality of convex polygons based on the features of the game scene comprises:
- determining unreachable areas and reachable areas in each of the first areas, based on the geographic features and character features of the game scene;
- and
- dividing the reachable area in each of the first areas into a plurality of convex polygons;
- for each of the first areas, combining adjacent convex polygons of said plurality of convex polygons within the first area to obtain a plurality of second areas in the first area, such that a set of second areas are obtained for the same scene;
- computing a first path, said first path starting from a first point to a second point and passing through a group of second areas of said set of second areas;
- and
- computing a second path based on the first path, said second path starting from the first point to the second point and passing through a group of convex polygons of said group of second areas.
Dependencies are inferred from the claim text.