CN108815850B

CN108815850B - Method and client for controlling path finding of analog object

Info

Publication number: CN108815850B
Application number: CN201810621936.4A
Authority: CN
Inventors: 林瑞柠
Original assignee: Tencent Technology Shenzhen Co Ltd
Current assignee: Tencent Technology Shenzhen Co Ltd
Priority date: 2018-06-15
Filing date: 2018-06-15
Publication date: 2021-01-05
Anticipated expiration: 2038-06-15
Also published as: CN108815850A

Abstract

The embodiment of the invention discloses a method for controlling the way searching of an analog object, which comprises the following steps: acquiring a node position according to a first position and a second position of the simulation object, wherein the first position represents a starting position of the simulation object, and the second position represents an end position of the simulation object; determining a first routing path according to the first position and the node position; controlling the simulation object to move from the first position to the node position according to the first routing path; determining a second routing path according to the node position and the second position; and controlling the simulation object to move from the node position to the second position according to the second routing path. The embodiment of the invention also discloses a client. In the embodiment of the invention, in the process of simulating the path finding of the object, the whole path finding path is divided into a plurality of path finding paths, the length of the path finding paths is reduced, and the calculation amount can be effectively reduced when each path finding path is calculated, so that the performance cost is reduced, and the execution efficiency of a client is improved.

Description

Method and client for controlling path finding of analog object

Technical Field

The invention relates to the technical field of computers, in particular to a method and a client for controlling the path finding of a simulation object.

Background

With the continuous development of internet technology, experience strategy games (SLG) are becoming an attractive entertainment item. SLG provides players with an environment that can deal with more complex things by thinking about the problem, allowing players to freely control, manage and use people or things in the game, and by this free means, and players thinking about fighting against enemies, to achieve the goals required by the game.

In order for the combat effect to be better performed during the course of the SLG combat, hundreds of soldiers in the hero are typically required to combat together. And each soldier uses the A-algorithm to search for enemies, and the A-algorithm can estimate the distance from the current node to the terminal point, so that the path-finding path with the lowest cost is obtained.

However, it is feasible for one soldier to use the a-algorithm to find enemies, but the use of the a-algorithm by hundreds of soldiers to find enemies simultaneously consumes a lot of computing resources, thereby causing excessive performance overhead, which is difficult to realize for the client, and causing the battle picture to be stuck.

Disclosure of Invention

The embodiment of the invention provides a method and a client for controlling the way finding of a simulation object, wherein in the process of the way finding of the simulation object, the whole way finding path is divided into a plurality of way finding paths, the length of the way finding paths is reduced, and the calculation amount can be effectively reduced when each way finding path is calculated, so that the performance cost is reduced, and the execution efficiency of the client is improved.

In view of the above, a first aspect of the present invention provides a method for controlling a way-finding of an analog object, including:

acquiring a node position according to a first position and a second position of a simulation object, wherein the first position represents a starting position of the simulation object, and the second position represents an end position of the simulation object;

determining a first routing path according to the first position and the node position;

controlling the simulation object to move from the first position to the node position according to the first routing path;

determining a second routing path according to the node position and the second position;

and controlling the simulation object to move from the node position to the second position according to the second routing path.

A second aspect of the present invention provides a client, comprising:

the acquisition module is used for acquiring a node position according to a first position and a second position of a simulation object, wherein the first position represents a starting position where the simulation object is located, and the second position represents an end position where the simulation object is located;

a determining module, configured to determine a first routing path according to the first position and the node position obtained by the obtaining module;

the control module is used for controlling the simulation object to move from the first position to the node position according to the first routing path determined by the determination module;

the determining module is further configured to determine a second routing path according to the node position and the second position obtained by the obtaining module;

the control module is further configured to control the simulation object to move from the node position to the second position according to the second routing path determined by the determination module.

A third aspect of the present invention provides a client, comprising: a memory, a transceiver, a processor, and a bus system;

wherein the memory is used for storing programs;

the processor is used for executing the program in the memory and comprises the following steps:

controlling the simulation object to move from the node position to the second position according to the second routing path;

the bus system is used for connecting the memory and the processor so as to enable the memory and the processor to communicate.

A fourth aspect of the present invention provides a computer-readable storage medium having stored therein instructions, which, when run on a computer, cause the computer to perform the method of the above-described aspects.

According to the technical scheme, the embodiment of the invention has the following advantages:

the embodiment of the invention provides a method for controlling a simulation object to seek a way, which comprises the steps that a client can obtain a node position according to a first position and a second position of a simulation object, a first seeking path is determined according to the first position and the node position, and then the simulation object is controlled to move from the first position to the node position according to the first seeking path. The client side continues to determine a second routing path according to the node position and the second position, and then controls the simulation object to move from the node position to the second position according to the second routing path. By the mode, in the process of searching the path of the simulation object, the whole path searching path is split into the plurality of path searching paths, the length of the path searching paths is reduced, and the calculation amount can be effectively reduced when each path searching path is calculated, so that the performance cost is reduced, and the execution efficiency of the client is improved.

Drawings

FIG. 1 is a schematic diagram of an architecture of a simulated object routing system according to an embodiment of the present invention;

FIG. 2 is a schematic flow chart of simulated object routing according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of an interface for simulating object routing according to an embodiment of the present invention;

FIG. 4 is a schematic flow chart of the path finding of the simulation object by the A-star algorithm in the embodiment of the present invention;

FIG. 5 is a diagram of an embodiment of a method for controlling routing of a dummy object according to an embodiment of the present invention;

FIG. 6 is a diagram illustrating controlling fractional routing of a simulated object according to an embodiment of the present invention;

FIG. 7 is a diagram illustrating controlling simulated object routing according to an embodiment of the present invention;

FIG. 8 is a diagram of an embodiment of determining a target seek range according to an embodiment of the present invention;

FIG. 9 is a schematic diagram of obtaining a distance sequence by binary sorting according to an embodiment of the present invention;

FIG. 10 is a diagram illustrating an embodiment of obtaining distance sequences using a binary tree;

FIG. 11 is a diagram illustrating a comparison between a binary ordering method and a binary ordering tree for obtaining a distance sequence according to an embodiment of the present invention;

FIG. 12 is a diagram of an embodiment of batching way-finding requests according to an embodiment of the present invention;

FIG. 13 is a diagram of an embodiment of a client in an embodiment of the present invention;

FIG. 14 is a schematic diagram of another embodiment of the client in the embodiment of the present invention;

FIG. 15 is a schematic diagram of another embodiment of the client according to the embodiment of the present invention;

fig. 16 is a schematic structural diagram of a client according to an embodiment of the present invention.

Detailed Description

The terms "first," "second," "third," "fourth," and the like in the description and in the claims, as well as in the drawings, if any, are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used is interchangeable under appropriate circumstances such that the embodiments of the invention described herein are, for example, capable of operation in sequences other than those illustrated or otherwise described herein. Furthermore, the terms "comprises," "comprising," and "having," and any variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method, system, article, or apparatus that comprises a list of steps or elements is not necessarily limited to those steps or elements expressly listed, but may include other steps or elements not expressly listed or inherent to such process, method, article, or apparatus.

It should be understood that the present invention can be applied to interactive applications, such as a strategic Game (SLG), a Multiplayer Online Battle Arena (MOBA), and a Role Playing Game (RPG). Such games often have combat scenarios that require "heroes" to have hundreds of "soldiers" in the game for better combat performance. However, the server is forced to do fighting calculation for hundreds of people, so that the scheme divides the fighting of hero and soldier into two processes which are respectively executed by the server and the client. For convenience of introduction, please refer to fig. 1, where fig. 1 is a schematic diagram of an architecture of a simulated object routing system according to an embodiment of the present invention, and as shown in the figure, a server calculates a plurality of enemy paths of "hero", and a client simulates the enemy paths of all "soldiers". It can be understood that the client can be deployed on the terminal device, and enemy seeking paths of heroes and soldiers are displayed through a display interface of the terminal device.

It is understood that the terminal devices include, but are not limited to, tablet computers, notebook computers, mobile phones, and personal computers.

The client side adopts the A star algorithm when simulating the 'soldier' to seek the enemy, the fighting process of the 'soldier' can be simulated really, the playability of hundreds of people in battle is met, and the expressive force of the fighting effect is enhanced. Referring to fig. 2, fig. 2 is a schematic flow chart illustrating a simulation object path finding process in an embodiment of the present invention, where, as shown in the figure, the simulation object in the present invention may be an "soldier", specifically:

in the step A1, each 'soldier' in the 'hero A' team searches each 'soldier' in the 'hero B' team, wherein the 'hero A' and the 'hero B' belong to an enemy relationship;

in the step A2, whether the target 'soldier' in the 'hero B' team is found within a range is judged, if yes, the step A3 is carried out, and if not, the target 'hero' in the 'hero B' team is directly used as the target;

in the step A3, the 'soldiers' in the 'hero A' team move to the positions of the target 'soldiers' in the 'hero B' team, and an A star algorithm is used for seeking a path in the moving process;

in step A4, the 'soldiers' in the 'hero A' team start to attack the target 'soldiers' in the 'hero B' team;

in step a5, it is determined whether the target has died, and if so, the "soldier" in the "hero a" team may begin searching for another "soldier" in the "hero B" team.

Referring to fig. 3, fig. 3 is a schematic diagram of an interface for simulating object routing in an embodiment of the present invention, where black and white represent two different teams, respectively, and a large circle represents "hero" and a small circle represents "soldier", as shown in the figure. The whole game map can be divided according to square grids, and "hero" and "soldier" both have respective point location grid regions, and refer to the flow shown in fig. 4 in the moving process, fig. 4 is a schematic flow diagram of a simulation object in the embodiment of the present invention for finding a path by using an a-star algorithm, as shown in the figure, wherein the simulation object may be a "soldier", specifically, an enemy finding process of the "soldier" is taken as an example:

in step B1, firstly, the soldier starts to seek enemy by using the A star algorithm;

in the step B2, whether the soldier finds the optimal enemy searching path through the star A algorithm is judged, if yes, the step B4 is carried out, otherwise, the step B3 is carried out;

in step B3, in the event that the "soldier" does not find an optimal enemy seeking path, other enemy seeking paths may be used;

in step B4, when the "soldier" finds an optimal path, or when other enemy-seeking paths are found, the "soldier" may move according to the nodes on the enemy-seeking path;

in the step B5, whether the soldier finishes moving according to the nodes on the enemy searching path is judged, if yes, the step B1 is carried out, namely the soldier starts a new round of enemy searching by using an A star algorithm, and if not, the step B6 is carried out;

in the step B6, whether collision exists in the process of moving the soldier is judged, if yes, the step B1 is carried out, namely the soldier starts to search for an enemy in a new round by using an A star algorithm, and if not, the step B7 is carried out;

in step B7, it is determined whether the position of the "soldier" belongs to the attack range, if so, the "soldier" attacks, otherwise, the "soldier" moves according to the next node of the enemy-seeking path.

Referring to fig. 5, a method for controlling a way-finding of a dummy object according to the present invention is described below from the perspective of a client, where an embodiment of the method for controlling a way-finding of a dummy object according to the present invention includes:

101. acquiring a node position according to a first position and a second position of the simulation object, wherein the first position represents a starting position of the simulation object, and the second position represents an end position of the simulation object;

in this embodiment, the client acquires the simulation object in the scene of the interactive application program, where the simulation object may be a "soldier" role in the scene of the interactive application program, and the simulation object belongs to the same team. Referring to fig. 6, fig. 6 is a schematic diagram illustrating the control of the fractional routing of the simulation object according to the embodiment of the present invention, as shown in the drawing, the small square indicated by S1 is the starting position of the simulation object, i.e., the first position, and the small square indicated by S3 is the ending position of the last battle of the simulation object, i.e., the second position. The small squares indicated by S2 are node positions.

102. Determining a first routing path according to the first position and the node position;

in this embodiment, the client divides the entire seek path from the first location to the second location into multiple seek paths for calculation. It should be understood that the present embodiment will be described by taking the division into two routing paths as an example, however, in practical applications, the present invention should not be construed as being limited thereto, and the whole routing path may also be divided into three, four or more paths.

The client may first calculate a first routing path by using an a-star algorithm according to the first location and the node location, where the first routing path is a routing path with the lowest cost from the first location to the node location.

103. Controlling the simulation object to move from the first position to the node position according to the first routing path;

in this embodiment, the client controls the simulation object to move according to the calculated first routing path, that is, to move from the first position to the node position.

104. Determining a second routing path according to the node position and the second position;

in this embodiment, the client calculates a second routing path by using an a-star algorithm according to the node position and the second position, where the second routing path is a routing path with the lowest cost from the node position to the second position.

105. And controlling the simulation object to move from the node position to the second position according to the second routing path.

In this embodiment, the client controls the simulation object to move according to the calculated second routing path, that is, to move from the node position to the second position.

Optionally, on the basis of the embodiment corresponding to fig. 5, in a first optional embodiment of the method for controlling routing of a simulation object according to the embodiment of the present invention, acquiring a node position according to the first position and the second position of the simulation object may include:

acquiring N sub-node positions according to the first position and the second position of the simulation object, wherein N is an integer greater than 1;

after acquiring the node position according to the first position and the second position of the simulation object, the method may further include:

determining (N +1) routing paths according to the first position and the N child node positions;

and controlling the simulation object to move from the first position to the second position according to the (N +1) routing paths.

In this embodiment, a case where the node position includes N child node positions will be described. First, the client needs to obtain a first location and a second location. And then finding N child node positions according to the path interception rule. Assuming that the path intercept rule intercepts a path for every 10 small cells, starting from the first location, each child node location is found in turn on the way to the second location. For example, the best route from the first location to the second location passes through 38 small grids, and the path interception rule intercepts a path for every 10 small grids, so that 3 child node locations can be obtained, and finally 4 routing paths are generated. For convenience of description, table 1 will describe the relationship between the positions of the sub-nodes and the routing path, taking the example that the optimal route from the first position to the second position passes through 38 small grids.

TABLE 1

Path serial number	Starting point	End point	Path length of seek path
				1	First position	Sub node position number 1	10 small lattices
2	Sub node position number 1	Number 2 child node location	10 small lattices
				3	Number 2 child node location	Sub node position of No. 3	10 small lattices
4	Sub node position of No. 3	Second position	8 small lattices

As shown in the figure, there are 3 positions of the child nodes in total, and finally 4 routing paths are formed.

Secondly, in the embodiment of the present invention, a case that the node position includes a plurality of child node positions is introduced, the client may determine (N +1) routing paths according to the first position and the N child node positions, then control the simulation object to sequentially perform the segment routing according to the (N +1) routing paths, and finally control the simulation object to move from the first position to the second position. By the mode, one path finding can be divided into multiple path finding under the condition of ensuring normal path finding performance, and the length of a path finding path can be reduced. Thereby improving the efficiency of path computation.

Optionally, on the basis of the embodiment corresponding to fig. 5, in a second optional embodiment of the method for controlling routing of a simulation object according to the embodiment of the present invention, before acquiring the node position according to the first position and the second position of the simulation object, the method may further include:

acquiring the horizontal distance between the first position and the second position and the vertical distance between the first position and the second position;

determining a horizontal length according to the horizontal distance and a preset horizontal coefficient, and determining a vertical length according to the vertical distance and a preset vertical coefficient, wherein the horizontal length and the vertical length are used for determining a first area range;

if the first area range is smaller than a second area range, determining the first area range as a target route searching range, wherein the second area range is a preset area range;

and if the first area range is larger than the second area range, determining the second area range as a target routing range.

In this embodiment, the time-consuming factor in the simulated object path finding is that the number of blocking is large, so that the path finding is performed on most of the maps. As shown in fig. 7, fig. 7 is a schematic diagram of controlling the simulated object routing in the embodiment of the present invention, and taking the routing range of a "soldier" in a "white team" as an example, if the routing range is not limited, the "soldier" will probably go to the position of the "soldier" in a "black team" by a large circle along the direction indicated by the arrow in fig. 7. However, the 'soldier' does not need to seek a way on the whole map, two teams are in an array, the 'soldier' does not need to go around a long way, and the normal moving range is only in a red dotted frame. Therefore, the path searching range is limited, and the final target path searching range is obtained.

Referring to fig. 8, fig. 8 is a schematic diagram of an embodiment of determining a target seek range in an embodiment of the present invention, as shown in the figure, a first position (assumed to be a position of a white point) and a second position (assumed to be a position of a black point) are first obtained, then a horizontal distance between the two positions is obtained, that is, W is obtained, and a vertical distance between the two positions is obtained, that is, H is obtained. And then adding coefficient adjustment, wherein the coefficients comprise a preset horizontal coefficient and a preset vertical coefficient, and assuming that the preset horizontal coefficient and the preset vertical coefficient are both K, the preset horizontal coefficient and the horizontal distance can be added to obtain a horizontal length (W + K), or the preset horizontal coefficient and the horizontal distance are multiplied to obtain the horizontal length. And adding the preset vertical coefficient and the vertical distance to obtain the vertical length (H + K), or multiplying the preset vertical coefficient and the vertical distance to obtain the vertical length.

It is understood that K may be set to 10, and the second area range may be set to 625, and in practical applications, the K may also be adjusted according to the situation, and is not limited herein.

And obtaining a first area range according to the horizontal length and the vertical length, comparing the first area range with the second area range, and taking a smaller area of the first area range and the second area range as a target route searching range.

Secondly, in the embodiment of the present invention, the client may further calculate to obtain a first area range according to the first position and the second position, compare the first area range with a preset second area range, determine the first area range as the target route searching range if the first area range is smaller than the second area range, and otherwise determine the second area range as the target route searching range if the first area range is larger than the second area range. Through the method, a reasonable area can be limited when the routing path is calculated, and due to the fact that the whole map is very large, if the whole map is taken as the path calculation range by the simulation object, the calculation amount is too large, and therefore the calculation amount can be limited through comparison with the second area range, and performance of the client is improved.

Optionally, on the basis of the second embodiment corresponding to fig. 5, in a third optional embodiment of the method for controlling routing of a simulation object according to the embodiment of the present invention, acquiring a node position according to the first position and the second position of the simulation object may include:

calculating a third position in a target path-finding range by adopting an A star algorithm according to the first position and the second position of the simulation object, wherein the third position is the next position to which the simulation object moves from the first position;

calculating a fourth position in the target path-finding range by adopting an A star algorithm according to the third position and the second position of the simulation object, wherein the fourth position is a next position to which the simulation object moves from the third position;

if the position calculation times reach a preset calculation threshold, determining the fourth position as the node position;

and if the position calculation times do not reach the preset calculation threshold, calculating to obtain a fifth position in the target route finding range by adopting an A star algorithm according to the fourth position and the second position of the simulation object, wherein the fourth position is the next position to which the simulation object moves from the third position.

In this embodiment, a method for calculating the node position by using the a-star algorithm at the client will be described. The A star algorithm is one of the popular heuristic search algorithms and is widely applied to the field of path optimization. The method is characterized in that global information is introduced when each possible node in the shortest path is checked, the distance between the current node and the end point is estimated, and the estimated distance is used as a measure for evaluating the possibility that the node is positioned on the shortest path.

Specifically, the client acquires a starting point and a terminal of the simulation object, namely a first position and a second position. And then, calculating to obtain an optimal third position in the target path finding range by adopting an A star algorithm. For ease of understanding, a small lattice is introduced here for illustration. Assuming that the coordinates of the first position are (1,1), the coordinates of eight positions around the first position can be respectively expressed as (0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1) and (2,2), assuming that the coordinates of the second position are (10,10), the a-star algorithm can be used to calculate that (2,1) is the closest point to the second position, and then (2,1) is taken as the third position. Next, it is determined from the third position (2,1) which position among the eight positions in the periphery is closest to the second position, and the eight positions here can be represented as (1,0), (2,0), (3,0), (1,1), (3,1), (1,2), (2,2), and (3,2), respectively. Using the a-star algorithm, a point (3,1) closest to the second position can be calculated, and then (3,1) is taken as the fourth position.

And by analogy, counting the number of times is needed to calculate the position every time, namely the number of times of calculating the position is obtained, and if the number of times of calculating the position reaches a preset calculation threshold, the position obtained by the last calculation is taken as the position of the node. Otherwise, if the position calculation times do not reach the preset calculation threshold, the A star algorithm is continuously adopted to calculate the next position.

In the embodiment of the present invention, the client may calculate to obtain the node position by using an a-star algorithm, that is, first, according to the first position and the second position of the simulation object, a third position is calculated in the target routing range by using the a-star algorithm, and then a fourth position is continuously obtained, and if the number of times of calculating the position at this time reaches a preset calculation threshold, the fourth position is determined as the node position. Otherwise, the node position is continuously searched. Through the method, the client calculates the next optimal position by using the A star algorithm every time the client passes through one position, and finally a path with the minimum cost is formed, so that the performance of the client is improved. In addition, the whole routing path can be segmented according to the position calculation times, so that the calculation amount of each segment of path is controlled within a reasonable range.

Optionally, on the basis of the embodiment corresponding to fig. 5, in a fourth optional embodiment of the method for controlling a simulated object to seek a way according to the embodiment of the present invention, determining the first path-seeking path according to the first position and the node position may include:

acquiring eight first candidate positions around the first position as the center;

acquiring a first distance value corresponding to each first position to be selected according to the distance between each first position to be selected and the node position;

generating a first distance sequence according to a first distance value corresponding to each first to-be-selected position, wherein the first distance sequence is an increasing sequence or a decreasing sequence;

selecting a position to be selected corresponding to the minimum distance value from the first distance sequence as a third position, wherein the third position is the next position to which the simulation object moves from the first position;

taking the third position as the center to obtain eight second peripheral positions to be selected;

acquiring a second distance value corresponding to each second candidate position according to the distance between each second candidate position and the node position;

generating a second distance sequence according to a second distance value corresponding to each second candidate position and a first distance value corresponding to each first candidate position, wherein the second distance sequence is an increasing sequence or a decreasing sequence;

selecting a position to be selected corresponding to the minimum distance value from the second distance sequence as a fourth position, wherein the fourth position is a next position to which the simulation object moves from the third position;

and determining a first path-seeking path according to the first position, the third position and the fourth position.

In this embodiment, the idea of introducing the open list may be to acquire the path finding path by using the open list. Firstly, the first position is used as the center to obtain eight first candidate positions around the center, and each first candidate position has a certain distance from the node position, so that a first distance value corresponding to each first candidate position can be obtained. And putting the first distance value into a table to be verified, and then obtaining a first distance sequence by adopting a sorting algorithm, wherein the first distance sequence is an increasing sequence or a decreasing sequence.

And the client directly extracts the minimum distance value from the first distance sequence, the position corresponding to the minimum distance value is the third position, and theoretically, the distance from the first position to the third position is the optimal distance. And then, taking the third position as the center to obtain eight second candidate positions around the third position, similarly, obtaining a second distance value corresponding to each second candidate position according to the distance between each second candidate position and the node position, then adding the second distance value corresponding to each second candidate position into the first distance sequence, and adopting a sorting algorithm to re-sort the first distance sequence to generate a second distance sequence.

And the client directly extracts the minimum distance value from the second distance sequence, the position corresponding to the minimum distance value is the fourth position, and theoretically, the distance from the third position to the fourth position is the optimal distance. The client may then connect the first location, the third location and the fourth location to form the first seek path, or to form a portion of the first seek path.

It is understood that the method for obtaining the second routing path or more routing paths is similar to the above method, and is not described herein again.

Secondly, the embodiment of the invention provides an idea of opening a list, and the minimum distance value obtained each time is put into the distance sequence by adopting the A star algorithm, so that the distance value can be directly taken out of and put into the distance sequence. By the mode, the data are put in and taken out by utilizing the open list, and the time complexity can be effectively reduced.

Optionally, on the basis of the fourth embodiment corresponding to fig. 5, in a fifth optional embodiment of the method for controlling a simulated object to seek a way, according to a second distance value corresponding to each second candidate position and a first distance value corresponding to each first candidate position, generating a second distance sequence may include:

and sorting the second distance value corresponding to each second position to be selected and the first distance value corresponding to each first position to be selected by adopting a binary sorting method to obtain a second distance sequence.

In this embodiment, how to obtain the second distance sequence by the binary sorting method will be described. The binary sorting is an insertion sorting algorithm for improving the insertion sorting by using the idea of binary method, and elements of the designated index can be quickly positioned by using the characteristics of an array. The dichotomy sorting method is that when the ith element is inserted, the former element is halved and is compared with the middle element, if the former element is smaller than the middle element, the latter element is halved again, otherwise, the latter element is halved until the left element is larger than the right element, then all elements between the 1 st position of the ith element and the target position are moved backwards, and then the ith element is placed on the target position.

For easy understanding, please refer to fig. 9, fig. 9 is a schematic diagram of obtaining a distance sequence by using a binary sorting method according to an embodiment of the present invention, and as shown in the figure, assuming that an existing distance sequence is "134710111316", at this time, a second distance value 8 is added to the queue, the original distance sequence is halved by using the binary sorting method, assuming that a middle value of a first halving is 7, the sizes of 8 and 7 are determined, obviously 8 is greater than 7, then the sorting of the right half is performed, then the halving of "10111316" is performed, assuming that a middle value of a second halving is 11, the sizes of 8 and 11 are determined, obviously 8 is smaller than 11, then the sorting of the left half is performed, then the halving of "1011" is performed, assuming that a middle value of a third halving is 10, the sizes of 8 and 10 are determined, obviously 8 is smaller than 10, then 8 may be placed at the position of 10, and "10111316" is shifted backward, thereby generating an ordered second distance sequence.

The time complexity of binary ordering includes comparison, insertion, and extraction. Wherein, the middle value is compared, and then the first half or the second half is compared respectively, and the time complexity is represented as o (logn). The latter values are shifted backwards in time, the time complexity of which is denoted o (n). The last or first value in the fetch list is the minimum value box, whose time complexity is denoted as o (1).

In this embodiment of the present invention, the client may use a binary sorting method to sort the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position, so as to obtain a second distance sequence. By the mode, when the ith element of the sequence to be ranked is inserted, the previous sequence is ordered, so that the time complexity can be reduced by searching the position of the ith element by using a binary ranking method, and the secondary searching efficiency is improved.

Optionally, on the basis of the fourth embodiment corresponding to fig. 5, in a sixth optional embodiment of the method for controlling a simulated object to seek a way, according to a second distance value corresponding to each second candidate position and a first distance value corresponding to each first candidate position, generating a second distance sequence may include:

and sorting the second distance value corresponding to each second to-be-selected position and the first distance value corresponding to each first to-be-selected position by adopting a binary sorting tree to obtain a second distance sequence.

In this embodiment, the client may sort each distance value by using a binary sort tree, and finally obtain a distance sequence. And in the sorting process, arranging the first distance value corresponding to each first to-be-selected position obtained at the previous time and the second distance value corresponding to each second to-be-selected position obtained at the current time.

For convenience of introduction, please refer to fig. 10, fig. 10 is a schematic diagram of obtaining distance sequences by using a binary ordering tree according to an embodiment of the present invention, and how to order data by using binary ordering numbers will be described below with reference to fig. 10. The maximum key is recorded by using a large top heap, and the maximum record can be quickly selected from disorder. With a small top heap to record the minimum key, the minimum record can be quickly selected from the unordered. Taking the data corresponding to fig. 10 as an example, it is assumed that a shaping array a [ ] [ {16,7,3,20,17,8}, is given and subjected to heap ordering. A complete binary tree is first constructed from the array elements as shown in step one. And then constructing an initial heap, and adjusting from the last non-leaf node to obtain the binary tree shown in the step two. 20 and 16 resulted in 16 not meeting the properties of the stack and therefore required readjustment. After adjustment, the initial heap shown in step three of 10 is obtained, that is, each adjustment is to select the largest one from the parent node, the left child node and the right child node to exchange with the parent node, and if the child node which can be exchanged after the exchange does not meet the property of the heap, the exchanged child node needs to be adjusted again after each exchange. Sorting can be performed after the initial heap is available. At this point 3 is at the top of the heap and the nature of the less than full heap requires further adjustment until the heap is produced as shown in step four. So that the whole interval is ordered.

In summary, the temporal complexity of the binary ordering tree includes compare, insert, and fetch. The comparison process needs to be compared with the parent node to the root node, and the time complexity is represented as o (logn). The insertion is directly placed at the end of the binary tree, with the time complexity denoted as o (1). The top position is taken out, but the top position is kept to be the minimum value after the top position is taken out, so the time complexity is expressed as o (logn).

In this embodiment of the present invention, the client may use a binary sorting tree to sort the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position, so as to obtain a second distance sequence. By the mode, the binary sorting tree is stored in a chain mode, the advantage that the link storage structure does not need to move elements when insertion and deletion operations are executed is kept, only the link pointer needs to be modified after the proper insertion and deletion positions are found, and therefore time complexity can be reduced by using the binary sorting tree to search data, and slave search efficiency is improved.

Optionally, on the basis of the fifth or sixth embodiment corresponding to fig. 5, in a seventh optional embodiment of the method for controlling a way-finding of a simulation object provided in the embodiment of the present invention, the method may further include:

if the target path searching range is larger than the preset path searching area, a step of adopting a binary sorting tree to sort a second distance value corresponding to each second position to be selected and a first distance value corresponding to each first position to be selected to obtain a second distance sequence is carried out, wherein the target path searching range is the range of the simulation object which can be searched;

and if the target route searching range is smaller than the preset route searching area, sequencing a second distance value corresponding to each second position to be selected and a first distance value corresponding to each first position to be selected by adopting a binary sequencing method to obtain a second distance sequence.

In this embodiment, two schemes, namely a binary sorting method and a binary sorting tree, can be reasonably selected according to actual requirements. This depends on the size of the target routing range, since the binary sorting method is exponentially ascending, and the binary sorting tree is log ascending, and there is a cross point between the binary sorting method and the binary sorting tree, and the cross point is a preset routing area. That is, when the target seek range is smaller than the preset seek area, it is preferable to generate the distance sequence by using a binary sorting tree. When the target routing range is larger than the preset routing area, the binary sorting method is preferably used for generating the distance sequence. When the target routing range is equal to the preset routing area, one of the target routing range and the preset routing area can be selected arbitrarily.

After multiple tests, taking 100 "soldiers" seek as an example, in different seek ranges, a schematic diagram of comparing a binary sorting method with a binary sorting tree is shown in fig. 11, please refer to fig. 11, fig. 11 is a schematic diagram of comparing a distance sequence obtained by using the binary sorting method and the binary sorting tree in the embodiment of the present invention, and a seek area of a cross point of the binary sorting method and the binary sorting tree is 625(25 × 25), so when the number of lattices in a target seek range is less than 625, the binary sorting method is used, otherwise, the binary sorting tree is used.

Further, in the embodiment of the present invention, the target routing range may be compared with a preset routing area, if the target routing range is smaller than the preset routing area, a binary sorting tree is selected to generate a distance sequence, and if the target routing range is larger than the preset routing area, a binary sorting method is selected to generate the distance sequence. By the method, the sorting method with lower performance consumption can be selected according to actual conditions, so that the practicability of the scheme is enhanced, and the performance of the client side is improved.

Optionally, on the basis of the embodiment corresponding to fig. 5, in an eighth optional embodiment of the method for controlling routing of a simulation object according to the embodiment of the present invention, the simulation object includes a plurality of sub-simulation objects;

after determining the first routing path according to the first position and the node position, the method may further include:

receiving a first routing request;

selecting a first sub-simulation object set from the simulation objects according to the first routing request, wherein the first sub-simulation object set comprises a plurality of first sub-simulation objects;

receiving a second way-finding request;

selecting a second sub-simulation object set from the simulation objects according to the second routing request, wherein the second sub-simulation object set comprises a plurality of second sub-simulation objects;

controlling the simulated object to move from the first location to the node location according to the first routing path may include:

controlling the first sub-simulation object set to move from a first position to a node position according to a first routing path;

and controlling the second sub-simulation object set to move from the first position to the node position according to the first routing path.

In this embodiment, in practical applications, the simulation object may include a plurality of sub-simulation objects, and if the number of the sub-simulation objects is large, the sub-simulation objects may be controlled to move in the following manner.

Specifically, referring to fig. 12, fig. 12 is a schematic diagram of an embodiment of batched routing request processing according to an embodiment of the present invention, as shown in the figure, assuming that one of the simulation objects includes 200 sub-simulation objects (e.g., 200 "soldiers"), the 200 sub-simulation objects may be divided into 10 groups, and each group has 20 sub-simulation objects. First, a client obtains a first routing request, and determines a first sub-simulation object set from 200 sub-simulation objects according to the first routing request, wherein the first sub-simulation object set may include 20 'soldiers'. Similarly, the client continues to obtain a second routing request, and then determines a second set of sub-simulation objects from the remaining 180 sub-simulation objects according to the second routing request, wherein the second set of sub-simulation objects may include 20 "soldiers". And so on until all requests are processed.

When the simulation objects are controlled to move, a batched moving mode is also adopted, the first sub-simulation object set can be controlled to move according to the first path finding path, and then the second sub-simulation object set is controlled to move according to the first path finding path until all the sub-simulation objects in the simulation objects are moved completely.

Alternatively, the routing request may also be generated by each "soldier". In particular, during a combat playback process, a large number of "soldiers" seeking ways at the same time may occupy a large amount of processing resources. To avoid this, the management of the way-finding request queue is added. When each 'soldier' seeks a way, a way seeking request is generated and sent to a way seeking manager, and the way seeking manager is inserted into a queue firstly when receiving the way seeking request. Each frame of routing manager will take out a certain number of requests to process the routing logic and finally return the path result to the corresponding 'soldier'.

Through optimization, 200 'soldiers' routing is set, a routing manager is set to process 20 requests per frame, at the moment, the average time of each frame is 3 milliseconds, and the acceptable performance consumption of a client is achieved.

Secondly, in the embodiment of the present invention, the client may divide the simulation object into a plurality of sub-simulation object sets, each sub-simulation object set includes a plurality of sub-simulation objects, and when the client controls the movement of the simulation object, the sub-simulation object sets are moved in batches until all the sub-simulation objects in the simulation object move to the next node. Through the mode, the client only controls part of the simulation objects to move each time, all the simulation objects are moved in batch on the premise of not blocking the client picture, the performance consumption of the client can be reduced, and the data processing efficiency of the client is improved.

Referring to fig. 13, fig. 13 is a schematic diagram of an embodiment of a client according to the present invention, and the client 20 includes:

an obtaining module 201, configured to obtain a node position according to a first position and a second position of a simulation object, where the first position represents a start position where the simulation object is located, and the second position represents an end position where the simulation object is located;

a determining module 202, configured to determine a first routing path according to the first position and the node position acquired by the acquiring module 201;

a control module 203, configured to control the simulation object to move from the first position to the node position according to the first routing path determined by the determining module 202;

the determining module 202 is further configured to determine a second routing path according to the node position and the second position obtained by the obtaining module 201;

the control module 203 is further configured to control the simulation object to move from the node position to the second position according to the second routing path determined by the determining module 202.

In this embodiment, the obtaining module 201 obtains the node position according to the first position and the second position of the simulation object, wherein the first position represents a start position of the simulation object, the second position represents an end position of the simulation object, the determining module 202 determines a first routing path according to the first position and the node position obtained by the obtaining module 201, the control module 203 controls the simulation object to move from the first position to the node position according to the first routing path determined by the determining module 202, the determining module 202 determines a second routing path according to the node position and the second position acquired by the acquiring module 201, the control module 203 controls the simulation object to move from the node position to the second position according to the second routing path determined by the determining module 202.

The embodiment of the invention provides a client for controlling the routing of a simulation object, which comprises the steps of firstly obtaining the node position according to the first position and the second position of the simulation object, determining a first routing path according to the first position and the node position, and then controlling the simulation object to move from the first position to the node position according to the first routing path. The client side continues to determine a second routing path according to the node position and the second position, and then controls the simulation object to move from the node position to the second position according to the second routing path. By the mode, in the process of searching the path of the simulation object, the whole path searching path is split into the plurality of path searching paths, the length of the path searching paths is reduced, and the calculation amount can be effectively reduced when each path searching path is calculated, so that the performance cost is reduced, and the execution efficiency of the client is improved.

Optionally, on the basis of the embodiment corresponding to fig. 13, in another embodiment of the client 20 provided in the embodiment of the present invention,

the obtaining module 201 is specifically configured to obtain N child node positions according to a first position and a second position of a simulation object, where N is an integer greater than 1;

after obtaining the node position according to the first position and the second position of the simulation object, the method further includes:

the obtaining module 201 is further configured to obtain a horizontal distance between a first position and a second position of the simulation object and a vertical distance between the first position and the second position before obtaining a node position according to the first position and the second position of the simulation object;

the determining module 202 is further configured to determine a horizontal length according to the horizontal distance and a preset horizontal coefficient obtained by the obtaining module 201, and determine a vertical length according to the vertical distance and a preset vertical coefficient obtained by the obtaining module 201, where the horizontal length and the vertical length are used to determine a first region range;

the determining module 202 is further configured to determine the first area range as a target routing range if the first area range is smaller than a second area range, where the second area range is a preset area range;

the determining module 202 is further configured to determine a second area range as the target routing range if the first area range is larger than the second area range.

the obtaining module 201 is specifically configured to calculate a third position within the target routing range by using an a-star algorithm according to the first position and the second position of the simulated object, where the third position is a next position to which the simulated object moves from the first position;

calculating a fourth position in the target path finding range by adopting the A star algorithm according to the third position and the second position of the simulation object, wherein the fourth position is a next position to which the simulation object moves from the third position;

and if the position calculation times do not reach a preset calculation threshold, calculating a fifth position in the target path finding range by adopting the A star algorithm according to the fourth position and the second position of the simulation object, wherein the fourth position is a next position to which the simulation object moves from the third position.

the determining module 202 is specifically configured to obtain eight first candidate positions around the first position as a center;

generating a first distance sequence according to the first distance value corresponding to each first position to be selected, wherein the first distance sequence is an increasing sequence or a decreasing sequence;

taking the third position as a center to obtain eight second peripheral positions to be selected;

generating a second distance sequence according to the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position, wherein the second distance sequence is an increasing sequence or a decreasing sequence;

and determining the first path-finding path according to the first position, the third position and the fourth position.

the determining module 202 is specifically configured to sort the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position by using a binary sorting method, so as to obtain the second distance sequence.

the determining module 202 is specifically configured to sort the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position by using a binary sorting tree, so as to obtain the second distance sequence.

Optionally, on the basis of the embodiment corresponding to fig. 13, please refer to fig. 14, in another embodiment of the client 20 provided in the embodiment of the present invention, the client 20 further includes an executing module 204;

the executing module 204 is configured to execute the step of sorting, by using a binary sorting tree, the second distance value corresponding to each second position to be selected and the first distance value corresponding to each first position to be selected by using a binary sorting tree to obtain the second distance sequence if the target routing range is greater than a preset routing area, where the target routing range is a routable range of the simulation object;

the executing module 204 is further configured to execute the step of sorting the second distance value corresponding to each second position to be selected and the first distance value corresponding to each first position to be selected by using a binary sorting method to obtain the second distance sequence if the target routing range is smaller than the preset routing area.

Optionally, on the basis of the embodiment corresponding to fig. 13, please refer to fig. 15, in another embodiment of the client 20 provided in the embodiment of the present invention, the simulation object includes a plurality of sub-simulation objects;

the client 20 further comprises a receiving module 205 and a selecting module 206;

the receiving module 205 is configured to receive a first routing request after the determining module 202 determines a first routing path according to the first location and the node location;

the selecting module 206 is configured to select a first sub-simulation object set from the simulation objects according to the first routing request received by the receiving module 205, where the first sub-simulation object set includes a plurality of first sub-simulation objects;

receiving a second way-finding request;

the controlling the simulation object to move from the first position to the node position according to the first routing path includes:

controlling the first sub-simulation object set to move from the first position to the node position according to the first routing path;

As shown in fig. 16, for convenience of description, only the parts related to the embodiment of the present invention are shown, and details of the specific technology are not disclosed, please refer to the method part of the embodiment of the present invention. The terminal may be any terminal device including a mobile phone, a tablet computer, a Personal Digital Assistant (PDA), a Point of Sales (POS), a vehicle-mounted computer, and the like, taking the terminal as the mobile phone as an example:

fig. 16 is a block diagram showing a partial structure of a cellular phone related to a terminal provided by an embodiment of the present invention. Referring to fig. 16, the cellular phone includes: radio Frequency (RF) circuit 310, memory 320, input unit 330, display unit 340, sensor 350, audio circuit 360, wireless fidelity (WiFi) module 370, processor 380, and power supply 390. Those skilled in the art will appreciate that the handset configuration shown in fig. 16 is not intended to be limiting and may include more or fewer components than those shown, or some components may be combined, or a different arrangement of components.

The following describes each component of the mobile phone in detail with reference to fig. 16:

the RF circuit 310 may be used for receiving and transmitting signals during information transmission and reception or during a call, and in particular, receives downlink information of a base station and then processes the received downlink information to the processor 380; in addition, the data for designing uplink is transmitted to the base station. In general, the RF circuit 310 includes, but is not limited to, an antenna, at least one Amplifier, a transceiver, a coupler, a Low Noise Amplifier (LNA), a duplexer, and the like. In addition, RF circuit 310 may also communicate with networks and other devices via wireless communication. The wireless communication may use any communication standard or protocol, including but not limited to Global System for Mobile communication (GSM), General Packet Radio Service (GPRS), Code Division Multiple Access (CDMA), Wideband Code Division Multiple Access (WCDMA), Long Term Evolution (LTE), email, Short Messaging Service (SMS), and the like.

The memory 320 may be used to store software programs and modules, and the processor 380 executes various functional applications and data processing of the mobile phone by operating the software programs and modules stored in the memory 320. The memory 320 may mainly include a program storage area and a data storage area, wherein the program storage area may store an operating system, an application program required by at least one function (such as a sound playing function, an image playing function, etc.), and the like; the storage data area may store data (such as audio data, a phonebook, etc.) created according to the use of the cellular phone, and the like. Further, the memory 320 may include high speed random access memory, and may also include non-volatile memory, such as at least one magnetic disk storage device, flash memory device, or other volatile solid state storage device.

The input unit 330 may be used to receive input numeric or character information and generate key signal inputs related to user settings and function control of the cellular phone. Specifically, the input unit 330 may include a touch panel 331 and other input devices 332. The touch panel 331, also referred to as a touch screen, can collect touch operations of a user (e.g., operations of the user on the touch panel 331 or near the touch panel 331 using any suitable object or accessory such as a finger, a stylus, etc.) on or near the touch panel 331, and drive the corresponding connection device according to a preset program. Alternatively, the touch panel 331 may include two parts, a touch detection device and a touch controller. The touch detection device detects the touch direction of a user, detects a signal brought by touch operation and transmits the signal to the touch controller; the touch controller receives touch information from the touch sensing device, converts the touch information into touch point coordinates, sends the touch point coordinates to the processor 380, and can receive and execute commands sent by the processor 380. In addition, the touch panel 331 may be implemented in various types, such as a resistive type, a capacitive type, an infrared ray, and a surface acoustic wave. The input unit 330 may include other input devices 332 in addition to the touch panel 331. In particular, other input devices 332 may include, but are not limited to, one or more of a physical keyboard, function keys (such as volume control keys, switch keys, etc.), a trackball, a mouse, a joystick, and the like.

The display unit 340 may be used to display information input by the user or information provided to the user and various menus of the mobile phone. The Display unit 340 may include a Display panel 341, and optionally, the Display panel 341 may be configured in the form of a Liquid Crystal Display (LCD), an Organic Light-Emitting Diode (OLED), or the like. Further, the touch panel 331 can cover the display panel 341, and when the touch panel 331 detects a touch operation on or near the touch panel 331, the touch panel is transmitted to the processor 380 to determine the type of the touch event, and then the processor 380 provides a corresponding visual output on the display panel 341 according to the type of the touch event. Although in fig. 16, the touch panel 331 and the display panel 341 are two independent components to implement the input and output functions of the mobile phone, in some embodiments, the touch panel 331 and the display panel 341 may be integrated to implement the input and output functions of the mobile phone.

The handset may also include at least one sensor 350, such as a light sensor, motion sensor, and other sensors. Specifically, the light sensor may include an ambient light sensor that adjusts the brightness of the display panel 341 according to the brightness of ambient light, and a proximity sensor that turns off the display panel 341 and/or the backlight when the mobile phone is moved to the ear. As one of the motion sensors, the accelerometer sensor can detect the magnitude of acceleration in each direction (generally, three axes), can detect the magnitude and direction of gravity when stationary, and can be used for applications of recognizing the posture of a mobile phone (such as horizontal and vertical screen switching, related games, magnetometer posture calibration), vibration recognition related functions (such as pedometer and tapping), and the like; as for other sensors such as a gyroscope, a barometer, a hygrometer, a thermometer, and an infrared sensor, which can be configured on the mobile phone, further description is omitted here.

Audio circuitry 360, speaker 361, microphone 362 may provide an audio interface between the user and the handset. The audio circuit 360 may transmit the electrical signal converted from the received audio data to the speaker 361, and the audio signal is converted by the speaker 361 and output; on the other hand, the microphone 362 converts the collected sound signals into electrical signals, which are received by the audio circuit 360 and converted into audio data, which are then processed by the audio data output processor 380 and then transmitted to, for example, another cellular phone via the RF circuit 310, or output to the memory 320 for further processing.

WiFi belongs to short-distance wireless transmission technology, and the mobile phone can help a user to receive and send e-mails, browse webpages, access streaming media and the like through the WiFi module 370, and provides wireless broadband internet access for the user. Although fig. 16 shows the WiFi module 370, it is understood that it does not belong to the essential constitution of the handset, and may be omitted entirely as needed within the scope not changing the essence of the invention.

The processor 380 is a control center of the mobile phone, connects various parts of the whole mobile phone by using various interfaces and lines, and performs various functions of the mobile phone and processes data by operating or executing software programs and/or modules stored in the memory 320 and calling data stored in the memory 320, thereby performing overall monitoring of the mobile phone. Optionally, processor 380 may include one or more processing units; optionally, processor 380 may integrate an application processor, which primarily handles operating systems, user interfaces, application programs, etc., and a modem processor, which primarily handles wireless communications. It will be appreciated that the modem processor described above may not be integrated into processor 380.

The handset also includes a power supply 390 (e.g., a battery) for powering the various components, optionally, the power supply may be logically connected to the processor 380 through a power management system, so that the power management system may be used to manage charging, discharging, and power consumption.

Although not shown, the mobile phone may further include a camera, a bluetooth module, etc., which are not described herein.

In the embodiment of the present invention, the processor 380 included in the terminal further has the following functions:

Optionally, the processor 380 is specifically configured to perform the following steps:

acquiring N sub-node positions according to a first position and a second position of a simulation object, wherein N is an integer greater than 1;

Optionally, the processor 380 is further configured to perform the following steps:

acquiring a horizontal distance between the first position and the second position and a vertical distance between the first position and the second position;

if the first area range is smaller than a second area range, determining the first area range as a target routing range, wherein the second area range is a preset area range;

and if the first area range is larger than a second area range, determining the second area range as the target routing range.

calculating a third position in the target routing range by adopting an A star algorithm according to the first position and the second position of the simulation object, wherein the third position is a next position to which the simulation object moves from the first position;

and sorting the second distance value corresponding to each second position to be selected and the first distance value corresponding to each first position to be selected by adopting a binary sorting method to obtain the second distance sequence.

and sorting the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position by adopting a binary sorting tree to obtain the second distance sequence.

if the target path finding range is larger than a preset path finding area, performing the step of adopting a binary sorting tree to sort the second distance value corresponding to each second position to be selected and the first distance value corresponding to each first position to be selected to obtain the second distance sequence, wherein the target path finding range is the range in which the simulation object can find paths;

and if the target route searching range is smaller than the preset route searching area, executing the step of sorting the second distance value corresponding to each second position to be selected and the first distance value corresponding to each first position to be selected by adopting a binary sorting method to obtain the second distance sequence.

receiving a first routing request;

receiving a second way-finding request;

the processor 380 is specifically configured to perform the following steps:

It is clear to those skilled in the art that, for convenience and brevity of description, the specific working processes of the above-described systems, apparatuses and units may refer to the corresponding processes in the foregoing method embodiments, and are not described herein again.

In the embodiments provided in the present invention, it should be understood that the disclosed system, apparatus and method may be implemented in other ways. For example, the above-described apparatus embodiments are merely illustrative, and for example, the division of the units is only one logical division, and other divisions may be realized in practice, for example, a plurality of units or components may be combined or integrated into another system, or some features may be omitted, or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or units, and may be in an electrical, mechanical or other form.

The units described as separate parts may or may not be physically separate, and parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units can be selected according to actual needs to achieve the purpose of the solution of the embodiment.

In addition, functional units in the embodiments of the present invention may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit. The integrated unit can be realized in a form of hardware, and can also be realized in a form of a software functional unit.

The integrated unit, if implemented in the form of a software functional unit and sold or used as a stand-alone product, may be stored in a computer readable storage medium. Based on such understanding, the technical solution of the present invention may be embodied in the form of a software product, which is stored in a storage medium and includes instructions for causing a computer device (which may be a personal computer, a server, or a network device) to execute all or part of the steps of the method according to the embodiments of the present invention. And the aforementioned storage medium includes: various media capable of storing program codes, such as a usb disk, a removable hard disk, a read-only memory (ROM), a Random Access Memory (RAM), a magnetic disk, or an optical disk.

The above-mentioned embodiments are only used for illustrating the technical solutions of the present invention, and not for limiting the same; although the present invention has been described in detail with reference to the foregoing embodiments, it will be understood by those of ordinary skill in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some technical features may be equivalently replaced; and such modifications or substitutions do not depart from the spirit and scope of the corresponding technical solutions of the embodiments of the present invention.

Claims

1. A method of controlling routing of an analog object, comprising:

acquiring a node position according to a first position and a second position of a simulation object, splitting the whole routing path into a plurality of routing paths, and reducing the length of the routing paths, wherein the first position represents a starting position of the simulation object, the second position represents an end position of the simulation object, the second position is a position of a target which has an enemy relationship with the simulation object, and the simulation object is a soldier; the simulation object comprises a plurality of sub simulation objects;

determining a first routing path by adopting an A star algorithm according to the first position and the node position, wherein the first routing path is a routing path with the lowest cost from the first position to the node position;

determining a second routing path by adopting an A star algorithm according to the node position and the second position, wherein the second routing path is a routing path with the lowest cost from the node position to the second position;

wherein the node position includes N child node positions, and the obtaining of the node position according to the first position and the second position of the simulation object includes: on an optimal route from a first position to a second position of a simulation object calculated by adopting an A star algorithm, obtaining N sub-node positions according to a path interception rule, wherein N is an integer greater than 1;

after acquiring the positions of the N child nodes on the optimal route from the first position to the second position of the simulation object calculated by the a-star algorithm according to the path interception rule, the method further includes:

and controlling the simulation object to sequentially perform segmented routing according to the (N +1) routing paths, and finally controlling the simulation object to move from the first position to the second position.

2. The method of claim 1, wherein prior to obtaining the node location from the first location and the second location of the simulated object, the method further comprises:

3. The method of claim 2, wherein obtaining node locations from the first location and the second location of the simulated object comprises:

4. The method of claim 1, wherein determining a first routing path based on the first location and the node location comprises:

5. The method of claim 4, wherein generating a second distance sequence according to the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position comprises:

6. The method of claim 4, wherein generating a second distance sequence according to the second distance value corresponding to each second candidate position and the first distance value corresponding to each first candidate position comprises:

7. The method of claim 5 or 6, further comprising:

8. The method of claim 1, wherein the simulation object comprises a plurality of sub-simulation objects;

after determining a first routing path according to the first location and the node location, the method further comprises:

receiving a first routing request;

receiving a second way-finding request;

9. A client, comprising:

the acquisition module is used for acquiring a node position according to a first position and a second position of a simulation object, dividing the whole routing path into a plurality of routing paths and reducing the length of the routing paths, wherein the first position represents a starting position of the simulation object, the second position represents an end position of the simulation object, the second position is a position of a target which has an enemy relationship with the simulation object, and the simulation object is a soldier; the simulation object comprises a plurality of sub simulation objects;

the determining module is used for determining a first routing path by adopting an A star algorithm according to the first position and the node position acquired by the acquiring module, wherein the first routing path is a routing path with the lowest cost from the first position to the node position;

the determining module is further configured to determine a second routing path by using an a-star algorithm according to the node position and the second position acquired by the acquiring module, where the second routing path is a routing path with the lowest cost from the node position to the second position;

the control module is further configured to control the simulation object to move from the node position to the second position according to the second routing path determined by the determination module;

the node position comprises N sub-node positions, the acquisition module is specifically used for acquiring the N sub-node positions on an optimal route from a first position to a second position of a simulation object calculated by adopting an A star algorithm according to a route interception rule, and N is an integer greater than 1;

after N sub-node positions are obtained on the optimal route from the first position to the second position of the simulation object calculated by the A star algorithm according to a route interception rule, the determining module is further used for determining (N +1) route finding paths according to the first position and the N sub-node positions;

the control module is further configured to control the simulation object to sequentially perform the segmented routing according to the (N +1) routing paths, and finally control the simulation object to move from the first position to the second position.

10. A client, the client comprising: a memory, a transceiver, a processor, and a bus system;

wherein the memory is used for storing programs;

the bus system is used for connecting the memory and the processor so as to enable the memory and the processor to communicate;

wherein the node position includes N child node positions, and the obtaining of the node position according to the first position and the second position of the simulation object includes: acquiring N sub-node positions on an optimal route from a first position to a second position of a simulation object calculated by adopting an A star algorithm, wherein N is an integer greater than 1;

11. The client of claim 10, wherein the processor is further configured to perform the steps of:

12. A computer-readable storage medium comprising instructions that, when executed on a computer, cause the computer to perform the method of any of claims 1 to 8.