Ahoy !

As mentioned in my preceding blog post, I started working on random map generation. I had some base ground generated, but I still needed to place entities (it could be rocks and plants, or enemies). My first guess was to use a uniform distribution. However, it can lead to very bad looking results, as you can easily get overpacked areas, and other one that are completely empty.

The solution I came up with was to use a Poisson Disk Sampling blue noise (using this algorithm). It allows to generate a cloud of points, where two points can not be closer than some minimal distance (and usually, you also get at least another point in less than twice this minimal distance). For example, it looks like this:

Now, the idea is to generate several such distributions, with different minimal distances depending on the size of the entities we want to place. For example, we want a tight-packed distribution for the tuftes of grass, but a sparser one for the trees, and an even sparser one for the groups of mobs. Following an idea from Jaap van Muijden GDC's talk, for each spawn point in my distribution, I look at the base ground and determine which entities can spawn there and with which probability (and I add some dithering for a better entities distribution). For example, if I put 100% chances of spawning a tuft of grass on the dark green ground, I get this:

I can also ask to spawn multiples entities on the same point, for example to generate groups of mobs. I can also add some jittering (in color, position, rotation, etc). For example, for my group of ducks, the code looks like this:

<distribution type="poisson" distance=500 sectionSize=5000 spawnType="unsafe">
	<spawnPoint  spawnProbability=.35>
			<character path="../duck/duckXML.txt" amount="[1,3]" />
			<modifier type="position" rng="uniform" x="[-100,100]" y="[-100,100]" />
	</spawnPoint>
	<spawnPoint  spawnProbability=.15>
		<character path="../duck/duckXML.txt" amount="[3,5]" />
		<modifier type="position" rng="uniform" x="[-100,100]" y="[-100,100]" />
	</spawnPoint>
</distribution>

This means I can spawn between 1 and 5 ducks at a single spawn point (and these spawn points are separated by at least a distance of 500), with a bigger probability to have between 1 and 3 ducks. Moreover, I jitter their position uniformaly between -100 and 100, so that not all the ducks are spawned at the same point. If two ducks are still spawned too close (or in a wall), the physics engine will separate them at runtime.

At the end of the day, I get something that looks like this:

The next step will be to implement random generation of points of interest, which require a special treatment.

As a bonus, here is the first art for the air balloon, which will serve as starting point and travelling hub for expeditions:

EDIT: Here is a new video with a basic version of the Point of Interest spawning system, also showing a bit more of what the world can look like: