Distributing shapes from a centre point

Question

I'm trying to improve my method of laying out the position of thousands of shapes with an equal footprint over a grid surface from a central point (it has a more organic look). The grid surface means that there's equal spacing between neighbours but I don't want to create a patch-work like pattern by picking a random x and y co-ordinate (or x and z in this case as I'm working in 3 dimensions). What I have now works but is incredibly slow when I start moving up from 2,000 objects. Is there a faster method? I'm avoiding the patch-work effect, like I said, as well as an even circular spread. The distribution right now is very city-like and perfect, but far too slow.

I've commented the function throughout so hopefully it explains everything thoroughly:

ArrayList buildingCoords; // stores the co-ordinates of occupied spaces
int w = 50 // Footprint dimensions. Width and depth.

PVector generateNewBuildingPosition(PVector coord) {
    float sW = 30; // gap between shapes
    // Starting at a coordinate of 0,0 if this is our 1st go
    // (PVector coord initially feeds 0,0)
    // or the last coordinate that was already taken
    // (this loops with the last coordinate if it fails)
    // we check one of the four spaces next to us with
    // the roll of a dice (in a way...)
    float randomX = random(0,15);
    float randomZ = random(0,15);
    if (randomX >= 10) { 
      randomX = w + sW; 
    } else if (randomX >= 5) { 
      randomX = (w + sW) * -1;
    } else {
      randomX = 0;
    }
      if (randomZ >= 10) { 
      randomZ = w + sW; 
    } else if (randomX >= 5) { 
      randomZ = (w + sW) * -1;
    } else {
      randomZ = 0;
    }

    // We've picked our direction.
    // We have a PVector that acts as a marker for where we're
    // placing. Adding or subtracting the movement of each
    // attempt, one at a time, means the shapes spreads out 
    // more organically from the centre rather than trying
    // to distribute each shape as a random patch.
    PVector newDirection = new PVector(randomX, 0, randomZ);
    coord.add(newDirection);
    // Our marker moves to the new spot, we check if it exists.
    // If it doesn't, we confirm it as this shape's anchor spot.
    // If it does, we loop this function again, feeding it where our
    // marker is.
    if(buildingCoords.contains(coord)) {
      generateNewBuildingPosition(coord);
    } else {
      // add this PVector to the arrayList
      buildingCoords.add(coord);
    }
    // Return the coordinates that just succeeded.
    return coord;
  }

Answer 1

This code handles 200,000 basically instantly. I had to guess at a few details but it should be close to what you are looking for.

public class Test {

    static Map<Integer, Vector3> buildingCoords;
    public static void main(String[] args) {
        buildingCoords = new HashMap();

        Vector3 start = new Vector3(0,0,0);

        for (int i = 0; i < 200000; i++)
            start = generateNewBuildingPosition(start);

        System.out.print("Done");

    }

    static Vector3 generateNewBuildingPosition(Vector3 coord) {
        int w = 50; // Footprint dimensions. Width and depth.
        float sW = 30; // gap between shapes
        // Starting at a coordinate of 0,0 if this is our 1st go
        // (PVector coord initially feeds 0,0)
        // or the last coordinate that was already taken
        // (this loops with the last coordinate if it fails)
        // we check one of the four spaces next to us with
        // the roll of a dice (in a way...)
        float randomX = (float)random() * 15;
        float randomZ = (float)random() * 15;
        if (randomX >= 10) randomX = w + sW;
        else if (randomX >= 5) randomX = (w + sW) * -1;
        else randomX = 0;

        if (randomZ >= 10) randomZ = w + sW;
        else if (randomX >= 5) randomZ = (w + sW) * -1;
        else randomZ = 0;


        // We've picked our direction.
        // We have a PVector that acts as a marker for where we're
        // placing. Adding or subtracting the movement of each
        // attempt, one at a time, means the shapes spreads out
        // more organically from the centre rather than trying
        // to distribute each shape as a random patch.
        Vector3 newDirection = new Vector3(randomX, 0, randomZ);
        coord.add(newDirection);
        // Our marker moves to the new spot, we check if it exists.
        // If it doesn't, we confirm it as this shape's anchor spot.
        // If it does, we loop this function again, feeding it where our
        // marker is.
        if(buildingCoords.containsKey(coord.hashCode())) {
            generateNewBuildingPosition(coord);
        } else {
            // add this PVector to the arrayList
            buildingCoords.put(coord.hashCode(), coord);
        }
        // Return the coordinates that just succeeded.
        return coord;
    }
}

class Vector3 {

    float x, y, z; // package-private variables; nice encapsulation if you place this in a maths package of something

    Vector3(float x, float y, float z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public Vector3 add(Vector3 vector) {
        x += vector.x;
        y += vector.y;
        z += vector.z;
        return this; // method chaining would be very useful
    }

    @Override
    public int hashCode(){
        return Float.hashCode(x + y + z);
    }

}

Edit: hashCode as shown is not very sound and may cause issues. You should read: Hashing 2D, 3D and nD vectors