1
\$\begingroup\$

I want to create an effectively infinite world, like Minecraft, where chunks are generated as users come close to the edge of their current chunk.

As I understand it, monsters in Minecraft are put to sleep when the chunk they are currently in is unloaded (as far as I understand, if a player moves away from a chunk and that chunk is not close to any player, it is unloaded). That is, they don't move or do anything, and are just stored statically on disk.

This means that all the monsters are effectively territorial and have the behavior of being awake only if a player is nearby - otherwise they sleep forever.

EDIT: Actually in Minecraft mobs despawn when a certain distance away from the player, resulting in a more random experience.

What if I want to simulate the behavior of large scale migrating herds? In an infinitely large world, there should be infinitely many monsters randomly wandering around. There might be herds of monsters wandering around. Obviously they cannot be all loaded in memory at once.

Now, if a player discovers such a herd, he might want to walk away some distance, and then come back later to follow the herd's tracks, which might be quite some distance, but he will eventually catch up to it. This seems impossible with Minecraft's way of dealing with loading/unloading chunks.

Is there some way of simulating long distance monster migrations whilst maintaining Minecraft's advantage of having memory usage be linear with respect to the number of players (rather than the size of the world)?

\$\endgroup\$
  • \$\begingroup\$ Minecraft deletes the monsters shortly after they exited the updated chunks \$\endgroup\$ – Bálint Sep 3 '17 at 19:34
2
\$\begingroup\$

To have consistent mob migration without storing & ticking them all, the mob behaviour has to be something you can query as a function of time & space.

ie. Given a point in spacetime, your system needs to be able to answer "what mobs are nearby?"

Probably the easiest way to do this is to make mobs migrate on periodic paths — loops or lines across your world, where a mob crosses a given point on the path at regular intervals (either the same mob looping around, or a new mob following the same trail).

There are ways to make these behaviours aperiodic & more organic too, but that can be added as an extra layer of complexity later, if you find you need it, so I'll focus on the simplest case for now, assuming roughly circular periodic migrations.

  1. Generate a psuedorandom seed based on the location of your chunk, using something like a spatial hash function.

  2. Use this seed to pseudorandomly choose parameters:

    • mob composition
    • center of migration route (within this chunk)
    • radius of migration route (potentially outside this chunk)
    • frequency & phase offset of migration

    Because these are chosen from a seed that depends only on the chunk's location, whenever you arrive at this chunk you'll generate the same mob parameters, so they remain consistent even if you walk away.

  3. Based on these parameters, we know where the mob will appear at any point in time:

    phase = 2π * frequency * time + phaseOffset mob.x = center.x + cos(phase) * radius mob.y = center.y + sin(phase) * radius

    You can displace this curve to be more organic, or to conform to walkable portions of the chunk(s) it crosses (since by the time you're close enough to realize the mob, you should have the terrain it crosses loaded), as long as this displacement is deterministic.

  4. Now, when we enter a new chunk, we can query the location of this chunk's mob(s), as well as the mobs of any chunks within the maximum migration radius, to see if any are close enough to realize.

This approach isn't without its problems. If you kill one or more members of a mob, then walk away and come back so it's re-realized from the math formulas above, poof, those dead members will have resurrected.

To prevent this, you'll want to store the states of any mob the player interacted with (or observed them interact with each other, if you have predators who chase prey, for example). You don't need to store this data forever, thankfully. The data can "decay" over time and ultimately be discarded once it's old enough that the mob could plausibly have returned to its natural state (or that the player is likely to have forgotten them) When you want to query a mob, first check if it has one of these "exceptions to the rule" stored, and modify the result accordingly.

This strategy can also cause issues if the player can lure or herd a mob off its prescribed course. Once again you can store this detour and offset the mob's migration until sufficient time has passed for them to get back on-track.

This should give at least a basic recipe for implementing this kind of feature, with room for elaboration.

\$\endgroup\$
  • \$\begingroup\$ If the pattern is periodic, wouldn't it make more sense to use modular arithmetic than pseudorandom generation? \$\endgroup\$ – user2108462 Sep 4 '17 at 8:44
  • \$\begingroup\$ Periodic in time, but also continuous in time. Doing this with trig functions gets us both these traits AND the initial shape of the path with any floating point time period we choose, while modular arithmetic would constrain the period selection to large integers. It's equivalent in the end, but takes more care. For paths with limited wander, we're not required to be periodic in space, hence going pseudorandom to see more variation across the map. Migrations along unbounded curves are easier to implement periodically in space though, since many widely-separated chunks share a curve. \$\endgroup\$ – DMGregory Sep 4 '17 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.