CN-121996826-A - Space query method and device for objects in large-scale real-time combat scene

CN121996826ACN 121996826 ACN121996826 ACN 121996826ACN-121996826-A

Abstract

The application provides a space query method and device, a computing device and a computer readable storage medium for objects in a large-scale real-time combat scene, the method comprises the steps of superposing a compact grid layer and a loose grid layer which are uniformly distributed in a game scene, and positioning a game object to a specific unit cell of the loose grid layer by utilizing the mapping relation between world coordinates and grid dimensions. A mechanism combining coarse screening and fine measurement is introduced in a specific query flow, most of spatially irrelevant objects are rapidly removed, and then, only the screened candidate objects are subjected to accurate geometric collision or distance judgment so as to remove misjudgment objects generated by grid boundary division. According to the scheme, the number of objects participating in accurate calculation is greatly reduced through coarse-grained screening of the grid layer, and the CPU resource consumption is effectively reduced by combining an optimized index calculation mode, so that the instantaneity and the accuracy of space inquiry are remarkably improved.

Inventors

Hua Changmiao
LI JIANLIANG

Assignees

北京雪境科技有限公司
上海沛炫网络科技有限公司

Dates

Publication Date: 20260508
Application Date: 20260121

Claims (11)

1. A method for spatial query of objects in a large-scale real-time combat scene, comprising: The method comprises the steps of initializing a compact grid layer and a loose grid layer, receiving a game object generated by each frame, storing references of the game object into corresponding loose grid layer cells according to the center point position of the game object, and establishing a mapping relation between the compact grid layer and the loose grid layer according to a dynamic AABB bounding box of the game object, wherein the compact grid layer and the loose grid layer are space division structures with fixed sizes and cover the whole game scene, and the cell size of the loose grid layer is n times of the cell size of the compact grid layer, and n is an integer greater than 1; responding to the query request, and determining a first candidate cell according to the intersection of the query area and the tight grid layer; Determining a second candidate cell mapped with the first candidate cell in the loose grid layer according to the first candidate cell, and obtaining a candidate target game object according to the intersection of the dynamic AABB bounding box of the second candidate cell and a query area; and carrying out accurate intersection test on the candidate target game object and the query area to obtain a target game object.
2. The method of claim 1, wherein storing the reference to the game object in the corresponding loose grid layer cell according to the center point location of the game object comprises: The method comprises the steps of obtaining the real-time position of a center point of a game object, mapping the real-time position to cells of a loose grid layer, and placing pointers of the game object into the corresponding cells of the loose grid layer, wherein the cells of one loose grid layer comprise at least one pointer of the game object.
3. The method of claim 2, wherein placing the pointers of the game objects into cells of a corresponding loose grid layer comprises: Checking the number of game objects to be placed into the cells of the loose grid layer, if the number is smaller than a first threshold value, using a stack array preset in the storage component SMALLLIST to complete the function, and if the number is larger than or equal to the first threshold value, switching to apply for a larger continuous space on the stack memory to complete the function.
4. The method of claim 1, wherein establishing the mapping of the tight mesh layer to the loose mesh layer according to the dynamic AABB bounding box of the game object comprises: Traversing the loose grid layer cells, finding out the tight grid layer cells covered by the dynamic AABB bounding boxes of the game objects in each loose grid layer cell, and establishing the mapping relation between the tight grid layer cells and the loose grid layer cells, wherein when the loose grid layer cells comprise a plurality of game objects, the dynamic AABB bounding boxes of the game objects are combined.
5. The method of claim 1, wherein determining a first candidate cell based on an intersection of a query region with the tight mesh layer comprises: Mapping AABB bounding box coordinates of the query area into row and column indexes of a compact grid layer, determining a rectangular index range covering the compact grid layer, and screening out all first candidate cells in the range; the division calculation is converted into efficient single instruction operation by pre-calculating the reciprocal of the cell size of the compact grid layer and carrying out parallel multiplication operation on four boundary coordinates by combining with a SIMD instruction.
6. The method of claim 5, wherein a second candidate cell mapped to the first candidate cell in the loose grid layer is determined according to the first candidate cell, and a candidate target game object is obtained according to the intersection of a dynamic AABB bounding box of the second candidate cell and a query region: according to the mapping relation, a plurality of cells of a loose grid layer mapped with the first candidate cells are obtained to serve as second candidate cells; And when the AABB bounding box of the query area is intersected with the dynamic AABB bounding box of the second candidate cell, adding the game object corresponding to the current second candidate cell into a candidate target game object list.
7. The method of claim 6, wherein performing a precision intersection test on the candidate target game object and the query region to obtain a target game object comprises: And acquiring the specific shape of the query area, judging whether the specific shape of the query area is intersected with the real shape of the candidate target game object, and if so, putting the specific shape of the query area into a list to be used as the target game object obtained by query.
8. The method of claim 1, wherein storing the reference to the game object in the corresponding loose grid layer cell according to the center point location of the game object comprises: And converting the real-time positions of the game objects into grid unit indexes of the loose grid layers, generating key values according to the indexes, and sequencing and rearranging object data in the memory according to the key values so that game objects with adjacent space positions are continuously distributed on physical memory addresses.
9. A spatial query device for objects in a large-scale real-time combat scene, comprising: the initialization unit is used for initializing the compact grid layer and the loose grid layer and receiving game objects generated by each frame; The game device comprises a game object, a layout unit, a compact grid layer and a loose grid layer, wherein the game object is used for storing a reference of the game object into a corresponding loose grid layer cell according to the central point position of the game object, and a mapping relation between the compact grid layer and the loose grid layer is built according to a dynamic AABB bounding box of the game object; The first screening unit is used for responding to the query request and determining a first candidate cell according to the intersection of the query area and the tight grid layer; the second screening unit is used for determining a second candidate cell mapped with the first candidate cell in the loose grid layer according to the first candidate cell, and obtaining a candidate target game object according to the intersection of the dynamic AABB bounding box of the second candidate cell and the query area; and the accurate screening unit is used for carrying out accurate intersection test on the candidate target game object and the query area to obtain the target game object.
10. A computing device comprising a memory, a processor, and computer instructions stored on the memory and executable on the processor, wherein the processor, when executing the instructions, implements the steps of the method of any of claims 1-8.
11. A computer readable storage medium storing computer instructions which, when executed by a processor, implement the steps of the method of any one of claims 1 to 8.

Description

Space query method and device for objects in large-scale real-time combat scene Technical Field The present application relates to the field of computer technologies, and in particular, to a method and apparatus for spatial query of objects in a large-scale real-time combat scene, a computing device, and a computer readable storage medium. Background In a real-time combat equal-altitude concurrency scene, efficient space query on massive dynamic objects is a core requirement for guaranteeing system performance. For example, in RTS game, collision and skill range between units need to be determined quickly in real time, in MOBA game, all enemy characters in a designated range need to be acquired instantaneously when skill is released, and the operations depend on real-time and accuracy of space inquiry. In the prior art, although a tree structure (such as a quadtree and an octree) can process unevenly distributed objects, a recursion traversing mechanism of the tree structure has obvious bottleneck under a multi-core CPU and a cache architecture, wherein random memory access of tree nodes causes extremely low cache hit rate, frequent pointer jump consumes a large number of CPU cycles, when the number of objects is increased rapidly, query delay is difficult to meet the real-time requirement, and in addition, the insertion/deletion operation of the tree structure needs dynamic balance, so that performance jitter is further aggravated. Although the space hash can process dynamic objects, hash collision can cause unstable inquiry performance, especially in an object dense area, the collision probability increases to cause performance dip, and frame rate stability is difficult to ensure. The technical defects are particularly remarkable in large-scale real-time combat, the traditional algorithm can not meet the core requirement of rapidly acquiring the roles in a certain range, so that the problems of collision detection delay, skill judgment errors and the like are caused, and the game experience is seriously influenced. Therefore, a new space division algorithm capable of maintaining query efficiency and optimizing memory access mode is needed to solve the performance bottleneck in the prior art and meet the high requirements of modern game engines on instantaneity and stability. Disclosure of Invention In view of this, embodiments of the present application provide a method and apparatus for spatial query of objects in a large-scale real-time combat scene, a computing device, and a computer-readable storage medium, so as to solve the technical drawbacks existing in the prior art. According to a first aspect of an embodiment of the present application, there is provided a spatial query method for an object in a large-scale real-time combat scene, including: The method comprises the steps of initializing a compact grid layer and a loose grid layer, receiving a game object generated by each frame, storing references of the game object into corresponding loose grid layer cells according to the center point position of the game object, and establishing a mapping relation between the compact grid layer and the loose grid layer according to a dynamic AABB bounding box of the game object, wherein the compact grid layer and the loose grid layer are space division structures with fixed sizes and cover the whole game scene, and the cell size of the loose grid layer is n times of the cell size of the compact grid layer, and n is an integer greater than 1; responding to the query request, and determining a first candidate cell according to the intersection of the query area and the tight grid layer; Determining a second candidate cell mapped with the first candidate cell in the loose grid layer according to the first candidate cell, and obtaining a candidate target game object according to the intersection of the dynamic AABB bounding box of the second candidate cell and a query area; and carrying out accurate intersection test on the candidate target game object and the query area to obtain a target game object. According to a second aspect of an embodiment of the present application, there is provided a spatial query device for an object in a large-scale real-time combat scene, including: the initialization unit is used for initializing the compact grid layer and the loose grid layer and receiving game objects generated by each frame; The game device comprises a game object, a layout unit, a compact grid layer and a loose grid layer, wherein the game object is used for storing a reference of the game object into a corresponding loose grid layer cell according to the central point position of the game object, and a mapping relation between the compact grid layer and the loose grid layer is built according to a dynamic AABB bounding box of the game object; The first screening unit is used for responding to the query request and determining a first candidate cell according to the intersection of the query area and the tigh