5 ms·

Somehow, I feel like reading that article diminished the original critique, however, inefficient raycasts aren't some sort of pathological edge case. Raycasts

Somehow, I feel like reading that article diminished the original critique, however, inefficient raycasts aren't some sort of pathological edge case. Raycasts are the most commonly used spatial queries in a 3d game. Hopefully this discussion will lead towards this issue being resolved. I actually found Sam Pruden's complaint a bit odd since it sounds like he's developing a 2d game. If you're spamming 1000s of raycasts per frame for your 2d game, there's probably something else going on...

hutzlibu 3y ago
"If you're spamming 1000s of raycasts per frame for your 2d game, there's probably something else going on..." Yup .. but maybe not stupidity, but rather a non generic game. In my case I need lots of raycasts, to determine what exactly the player and the enemy bots can see. Basically I have a simulation in 2D (using box2d directly in js as a wasm libary) - and all the bots and the player only (mostly) get information based on raycasts. They have to scan the world and react to that information, which leads to a different result, than the usual approach (cheating). So I am looking forward to get this fixed asap as well and also cannot really consider godot before that. Edit: performance problems with raycasts I had to experience as well, because the roundtrip js to wasm is expensive. I first wrote a WebGPU shader doing only raycasting in my world, but better was modifying box2d (and compiling to wasm) to include a function, that does all my raycasts in one call and returns a big array (or rather a array with pointers to the structs in the internal wasm heap).
- rngname22 3y ago
  If the game is 2D and you can divide space into tiles/blocks and walls/obstacles have their own blocks/tiles (or you can easily establish a grid over your world and determine what cell each actor is in), I wonder if there's way to use BFS in a maze-solving manner to calculate shortest path between a given actor and the target you want to check visibility for, and if the distance in blocks/tiles returned by BFS/pseudo-pathfinding is greater than a direct distance formula calculation between the two blocks/cells then maybe you know there's an obstacle? I guess that requires you to be able to create the network/graph of traversable nodes as well.
  - QuadmasterXLII 3y ago
    (Roughly, glossing over ‘linear in what?’) Good bfs gets close to linear, good raycasting should be way, way sublinear
    - LarsDu88 3y ago
      "Good raycasting should be sublinear" yes, but some folks like to stick 100 raycasts on every character which will kill the performance regardless of what engine your making your game in.
      - eutectic 3y ago
        We now have games which rely on shooting millions of rays per frame for rendering.
  - hutzlibu 3y ago
    Well, the world is destructible, so when there is a small hole (of dynamic size) in a wall, then a enemy bot should really only see the player, if there is no rubble blocking the path. Meaning tiles are waay too big for my simulation and raycasting the most straightforward way, also some enemies can evade projectiles and obstacles, but also have to scan them first. And it works already the way I want it. It could just be more performant, so more details and realism would be possible.
    - rcme 3y ago
      And, additionally, raycasting should just work in a good game engine. “You don’t need raycasting” is a seriously weak argument.
      - hutzlibu 3y ago
        Yes. I just expect raycasting to work allmost as good as possible, not on 50% to become a unnecessary blocker. But they say, they are going to fix it with some priority.
- ehutch79 3y ago
  Wait. that doesn't sound like you're doing 1000s of raycasts? Just a few, maybe a dozen? also, sounds like you're using JS, not Godot?
  - hutzlibu 3y ago
    Well, I would like to be able to do 1000s of raycast per frame (360 for each bot), but cannot and yes, I do not use godot, but my own engine (with pixijs for graphics and a emscriptem port of box2d for physics https://github.com/Birch-san/box2d-wasm https://github.com/Birch-san/box2d-wasm.) Godot uses box2d, too, so that would be convenient, if I switch to godot, but only if it is worth the performance improvement, which it currently does not seem to be. Maybe next year.
    - bluescrn 3y ago
      The usual solution for something like this is just to spread the work over multiple frames. Most game enemy logic doesn't need running every single frame. Update 10% of your bots every frame. Also consider whether 360 rays is really needed to begin with, one ray per degree sounds like an arbitrary first-pass value. Can you cast a smaller set of rays first, and only cast the in-between rays if certain conditions are met (e.g. the initial rays hit something close, or their hit distances vary significantly)
      - hutzlibu 3y ago
        "Can you cast a smaller set of rays first, and only cast the in-between rays if certain conditions are met " Yes I can do this. But my case is really special as in basically the players have to do this by themself. As it is (also) a hacking game, meaning they have a limited scan budget and need to figure out to spend it the most useful for their bots.. but since they also want to evade projectiles and other bots, they want to scan as much as possible to not miss a threat. So it works the way it is. Just would scale better, with better raycast performance. I probably should have hinted more above, why my case is really special, but that was kind of my point, there are always special cases. And I do not want to limit my design, because of a bad raycast implementation.
- fidotron 3y ago
  > because the roundtrip js to wasm is expensive. Is this a thing? I've been using ammo (wasm bullet) and while wasm interfacing certainly has a mismatch with idiomatic js I haven't knowably hit a problem with that bridge.
  - hutzlibu 3y ago
    It used to be waaaay more expensive and has gotten much better now. But it still costs, all I know is, that when I do 600 raycasts each, it costs me around 8 ms on medium hardware. Batching it reduces the cost to 2 ms for me. For simple things like GetPosition I did not noticed a perf hit, but for getting vertices I also did. So mid term, I will batch all often used calls into wasm. For now raycasting was the biggest bottleneck.
    - fidotron 3y ago
      Thanks for that! I will have to take a deeper look.
  - meheleventyone 3y ago
    Yeah it’s quite common on most interop boundaries because there is always some amount of marshalling. It used to be a thing in Unity that it was significantly faster to run your own tick for all entities from a manager that hooked the callback from native code than to have to cross back and forth n entity times. For anything you’re doing in WASM it’s much better to batch and cross the boundary as little as possible in hot loops. For example a performant renderer wouldn’t translate all the API calls but put together a command buffer to be returned to JS and then forwarded to the API in one go.
- LarsDu88 3y ago
  It's hard to tell without seeing a screenshot or video of the game in question, but there are almost certainly ways to optimize this problem. If there are on the order of even several dozen enemies on the screen at any given time, you could simply maintain runtime sets of different factions and only do line-of-sight checks between hostile groups within a certain proximity. There's probably hundreds of better ways to do this than by spamming raycasts. I have a VR space game with dozens of spaceships, and there are generally never more than num_spaceships raycasts getting fired every frame
  - hutzlibu 3y ago
    "but there are almost certainly ways to optimize this problem." Sure, I optimize what I can. But there is only so much I can do, without hurting the core game mechanic. Which is a arcade shooter, but also a hacker game, where you program your bots. So the bots are mostly limited to radar distance information by design, to work out their position in the world and what to do next (but to make this work with many bots, I already had to cheat a lot). And it is unreleased, in case you are wondering .. but I hope to ship an alpha, soon. So it already works and it is fun. So I won't change core functionality, but I am still optimizing wherever I can. 3 months ago, it would only run on gaming hardware. Now medium mobile phones (a big market) are within reach.
  - JuanPosadas 3y ago
    > raycasts getting fired every frame Also don't need to do this every frame, do X% each tick (not frames literally), rotating which objects get their checks.
db48x 3y ago
If you’re doing thousands of raycasts per frame in any game, 2D or 3D, then something has gone wrong. Raycasts are very general, and there is often a more specialized way to get the same information that won’t require as much work.
- moffkalast 3y ago
  Maybe there's thousands of guns being fired.
  - db48x 3y ago
    Ok, if you’ve got thousands of players in the game then you’re doing _something_ right, even if the raycasts aren’t helping :)
- pelasaco 3y ago
  I don't think how it can be wrong. I wrote a beaten-up game, 2.5D. Player(s) + Enemies + NPCs + Weapons + Bullets.. I can imagine that in some moments, we were easily doing a few hundreds of raycasts per frame.
  - db48x 3y ago
    Raycasts are a very useful tool, and you shouldn’t avoid using them if they’re the only thing that will work. But a _fully general_ raycast is always the most expensive option. For example, an axis–aligned raycast will always be cheaper and might do the job just as well. The previously mentioned case of doing hundreds of raycasts all starting in the same location but each in a different direction could be done with rasterization instead. That’ll involve a single loop over all the triangles in the world instead of one loop over the same triangles for each raycast. And for NPC vision you could rasterize billboards instead of the full character geometry. You can probably simplify the world geometry too. That’s all I mean.
    - Rapzid 3y ago
      I mean it's game dev, there's always work arounds and efficiency hacks. But what does any of this has to do with improving the ABI?
TazeTSchnitzel 3y ago
There are multiple APIs for doing raycasts in Godot; this one happens to be the least efficient.
deleted 3y ago
[deleted]
Kiro 3y ago
Isn't that how you do line-of-sight/shadows, with thousands of raycasts for all pixels on screen?
- kaibee 3y ago
  Absolutely not. There's uh, a lot of tutorials on YouTube about how to go about implementing this kinda thing, depending on the kind of game (top-down 2d, vs 3d etc). Sorry don't have time to do a full write up lol.
  - hutzlibu 3y ago
    But this approach actually also works and delivers different results in 2D space, than doing what you probably have in mind. This approach in 3D would basically mean live raycasting rendering, which is something I would like to try in the future.
- starkparker 3y ago
  That's raytracing. You can do LOS by raycasting only at line segments and points of blocking shapes, especially in 2D, which is the original post's concern. https://ncase.me/sight-and-light/ https://ncase.me/sight-and-light/
TylerGlaiel 3y ago
There's nothing wrong with spamming 1000s of raycasts per frame in a 2D game. They should be very cheap, so the performance impact of that should not be something you have to think about, and if some interaction or mechanic is easy to express with a boatload of raycasts, you should be able to just do that
- LarsDu88 3y ago
  It depends on the type of game, but 360 raycasts per bot is definitely a code smell that warrants a closer look at how the game is being architected.
Cyphus 3y ago
> inefficient raycasts aren't some sort of pathological edge case. You're right that raycasts aren't an edge case in terms of usage, but Juan Linietsky's point is that the inefficient path used for this API call is a rare exception to the efficient paths used by the vast majority of the API.

hutzlibu 3y ago

"If you're spamming 1000s of raycasts per frame for your 2d game, there's probably something else going on..." Yup .. but maybe not stupidity, but rather a non generic game. In my case I need lots of raycasts, to determine what exactly the player and the enemy bots can see. Basically I have a simulation in 2D (using box2d directly in js as a wasm libary) - and all the bots and the player only (mostly) get information based on raycasts. They have to scan the world and react to that information, which leads to a different result, than the usual approach (cheating). So I am looking forward to get this fixed asap as well and also cannot really consider godot before that. Edit: performance problems with raycasts I had to experience as well, because the roundtrip js to wasm is expensive. I first wrote a WebGPU shader doing only raycasting in my world, but better was modifying box2d (and compiling to wasm) to include a function, that does all my raycasts in one call and returns a big array (or rather a array with pointers to the structs in the internal wasm heap).

rngname22 3y ago
If the game is 2D and you can divide space into tiles/blocks and walls/obstacles have their own blocks/tiles (or you can easily establish a grid over your world and determine what cell each actor is in), I wonder if there's way to use BFS in a maze-solving manner to calculate shortest path between a given actor and the target you want to check visibility for, and if the distance in blocks/tiles returned by BFS/pseudo-pathfinding is greater than a direct distance formula calculation between the two blocks/cells then maybe you know there's an obstacle? I guess that requires you to be able to create the network/graph of traversable nodes as well.
- QuadmasterXLII 3y ago
  (Roughly, glossing over ‘linear in what?’) Good bfs gets close to linear, good raycasting should be way, way sublinear
  - LarsDu88 3y ago
    "Good raycasting should be sublinear" yes, but some folks like to stick 100 raycasts on every character which will kill the performance regardless of what engine your making your game in.
    - eutectic 3y ago
      We now have games which rely on shooting millions of rays per frame for rendering.
- hutzlibu 3y ago
  Well, the world is destructible, so when there is a small hole (of dynamic size) in a wall, then a enemy bot should really only see the player, if there is no rubble blocking the path. Meaning tiles are waay too big for my simulation and raycasting the most straightforward way, also some enemies can evade projectiles and obstacles, but also have to scan them first. And it works already the way I want it. It could just be more performant, so more details and realism would be possible.
  - rcme 3y ago
    And, additionally, raycasting should just work in a good game engine. “You don’t need raycasting” is a seriously weak argument.
    - hutzlibu 3y ago
      Yes. I just expect raycasting to work allmost as good as possible, not on 50% to become a unnecessary blocker. But they say, they are going to fix it with some priority.
ehutch79 3y ago
Wait. that doesn't sound like you're doing 1000s of raycasts? Just a few, maybe a dozen? also, sounds like you're using JS, not Godot?
- hutzlibu 3y ago
  Well, I would like to be able to do 1000s of raycast per frame (360 for each bot), but cannot and yes, I do not use godot, but my own engine (with pixijs for graphics and a emscriptem port of box2d for physics https://github.com/Birch-san/box2d-wasm https://github.com/Birch-san/box2d-wasm.) Godot uses box2d, too, so that would be convenient, if I switch to godot, but only if it is worth the performance improvement, which it currently does not seem to be. Maybe next year.
  - bluescrn 3y ago
    The usual solution for something like this is just to spread the work over multiple frames. Most game enemy logic doesn't need running every single frame. Update 10% of your bots every frame. Also consider whether 360 rays is really needed to begin with, one ray per degree sounds like an arbitrary first-pass value. Can you cast a smaller set of rays first, and only cast the in-between rays if certain conditions are met (e.g. the initial rays hit something close, or their hit distances vary significantly)
    - hutzlibu 3y ago
      "Can you cast a smaller set of rays first, and only cast the in-between rays if certain conditions are met " Yes I can do this. But my case is really special as in basically the players have to do this by themself. As it is (also) a hacking game, meaning they have a limited scan budget and need to figure out to spend it the most useful for their bots.. but since they also want to evade projectiles and other bots, they want to scan as much as possible to not miss a threat. So it works the way it is. Just would scale better, with better raycast performance. I probably should have hinted more above, why my case is really special, but that was kind of my point, there are always special cases. And I do not want to limit my design, because of a bad raycast implementation.
fidotron 3y ago
> because the roundtrip js to wasm is expensive. Is this a thing? I've been using ammo (wasm bullet) and while wasm interfacing certainly has a mismatch with idiomatic js I haven't knowably hit a problem with that bridge.
- hutzlibu 3y ago
  It used to be waaaay more expensive and has gotten much better now. But it still costs, all I know is, that when I do 600 raycasts each, it costs me around 8 ms on medium hardware. Batching it reduces the cost to 2 ms for me. For simple things like GetPosition I did not noticed a perf hit, but for getting vertices I also did. So mid term, I will batch all often used calls into wasm. For now raycasting was the biggest bottleneck.
  - fidotron 3y ago
    Thanks for that! I will have to take a deeper look.
- meheleventyone 3y ago
  Yeah it’s quite common on most interop boundaries because there is always some amount of marshalling. It used to be a thing in Unity that it was significantly faster to run your own tick for all entities from a manager that hooked the callback from native code than to have to cross back and forth n entity times. For anything you’re doing in WASM it’s much better to batch and cross the boundary as little as possible in hot loops. For example a performant renderer wouldn’t translate all the API calls but put together a command buffer to be returned to JS and then forwarded to the API in one go.
LarsDu88 3y ago
It's hard to tell without seeing a screenshot or video of the game in question, but there are almost certainly ways to optimize this problem. If there are on the order of even several dozen enemies on the screen at any given time, you could simply maintain runtime sets of different factions and only do line-of-sight checks between hostile groups within a certain proximity. There's probably hundreds of better ways to do this than by spamming raycasts. I have a VR space game with dozens of spaceships, and there are generally never more than num_spaceships raycasts getting fired every frame
- hutzlibu 3y ago
  "but there are almost certainly ways to optimize this problem." Sure, I optimize what I can. But there is only so much I can do, without hurting the core game mechanic. Which is a arcade shooter, but also a hacker game, where you program your bots. So the bots are mostly limited to radar distance information by design, to work out their position in the world and what to do next (but to make this work with many bots, I already had to cheat a lot). And it is unreleased, in case you are wondering .. but I hope to ship an alpha, soon. So it already works and it is fun. So I won't change core functionality, but I am still optimizing wherever I can. 3 months ago, it would only run on gaming hardware. Now medium mobile phones (a big market) are within reach.
- JuanPosadas 3y ago
  > raycasts getting fired every frame Also don't need to do this every frame, do X% each tick (not frames literally), rotating which objects get their checks.

db48x 3y ago

If you’re doing thousands of raycasts per frame in any game, 2D or 3D, then something has gone wrong. Raycasts are very general, and there is often a more specialized way to get the same information that won’t require as much work.

moffkalast 3y ago
Maybe there's thousands of guns being fired.
- db48x 3y ago
  Ok, if you’ve got thousands of players in the game then you’re doing _something_ right, even if the raycasts aren’t helping :)
pelasaco 3y ago
I don't think how it can be wrong. I wrote a beaten-up game, 2.5D. Player(s) + Enemies + NPCs + Weapons + Bullets.. I can imagine that in some moments, we were easily doing a few hundreds of raycasts per frame.
- db48x 3y ago
  Raycasts are a very useful tool, and you shouldn’t avoid using them if they’re the only thing that will work. But a _fully general_ raycast is always the most expensive option. For example, an axis–aligned raycast will always be cheaper and might do the job just as well. The previously mentioned case of doing hundreds of raycasts all starting in the same location but each in a different direction could be done with rasterization instead. That’ll involve a single loop over all the triangles in the world instead of one loop over the same triangles for each raycast. And for NPC vision you could rasterize billboards instead of the full character geometry. You can probably simplify the world geometry too. That’s all I mean.
  - Rapzid 3y ago
    I mean it's game dev, there's always work arounds and efficiency hacks. But what does any of this has to do with improving the ABI?

TazeTSchnitzel 3y ago

There are multiple APIs for doing raycasts in Godot; this one happens to be the least efficient.

deleted 3y ago

[deleted]

Kiro 3y ago

Isn't that how you do line-of-sight/shadows, with thousands of raycasts for all pixels on screen?

kaibee 3y ago
Absolutely not. There's uh, a lot of tutorials on YouTube about how to go about implementing this kinda thing, depending on the kind of game (top-down 2d, vs 3d etc). Sorry don't have time to do a full write up lol.
- hutzlibu 3y ago
  But this approach actually also works and delivers different results in 2D space, than doing what you probably have in mind. This approach in 3D would basically mean live raycasting rendering, which is something I would like to try in the future.
starkparker 3y ago
That's raytracing. You can do LOS by raycasting only at line segments and points of blocking shapes, especially in 2D, which is the original post's concern. https://ncase.me/sight-and-light/ https://ncase.me/sight-and-light/

TylerGlaiel 3y ago

There's nothing wrong with spamming 1000s of raycasts per frame in a 2D game. They should be very cheap, so the performance impact of that should not be something you have to think about, and if some interaction or mechanic is easy to express with a boatload of raycasts, you should be able to just do that

LarsDu88 3y ago
It depends on the type of game, but 360 raycasts per bot is definitely a code smell that warrants a closer look at how the game is being architected.

Cyphus 3y ago

> inefficient raycasts aren't some sort of pathological edge case. You're right that raycasts aren't an edge case in terms of usage, but Juan Linietsky's point is that the inefficient path used for this API call is a rare exception to the efficient paths used by the vast majority of the API.