Hacker News Reader

Comment by LarsDu88 | Hacker News Reader

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

View on HN

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

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.

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.

And, additionally, raycasting should just work in a good game engine. “You don’t need raycasting” is a seriously weak argument.

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.

(Roughly, glossing over ‘linear in what?’) Good bfs gets close to linear, good raycasting should be way, way sublinear

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

We now have games which rely on shooting millions of rays per frame for rendering.

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

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

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

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?

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

It's hard to evaluate this without seeing a screenshot of your game, but 360 raycasts per bot per frame for a basic 2d game is INSANE.

It sounds like you are trying to query every angle in every direction for every character. This is madness.

I have a 3d space game in Unity which uses raycasts for navigation. Each ship fires a maximum of 1 navigation raycast per frame with a sweep pattern. In addition there are anti collision thrusters placed around each ship which fire roughly every second in a staggered pattern to prevent ships from getting stuck

In my fully 3d game, that's effectively ~1 raycast per frame per enemy. To locate hostiles, each ai character scans a runtime set of potential hostiles and does a line-of-sight query roughly once every 5 seconds.

There definitely is another issue going on here with your setup that is independent of the extreme overhead in Godot.

I would recommend Sebastian Langue's excellent boids video to get a sense about other strategies to deal with these types of queries: https://www.youtube.com/watch?v=bqtqltqcQhw

It's possible that they are building a game in which players can program bots that only know the state of the world by performing raycasts, as if it were a sensor of sorts. That would be a valid reason to require such an amount of raycasts per bot - although I probably would not run them every frame, but rather spread the load throughout multiple frames.

Yes exactly. But the projectiles are moving every tick, so the evading logic wants to run every tick as well. But optimizing that will be up to the player..

I’d recommend cheating! It only has to appear to the user that the bot is scanning the world. For example in this specific case you could find all the projectiles close enough to the bot to be detected and do one raycast per projectile to determine visibility. This is functionally the same result as many dense raycasts but at a fraction of the computational cost because you have all the information already in the simulation.

Although I really like the idea of giving the player control over how the bot raycasts and letting them optimise that. Lots of fun strategies to find there! I’d even bound it so they can’t afford to do too many raycasts so they have to get creative.

> Although I really like the idea of giving the player control over how the bot raycasts and letting them optimise that. Lots of fun strategies to find there! I’d even bound it so they can’t afford to do too many raycasts so they have to get creative.

This is actually exactly what I did when I built a similar game about a decade ago! Bots had a budget of 20 raycasts per second, which would slowly replenish. It was the bot programmer's responsibility to figure out the best way to use them. It was a lot of fun! :)

"It sounds like you are trying to query every angle in every direction for every character. This is madness."

It is just a different game than yours, so maybe don't judge?

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)

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

You can still optimize this. If the scan has to establish line-of-sight between bots, your engine can establish that, and when firing raycasts, to skip those that are known to be misses. It doesn't change anything for the bot that fires raycasts. You could also calculate extremes (leftmost and rightmost) and return positives in between. This would decrease number of raycasts by two orders of magnitude. Also add a possibility to skip every 2nd, 3rd etc frame so that you can evaluate if it impacts game play.

Wait. I was thinking 1000s of objects doing raycasts.

Ideally yes, this is what I would like to do, to be able to control armies of bots. So because of the limitations, there are only 2-3 smart bots and lots of dumb ones.

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

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.

Thanks for that! I will have to take a deeper look.

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.

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

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.

I learned to code in the 8-bit days where you'd count to 1000 in a BASIC for loop to create a significant delay. I guess I've not got out of the mindset that doing anything 1000x is quite a lot (particularly when you're aiming to do it 60 or more times per second).

But as somebody working in Unity (and often on mobile), there's still many cases where 1000 of something is a lot, and should perhaps be cause to rethink your approach. For example 1000 draw calls, 1000 UI elements, 1000 instances of even the most simple prefab.

1000 raycasts per frame is also something that I'd try to avoid. But if they seemed important, you've just got to try it and profile it. Nobody can answer 'what is the cost of 1000 raycasts?' without a fair bit more information.

I agree that profiling is the ultimate arbiter.

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.

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.

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?

The original complaint was that Godot’s C# bindings have a raycast method that returns a dictionary. The reply article point out that this is a legacy of an earlier, less performant, C# implementation and that the work to clean it up was already under way. My point is only that raycasts are already something that you want to avoid; the extra work of allocating a dictionary each time you call it is unfortunate but not fatal.

Maybe there's thousands of guns being fired.

Ok, if you’ve got thousands of players in the game then you’re doing _something_ right, even if the raycasts aren’t helping :)

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

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

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.

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

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/

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.

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.

Reply on news.ycombinator.com