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.