Game and Bug: Going Through the Walls
2025. 02. 15.
Once while working at a game company, I caught a user who had entered a new map that hadn't been released yet. Since the portal to this map hadn't been implemented, there was no way to reach this isolated field except by flying to it. However, in this game, players couldn't even jump, let alone fly. How on earth could the user have gone to a region where movement was blocked? As later revealed, this user had "penetrated" through a blocked section in the existing map. What does it mean to penetrate through? Similar to the previous portal bug, understanding this requires knowledge about how game spaces work, especially techniques for movement and its limitations.
Before talking about game spaces, let's think about real physical space. Imagine someone in a room. The room can be any shape as long as it has at least one wall. If this person wants to go to the space beyond the wall and walks toward it, they will obviously hit the wall before reaching the space beyond. Why do they hit the wall? Because the wall already occupies that space, and since it's firmly fixed, it remains in place when the person applies force to move into the wall's space. So, for the concept of collision to exist, there must be an underlying premise that multiple objects cannot exist in the same space simultaneously.
What about in game spaces? Interestingly, in virtual spaces, multiple objects can exist in the same space simultaneously unless specific rules are set. More specifically, if you don't define what interactions can occur between two objects, they exist as if in completely different worlds, having no effect on each other. Therefore, to prevent a character from moving beyond a wall in a game, you need additional mechanisms. For example, you can check whether two objects' occupied spaces overlap—i.e., detect collisions—and block movement accordingly. I explained frames in a previous article, and that concept is useful here too. If in the current frame, a person and a wall don't overlap, but in the next frame, the person would move to overlap with the wall, you can adjust the person's position so their final location doesn't overlap with the wall—this is one straightforward way to implement collision prevention.
The challenge lies in how to implement this collision detection specifically. Since the game was 3D, it seems like we should create an algorithm to detect if two 3D shapes overlap. However, 3D shape collision detection requires a lot of computation, which isn't suitable for calculating frames in real-time. Since this game didn't support jumping or flying anyway, projecting 3D shapes onto the ground to get 2D shapes and then detecting collisions between these 2D shapes seems reasonable. But if you try to implement collision detection between two 2D shapes naively—for example, checking if all points of an m-sided polygon fall inside an n-sided polygon—you'd need computations proportional to m * n in the worst case, which would take a long time to calculate frames if characters are complexly shaped (moreover, this method is incorrect for collision detection; two triangles forming a hexagram overlap, but all points of each shape lie outside the other). So, if you don't need to detect overlap between two shapes very precisely, collision detection is often done using rectangles that envelop the shapes. You can find more information by searching for keywords like AABB (axis-aligned bounding box) or OBB (oriented bounding box). This approach allows for significant reduction in necessary computations without significantly affecting gameplay.
Although my memory is a bit fuzzy since it's been a long time since I maintained that game, I think the game engine was optimized one step further. If my character is moving forward, couldn't we reduce computations once more by checking if just one point in front of the character collides with another object? This optimization seemed to work quite well—until a very creative user came along. From here, some of my recollections about the bug are hazy, so this includes some speculation. A creative user discovered that by equipping items or consuming potions that decrease movement speed, they could change their movement speed to a negative value. In other words, when controlling the character to move forward, they would actually move backward. So while the collision detection point was in front of the character, the character was actually moving backward, allowing the character's back to pass through other objects. This user might have discovered this phenomenon accidentally while exploring the map. And then, while overlapping with a wall at the edge of the map, they might have switched equipment to make their movement speed positive again, tried to move, and either got thrown into some space behind the wall or found themselves able to move freely in the space behind the wall because there were no obstacles. Now, an unknown world that they couldn't explore before opened up to the user. They could go around every corner to see if there were any maps hidden by the developers.