Bagaimana cara menempatkan entitas secara acak yang tidak tumpang tindih?

11

Saya membuat lingkungan yang dibuat secara acak untuk game yang saya kembangkan. Saya menggunakan OpenGLdan mengkode Java.

Saya mencoba menempatkan pohon secara acak di dunia saya (untuk membuat hutan), tetapi saya tidak ingin modelnya tumpang tindih (yang terjadi ketika dua pohon ditempatkan terlalu dekat satu sama lain). Inilah gambar dari apa yang saya bicarakan:

masukkan deskripsi gambar di sini

Saya dapat memberikan lebih banyak kode jika perlu, tetapi ini cuplikan penting. Saya menyimpan objek saya ArrayListdengan List<Entity> entities = new ArrayList<Entity>();. Saya kemudian menambahkan ke daftar itu menggunakan:

Random random = new Random();
for (int i = 0; i < 500; i++) {
    entities.add(new Entity(tree, new Vector3f(random.nextFloat() * 800 - 400, 
    0, random.nextFloat() * -600), 0, random.nextFloat() * 360, 0, 3, 3, 3);
}

di mana masing-masing Entitymengikuti sintaks berikut:

new Entity(modelName, positionVector(x, y, z), rotX, rotY, rotZ, scaleX, scaleY, scaleZ);

rotXadalah rotasi sepanjang sumbu x, dan scaleXskala dalam arah x, dll.

Anda dapat melihat bahwa saya menempatkan pohon-pohon ini secara acak dengan random.nextFloat()untuk xdan zposisi, dan membatasi rentang sehingga pohon-pohon akan muncul di lokasi yang diinginkan. Namun, saya ingin entah bagaimana mengontrol posisi-posisi ini, sehingga jika ia mencoba menempatkan pohon terlalu dekat dengan pohon yang ditempatkan sebelumnya, itu akan menghitung ulang posisi acak baru. Saya berpikir bahwa setiap pohon Entitydapat memiliki bidang lain, seperti treeTrunkGirth, dan jika pohon ditempatkan pada jarak antara lokasi pohon lain dan itu treeTrunkGirth, maka itu akan menghitung ulang posisi baru. Apakah ada cara untuk menyelesaikan ini?

Saya senang menambahkan potongan kode dan detail yang diperlukan.

gerobak
sumber
3
Pengambilan sampel disk Poisson harus melakukan pekerjaannya. Tidak tahu apakah ini yang terbaik untuk ini dan tidak pernah benar-benar diterapkan / digunakan, tetapi tampaknya setidaknya sebagai awal yang baik. Periksa artikel ini: devmag.org.za/2009/05/03/poisson-disk-sampling
Mars
@ Mars Wow, tautan itu sangat membantu, terima kasih. Saya akan melihat apa yang bisa saya lakukan, dan mungkin kembali dengan jawaban saya sendiri.
wcarhart
@ Pikalek Ya, saya pikir pertanyaan yang Anda tautkan adalah duplikat. Apakah saya hanya akan menggunakan bidang xz sebagai area untuk "peta bintang," seperti pada pertanyaan lainnya?
wcarhart
Ya, gunakan bidang xz dalam kasus Anda. Juga, gunakan treeTrunkGirthbukan konstanta untuk menentukan jarak minimum untuk menempatkan pohon jika mereka perlu bervariasi.
Pikalek
@ Pikalek Jika Anda menambahkan semua itu dalam jawaban, saya akan memilihnya sebagai yang terbaik. Terima kasih untuk bantuannya.
wcarhart

Jawaban:

15

Sebuah Poisson-Disk pengambilan sampel distribusi akan memungkinkan Anda untuk memilih titik acak jarak minimum terpisah. Situasi Anda mirip dengan pertanyaan ini , tetapi karena pohon Anda bukan titik ideal, Anda perlu mengubah pemeriksaan jarak sebagai berikut: jarak antara pohon baru yang potensial & pohon yang ada, harus kurang dari jumlah jari-jari mereka. .

Algoritma Bridson dapat secara efisien menyelesaikan masalah dalam O (n), tetapi bisa sedikit rumit untuk menyesuaikannya untuk jarak variabel. Jika parameter Anda agak rendah & / atau Anda mengkomputasi medan Anda, solusi brute force juga dapat membantu Anda. Berikut adalah beberapa contoh kode yang memaksa masalah dengan memeriksa setiap potensi penempatan pohon baru terhadap semua pohon yang ditempatkan sebelumnya:

public static class SimpleTree{
    float x;
    float z;
    float r;

    public SimpleTree(Random rng, float xMax, float zMax, float rMin, float rMax){
        x = rng.nextFloat() * xMax;
        z = rng.nextFloat() * zMax;
        r = rng.nextFloat() * (rMax-rMin) + rMin;
    }
}

private static ArrayList<SimpleTree> buildTreeList(float xMax, float zMax, 
        float rMin, float rMax, int maxAttempts, Random rng) {
    ArrayList<SimpleTree> result = new ArrayList<>();

    SimpleTree currentTree = new SimpleTree(rng, xMax, zMax, rMin, rMax);
    result.add(currentTree);

    boolean done = false;
    while(!done){
        int attemptCount = 0;
        boolean placedTree = false;
        Point nextPoint = new Point();
        SimpleTree nextTree = null;
        while(attemptCount < maxAttempts && !placedTree){
            attemptCount++;
            nextTree = new SimpleTree(rng, xMax, zMax, rMin, rMax);
            if(!tooClose(nextTree, result)){
                placedTree = true;
            }
        }
        if(placedTree){
            result.add(nextTree);
        }
        else{
            done = true;
        }
    }

    return result;
}

private static boolean tooClose(SimpleTree tree, ArrayList<SimpleTree> treeList) {
    for(SimpleTree otherTree : treeList) {
        float xDiff = tree.x - otherTree.x;
        float zDiff = tree.z - otherTree.z;

        float dist = (float)Math.sqrt((xDiff * xDiff) + (zDiff * zDiff));
        if(dist < tree.r + otherTree.r){
            return true;
        }
    }        
    return false;
}

Dengan parameter berikut:

 maxAttempts = 500;
 width = 300;
 height = 200;
 minSize = 2;
 maxSize = 15;

Saya dapat menempatkan & membuat secara acak antara 400-450 pohon dalam waktu kurang dari sedetik. Ini sebuah contoh: masukkan deskripsi gambar di sini

Pikalek
sumber
Apakah ini menggunakan sampling disk Poisson?
wcarhart
Ya, saya telah mengedit untuk menjadikannya eksplisit.
Pikalek
Cobalah untuk menggunakan math.pow on tree.r + other tree.r, 2, bukannya math.sqrt, sqrt biasanya lebih lambat dari pow
Ferrybig
1
@Ferrybig Membandingkan jarak kuadrat lebih cepat, tetapi itu tidak mengubah fakta bahwa itu adalah algoritma brute force & masih akan menjadi O (n ^ 2). Jika solusi yang lebih cepat diperlukan, gunakan algoritma Bridson. Juga, menggunakan Math.pow(x,2)belum tentu lebih baik / berbeda dari menggunakan x*xseperti yang dibahas di sini .
Pikalek
1
Saya memiliki masalah serupa dengan medan dan memastikan beberapa penyebaran yang layak dan tidak tumpang tindih. Sebenarnya saya telah melakukan variasi, dalam versi saya tress / brush tersebar secara acak di seluruh area medan. Saya kemudian menjalankan fungsi posting ini untuk memeriksa jarak setiap item terhadap satu sama lain, di mana mereka terlalu dekat saya mendorong mereka terpisah. Meskipun ini akan menimpa mungkin pada pohon lain di daerah tersebut. Saya ulangi ini sampai tidak ada tabrakan. itu lebih lambat tetapi apa yang saya juga miliki sebagai bonus adalah hal-hal seperti pembukaan (tidak ada di mana-mana tertutup!) dan kepadatan pohon tampak lebih "menarik".
ErnieDingo