Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Efficient path-finding method and system based on the same cost grids

A grid and overhead technology, applied in the Internet field, can solve problems such as inefficiency and difficulty in meeting the implementation requirements of virtual reality application services, and achieve the effects of speeding up pathfinding, saving computing overhead, and reducing overhead

Active Publication Date: 2014-11-19
FOCUS TECH
View PDF4 Cites 18 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0009] This method has a disadvantage: if there are many grid points with a small total cost value in the current area, even if the target point is in front of you, those points with a small total mobile cost value will be judged first, resulting in the stability of this A* algorithm. But it is not efficient, and it is difficult to meet the implementation requirements of virtual reality application services on the Internet

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
  • Efficient path-finding method and system based on the same cost grids
  • Efficient path-finding method and system based on the same cost grids
  • Efficient path-finding method and system based on the same cost grids

Examples

Experimental program
Comparison scheme
Effect test

example 1

[0140] example 1: Figure 12 , the method of the present invention and prior art application effect comparison diagram (example 1).

[0141] In this example, the A* algorithm has gone through 81 steps to find the target, and the method of the present invention has gone through 57 steps, including the optimization from the starting point to the first and second inflection points, wherein, the 81 steps of A* include the calculation of each node F-values ​​work where:

[0142] F: The total mobile cost of the current node, which is equal to G+H.

[0143] G: The cost of movement from the starting point to the current node on the grid.

[0144] H: The estimated cost of moving the current node to the end point.

[0145] However, this method only needs to calculate the cost value in the 13-step optimization process.

example 2

[0146] Example 2: Figure 13 , the method of the present invention and prior art application effect comparison diagram (example 2).

[0147] In this example, the A* algorithm has gone through 88 steps and draws the conclusion that the destination cannot be reached, while this method uses 11 steps to draw the conclusion that the destination cannot be reached. Among them, the 88th step of the A* algorithm calculates the F value of the node. However, since this method does not reach the destination, there is no optimization process, and there is no need to calculate the cost value.

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 discloses an efficient path-finding method and system based on the same cost grids. The system comprises an initiating module, a path-finding subsystem and a path combining and optimizing module. The initiating module is used for dividing a real map for path-finding into a plurality of grids which are the same in size, and determining the initial point position (x0, y0) and the target point position (xn, yn) in the form of coordinates. The path-finding subsystem is used for finding a path from the initial point to the target point. The path combining and optimizing module is used for calculating the length of a backtracking path, and selecting the shortest path as the final advancing path through comparison between the length of the backtracking path and the length of paths between every two adjacent inflection points in the path to be selected. The method includes the first step of initiation, the second step of path-finding and the third step of path optimization. By means of the method and system, the path-finding speed is increased, cost of a server or a client side is reduced, and path-finding efficiency is larger than A*.

Description

technical field [0001] The invention belongs to the field of the Internet, and in particular relates to a method and system for efficient pathfinding based on the same overhead grid. Background technique [0002] At present, due to the improvement of Internet transmission speed, a large number of virtual reality services and applications are gradually expanding on the Internet, such as virtual exhibition halls, virtual museums, virtual tours, 3D games, etc. These application services must use the wayfinding system to help mobile units bypass obstacles to reach the destination. Especially in virtual reality applications with multiplayer online versions, such as 3D games, the pathfinding system needs to consume a large amount of computing resources of the server. [0003] Therefore, the optimization of the pathfinding algorithm can greatly improve the efficiency of the server and increase the load capacity of a single server, which is very helpful to the normal operation of t...

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
IPC IPC(8): G06F17/30G06Q10/04
CPCG06F16/954G06Q10/047
Inventor 陈阳卜雄剑涂敏飞
Owner FOCUS TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com