5 ms·

I am wondering why floors also are hard, the falling though the world is a bug I see too often, especially on the indie games I tried.

tinus_hn 5y ago
It’s not hard, Quake did it right many years ago. It just requires you to limit yourself in ways that aren’t acceptable these days.
- bruce343434 5y ago
  As someone outside of this field, could you elaborate on how quake "did it right" and how it requires you to limit yourself?
  - deleted 5y ago
    [deleted]
  - tinus_hn 5y ago
    Quake, for optimization reasons, did a lot of preprocessing on the geometry that makes up the world. This made it possible to render it on slow hardware. The process for one required the designer to make sure there were no cracks anywhere to fall through, because if you had one the preprocessing would fail. The preprocessor divides the entire inside of the level into convex areas and builds a graph that expresses where they touch. So for movement, if you just make sure that you can only go from one area into another that according to the graph touches it, there simply is no way to move out of bounds because the out of bounds area is not in the graph at all. This does mean though that you have a world that is mostly static, that consists only of indoor spaces and has a limited amount of complexity because otherwise the preprocessing results in an unmanageable amount of data. There is just no way you can preprocess the whole world like that in a modern open world game.
djmips 5y ago
I think it's because floors are often modelled infinitely thin, a plane with no thickness. It's all to easy to get on the wrong side of that plane for any number of reasons.
- simion314 5y ago
  But why not model it with 1m thinness and put some trigger code if you touch the other side to reset you, same for objects. I am not a game dev, so at first look a level editor that is mostly drag and drop should solve this for the level designers, but for some reason you can still fall through floors.
  - umvi 5y ago
    Scenario: - you have a 1m thick floor in your video game. - your video game has physics in it (like gravity, collisions, etc). - your game runs at 60 fps Given these assumptions, if any in-game object ever exceeds a velocity 60 m/s then on one frame it will be above the floor and on the next frame it will be below the floor without ever triggering a collision. Oops. Let me guess: "Just make the floor infinitely thick". Sure that would work but it sort of limits the kinds of maps and terrain you can make if the floor is always infinitely thick. One way to solve it without infinitely thick floors is to draw an imaginary line between your current position and previous position every frame and check if the line would have collided with anything . If it does - do something (make the player die, move them back above the floor, etc.). It gets more complex when it's not just the floor you have to worry about clipping through but the wall and the ceiling and all other objects.
  - adanto6840 5y ago
    Oh we definitely try "simple" approaches like that, whenever we can. And if the entire 'level' is, well, level & there are no elevation changes (or elevation changes are restricted to '1 elevation per floor of a structure, for instance) then sure, that type of solution works. Otherwise though, the 'trigger' code you suggest ends up generally being some kind of math (ie physics, regardless of whether it's via a physics engine layer or a game/state layer); you essentially have to figure out "where" on the plane the object is, convert that to the proper coordinate system for your overall level, and then 'sample' the underlying terrain/mesh/ground covering to figure out if you're in a legal position. Typically this ends up being implemented as a "clamp" of sorts; you will pretty rapidly end up with oddities, floating point precision quirks, and the like. The "best solution" will vary, often drastically, from game to game. FWIW, I've been doing game-dev for almost 10 years now & have almost exclusively done "AI/NPC" agents. We've faced what I would classify as pretty much the same issue with AI agents, especially when you want them to follow nice, smooth paths while also realistically 'bumping into' each-other -- yet ensuring that they will never, ever, ever go through a wall. It sounds so stupidly-simple but, I can assure you, it is not! If you had unlimited resources (read: CPU), then it's not so bad, you can calculate for "optimal" every frame -- in reality, you never have unlimited resources, and seemingly-simple calculations like this have to run extremely fast and they cannot be allowed to fail (there's nothing more frustrating & game-breaking than NPCs that get 'stuck' behind a wall or in an area that they cannot vacate, etc). You can write code for agents to "detect stuck + get un-stuck" but, similarly, doing that fast is non-trivial; and ideally you don't want them stuck to begin with!! It's a massive can of worms. ;)
fxtentacle 5y ago
For keeping things from falling through, you need to project the movement vector onto the plane. That means sqrt of magnitude and dot product. If you keep doing that every frame, a lot of tiny and otherwise insignificant floating point errors are going to sum up. The correct approach is to not model the floor as thin sheet geometry but instead to model it as solid objects, e.g. the CSG approach used in Quake, Half-Life 1 and Unreal 1 & 2. I believe those games didn't have any falling through bugs.
- foxfluff 5y ago
  https://wiki.beyondunreal.com/Legacy:BSP_Hole https://wiki.beyondunreal.com/Legacy:BSP_Hole
  - fxtentacle 5y ago
    Also there, I believe the underlying issue is lack of floating point precision. That's why the fix is to nudge the brush a bit and/or move it back onto the integer grid.
- thaumasiotes 5y ago
  > The correct approach is to not model the floor as thin sheet geometry but instead to model it as solid objects, e.g. the CSG approach used in Quake, Half-Life 1 and Unreal 1 & 2. While I never actually did any level editing, I did read a guide to the Unreal Tournament level editor, which said that UT was unusual in that a blank level was filled with mass and the level creation process involved subtracting that away to create empty space, rather than adding objects to an empty void. Related?
  - fxtentacle 5y ago
    Yes and no. The Unreal approach makes it easy to create levels with a waterproof outer hull which allows you to use certain optimizations (such as portals in the BSP tree) to reduce what you need to draw. But even without that, CSG usually produces only geometry that has a thickness, and that's what helps with the sliding through floors in the first place. But since the Unreal approach makes it very easy to query if a point is inside the valid space of the level, or not, that's also used as a shortcut for determining if things did fall through somewhere. So yes, the "blank filled with mass" approach further reduces the problem but no, it's not strictly necessary.
Animats 5y ago
This is why people buy physics engines or use game engines with physics engines built in. It's a solved problem, but the heavy machinery is non-trivial. (I used to work on ragdoll physics.)
db48x 5y ago
https://www.youtube.com/watch?v=YE8MVNMzpbo https://www.youtube.com/watch?v=YE8MVNMzpbo Here’s a game developer talking about the problem and how they solved it in The Witness, but note well the limitations he describes. It’s not directly useful if the player can jump, for instance.

tinus_hn 5y ago

It’s not hard, Quake did it right many years ago. It just requires you to limit yourself in ways that aren’t acceptable these days.

bruce343434 5y ago
As someone outside of this field, could you elaborate on how quake "did it right" and how it requires you to limit yourself?
- deleted 5y ago
  [deleted]
- tinus_hn 5y ago
  Quake, for optimization reasons, did a lot of preprocessing on the geometry that makes up the world. This made it possible to render it on slow hardware. The process for one required the designer to make sure there were no cracks anywhere to fall through, because if you had one the preprocessing would fail. The preprocessor divides the entire inside of the level into convex areas and builds a graph that expresses where they touch. So for movement, if you just make sure that you can only go from one area into another that according to the graph touches it, there simply is no way to move out of bounds because the out of bounds area is not in the graph at all. This does mean though that you have a world that is mostly static, that consists only of indoor spaces and has a limited amount of complexity because otherwise the preprocessing results in an unmanageable amount of data. There is just no way you can preprocess the whole world like that in a modern open world game.

djmips 5y ago

I think it's because floors are often modelled infinitely thin, a plane with no thickness. It's all to easy to get on the wrong side of that plane for any number of reasons.

simion314 5y ago
But why not model it with 1m thinness and put some trigger code if you touch the other side to reset you, same for objects. I am not a game dev, so at first look a level editor that is mostly drag and drop should solve this for the level designers, but for some reason you can still fall through floors.
- umvi 5y ago
  Scenario: - you have a 1m thick floor in your video game. - your video game has physics in it (like gravity, collisions, etc). - your game runs at 60 fps Given these assumptions, if any in-game object ever exceeds a velocity 60 m/s then on one frame it will be above the floor and on the next frame it will be below the floor without ever triggering a collision. Oops. Let me guess: "Just make the floor infinitely thick". Sure that would work but it sort of limits the kinds of maps and terrain you can make if the floor is always infinitely thick. One way to solve it without infinitely thick floors is to draw an imaginary line between your current position and previous position every frame and check if the line would have collided with anything . If it does - do something (make the player die, move them back above the floor, etc.). It gets more complex when it's not just the floor you have to worry about clipping through but the wall and the ceiling and all other objects.
- adanto6840 5y ago
  Oh we definitely try "simple" approaches like that, whenever we can. And if the entire 'level' is, well, level & there are no elevation changes (or elevation changes are restricted to '1 elevation per floor of a structure, for instance) then sure, that type of solution works. Otherwise though, the 'trigger' code you suggest ends up generally being some kind of math (ie physics, regardless of whether it's via a physics engine layer or a game/state layer); you essentially have to figure out "where" on the plane the object is, convert that to the proper coordinate system for your overall level, and then 'sample' the underlying terrain/mesh/ground covering to figure out if you're in a legal position. Typically this ends up being implemented as a "clamp" of sorts; you will pretty rapidly end up with oddities, floating point precision quirks, and the like. The "best solution" will vary, often drastically, from game to game. FWIW, I've been doing game-dev for almost 10 years now & have almost exclusively done "AI/NPC" agents. We've faced what I would classify as pretty much the same issue with AI agents, especially when you want them to follow nice, smooth paths while also realistically 'bumping into' each-other -- yet ensuring that they will never, ever, ever go through a wall. It sounds so stupidly-simple but, I can assure you, it is not! If you had unlimited resources (read: CPU), then it's not so bad, you can calculate for "optimal" every frame -- in reality, you never have unlimited resources, and seemingly-simple calculations like this have to run extremely fast and they cannot be allowed to fail (there's nothing more frustrating & game-breaking than NPCs that get 'stuck' behind a wall or in an area that they cannot vacate, etc). You can write code for agents to "detect stuck + get un-stuck" but, similarly, doing that fast is non-trivial; and ideally you don't want them stuck to begin with!! It's a massive can of worms. ;)

fxtentacle 5y ago

For keeping things from falling through, you need to project the movement vector onto the plane. That means sqrt of magnitude and dot product. If you keep doing that every frame, a lot of tiny and otherwise insignificant floating point errors are going to sum up. The correct approach is to not model the floor as thin sheet geometry but instead to model it as solid objects, e.g. the CSG approach used in Quake, Half-Life 1 and Unreal 1 & 2. I believe those games didn't have any falling through bugs.

foxfluff 5y ago
https://wiki.beyondunreal.com/Legacy:BSP_Hole https://wiki.beyondunreal.com/Legacy:BSP_Hole
- fxtentacle 5y ago
  Also there, I believe the underlying issue is lack of floating point precision. That's why the fix is to nudge the brush a bit and/or move it back onto the integer grid.
thaumasiotes 5y ago
> The correct approach is to not model the floor as thin sheet geometry but instead to model it as solid objects, e.g. the CSG approach used in Quake, Half-Life 1 and Unreal 1 & 2. While I never actually did any level editing, I did read a guide to the Unreal Tournament level editor, which said that UT was unusual in that a blank level was filled with mass and the level creation process involved subtracting that away to create empty space, rather than adding objects to an empty void. Related?
- fxtentacle 5y ago
  Yes and no. The Unreal approach makes it easy to create levels with a waterproof outer hull which allows you to use certain optimizations (such as portals in the BSP tree) to reduce what you need to draw. But even without that, CSG usually produces only geometry that has a thickness, and that's what helps with the sliding through floors in the first place. But since the Unreal approach makes it very easy to query if a point is inside the valid space of the level, or not, that's also used as a shortcut for determining if things did fall through somewhere. So yes, the "blank filled with mass" approach further reduces the problem but no, it's not strictly necessary.

Animats 5y ago

This is why people buy physics engines or use game engines with physics engines built in. It's a solved problem, but the heavy machinery is non-trivial. (I used to work on ragdoll physics.)

db48x 5y ago

https://www.youtube.com/watch?v=YE8MVNMzpbo https://www.youtube.com/watch?v=YE8MVNMzpbo Here’s a game developer talking about the problem and how they solved it in The Witness, but note well the limitations he describes. It’s not directly useful if the player can jump, for instance.