Sunday, June 23, 2013

Quickly placing random objects in a landscape without overlap

For me, creating procedural content is one of the most awesome things ever! Despite having created it yourself, you're still not quite sure what you'll expect this time. So today I'm going to discuss a problem that I often have: placing objects randomly in a scene, without having them overlap eachother!

It's a small scene, but nothing's overlapping, not even with the path. Looks like the code works to me!

The easiest approach to creating a random landscape is to just launch into a for loop, and just start assigning random coordinate! And that's often pretty great all by itself, but you'll get -tons- of overlap.

Sooo... let's just check if it overlaps with anything, and if it does, assign it a new random position? Great! What if there's no room, or very little room? You could easily spend a lot of loops trying to pick a good spot, or even worse, catch yourself in an infinite loop. It also takes an unpredictable duration, which is generally a bad idea.

The solution I've decided on isn't perfect, but it is a decent approximate, and it's fairly fast. The idea is to create a grid over the area, and use each cell in it to store the distance to the nearest object. If we're using a bounding circle to determine where an object will fit, then these values should instantly tell us whether or not that cell is a valid location!

ASCII Visualizations are the best.

As you can see here, we've got an ASCII gradient, to show distance from a single placed object, with 'x' marking the actual areas the object takes up. The data is actually stored as floats, so it's very simple to tell the actual distance. Here's the code I used to make it:

PlacerRandom random = new PlacerRandom(0);
Placer placer = new Placer(20, 20, random);
placer.PlaceCircle(4, 4, 2);

You can find the Placer code at the bottom of this post. From here, it's pretty simple to pick out valid cells, and then choose one of those to spawn your object at. Using the placer's GetCircle method, you can pick out a random location that will fit a given radius.

This scene contains a path, and 4 objects. It looks a bit more confusing.

I also discovered the need to add paths through my world, so I wanted to be able to set lines that would be clear of stuff. Using the closest point on a line algorithm with a distance test, it's not hard to do exactly the same sort of thing with a line. Here's the code I used to create this scene:

PlacerRandom random = new PlacerRandom(0);
Placer placer = new Placer(20, 20, random);
placer.PlaceLine(0, 8, 20, 15, 1f);
float x = 0, y = 0;
float radius = 2;
for (int i = 0; i < 4; i++) {
 placer.GetCircle(radius, out x, out y);
 placer.PlaceCircle(x, y, radius);

The speed for these is pretty excellent on small maps, for a 32x32 grid, getting and placing 100 circles was about 3ms on my machine. Unfortunately, this goes up pretty fast, with a 128x128 grid taking about 33ms for the same thing. Fortunately, it's not likely you'll be doing this sort of thing every frame, but if you're generating tiles as you move, having a hiccup might not be ideal either.

There's plenty of room for optimization, better math, different distance algorithms, silly things, but it's already pretty workable.

Oh, and don't forget, even after you've placed all those objects, that distance information can still be pretty handy! As you can see in my leading image, I've used it to do some fake shadow estimates. With a bit of tweaking, that'll look excellent =D

You can download the code for Placer.cs and PlacerRandom.cs. I haven't really polished them yet, I still consider them a WIP , but it should be pretty easy to use! Also, this code should work right away in Unity.

Sunday, June 16, 2013

Alpha test-like results using regular alpha blend.

So it turns out that using alpha test on mobile hardware can be a rather expensive thing. Technically, so is alpha blending, but hey, transparency is kinda important! I'd just like to present a really simple method here for obtaining alpha test-like results while still using regular old alpha blending.

Edges on an alpha-test material ("Unlit/Tranparent Cutout" from Unity)

Alpha test edges are beautifully smooth, and extremely desirable in many cases, try telling one of your artists they can't use it for the project, see how that goes! Here's an example with a standard alpha blend:

Alpha blend, eww, gross ("Unlit/Transparent" from Unity)

There's really just no substitute for that crisp edge, but fortunately, you don't have to settle for one! If you think about it, it's really just a sharp edge where the alpha goes straight from 0.0->1.0, if we can replicate that, then we should be all set! Math to the rescue, and simple math at that!

Using the plain old y = mx + b algorithm, we can create a graph that does exactly that! With a super steep slope, and a small offset to x, take a look at the graph for y = 10,000(x-0.5):

I love Google

So check that out! Looks pretty much like an on/off switch to me, all that's missing is to clamp it between 0.0 and 1.0 with a call to saturate, and we should be all set! We can attach that 0.5 to a variable, and expose it to users as a cutoff slider.

Custom alpha blend shader with our awesome math function.

I'm honestly not sure I can actually tell the difference here! And that's pretty awesome. The code for it is super simple, but the results look great! I haven't actually tested all this on mobile just yet, but if what I hear is correct, this could be a better solution than alpha testing. Although, I honestly wouldn't be surprised to see that change from device to device. If people are interested, I can try and have some stats on that in the future!

Here's the code, CG, in the format of a Unity shader, or you can download it here.

Shader "Custom/AlphaBlend Cutout" {
 Properties {
  _Tex   ("Texture (RGB)", 2D   ) = "white" {}
  _Cutoff("Alpha cutoff",  Float) = 0.5
 SubShader {
  Tags { "Queue"="Transparent" "RenderType"="Transparent"  }
  Blend SrcAlpha OneMinusSrcAlpha

  LOD 200
  Pass {
   #pragma vertex   vert
   #pragma fragment frag
   #include "UnityCG.cginc"

   sampler2D _Tex;
   float     _Cutoff;

   struct VS_OUT {
    float4 position : SV_POSITION;
    float2 uv       : TEXCOORD0;

   VS_OUT vert (appdata_full input) {
    VS_OUT result;
    result.position = mul (UNITY_MATRIX_MVP, input.vertex);
    result.uv       = input.texcoord;

    return result;

   half4 frag (VS_OUT input) : COLOR {
    half4 color = tex2D(_Tex, input.uv);
    float alpha = saturate(10000*(color.a-_Cutoff));
    return half4(color.rgb,alpha);