Eureka AIR delivers breakthrough ideas for toughest innovation challenges, trusted by R&D personnel around the world.

Path-finding method for optimal path

An optimal path and shortest path technology, applied in special data processing applications, instruments, electrical digital data processing, etc., can solve problems such as twists and turns, poor player experience, and affect user enthusiasm for use, so as to improve use enthusiasm Effect

Active Publication Date: 2007-07-11
SHENZHEN TENCENT COMP SYST CO LTD
View PDF0 Cites 33 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0010] However, the shortest path calculated by the above method has the following disadvantages: since the entire scene is composed of several triangular meshes of different shapes, even if there is no obstacle blocking between two points, it can be reached in a straight line, then, through the above-mentioned method The shortest path calculated by some methods still needs to pass through the midpoints of several triangular meshes in sequence, so the shortest path will appear zigzag. Therefore, in a two-dimensional or three-dimensional computer game, when the player makes an object from When moving from one point to another point, even if there is no obstacle in the middle to reach it in a straight line, the shortest path taken by the object is a winding line, which does not reflect the optimality of the shortest path and makes the player experience bad. , affecting user enthusiasm for using

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Path-finding method for optimal path

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0028] In order to make the advantages and features of the present invention clearer, the present invention will be further described in detail below in conjunction with exemplary embodiments with reference to the accompanying drawings.

[0029] The present invention will be described in detail by taking the method of finding the optimal path between two points in the scene of a computer three-dimensional game as an example. The initial shortest path obtained according to the method of the prior art does not fully reflect the optimality of the shortest path, because even if there is a straight line between two points, the shortest path is still meandering. For this, the present invention proposes a An improved method, smoothing the initial shortest path calculated by the prior art, that is, replacing the meandering path with a straight-line reachable path, the specific processing flow is shown in Fig. 1, and Fig. 1 is to find the optimal path according to the present invention ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a optimal path searching method. It creates typological chart made of spot and lines of the scenic spot, computing the initial shortest path of the designated two points in the typological chart, with the initial shortest path being formed by serial passed spots and lines, sequentially judging the direct linear arrival from the start point of the initial shortest path to the continuous spots, till the farthest spot away from the start point, and judging whether the farthest spot is the final point or not, if not, regarding the farthest point as the start point and return to execute this step, otherwise, sequentially connecting two points between them as the optimal path output. It provides a smooth treatment for the shortest path, substituting the zigzag path by the line reachable path, representing the shortest path optimization, improving the activeness of the user.

Description

technical field [0001] The invention relates to a method for calculating a path, in particular to a method for finding an optimal path between any two points in a two-dimensional or three-dimensional grid. Background technique [0002] In two-dimensional and three-dimensional computer games, there are many scenes, such as houses, corridors in houses, land, ocean, etc., for these scenes, the computer describes them in the form of grids, that is, a scene is composed of several adjacent Generally, triangles are used as the basic grid. In two-dimensional or three-dimensional space, any triangle can be determined as long as the coordinates of the three vertices are given, especially in a three-dimensional game, the computer system can save the scene by saving the three-dimensional coordinates of the three vertices of the triangle. Therefore, no matter how complex a scene is, it is composed of several triangular meshes of different shapes. How many triangular meshes a scene is d...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06F19/00
Inventor 王麒
Owner SHENZHEN TENCENT COMP SYST CO LTD
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Eureka Blog
Learn More
PatSnap group products