For PC games, today, today, how to determine what the object under the mouse is what is the problem of almost all games must face. There are several ways to provide reference only. 1. Encirclement Border Method: Generally, a companion frame is created for each object in the game, determine if all visible objects are traversed, determine whether the mouse coordinate point is internally enabled in the inside of a surrounding box. The advantages of this method are simple, and the algorithm is easily understood, and when the rectangular enclosure is used, the number of objects is also good when the number of objects is limited. The disadvantage is that the selection is not accurate enough, and the details of the object cannot be selected. In a 2D game, the package frame is generally a rectangle, or a combination of several rectangles, while the 3D game uses a surrounding box, or a bolus or a combination thereof. Regardless of the specific method, its algorithm is essentially the same. 2, enumeration method: one of the low efficiency. And 1, the encirclement method is similar, it also needs to traverse all visible objects, but due to the lack of the envelope case mechanism, only the object is located in the position of the mouse whether there is a valid pixel, or the effective alpha value, for 3D objects It is to check whether the ray formed by the mouse point is somewhere to cross the object. This method can achieve very precise selection, but since the efficiency is too low, few direct use, generally use method 1 to reduce the number of traversal objects, and then use this method to achieve accurate selection. 3, feedback method: This is a very effective, very fast method, especially in 3D games, is unparalleled. The implementation of the feedback method is very simple. First, we must maintain a background buffer. When drawing the target object, the visible information of the object (typically the object picture of the object picture, or the z value) is written to the background buffer, then the mouse correspondence The value of the position of the buffer has a change, and if it changes, it indicates that the object just drawn can be selected by the mouse. When the buffer is complex, some of the objects you can select after the draw is completed, you can get a list of objects that can be selected, and then simply extract the required objects from this list as long as it is simpler, depending on certain principles. This mechanism is in 2D, which generally does not maintain additional buffers and directly uses the drawing buffer. Under 3D, the built-in feedback method is provided like OpenGL, which is more convenient for users. Similar mechanisms can be practically utilized using Z Buffer, Template Covers. This method can achieve accurate to the pixel level, and there is hardly affecting the operational efficiency. A disadvantage is that there is a high control permission on the code of the drawing section. 4. Direct mapping method: This is also an efficient algorithm that can reach the time complexity of O (1). Common in the 2D war game. In such games, the scene is stored in a two-dimensional table, saved each item of the table, saves its object information above, we can pass a simple algorithm, from the current mouse location index, then directly The items that read the index should be selected. This method can also be used in a 3D game of a fixed perspective or even a 3D game of a fixed perspective. The disadvantage of this method is that the object is in the scene, which can only be placed in two-dimensional table, or multiple layers of two-dimensional tables. This method is also relatively large for memory space. Chess games are more suitable for use this method. Since each method has its own intrinsic advantages and disadvantages, and the scene is more variable, the scene is more varied, complicated. In order to adapt to the actual needs, the above method can be used in combination, thereby raising shortness, better demand. Other complex selection, such as scope selection (box selection), etc., can also be evolved by several basic methods.
