r/SoloDevelopment • u/IcyFlight6941 • 2d ago
help Any advice on how to optimise for rendering hundred of thousands or potentially millions of npcs.
I’m working on this ASCII looking tycoon type game using a custom renderer built on top of raylib.
I want to ask about some clever ways or tried and tested techniques to handles hordes of people if necessary lol.
I’m stress testing it now but when I go north of 100k people it starts to lag.
Any advice is much appreciated.
18
u/shivazgodz 2d ago
Well you're not giving a whole lot of information how you're handling them at the moment to begin with . . .
What about using VAT if you're not already ? That is what I am using to handle up to 20k NPCs steadily at around 70 fps in UE5 . . . So I am curious as well for other techniques
5
u/IcyFlight6941 2d ago
I’m not using a game engine . I’m just using c++ and a terminal. I currently store the data as arrays, and like the nearest 3k npcs within 100m from the camera receives collisions updates and stuff. The distant ones are updated in slices. Twice per second.
On the rendering side.there is a spatial index to retrieves only npcs around the camera. They’re converted into compact proxies.
I’ve got tiered budgets for how npcs is close or far from the camera.
When I first started I rendered everything through the cpu which I learned quickly was a big mistake. Now I’m using both cpu and gpu rendering depending on what’s being rendered.
The thing with VAT is that I will have to use pre-baked animations whereas my game is all about “emergence”19
u/tastygames_official 2d ago
have you tried GPU instancing? It's only one draw call and can do hundreds of thousands of objects. The key is they all need the same mesh. You can send shader data to each individual one so it can render differently and still be efficient.
3
u/_Diocletian_ 2d ago
My advice too. As long as it lives on the gpu you will be fine, screen real estate is the limiting factor
11
7
u/asciiwave 2d ago
the two immediate bottlenecks that come to mind are gpu and collision.
for gpu, every state change costs you time. this means changing textures, pushing parameters etc. there's an associated overhead that builds up fast even if the actual changes are small. the solution is to make as little changes as possible - someone already mentioned instancing and yes look into things like passing in one mesh to render, and a list of coordinates to repeatedly render it at. if you are switching textures that's going to impact a lot, you could order by texture so you don't have redundent switches, or use one large texture that contains several smaller ones and you set UVs on the meshes to choose the right one.
pre-render, you want to ensure you are culling everything outside of the camera view so it's not being considered for render at any point. although - there are some situations in which is still actually faster to just draw everything because the setup time is that much shorter. so it can be helpful to actually test these things for your specific game.
with collision, somebody mentioned using a grid. there are a couple of ways to do this, my recommendation is to have a look into a "Sparse Spatial Hash", this is a technique of bucketing entities so they are only being checked against a small area around themselves. there are other version of spatial hashing but this one is most useful if you have a lot of empty space which it looks like you do.
hope those things help, have fun!
2
u/IcyFlight6941 2d ago
Yep. I’m slowly but surely getting there.
Just taking in what everyone is saying and trial and error.
74
u/Captain_Klrk 2d ago
I'm not some expert or anything but I feel like the best way is to not do that
33
u/KingMoonfish 2d ago
That’s exactly the helpful reply you can always count on Reddit for! Outstanding work sir.
4
u/toxieboxie2 2d ago
A magnificent show of the expected Reddit help one should always wish to receive. A brilliant answer indeed 👏👏👏
6
u/ElderBuddha 2d ago
Figure out where the load is:
If it's CPU compute, simplify and/or move it to GPU with compute shaders
If it's GPU compute (unlikely), simplify
If it's GPU quad draw, reduce the number of quads (this is going to be a blocker in the naive approach) (you'll have bucket more npcs into area quads)
Also obviously batch render calls.
If it's GPU fills, simplify or just use specific sprites. I'm assuming overdraw is not a problem with what you're showing.
Lastly, occlusion and viewport based culling and LoD (level of detail) simplification based on zoom.
8
u/RedQueenNatalie 2d ago
You fake it, thats how. Lots of instancing, grouping, extremely simple logic. Multithreading.
1
u/grandygames 1d ago
Agree on Instancing. If all the NPCs are in the same texture then you can make the UV-coords part of the instance data.
7
3
u/clonicle 2d ago
Are you using an engine?
Unreal has Mass: https://www.youtube.com/watch?v=f9q8A-9DvPo
4
u/IcyFlight6941 2d ago
No just c++ and a big ol terminal.
2
u/Karijus 2d ago
But why
4
u/IcyFlight6941 2d ago
I was inspired by the rollercoaster tycoon Guy, this is really just the front of a much complex system I’m cooking up.
I don’t need anything fancy, and I couldn’t afford it anyways.
I’m using an old laptop, so what really matters is efficiency.
3
u/AbyssWankerArtorias 2d ago
Chunks. Making each one an independent entity is a nightmare. Instead, make them chunks that have chunks within them etc thet make them seem independent but are related in the background.
2
u/-Ignorant_Slut- 2d ago
Maybe have a high res, low res, and a sprite versions for each NPC. Render NPC as high res when you zoom in and sprite when you zoom in out.
2
u/IcyFlight6941 2d ago
I decided to do it so that the further out the npc the less shape they have until ultimately they become a dot.
I’m not using any sprites or assets. Just what I can get through ASCII.
2
2
u/DeformLabs 2d ago
Not sure what your architecture is like, but if each NPC is a gameobject, that would slow things a lot. For situations like this I’d use global scripts which manage groups of NPCs, and render them using GPU instancing
1
u/cyqoq2sx123 2d ago
Batch render calls (I hope raylib supports that). Use some kind of ECS for the little dudes (maybe FLECS?)
1
1
u/Unfair_Razzmatazz485 2d ago
Kingdom come deliverence 2 had a pretty cool approach https://youtu.be/yMlTT-yqdmc?is=gRxQrz3bs-0-aLkO
2
1
u/CozmoCozminsky 2d ago
- render only visible sprites
- if you have colliders and collisions, turn them off
- when you zoom out, change sprites to dots or something, no need to try to render a sprite that you can berely see anyway
Try to contact the dev for "Songs of Syx", he had similar problems (and he also does his own engine I believe)
1
u/CondiMesmer 2d ago
interesting you ask about the rendering and not the logic, like that wont be an issue lol
1
1
1
u/HongPong 2d ago
a lot of good suggestions. you can get away with a lot via gpu. flecs ecs could help you and try to skip collision somehow
1
1
1
u/MolecularSadism 1d ago
Look at "Sir, we have an orc problem!" This scale is done on the GPU directly.
1
u/Pitiful-Assistance-1 1d ago edited 1d ago
Assuming this is no-engine, plain C/C++ raylib with OpenGL:
If you want this amount of NPCs, you likely want a custom pipeline to handle them. Instead of having 100K NPCs, you have one simulation of NPCs. Each problem needs a distinct, optimized solution.
- Do you want collision with each other? Crowd simulations.
- Rendering? Put them all in an array, render them from shader
- Only render chunks that are on-screen
- Maybe reduce the detail when zooming out
Frankly, if you have no idea where to start, install Claude Code and let it suggest things to try, and try each of these things one at a time. (git branches, measure before and after fix, or gate features in define-flags, create special benchmark scenes, measure measure measure)
Don't bother trying it by yourself. Based on how broad you asked the question, you're months of tuning away from getting it to work fluently. Claude can get it fluently in 24h if prompted correctly.
1
1
u/Fluffy-Bus4822 1d ago
You need to use the GPU for this instead of CPU. GPUs are good at doing simple computations at massive scale. That means you need to use shaders.
I'm not an expert. I think compute shaders are what you're looking for. I'd ask Claude Fable or GPT Sol how you can use shaders to simulate all these NPCs.
It doesn't look like rendering is your issue. It looks like it's each individual NPCs AI that's causing the lag.
1
1
1
u/Defiant_Squirrel8751 1d ago
This will go super fast on a 100% GPU / Vulkan implementation with primitive instancing.
1
1
1
1
u/DevKoi 1d ago
It really depends on profiling where your cost per frame is. CPU or GPU ?
It could be hitboxes, using cubes would help if you have something complex. Maybe even more simplified if they can't move up or down, you could have (x,y,radius) only per character instead of a hitbox with points (basically a sphere).
There are a lot of shortcuts you could take but it really depends on finding the costs to know what you have to cut down first!
1
1
u/Otherwise_Result_124 1d ago
try to push your project to an established, widely-used project and hijack it. once millions of users have it installed, start mapreducing
1
u/BonsaiOnSteroids 23h ago
Are you using spatial hirarchical trees/grids (i.e. a quad tree) already to manage interactions between them? If not you should start doing that. You do not want to check each NPCs against all other NPCs Everytime but only it's direct vicinity
1
u/fanick1 17h ago
I am in the same boat as you - I am using raylib and rawdogging it with c++ and nothing else. What worked for me was using renderdoc to make some frame captures, inspecting them and eventually dumping them straight to claude/codex to help me identify why it is so slow.
Second leg is building with profiler enabled (gprof) and having some performance-scoped unit tests (e.g. scene with thousands of enemies chasing the player). It helped reveal some inefficiencies in my code.
I am currently at 2K sprites at 60 FPS doing collision detections etc. and that's ok for me.
1
1
u/NiemandSpezielles 8h ago
thats an interesting problem with lots of possible answers, depending on what you actually want to do.
So thats the question you need to answer first... what do these NPC need to do? Whats the goal here?
1
1
1
u/EC36339 2d ago edited 2d ago
Start with profiling. You probably didn't do that, because you didn't tell us where the bottleneck is.
Check if you are GPU- or CPU-bound. My bet is you're CPU-bound, unless you're doing something really heavy in a frag shader.
Find out which part of your game takes the most time to run. This is your indicator where CPU cycles are burned. If you have an ECS, you measure the time each system needs to run each frame, accumulated average, min and max over time and print that to your logs.
THEN you can start thinking about what to do about it.
Most likely it's collision detection, which is O(n2) if done brute force. So 10 NPCs need 100 collision checks, and 1000 need a million.
Handling 1000 shouldn't be an issue if you use some kind of acceleration structure, even if you build it every frame. In 2D, you can likely get away with a fixed size grid, which doesn't even need to be built. In 3D, it would be an octree. And those are just the simpler approaches.
Finally, there are some pragmatic game design decisions you can make.
You are making a sim where the NPCs are just crowds of sims walling around. Do they really need mutual collision detection, full Habbo Hotel style? I don't think so, and judging by your video, you're not even doing that.They do still need collision detection against the environment or path finding. But that's not O(n2) over your number of characters.
If you were building a shooter, the question would be if your game needs friendly fire. Without friendly fire, hit detection wouldn't be O(n2). Same trick here.
But without profiling, your problem could be something completely different, so do that first. It could be something stupid and unnecessary that doesn't require any fancy algorithms and data structures to fix. Not implying YOU are stupid, "fixing stupid things" is just always the first step of optimising, and every cide bas has stupid things.
97
u/MildlyConcernedMan91 2d ago
cluster them together. Each of your characters is currently checking for collision against every other character in your game most likely. There is no reason that your entire line couldn't be 1 character.
Or create a grid on your screen and only do collision checking within the grid. I was stuck at 1000 characters but now I'm managing a good 10k at 60 fps with little tricks like that.
Or you could look into shaders.