Handmade Hero » Forums » Code » Simulation Region question
Fred
20 posts
1 project

None

#2617 Simulation Region question
2 years, 4 months ago Edited by Fred on Feb. 12, 2015, 2:01 p.m.

Regarding last night's stream about refactoring the low and high entity logic (I haven't watched the whole thing yet, I'm 50 min in).

Casey explained at the beginning that he plans to use a simulation region to update the game in the background for all the areas that aren't directly under the focus of the main camera.
He explained that this "virtual" simulation region would scan/cycle on the entire world to update the simulation there at a lower frequency.
But I don't quite get how this is going to work.
Let's say we have an NPC (like a bird) in a far region of the world. And we want to have that NPC move in a straight line to reach the hero.
That NPC would have a certain velocity, like the equivalent of moving a screen width in 3 seconds. So, at 30fps, that NPC is expected to move by 1/90th of a screen width per frame.
But how do we accurately simulate this with a "sliding" simulation region?
If the "sliding" simulation region needs to update 10,000 non-active areas, at the rate of one per frame, it means that our NPC motion would only be simulated for one frame every 10,000 frames, or once every 5 minutes.
I see two possible schemes at that point:

1) If the delta t used to move the NPC is one frame worth of time (33 msec), then the NPC would effectively move 10,000 times slower than its expected speed.
But this means that the effective NPC movement speed has to be capped dramatically. The effective speed on background entities would depend on the background simulation speed.

2) If we use a delta t of 5 minutes to update the NPC movement, then we run into the issue that his movement increment would be ~100 screen width during the simulated frame. Casey talked about creating a buffer zone of high entities around the simulated region to account for collisions when simulated entities leave the simulation region, but there's no way we can make it 100 screen wide obviously.

Am I missing something?

None
norswap
29 posts
#2618 Simulation Region question
2 years, 4 months ago Edited by norswap on Feb. 13, 2015, 12:23 a.m.

I second the question; and I'll add three of my own.

A.) Aren't we violating the "make the usage code first" rule by implementing the simulation regions now? We don't yet have entities that do things while not being close to the hero. It does seem we're not even sure what exactly we want them to do when they are far away. (By the way, I guess the same remark could have applied when the high/low entity system was being introduced.)

B.) Since entities can cross region boundaries, how do we "sync" region updates? This problematic is present in Fred's questions as well. The problem with updating remote regions more slowly is that each update must account for a larger time slice. This means we risk missing collisions (and other events) that would have occurred if we had updated the whole world multiple times with shorter time slices.

C.) Do we really want remote entities to act like entities on the screen? Simulating the whole minute collision and pathfinding process (and maybe other things besides) seems very expensive.

The way I would have envisioned it is to have high-level policies: things like "gobelin wants to steal an apple and bring it back to its den". Then we can simply give a time diff and estimate how far along the task the gobelin is, as well as his state. In this case, it would impact the gobelin's position, as well as whether he's carrying an apple. This estimation can be much more rough than the pathfinding we do on the screen displayed to the user.

Additionally, the user doesn't really care about remote encounters between NPCs. Imagine a wolf moving south meets a sheep going north and eats it; the player will not have the awareness that this happens. If we really want to model these dynamics for some reason, we can generate these encounters following some model/distribution and enact their consequences (e.g., put a sheep skeleton on tilechunk 21). The user won't be able to tell the difference.

Finally, I think many entities might have a fundamentally different behaviour depending whether the player is present or not. In those cases, it's not really true that we would need to code everything twice (once for when the player is on-screen, and once for when he isn't).
cmuratori
Casey Muratori
799 posts
1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#2623 Simulation Region question
2 years, 4 months ago

The idea is as follows:

1) Hopefully, we will be able to update _more_ than two simulation regions per frame. The idea would be to do as many as we can, and hopefully across multiple cores, so that we would at least be doing 64 regions per frame, etc. So even if we updated the 10,000 region case, we'd be talking a few seconds per update, not 5 minutes.

2) We don't need to update any regions that don't have entities in them that are active, so we can effectively prune the number of possible simulation regions down quite a bit from the total number of regions in the game. For entities that are not acting in a global way at the moment (like trees or something), those regions of the world never have to be simulated at all.

As for writing the usage code first, no, I absolutely did write the usage code first :) The entity code we have already was difficult to write, in my opinion, in a way that would allow lots of such entities to work around the world. Just moving the familiar and the sword was causing problems. So we already had the opportunity to make a good code upgrade, because the problems were already obvious. There was not a lot of point in doing more things, because basic entity movement needs to be handled well with the large world / large entity count model, and once we have some kind of structure for that, we can start to see if we need other superstructure things (like for pathfinding, etc.)

- Casey
norswap
29 posts
#2625 Simulation Region question
2 years, 4 months ago

Okay, the fact that we have a bootstrapping issue (need to have some kind of infrastructure to test with a lot of entities) is a fair point!

I'd really appreciate it if you could address questions B. and C. though (especially C.).
cmuratori
Casey Muratori
799 posts
1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#2631 Simulation Region question
2 years, 4 months ago

With continuous collision detection, there's no such thing as "missing" a collision, so that's not an issue. We have to deal with that either way because collision detectors that can fail due to timestep problems can fail just in general, so we don't want that either way.

For C, either it is or isn't a problem, we'll see. If it is a problem, then we just make a superstructure for pathfinding and we use it when updating the non-camera sim region. It's really easy for us to set flags on a sim region now, so we can actually do anything we want in terms of spot improvements to performance.

- Casey
d7samurai
66 posts

innovation through innovation™

#2632 Simulation Region question
2 years, 4 months ago Edited by on Feb. 14, 2015, 12:47 a.m.

Regarding NPCs "on a mission":

It would be possible to have a "priority list" reserved for entities involved in current quests or events in the world that need to be simulated in coordination with the hero even if they are far away.

Entities on this list would be visited every frame (or nth frame), regardless of where the "low frequency region update" iteration is ATM, ensuring that they are always sufficiently in sync.

At the start of a quest, the pertinent entities would be placed on that list (and perhaps the number of "regular off-screen regions to update" decreased accordingly, to keep the load per frame ~constant) and flagged to only be updated in relevant ways (no need for accurate collision detection etc - just make sure it visits the places it needs to / throws switches / drops items and so on).

software development should be a creative exercise, not a technical ordeal
cmuratori
Casey Muratori
799 posts
1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#2636 Simulation Region question
2 years, 4 months ago

Exactly. We can prioritize regions of the world where we think interest is warranted, etc. I think the sim regions give us lots of flexibility to do whatever we need to do as the usage evolves throughout the development of the game proper, and that's very important!

- Casey
ikerms
Iker Murga
43 posts
#2640 Simulation Region question
2 years, 4 months ago

It looks to me like something as silly as there is an X% chance of Y character appearing on screen moving on Z direction might be indistinguishable from constantly simulating the whole world to someone playing the game (would need to be tweaked a lot but I think it could work).

Casey, what I have assumed until now has been that you have some specific events in your head for the game for which a simple random system would not work and that is the reason why you have decided to simulate the whole world constantly.

I also thought another possible reason might was that you made it more complicated for the educational value.

Am I wrong on both counts?
cmuratori
Casey Muratori
799 posts
1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#2643 Simulation Region question
2 years, 4 months ago

Both are true, actually!

- Casey
Fred
20 posts
1 project

None

#2652 Simulation Region question
2 years, 4 months ago Edited by Fred on Feb. 14, 2015, 2:08 p.m.

I've been wondering about this from the point of view of "worst case scenario" that Casey brought up a while back in the stream.

It seems to me that with the original high/low entity approach if we could simulate about N entities with high quality physics/AI in the main screen at once, we wanted also to be able to simulate a much higher number (say O(N^k)) of non-visible entities in the background using simpler physics/AI.
This was more about solving scalability. But the downside was that this would introduce two levels of logic for physics, AI, etc.
Also, it could just happen by chance that a high number of active entities converge onto the main screen/region at once (we never talked about limiting this in anyway), like the hero and three big gangs of monstars all running into each other. So the worst case scenario really is "given our high quality physics/AI, how many entities can we handle at once on the screen?".
Being able to do O(N^k) low updates in the background is nice, but it's a lot of work for something that's not the worst case scenario and that the player would basically never even see.
An example of a game style that could benefit from this is more like a RTS where you can zoom in down to the individual soldier level, with advanced path finding around detailed environment, explosion/bullet physics, etc and then zoom out to the world level where you see battles on a huge map where troops are abstracted into symbolic entities (tank divisions, etc) and the outcome of encounters there are computed using dice rolls, etc.

The new approach of just having simulation regions using the same physics/AI is more about focusing on worst case scenario and flexibility.
So if we can manage N entities at once on the main screen (not taking into account rendering), then using the new approach I don't think that we can expect to update correctly much more than O(N) entities globally using multiple simulation regions (even if at a slightly lower frequency, etc).
But that's okay because we can now focus on improving the worst case scenario (increase N).
And this also adds extra flexibility, like handling splitscreen.

None
norswap
29 posts
#2656 Simulation Region question
2 years, 4 months ago

Okay, thanks for the answers! And in the end, we'll see how it pans out anyway.
cmuratori
Casey Muratori
799 posts
1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#2681 Simulation Region question
2 years, 4 months ago

Actually, I think we can still solve the scalability problem with simulation regions. A simulation region could be marked as high or low frequency, and then certain operations that are expensive could be specially written for the low frequency case. This gives us all the benefits of my original approach, but with the massive improvement that you only have to recode the sim parts that are actually causing you performance problems, rather than all of them.

- Casey