7 ms·

"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

"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.

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.