Jump to content

  • Curse Sites
Become a Premium Member! Help
Latest News Article

Mob spawning algorithm in 1.2_01 analyzed


  • This topic is locked This topic is locked
57 replies to this topic

#1

Marglyph
    Marglyph

    Redstone Miner

  • Members
  • 535 posts

Posted 20 January 2011 - 09:31 PM

Hello. I've been spending some time recently with the decompiled mob spawning algorithm for patch 1.2_01, both looking at the code and adding logging statements to see what goes on in live games. I created a forum account to share my findings, since the Mob Spawning Science thread is now well out of date.

Here it is! First, I'll go over the entire algorithm itself as it is implemented now, then take a stab at what it all means. If it's tl;dr... oh well :Sheep:

The Algorithm

1. Place the 289 chunks that are in a 17x17 square centered on the player into a HashSet. (In multiplayer, the areas around each player are added, and overlaps are counted only once).

2. Loop through the three basic mob types: monster, creature (i.e. animal/passive), and waterCreature. For each mob type, separately do the following:

4. Check whether the mob limit has been exceeded, and if so skip this mob type. The limit is equal to a constant times the number of chunks being considered, divided by 256. The constants are: monster 70, creature 15, waterCreature 5. In single-player, this means the actual limits are: monster 79, creature 16, waterCreature 5.

However, this doesn't mean what it sounds like. The cap is checked before looping through the chunks, not for each chunk, and each chunk can spawn up to 4 monsters, which can cause spawning well over the "cap." E.g. I got 17 squid once while testing because 3 groups of 4 spawned when there were already 5 (the "cap").

3. Loop through the chunks in whatever order the HashSet gives them to you. This is a deterministic order! I discuss this more in the Analysis section. For each chunk, do the following:

4. Pick a random mob type that is within the current basic type and appropriate to the biome.

5. Generate a random coordinate inside the chunk.

6. If there's a solid block there, skip to the next chunk.

7. If the mob type is waterCreature and the block isn't water, skip to the next chunk.

8. Make a total of 12 attempts to place up to 4 creatures in a sort of normal-ish distribution centered on the chosen point. The maximum possible displacement is 20 east or west, 20 north or south, and 0 up or down, but it's far more likely the points will be much closer to the original point. (Note: there is randomization in the code for elevation, but it uses nextInt(1), which will always be 0.)

9. For each of these coordinates, first check whether it's possible to put a mob there.

9a. For a waterCreature, check that there is water at the coordinate and that there is not a solid block above the coordinate.

9b. For a monster or creature, check that there is a solid block below the coordinate, not a solid block at the coordinate or above the coordinate, and not water at the coordinate. (Note: this applies to spiders, too, so they cannot spawn under a 1-high ceiling).

10. Make sure the coordinate is not within 24 meters of any player or the world's spawn point (3D Cartesian distance -- i.e. the zone of exclusion is a sphere.)

11. Assuming all those conditions have been met, generate a mob!

12. If the mob is a spider, roll a 1 in 100 chance of it having a skeleton rider. (The same function makes colored sheep).

13. Perform entity & block collision checks on the mob's bounding box.

14. If ALL that succeeded, increment the count of mobs spawned in this chunk and actually place the mob. If we've placed 4 mobs, skip to the next chunk.

Analysis

1. (Section removed) There is no apparent way to exploit the order in which chunks are traversed. The proof of this was in my own post and I didn't even realize it at first... It's still unclear whether flat traps or towers have an advantage without further testing.

2. Typically, the mob limit fills up extremely quickly.

3. All ways of preventing spawning in an area are equivalent (due to no more bailout). Lighting, filling, half-steps, etc. And the only reason to prevent spawning now (as far as traps are concerned) is to keep the mob limit from filling up outside your trap as quickly. Over the long run, however, unless you manage to completely fill/light/clear an entire 272x272 block area (good luck!) mobs will spawn outside your trap, so it's more important for your trap to be very likely to receive spawns when things despawn/die.

4. The algorithm appears to favor areas with contiguous spawnable area. The *initial* random coordinate chosen has to be non-solid (and water for water creatures) and the random coordinates around it have to be as well. Occasionally one of these nearby coordinates will be the original coordinate, but not most of the time. So most of the time, the algorithm requires at least two nearby coordinates at the same elevation to both be acceptable. Theoretically, this should make spawns rarer on steep hills, thin bridges/peninsulas, etc., than in flat areas.

5. I don't understand despawning yet, and would appreciate someone giving me the class/method name to look at if anyone knows. I do know, however, that there is a lot of despawning, so understanding it is important! I started a new world and logged all monster spawns. There were:

963 the first day, mostly underground
448 the first night, weighted more toward the surface but still many underground.
728 the second day, mostly underground
361 the second night, weighted toward surface

Obviously there must be a lot of despawning since more will not spawn over 79 at any given time.

6. Controlling squid spawning is really difficult. It's very likely for 4 at a time to spawn in oceans, reaching the limit quickly. Even using MCEdit to fill the entire spawn region in cobble and air, and make a pool, I had trouble because any small mistake with water around the edges would lead to them spawning there instead of my pool. Furthermore, since there will often be more than 6 squid in existence, you may have to kill more than one to allow more to spawn. As if that weren't enough, you can't force them to despawn using peaceful mode since they're non-hostile. (Added) Squid also do not despawn naturally.

(Added) 7. Hypothetically, a mob trap with air around it should spawn marginally more than one with solid blocks around it (i.e. a floating trap might outperform a buried trap... somewhat.) This is because a point could be chosen outside the trap and still spawn inside the trap (because of the distribution around the chosen point). If that point contains a block the chunk will be skipped, but if it contains air it'll be given a chance.

Notes

1. The algorithm is in bp.class. I used Fernflower to decompile the code after finding that JD-GUI made important mistakes (such as not decompiling enum values, and doing some loop control flow wrong.) It's possible that there are still some mistakes in the decompilation, but I think I've got it right.

2. Any of this may of course change with any future patch, as it already has changed quite a bit! Personally, I think that chunk traversal should be randomly shuffled. If this is too CPU-intensive, a bunch of shuffle orders could be pre-generated, meaning only one more random number per execution of the spawn function.

3. Minecraft internally uses x,y,z coordinates where x is north-south (increasing to the south), y is up-down (increasing up) and z is east-west (increasing west). So top-down coordinates (e.g. chunks) are actually (x,z) not (x,y).

That's all I've got for now. Anyone want to try some more empirical testing?

Register or log in to remove.

#2

Wrathful
    Wrathful

    Redstone Miner

  • Members
  • 566 posts
  • Location: Athens, GA

Posted 20 January 2011 - 09:35 PM

Excellent data. Thanks for your contribution!
If you wish to make an apple pie from scratch, you must first invent the universe.
--Carl Sagan

I am Scjoiner on YouTube. Check out my insane redstone stuff. Scjoiner's Channel

#3

nathanle
    nathanle

    Redstone Miner

  • Members
  • 594 posts
  • Location: World 3

Posted 20 January 2011 - 10:06 PM

thank you, this means that there must be a water pool in a cave somewhere beneath my aquarium that is stealing all the squids.
[insert inspiring and original signature here]

#4

dobby200

Posted 20 January 2011 - 10:38 PM

Thats some awesome work there. It looks like some new mob grinders could start appearing!
Drowning?
Eat bacon.

#5

Amphouse

Posted 20 January 2011 - 10:56 PM

Excellent first post, I want people to see this.

Ultra-Orange said:

Direwolf20 said:

#37) Ores tend to spawn in packs
If you take one out you better be ready to take on its angry cousins!

Took out an over head coal node once and was snuffed by a gang of Gravel seeking revenge!
Posted ImagePosted ImagePosted Image
Posted Image

#6

MadCows
    MadCows

    Zombie Killer

  • Members
  • 152 posts

Posted 20 January 2011 - 11:13 PM

do you have any insight as to whether or not slimes have actually been added back in and if so under what conditions they spawn? I only ask because I just read a thread saying they were back but others were saying they never left and other such contradictory claims.

Blaze said:

stinkbom333 said:

Use a pick Axe. It Has 2sticks and Three Rock/Materiel lined on top
I... but... what... who doesn't know this!? I don't even...

#7

DavidB1111

Posted 21 January 2011 - 12:06 AM

Notch himself said slimes are in, according to the Coesquest livestream he was on.

They are just extremely rare, until such times he finally fixes the remaining problems with them.
I believe that's why he made them rarer now.

They only spawn close to the bedrock, and only in certain areas. Combine that with how rare they spawn now, and they really are hard to find. :Pig:

But they are there.
I have Asperger's Syndrome, a mental disorder of the Autistic Spectrum, apologies in advance if my posts seem a bit off.

#8

Marglyph
    Marglyph

    Redstone Miner

  • Members
  • 535 posts

Posted 21 January 2011 - 12:07 AM

I wrote a Java utility to calculate what order chunks around the player will be traversed by the spawning algorithm. Generally, there are clear patterns and often the first chunks traversed are in a row. Source: https://gist.github.com/788949

MadCows, sorry, slimes aren't spawnable. The biome definitions in hf.class are accompanied by lists of monsters, creatures, and waterCreatures that can be spawned. (Which, right now, are the same for all biomes except for hell/nether, which has its own subclass). Slimes aren't there.

#9

MadCows
    MadCows

    Zombie Killer

  • Members
  • 152 posts

Posted 21 January 2011 - 12:20 AM

DavidB1111 said:

Notch himself said slimes are in, according to the Coesquest livestream he was on.

Marglyph said:

MadCows, sorry, slimes aren't spawnable. The biome definitions in hf.class are accompanied by lists of monsters, creatures, and waterCreatures that can be spawned. (Which, right now, are the same for all biomes except for hell/nether, which has its own subclass). Slimes aren't there.

once again, there's still a bunch of this:

MadCows said:

I just read a thread saying they were back but others were saying they never left and other such contradictory claims.

I think I'm more willing to believe Marglyph who has looked at the actual spawning code but that doesn't explain why Notch would have said it's in if it isn't. DavidB1111, did you actually see the quote?

Blaze said:

stinkbom333 said:

Use a pick Axe. It Has 2sticks and Three Rock/Materiel lined on top
I... but... what... who doesn't know this!? I don't even...

#10

DavidB1111

Posted 21 January 2011 - 12:28 AM

Marglyph said:

I wrote a Java utility to calculate what order chunks around the player will be traversed by the spawning algorithm. Generally, there are clear patterns and often the first chunks traversed are in a row. Source: https://gist.github.com/788949

MadCows, sorry, slimes aren't spawnable. The biome definitions in hf.class are accompanied by lists of monsters, creatures, and waterCreatures that can be spawned. (Which, right now, are the same for all biomes except for hell/nether, which has its own subclass). Slimes aren't there.

Maybe you're looking in the wrong place? Because Slimes should be spawning. Notch said they should be in the game. If they're not in the code, then you should tell Notch immediately so he can fix it.


Madcows, it's in the Coequest Livestream. I can provide the Youtube link. But you're going to have to watch for probably 20 or so minutes until Notch said it. I don't remember the exactly time.

i was there in the Livestream the moment Notch said that Slimes were back, and that they should spawn.

I know Margylph looked into the code, but it might be somewhere else. It doesn't really make sense for Notch to say that they are in the game, if it isn't true.
I have Asperger's Syndrome, a mental disorder of the Autistic Spectrum, apologies in advance if my posts seem a bit off.

#11

corveroth
    corveroth

    Tree Puncher

  • Curse Premium
  • Curse Premium
  • 20 posts

Posted 21 January 2011 - 12:35 AM

It could simply be that Notch was mistaken. It's been known to happen, and he's not the only person with access to the source code. He could've missed a change, or even forgotten that he changed it himself.

I'll concede that it is theoretically possible that the slime-spawning code is somewhere else entirely, but it wouldn't make much sense. That would require duplicating at least some of the code (generally considered a bad practice) for questionable gain.

#12

Marglyph
    Marglyph

    Redstone Miner

  • Members
  • 535 posts

Posted 21 January 2011 - 01:08 AM

The code for slimes is still there (in pl.class currently), it just isn't on the list of monsters to spawn. It's simple enough to add them back to the list in hf. I just tried it out and they started spawning. I also searched for all references to pl in the code, and there's nothing that "directly" creates them.

Elevation is an interesting issue. The main spawning algorithm does not directly base anything on elevation. However, each mob class can define its own special conditions for where it can spawn.

Slimes' special conditions include:
    [*:2hdjcrte]1:100 chance of spawning (each time) (oddly implemented as two 1:10s and-ed together)
    [*:2hdjcrte]Can only spawn as the smallest size (size is randomly generated on creation so, unless it's set somewhere else, effectively this is another 1:3 chance of spawning, meaning 1:300 per attempted placement overall)
    [*:2hdjcrte]Elevation less than 16
    [*:2hdjcrte]Two more conditions that are hard to decipher

The superclass for animals apparently uses this same method to check for grass and light level (> 8), and the superclass for monsters uses it to check for light level and something else. The mobs besides slimes don't seem to have individual conditions.

The monster light check generates a random integer from 0 to 7, and checks whether the light level is less than or equal to it. In other words, monster spawns have a (x/8) chance of being canceled at light level x.

I'm about at the limit of what I can say from looking at obfuscated code for now. Going to go look for despawn code.

#13

corveroth
    corveroth

    Tree Puncher

  • Curse Premium
  • Curse Premium
  • 20 posts

Posted 21 January 2011 - 01:17 AM

Might you be able to answer a question for me, as regards obfuscated code? I'm seeing the same code from Fernflower and from JD, so I'm not sure if this is a general decompilation problem, an amusing coincidence, or just Notch referencing XKCD to screw with us.

The Clay class. Check that last method.

import java.util.Random;

public class mx extends pj {

   public mx(int var1, int var2) {
	  super(var1, var2, ic.v);
   }

   public int a(int var1, Random var2) {
	  return eo.aG.ba;
   }

   public int a(Random var1) {
	  return 4;
   }
}


#14

Wrathful
    Wrathful

    Redstone Miner

  • Members
  • 566 posts
  • Location: Athens, GA

Posted 21 January 2011 - 01:35 AM

return 4;

O.o
If you wish to make an apple pie from scratch, you must first invent the universe.
--Carl Sagan

I am Scjoiner on YouTube. Check out my insane redstone stuff. Scjoiner's Channel

#15

Marglyph
    Marglyph

    Redstone Miner

  • Members
  • 535 posts

Posted 21 January 2011 - 01:41 AM

Obfuscated code is annoying. I'm trying to insert print statements into the world class, but my de/recompiled version comes with infinite recursion that definitely shouldn't be there :/

corveroth: There are various reasons to do something like that. In this case, the pj (block) class defines a method with the signature a(Random), and has a whole ton of subclasses, various of which override the a method. The clay class returns 4, other classes return other fixed values, and some (possibly just redstone) actually use the random object and return random values.

Another reason for the same practice might be a "stub" method that will return random values later, but is returning a fixed value for now for testing purposes or because only one value is implemented so far.

#16

corveroth
    corveroth

    Tree Puncher

  • Curse Premium
  • Curse Premium
  • 20 posts

Posted 21 January 2011 - 01:48 AM

Reasonable enough, but can you blame me for immediately thinking of this?

#17

Marglyph
    Marglyph

    Redstone Miner

  • Members
  • 535 posts

Posted 21 January 2011 - 08:14 AM

I found (most of) the despawn code. Still can't get it all to recompile, but I can analyze it and have been testing what I can compile.

Animals and monsters will both despawn if more than 128 meters from the player, animals immediately and monsters with a bit of a delay. The radius for chunk unloading seems to be not much more than this, and monsters in unloaded chunks will not despawn but will still count toward the cap. (I'm not completely sure this is due to chunk unloading, but I know far-away creatures will stay in the entity list and not despawn, even if you set difficulty to peaceful, until you get closer to them). Incidentally, around 1/3 of the total 17x17 chunk spawning area is more than 128 meters from the player.

Animals have something like a 2.5% chance per second of despawning after they have been idle for 30 seconds. I'm not entirely sure what clears the idle timer, since I have seen mobs moving around a bit while their idle timer counts up. I think it might have to do with pathfinding vs wandering aimlessly but am not sure.

Monsters have something like a 0.25% chance per second of despawning after they have been idle for something like 40-50 seconds. There's a lot of randomness involved. They can hang on for minutes while their idle timer counts up, I know that much.

Squid don't have despawn code that I can find, and they don't seem to despawn in games either. After I copied and pasted some despawn code, a squid tower actually worked, sort of (the limit is still really low).

Ghasts don't appear to despawn due to being far from the player or check an idle timer. They despawn based on some property of the world, maybe when the nether unloads?

#18

Sathka
    Sathka

    Carpenter

  • Members
  • 60 posts

Posted 21 January 2011 - 08:28 AM

I don't fully understand, but I remember notch "turning down" the amount of mobs spawned immediately after the update.  Has it been turned back up?

Posted Image
Welcome a stranger into your world... play the Herobrine world-transfer game!

#19

scoop75
    scoop75

    Coal Miner

  • Members
  • 134 posts

Posted 21 January 2011 - 08:41 AM

nice post and great work done...


as a side note: I happen to notice a dramtic spawn decrease on my last map, so I restartet and built a conventional mobtower on the 0,0 chunk. the spawn (and drop-)-rate is off the charts. nothing like before beta but I easy get around from 1500 drops up to 2000 / hour.

your information inspired my to extend the design to include passive mob spawning platforms attached to the tower and test that out.

thanks

#20

kyzla
    kyzla

    Out of the Water

  • Members
  • 2 posts

Posted 21 January 2011 - 02:41 PM

I dont know if I did understand this analysis right, so i got a stupid question: if i make a mob spawn tower which have 10 floors which are 16x16x2 blocks, will spawns be better than having only one floor 16x16x2?