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);
placer.DebugDistance();
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);
}
placer.DebugDistance();
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.
