MineCraft源码分析(一)

写在前面

MineCraft是一款沙盒式建造游戏，缔造者为Mojang Studios创始人马库斯·佩尔松，其灵感源于《无尽矿工》､《矮人要塞》和《地下城守护者》。现首席创意官为延斯·伯根斯坦，首席开发者为昂内丝·拉尔森。玩家可以在游戏中的三维空间里创造和破坏林林总总的方块，甚至在多人服务器与单人世界中体验不同的游戏模式，打造精美的建筑物，创造物和艺术品。且Minecraft的游戏平台已囊括了移动设备和游戏主机。
相信很多人都在自己的童年游戏生涯中接触到过MC。对我来说，MC更像是一种回忆，承载起了众多与玩伴们在方块的世界中冒险与生活的温馨记忆。大学以来，我先后尝试了在游戏中实现基于红石体系的复杂电路系统，热衷于寻找游戏中隐含的机制与特性，并基于我所掌握的软件工程知识进行相应的解读。如今，我终于有机会和能力进行MC源代码的阅读，我希望能够通过这样的经历提高我的软件编码水平和阅读能力，进一步加深对Java语言的理解和应用，同时能够记录成文为后来的探索者们提供建议、指明方向。

MineCraft源代码的获取

首先，根据官方MineCraft开发小组的说法，他们将会持续开放部分MineCraft的源代码供玩家制作Mod，提升游戏的Java引擎与制作自己的游戏项目。但是就目前来看，他们并没有完成完整的源代码的公布，不过这并不妨碍部分爱好者进行对MC源代码的初步了解。
https://github.com/Mojang/brigadier 官方源代码公布地址

其次，由www.modcoderpack.com 给出了另一种解包MC的方法。目前网页上提供了MCP940、937、931、928、918、908的6个对应不同版本的包。下载之后按照文件中记录操作即可。不过最高支持的MC的版本停留在1.12，无法对最新MC的源码和特性进行分析。
http://www.modcoderpack.com/website/content/mcp-910 MCP-Packages

如上两种方法都不能让我们拿到较为满意的代码，于是我选择通过MCP-Reborn项目进行对MC源代码的获取。值得注意的是，MC将自己的源码做了混淆处理之后才打包成为jar包，因此MCP架构下的反推只能说是得到一些可以运行的无限接近MC源码的代码，可能与真·MC源代码有出入。

IDEA引入MCP-Reborn-1.16

⚠️ WARNING ⚠️: You CANNOT publish any code generated by this tool.
注意：开发者禁止任何人发布基于本框架生成的任何代码！

首先解压缩文件，将其导入IDEA中，项目会自行完成MCP的构建。在运行过程中会遇到某文件无法下载的问题，通常，将你的网络切换为外网即可解决问题。初次架构会耗费较长的时间，请确保架构成功之后(无Error)再进入下一步的操作。
构建完毕后打开右侧Gradle，找到mcp-reborn->Tasks->mcp->setup，双击运行，开始反编译。
反编译完成后即可在左侧Project->MCP-Reborn->src中找到源码。
如需运行Minecraft可在src->main->java->mcp->client->start中运行类Start（public class Start）。
此外，在更改源代码之后需要进行的测试，打包方法，请参考:https://github.com/Hexeption/MCP-Reborn 中Readme文档的说明，本文不作探讨。
项目Github地址：https://github.com/Hexeption/MCP-Reborn

AbstractFishEntity —— 以鱼类抽象实体类为例介绍Entity类别

首先我们进入entity包中passive->fish类，找到声明鱼类实体的AbstractFishEntity类。
我们发现，他首先进行了对鱼型实体的初始化以及部分动作的声明和定义：

Code

protected float getStandingEyeHeight(Pose poseIn, EntitySize sizeIn) {
      return sizeIn.height * 0.65F;
   }

public static AttributeModifierMap.MutableAttribute func_234176_m_() {
    return MobEntity.func_233666_p_().createMutableAttribute(Attributes.MAX_HEALTH, 3.0D);
}

public boolean preventDespawn() {
    return super.preventDespawn() || this.isFromBucket();
}

public static boolean func_223363_b(EntityType<? extends AbstractFishEntity> type, IWorld worldIn, SpawnReason reason, BlockPos p_223363_3_, Random randomIn) {
      return worldIn.getBlockState(p_223363_3_).isIn(Blocks.WATER) && worldIn.getBlockState(p_223363_3_.up()).isIn(Blocks.WATER);
   }

public boolean canDespawn(double distanceToClosestPlayer) {
    return !this.isFromBucket() && !this.hasCustomName();
}

public int getMaxSpawnedInChunk() {
    return 8;
}

protected void registerData() {
      super.registerData();
      this.dataManager.register(FROM_BUCKET, false);
   }

如上，定义了获取实体视角高度(StandingEyeHeight)的函数，定义了它允许消失与否的判定条件，实体是否位于特定Block中的判定(isIn(Blocks.WATER))，以及其最大的生成块数据,最后将其注册进保存实体的数据集中。
接下来，开始对实体参数的设定与判断：

Code

protected void registerGoals() {
      super.registerGoals();
      this.goalSelector.addGoal(0, new PanicGoal(this, 1.25D));
      this.goalSelector.addGoal(2, new AvoidEntityGoal<>(this, PlayerEntity.class, 8.0F, 1.6D, 1.4D, EntityPredicates.NOT_SPECTATING::test));
      this.goalSelector.addGoal(4, new AbstractFishEntity.SwimGoal(this));
   }

   protected PathNavigator createNavigator(World worldIn) {
      return new SwimmerPathNavigator(this, worldIn);
   }

   public void travel(Vector3d travelVector) {
      if (this.isServerWorld() && this.isInWater()) {
         this.moveRelative(0.01F, travelVector);
         this.move(MoverType.SELF, this.getMotion());
         this.setMotion(this.getMotion().scale(0.9D));
         if (this.getAttackTarget() == null) {
            this.setMotion(this.getMotion().add(0.0D, -0.005D, 0.0D));
         }
      } else {
         super.travel(travelVector);
      }

   }

接下来是为鱼类实体进行Goal的注册，通过addGoal函数

Code

public void addGoal(int priority, Goal task) {
      this.goals.add(new PrioritizedGoal(priority, task));
   }

注册实体的Goal信息
函数中包含两个值，分别是Goal的优先级与Goal的目标函数
对鱼类实体而言，需要添加的Goal有Panic、AvoidEntityGoal、SwimGoal三种，

Code

public PanicGoal(CreatureEntity creature, double speedIn) {
      this.creature = creature;
      this.speed = speedIn;
      this.setMutexFlags(EnumSet.of(Goal.Flag.MOVE));
   }

public boolean shouldExecute(){…}
protected boolean findRandomPosition(){…}
public boolean isRunning(){…}
public void startExecuting(){…}
public void resetTask(){…}
public boolean shouldContinueExecuting(){…}
protected BlockPos getRandPos(IBlockReader worldIn, Entity entityIn, int horizontalRange, int verticalRange){…}

Panic_Goal主要用于判定该实体对于敌对生物接近等产生的恐慌进行反应，在鱼类实体中具有最高的优先级0

Code

public AvoidEntityGoal(CreatureEntity entityIn, Class<T> classToAvoidIn, float avoidDistanceIn, double farSpeedIn, double nearSpeedIn){…}
public AvoidEntityGoal(CreatureEntity entityIn, Class<T> avoidClass, Predicate<LivingEntity> targetPredicate, float distance, double nearSpeedIn, double farSpeedIn, Predicate<LivingEntity> p_i48859_9_){…}
public AvoidEntityGoal(CreatureEntity entityIn, Class<T> avoidClass, float distance, double nearSpeedIn, double farSpeedIn, Predicate<LivingEntity> targetPredicate){…}
public boolean shouldExecute(){…}

public boolean shouldContinueExecuting() {
      return !this.navigation.noPath();
   }

public void startExecuting() {
    this.navigation.setPath(this.path, this.farSpeed);
}

public void resetTask() {
    this.avoidTarget = null;
}
public void tick()

AvoidEntityGoal函数提供实体用于躲避其他实体所需的向量计算，它的优先级为2

Code

static class SwimGoal extends RandomSwimmingGoal {
      private final AbstractFishEntity fish;

      public SwimGoal(AbstractFishEntity fish) {
         super(fish, 1.0D, 40);
         this.fish = fish;
      }

      public boolean shouldExecute() {
         return this.fish.func_212800_dy() && super.shouldExecute();
      }
   }

最后是从RandomSwimmingGoal中衍生出的SwimGoal，他被封装在鱼类实体类中，用于控制鱼的移动

此外，我们还注意到，鱼的实体类还调用了数个与声音相关的函数匹配其移动时所产生的声音输出

Code

protected abstract SoundEvent getFlopSound();

protected SoundEvent getSwimSound() {
   return SoundEvents.ENTITY_FISH_SWIM;
}

protected void playStepSound(BlockPos pos, BlockState blockIn) {
}

通过如上的分析我们已经初步了解了MC中对于不同实体类所采用的相同的编写方式，但是其他的生物实体可能远复杂于鱼类实体。例如，在马类实体中，用于注册的Goals增加到了7个，分为6个不同的优先级，控制了实体惊恐状态、四处奔跑状态、交配状态、跟随父母状态、规避水地形状态、凝视状态、随机朝向状态的动作。而且还有更多的函数用于控制其是否带有箱子、是否为驯服状态、与牵引绳的交互状态、吃草、饲养、心情与繁殖的状态等，同时也有相应的声音调度方法。

我们还可以注意到，对实体类进行编写时，MC对一类动作相似的的生物进行了归纳，并从该基类衍生出不同的个体类，这大大减少了代码量，但是却显著增大了代码的耦合性，对基类进行修改的时候还可能产生涟漪效应。此外，在实体类中还出现了诸如func_223363_b()、0.65F等的不规范函数命名与魔术值，增大了代码的阅读难度，让可维护性下降。

从Biome包开始分析MC地形生成相关逻辑

首先我们从Biomes的定义开始说起。
在world->bimoe->provider->Biomes.java中，定义了MC中所有可能生成的生物群系

Code

public static final RegistryKey<Biome> OCEAN = makeKey("ocean");
   public static final RegistryKey<Biome> PLAINS = makeKey("plains");
   public static final RegistryKey<Biome> DESERT = makeKey("desert");
   public static final RegistryKey<Biome> MOUNTAINS = makeKey("mountains");
   public static final RegistryKey<Biome> FOREST = makeKey("forest");
   public static final RegistryKey<Biome> TAIGA = makeKey("taiga");
   public static final RegistryKey<Biome> SWAMP = makeKey("swamp");
   public static final RegistryKey<Biome> RIVER = makeKey("river");
   public static final RegistryKey<Biome> NETHER_WASTES = makeKey("nether_wastes");
   public static final RegistryKey<Biome> THE_END = makeKey("the_end");
   public static final RegistryKey<Biome> FROZEN_OCEAN = makeKey("frozen_ocean");
   public static final RegistryKey<Biome> FROZEN_RIVER = makeKey("frozen_river");
   public static final RegistryKey<Biome> SNOWY_TUNDRA = makeKey("snowy_tundra");
   public static final RegistryKey<Biome> SNOWY_MOUNTAINS = makeKey("snowy_mountains");
   public static final RegistryKey<Biome> MUSHROOM_FIELDS = makeKey("mushroom_fields");
   public static final RegistryKey<Biome> MUSHROOM_FIELD_SHORE = makeKey("mushroom_field_shore");
   public static final RegistryKey<Biome> BEACH = makeKey("beach");
   public static final RegistryKey<Biome> DESERT_HILLS = makeKey("desert_hills");
   public static final RegistryKey<Biome> WOODED_HILLS = makeKey("wooded_hills");
   public static final RegistryKey<Biome> TAIGA_HILLS = makeKey("taiga_hills");
   public static final RegistryKey<Biome> MOUNTAIN_EDGE = makeKey("mountain_edge");
   public static final RegistryKey<Biome> JUNGLE = makeKey("jungle");
   public static final RegistryKey<Biome> JUNGLE_HILLS = makeKey("jungle_hills");
   public static final RegistryKey<Biome> JUNGLE_EDGE = makeKey("jungle_edge");
   public static final RegistryKey<Biome> DEEP_OCEAN = makeKey("deep_ocean");
   public static final RegistryKey<Biome> STONE_SHORE = makeKey("stone_shore");
   public static final RegistryKey<Biome> SNOWY_BEACH = makeKey("snowy_beach");
   public static final RegistryKey<Biome> BIRCH_FOREST = makeKey("birch_forest");
   public static final RegistryKey<Biome> BIRCH_FOREST_HILLS = makeKey("birch_forest_hills");
   public static final RegistryKey<Biome> DARK_FOREST = makeKey("dark_forest");
   public static final RegistryKey<Biome> SNOWY_TAIGA = makeKey("snowy_taiga");
   public static final RegistryKey<Biome> SNOWY_TAIGA_HILLS = makeKey("snowy_taiga_hills");
   public static final RegistryKey<Biome> GIANT_TREE_TAIGA = makeKey("giant_tree_taiga");
   public static final RegistryKey<Biome> GIANT_TREE_TAIGA_HILLS = makeKey("giant_tree_taiga_hills");
   public static final RegistryKey<Biome> WOODED_MOUNTAINS = makeKey("wooded_mountains");
   public static final RegistryKey<Biome> SAVANNA = makeKey("savanna");
   public static final RegistryKey<Biome> SAVANNA_PLATEAU = makeKey("savanna_plateau");
   public static final RegistryKey<Biome> BADLANDS = makeKey("badlands");
   public static final RegistryKey<Biome> WOODED_BADLANDS_PLATEAU = makeKey("wooded_badlands_plateau");
   public static final RegistryKey<Biome> BADLANDS_PLATEAU = makeKey("badlands_plateau");
   public static final RegistryKey<Biome> SMALL_END_ISLANDS = makeKey("small_end_islands");
   public static final RegistryKey<Biome> END_MIDLANDS = makeKey("end_midlands");
   public static final RegistryKey<Biome> END_HIGHLANDS = makeKey("end_highlands");
   public static final RegistryKey<Biome> END_BARRENS = makeKey("end_barrens");
   public static final RegistryKey<Biome> WARM_OCEAN = makeKey("warm_ocean");
   public static final RegistryKey<Biome> LUKEWARM_OCEAN = makeKey("lukewarm_ocean");
   public static final RegistryKey<Biome> COLD_OCEAN = makeKey("cold_ocean");
   public static final RegistryKey<Biome> DEEP_WARM_OCEAN = makeKey("deep_warm_ocean");
   public static final RegistryKey<Biome> DEEP_LUKEWARM_OCEAN = makeKey("deep_lukewarm_ocean");
   public static final RegistryKey<Biome> DEEP_COLD_OCEAN = makeKey("deep_cold_ocean");
   public static final RegistryKey<Biome> DEEP_FROZEN_OCEAN = makeKey("deep_frozen_ocean");
   public static final RegistryKey<Biome> THE_VOID = makeKey("the_void");
   public static final RegistryKey<Biome> SUNFLOWER_PLAINS = makeKey("sunflower_plains");
   public static final RegistryKey<Biome> DESERT_LAKES = makeKey("desert_lakes");
   public static final RegistryKey<Biome> GRAVELLY_MOUNTAINS = makeKey("gravelly_mountains");
   public static final RegistryKey<Biome> FLOWER_FOREST = makeKey("flower_forest");
   public static final RegistryKey<Biome> TAIGA_MOUNTAINS = makeKey("taiga_mountains");
   public static final RegistryKey<Biome> SWAMP_HILLS = makeKey("swamp_hills");
   public static final RegistryKey<Biome> ICE_SPIKES = makeKey("ice_spikes");
   public static final RegistryKey<Biome> MODIFIED_JUNGLE = makeKey("modified_jungle");
   public static final RegistryKey<Biome> MODIFIED_JUNGLE_EDGE = makeKey("modified_jungle_edge");
   public static final RegistryKey<Biome> TALL_BIRCH_FOREST = makeKey("tall_birch_forest");
   public static final RegistryKey<Biome> TALL_BIRCH_HILLS = makeKey("tall_birch_hills");
   public static final RegistryKey<Biome> DARK_FOREST_HILLS = makeKey("dark_forest_hills");
   public static final RegistryKey<Biome> SNOWY_TAIGA_MOUNTAINS = makeKey("snowy_taiga_mountains");
   public static final RegistryKey<Biome> GIANT_SPRUCE_TAIGA = makeKey("giant_spruce_taiga");
   public static final RegistryKey<Biome> GIANT_SPRUCE_TAIGA_HILLS = makeKey("giant_spruce_taiga_hills");
   public static final RegistryKey<Biome> MODIFIED_GRAVELLY_MOUNTAINS = makeKey("modified_gravelly_mountains");
   public static final RegistryKey<Biome> SHATTERED_SAVANNA = makeKey("shattered_savanna");
   public static final RegistryKey<Biome> SHATTERED_SAVANNA_PLATEAU = makeKey("shattered_savanna_plateau");
   public static final RegistryKey<Biome> ERODED_BADLANDS = makeKey("eroded_badlands");
   public static final RegistryKey<Biome> MODIFIED_WOODED_BADLANDS_PLATEAU = makeKey("modified_wooded_badlands_plateau");
   public static final RegistryKey<Biome> MODIFIED_BADLANDS_PLATEAU = makeKey("modified_badlands_plateau");
   public static final RegistryKey<Biome> BAMBOO_JUNGLE = makeKey("bamboo_jungle");
   public static final RegistryKey<Biome> BAMBOO_JUNGLE_HILLS = makeKey("bamboo_jungle_hills");
   public static final RegistryKey<Biome> SOUL_SAND_VALLEY = makeKey("soul_sand_valley");
   public static final RegistryKey<Biome> CRIMSON_FOREST = makeKey("crimson_forest");
   public static final RegistryKey<Biome> WARPED_FOREST = makeKey("warped_forest");
   public static final RegistryKey<Biome> BASALT_DELTAS = makeKey("basalt_deltas");

可以看到，MC预先设置了数十个Key-Value对用于标识不同的生物群系，并以此为基础开发了各个不同群系的生成方法。
接下来我们通过BiomeMaker方法中的makeBirchForestBiome函数来进一步了解生物群系的具体生成方法。

Code

public static Biome makeBirchForestBiome(float depth, float scale, boolean isTallVariant) {
      MobSpawnInfo.Builder mobspawninfo$builder = new MobSpawnInfo.Builder();
      DefaultBiomeFeatures.withPassiveMobs(mobspawninfo$builder);
      DefaultBiomeFeatures.withBatsAndHostiles(mobspawninfo$builder);
      BiomeGenerationSettings.Builder biomegenerationsettings$builder = (new BiomeGenerationSettings.Builder()).withSurfaceBuilder(ConfiguredSurfaceBuilders.field_244178_j);
      DefaultBiomeFeatures.withStrongholdAndMineshaft(biomegenerationsettings$builder);
      biomegenerationsettings$builder.withStructure(StructureFeatures.RUINED_PORTAL);
      DefaultBiomeFeatures.withCavesAndCanyons(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withLavaAndWaterLakes(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withMonsterRoom(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withAllForestFlowerGeneration(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withCommonOverworldBlocks(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withOverworldOres(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withDisks(biomegenerationsettings$builder);
      if (isTallVariant) {
         DefaultBiomeFeatures.withTallBirches(biomegenerationsettings$builder);
      } else {
         DefaultBiomeFeatures.withBirchTrees(biomegenerationsettings$builder);
      }

      DefaultBiomeFeatures.withDefaultFlowers(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withForestGrass(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withNormalMushroomGeneration(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withSugarCaneAndPumpkins(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withLavaAndWaterSprings(biomegenerationsettings$builder);
      DefaultBiomeFeatures.withFrozenTopLayer(biomegenerationsettings$builder);
      return (new Biome.Builder()).precipitation(Biome.RainType.RAIN).category(Biome.Category.FOREST).depth(depth).scale(scale).temperature(0.6F).downfall(0.6F).setEffects((new BiomeAmbience.Builder()).setWaterColor(4159204).setWaterFogColor(329011).setFogColor(12638463).withSkyColor(getSkyColorWithTemperatureModifier(0.6F)).setMoodSound(MoodSoundAmbience.DEFAULT_CAVE).build()).withMobSpawnSettings(mobspawninfo$builder.copy()).withGenerationSettings(biomegenerationsettings$builder.build()).build();
   }

一般来说，地形生成的函数通常具有一定的参数输入。对于稀有/罕见或者简单的的生物群系而言，生成函数也可以没有任何输入，例如makeSmallEndIslandsBiome()等。而对于常见的群系例如BirchForestBiome(桦树林)而言，它具有depth，scale，isTallVariant三个参数，分别代表了它的深度、规模以及是否为巨型群系。
在函数中，会对所有的生物以及地貌生成进行判定与执行，例如本段代码中，先后进行了是否有怪物生成、是否有被动型怪物生成、是否有要塞或矿井生成、是否有洞穴或峡谷生成等等。

MC与图形处理

引入噪声——以Prelin噪声为例

噪声的定义

在图形学中，我们使用噪声就是为了把一些随机变量来引入到程序中。从程序角度来说，噪声很好理解，我们希望给定一个输入，程序可以给出一个输出：

Code

value_type noise(value_type p) {
    ...
}

它的输入和输出类型的维数可以是不同的组合，例如输入二维输出一维，输入二维输出二维等。而这不同的函数集合就是噪声的具体实现。
在代码实践中，我们常常使用random函数等为我们提供相当数量的伪随机数，同样，在图形学中我们也经常会需要使用随机变量，例如火焰、地形、云朵的模拟等等，MC中就广泛的使用了随机变量。但是由于伪随机函数生成的随机值太“随机”了，我们一般称这样的噪声是白噪声，即功率谱密度在整个频域内均匀分布的噪声，它的视觉反馈非常不自然，听起来也很刺耳。同时我们可以发现，在现实世界中存在的噪声并不像白噪声具有过大的随机性，例如木头纹理、山脉起伏，它们的形状大多是趋于分形状（fractal）的，即包含了不同程度的细节。比如地形，它有起伏很大的山脉，也有起伏稍小的山丘，也有细节非常多的石子等，这些不同程度的细节共同组成了一个自然的地形表面。人们根据以上现象提出了许多希望用程序模拟自然噪声的方法。例如，Perlin噪声被大量用于云朵、火焰和地形等自然环境的模拟；Simplex噪声在其基础上进行了改进，提到了效率和效果；而Worley噪声被提出用于模拟一些多孔结构，例如纸张、木纹等。

根据wiki，由程序产生噪声的方法大致可以分为两类：

类别	名称
基于晶格的方法（Lattice based）	1.梯度噪声（Gradient noise）包括Perlin噪声，Simplex噪声，Wavelet噪声等；2.Value噪声（Value noise）。
基于点的方法（Point based）	Worley噪声

Perlin噪声、Simplex噪声和Value噪声在性能上大致满足：Perlin噪声 > Value噪声 > Simplex噪声，Simplex噪声性能最好。Perlin噪声和Value噪声的复杂度是O(2n)，其中n是维数，但Perlin噪声比Value噪声需要进行更多的乘法（点乘）操作。而Simplex噪声的复杂度为O(n2)，在高纬度上优化明显。

柏林噪声的提出

Perlin噪声的名字来源于它的创始人Ken Perlin。Ken Perlin早在1983年就提出了Perlin noise，当时他正在参与制作迪士尼的动画电影《电子世界争霸战》（英语：TRON），但是他不满足于当时计算机产生的那种非常不自然的纹理效果，因此提出了Perlin噪声。随后，他在1984年的SIGGRAPH Course上做了名为Advanced Image Synthesis [1]的课程演讲，并在SIGGRAPH 1985上发表了他的论文 [2]。由于Perlin噪声的算法简单，被迅速应用到各种商业软件中。我们这位善良的Perlin先生却并没有对Perlin噪声算法申请专利（他说他的祖母曾叫他这么做过……），如果他这么做了那会是多大一笔费用啊！（不过在2001年的时候，旁人看不下去了，把三维以上的Simplex噪声的专利主动授予了Perlin。对，Simplex噪声也是人家提出的……）再后来Perlin继续研究程序纹理的生成，并和他的一名学生又在SIGGRAPH 1989上发表了一篇文章 [3]，提出了超级纹理（hypertexture）。他们使用噪声+fbm+ray marching实现了各种有趣的效果。到1990年，已经有大量公司在他们的产品中使用了Perlin噪声。在1999年的GDCHardCore大会上，Ken Perlin做了名为Making Noise的演讲 [4]，系统地介绍了Perlin噪声的发展、实现细节和应用。如果读者不想读论文的话，强烈建议你看一下Perlin演讲的PPT。

后来在2002年，Perlin又发表了一篇论文5来改进原始的Perlin噪声中的一些问题，例如原来的缓和曲线s(t)=3t^2−2t^3的二阶导6−12t在t=0和t=1时均不等于0，这使得在相邻的晶格处它们的二阶导并不连续。因此Perlin提出使用一个更好的缓和曲线s(t)=6t^5−15t^4+10t^3；此外还改进了晶格顶点处随机梯度向量的选取。有兴趣的读者可以参考：

• Perlin在2002年发表的论文： http://mrl.nyu.edu/~perlin/paper445.pdf
• GPU Gems的文章： http://http.developer.nvidia.com/GPUGems/gpugems_ch05.html
• GPU Gems2的文章： http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter26.html

柏林噪声的实现

Perlin噪声的实现较为简单。概括来说，Perlin噪声的实现需要三个步骤：
定义一个晶格结构，每个晶格的顶点有一个“伪随机”的梯度向量。对于二维的Perlin噪声来说，晶格结构就是一个平面网格，三维的就是一个立方体网格。
输入一个点（二维的话就是二维坐标，三维就是三维坐标，n维的就是n个坐标），我们找到和它相邻的那些晶格顶点（二维下有4个，三维下有8个，n维下有2^n个），计算该点到各个晶格顶点的距离向量，再分别与顶点上的梯度向量做点乘，得到2^n个点乘结果。
使用缓和曲线（ease curves）来计算它们的权重和。在原始的Perlin噪声实现中，缓和曲线是s(t)=3t^2−2t^3，在2002年的论文6中，Perlin改进为s(t)=6t^5−15t^4+10t^3。这里简单解释一下，为什么不直接使用s(t)=t，即线性插值。直接使用的线性插值的话，它的一阶导在晶格顶点处（即t = 0或t = 1）不为0，会造成明显的不连续性。s(t)=3t^2−2t^3在一阶导满足连续性，s(t)=6t^5−15t^4+10t^3在二阶导上仍然满足连续性。

我们下面以二维的为例进行更详细的解释。我们可以用下面的图来表示上面的第一步和第二步：

一个问题是晶格顶点处的伪随机梯度向量是如何得到的，当然我们可以通过random这样的函数来计算单位正方形（二维）内的x和y分量值，但我们更愿意要那些在单位圆内的梯度向量。Perlin在他的实现中选择使用蒙特卡洛模拟方法来选取这些随机梯度向量。具体方法是（我把描述适应到了二维）：首先按之前的方法生成在单位正方形内随机梯度向量，然后剔除那些不在单位圆内的向量，直到找到了需要数目的随机梯度向量。Perlin把这些预计算得到的向量存储在一个查找表G[n]中，n是纹理大小，例如256 x 256大小的纹理对应n为256。虽然我们实际上需要n x n个梯度向量，这样会造成有些顶点的梯度是重复的。Perlin认为，重复是可以允许的，只要它们的间距够大就不会被察觉。因此，Perlin还预计算了一个随机排列数组P[n]，P[n]里面存储的是打乱后的0~n-1的排列值。这样一来，当我们想要得到(i, j)处晶格的梯度向量时，可以使用：

G=G[(i+P[j])mod n]

得到了梯度后，我们就可以进行点乘，得到4个点乘结果，然后使用缓和曲线对它们进行插值即可。这里使用的权重就是输入点到4个顶点的横纵距离。

在原始的Perlin噪声实现中，Perlin对梯度向量的选择一般是取单位圆（三维就是单位球）内一些不同方向的向量。在他后面的改进算法7中，Perlin建议把三维的梯度向量初始化为到立方体12条边的向量值，来保证各个方向之间的不关联性。

可以看出，Perlin噪声算法的时间复杂度为O(2^n)（n是维数），2^n其实就是每个晶格的顶点个数，对于每个输入点我们需要进行这么多次的点乘操作。因此，随着维数的增大，例如计算三维四维的Perlin噪声，时间会迅速增加。Perlin在2002年介绍了他优化后的一种噪声——Simplex噪声，这种噪声的复杂度是O(n^2)，在高纬度上时间优化明显，我们后面会讲到这种噪声。

一种柏林噪声的二维实现

它的主要代码如下：

Code

vec2 hash22(vec2 p)
{
    p = vec2( dot(p,vec2(127.1,311.7)),
              dot(p,vec2(269.5,183.3)));

    return -1.0 + 2.0 * fract(sin(p)*43758.5453123);
}
float perlin_noise(vec2 p)
{
    vec2 pi = floor(p);
    vec2 pf = p - pi;

    vec2 w = pf * pf * (3.0 - 2.0 * pf);

    return mix(mix(dot(hash22(pi + vec2(0.0, 0.0)), pf - vec2(0.0, 0.0)), 
                   dot(hash22(pi + vec2(1.0, 0.0)), pf - vec2(1.0, 0.0)), w.x), 
               mix(dot(hash22(pi + vec2(0.0, 1.0)), pf - vec2(0.0, 1.0)), 
                   dot(hash22(pi + vec2(1.0, 1.0)), pf - vec2(1.0, 1.0)), w.x),
               w.y);
}

这里的实现实际是简化版的，我们在算梯度的时候直接取随机值，而没有归一化到单位圆内。
上图包含了四种噪声组合，这也是Perlin在1999年的GDC上做演讲时采用的一个示例，不过Perlin的例子是三维的，而且添加了光照等计算。

• 左上角的部分。这是最简单的单独的Perlin噪声，它的噪声模拟如下：
  Code

  float noise_itself(vec2 p)
  {
      return noise(p * 8.0);
  }

  上面的代码在整个屏幕上模拟了一个8 x 8的网格结构。在绘制时，我们只需要将一个深蓝色乘以噪声即可得到类似的效果。

单独一个Perlin噪声虽然也有一定用处，但是效果往往很无趣。因此，Perlin指出可以使用不同的函数组合来得到更有意思的结果，这些函数组合通常就是指通过分形叠加（fractal sum），也就是我们之前说的fbm。

• 左下角的部分。这个部分使用了fbm进行叠加来形成一个分形噪声。公式如下：

  noise(p)+1/2noise(2p)+1/4noise(4p)+…

即每一次噪声的采样频率翻倍，而振幅减少一倍。很多文章错误地把这种计算认为是Perlin噪声，这是不对的。Perlin噪声只是对应了其中每一个octave。代码是：

Code

float noise_sum(vec2 p)
{
    float f = 0.0;
    p = p * 4.0;
    f += 1.0000 * noise(p); p = 2.0 * p;
    f += 0.5000 * noise(p); p = 2.0 * p;
    f += 0.2500 * noise(p); p = 2.0 * p;
    f += 0.1250 * noise(p); p = 2.0 * p;
    f += 0.0625 * noise(p); p = 2.0 * p;

   return f;
}

上面叠加了5层，并把初始化采样距离设置为4，这都是可以自定义的。这种噪声可以用来模拟石头、山脉这类物体。

• 右下角的部分。这一部分只是在上一部分进行了一点修改，对噪声返回值进行了取绝对值操作。它使用的公式如下：

  |noise(p)|+1/2|noise(2p)|+1/4|noise(4p)|+…

它对应的代码如下：

Code

float noise_sum_abs(vec2 p)
{
    float f = 0.0;
    p = p * 7.0;
    f += 1.0000 * abs(noise(p)); p = 2.0 * p;
    f += 0.5000 * abs(noise(p)); p = 2.0 * p;
    f += 0.2500 * abs(noise(p)); p = 2.0 * p;
    f += 0.1250 * abs(noise(p)); p = 2.0 * p;
    f += 0.0625 * abs(noise(p)); p = 2.0 * p;

    return f;
}

由于进行了绝对值操作，因此会在0值变化处出现不连续性，形成一些尖锐的效果。通过合适的颜色叠加，我们可以用这种噪声来模拟火焰、云朵这些物体。Perlin把这个公式称为turbulence（湍流）。

• 右上角的部分。这个部分是在之前turbulence公式的基础上使用了一个关于表面x分量的正弦函数：

  sin(x+|noise(p)|+1/2|noise(2p)|+1/4|noise(4p)|+…)

Code

float noise_sum_abs_sin(vec2 p)
{
    float f = 0.0;
    p = p * 7.0;
    f += 1.0000 * abs(noise(p)); p = 2.0 * p;
    f += 0.5000 * abs(noise(p)); p = 2.0 * p;
    f += 0.2500 * abs(noise(p)); p = 2.0 * p;
    f += 0.1250 * abs(noise(p)); p = 2.0 * p;
    f += 0.0625 * abs(noise(p)); p = 2.0 * p;
    f = sin(f + p.x/32.0);

    return f;
}

我们可以通过改变x分量前面的系数来控制条纹的疏密。

以上，我们就演示了基本的Perlin噪声的实现。Perlin在1999年Making Noise的演讲[4]中，还介绍了如何使用噪声来控制纹理动画。他指出，想要一个二维的turbulence纹理动画（例如云、火焰等），我们需要使用三维的噪声，其中第三维对应了时间变量。Shadertoy上有很多这样的例子.

噪声相关阅读材料

• Perlin噪声

1. 该文章详细地解释了真正的Perlin噪声以及和fbm的结合：http://flafla2.github.io/2014/08/09/perlinnoise.html
2. 2005年的这篇论文 [5]的开头部分也给出了不错的Perlin噪声的解释：http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
3. GPU Gems的文章：http://http.developer.nvidia.com/GPUGems/gpugems_ch05.html
4. GPU Gems2的文章：http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter26.html
5. 大牛scrawk的博客在Unity里实现了GPU Gems里面的方法：https://scrawkblog.com/2013/05/18/gpu-gems-to-unity-improved-perlin-noise/

• Value噪声

1. 课程：噪声的来源、应用和实现：http://scratchapixel.com/old/lessons/3d-advanced-lessons/noise-part-1/
2. 文章：http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

• Simplex噪声

1. 文章：三维的Simplex噪声：http://catlikecoding.com/unity/tutorials/simplex-noise/
2. Shadertoy上三维Simplex噪声的实现：https://www.shadertoy.com/view/XsX3zB和我的https://www.shadertoy.com/view/4sc3z2。

• fbm

1. 文章：仅fbm：https://code.google.com/p/fractalterraingeneration/wiki/Fractional_Brownian_Motion

• hash

1. Shadertoy：不同数据类型组合下的哈希函数的总结：https://www.shadertoy.com/view/4djSRW

参考文献

• [1] Perlin K. Course in advanced image synthesis[C]//ACM SIGGRAPH Conference. 1984, 18.
• [2] Perlin K. An image synthesizer[J]. ACM Siggraph Computer Graphics, 1985, 19(3): 287-296.
• [3] Perlin K, Hoffert E M. Hypertexture[C]//ACM SIGGRAPH Computer Graphics. ACM, 1989, 23(3): 253-262.
• [4] Perlin K. Making noise[C]//Proc. of the Game Developer Conference. 1999.
• [5] Gustavson S. Simplex noise demystified[J]. Linköping University, Linköping, Sweden, Research Report, 2005.
• [6] https://www.cnblogs.com/xiaowangba/p/6314642.html

MC中的噪声实现和用例

MC中常用且仅被使用的两种噪声是Perlin噪声和Simplex噪声
我们发现，在net.Minecraft.world.gen下有两个与噪声相关的函数，分别是PerlinNoiseGenerator与SimplexNoiseGenerator，他们分别代表了两种不同的梯度噪声模式。

解析噪声生成函数

基于噪声函数的区块生成器——NoiseChunkGenerator

MC生物AI的核心——传感器与感知器

Editing…