Dalam 2D, bagaimana cara efisien menemukan objek terdekat ke suatu titik?

35

Saya memiliki mesin permainan yang cukup besar dan saya ingin fitur untuk menemukan yang terdekat dari daftar poin.

Saya hanya bisa menggunakan teorema Pythagoras untuk menemukan jarak masing-masing dan memilih yang minimum, tetapi itu membutuhkan iterasi melalui semuanya.

Saya juga memiliki sistem tabrakan, di mana pada dasarnya saya mengubah objek menjadi objek yang lebih kecil pada grid yang lebih kecil (seperti minimap) dan hanya jika objek ada di ruang grid yang sama saya memeriksa collision. Saya bisa melakukan itu, hanya membuat jarak grid lebih besar untuk memeriksa kedekatan. (Daripada memeriksa setiap objek.) Namun, itu akan mengambil pengaturan tambahan di kelas dasar saya dan mengacaukan objek yang sudah berantakan. Apakah itu layak?

Adakah sesuatu yang efisien dan akurat yang dapat saya gunakan untuk mendeteksi objek mana yang paling dekat, berdasarkan daftar titik dan ukuran?

ultifinitus
sumber
Menyimpan versi kuadrat dari posisi x dan y sehingga Anda dapat melakukan teorema pythagoras tanpa harus melakukan sqrt mahal di akhir.
Jonathan Connell
3
Ini disebut pencarian tetangga terdekat . Ada banyak tulisan di internet tentang itu. Solusi yang biasa adalah dengan menggunakan semacam pohon partisi ruang .
BlueRaja - Danny Pflughoeft

Jawaban:

38

Masalah dengan quad / octree dalam pencarian tetangga terdekat adalah bahwa objek terdekat mungkin duduk tepat di seberang pembagian antara node. Untuk tabrakan, ini tidak apa-apa, karena jika tidak ada dalam node, kami tidak peduli. Tapi pertimbangkan contoh 2D ini dengan quadtree:

Contoh Quadtree

Di sini, meskipun item hitam dan item hijau berada di simpul yang sama, item hitam paling dekat dengan item biru. jawaban ultifinitus hanya dapat menjamin tetangga terdekat saja setiap item di pohon Anda ditempatkan di simpul sekecil mungkin yang bisa mengandungnya, atau dalam simpul unik - ini mengarah pada quadtrees yang lebih tidak efisien. (Perhatikan bahwa ada banyak cara berbeda untuk mengimplementasikan suatu struktur yang dapat disebut quad / octree - implementasi yang lebih ketat dapat bekerja lebih baik dalam aplikasi ini.)

Pilihan yang lebih baik adalah pohon kd . Kd-tree memiliki algoritma pencarian tetangga terdekat yang sangat efisien yang dapat Anda terapkan, dan dapat berisi sejumlah dimensi (karenanya dimensi "k".)

Animasi hebat dan informatif dari Wikipedia: kd-tree pencarian tetangga terdekat

Masalah terbesar dengan menggunakan kd-tree, jika saya ingat dengan benar, adalah bahwa mereka lebih sulit untuk memasukkan / menghapus item dari sambil menjaga keseimbangan. Oleh karena itu, saya akan merekomendasikan menggunakan satu kd-tree untuk objek statis seperti rumah dan pohon yang sangat seimbang, dan yang lain berisi pemain dan kendaraan, yang perlu diseimbangkan secara teratur. Temukan objek statis terdekat dan objek seluler terdekat, dan bandingkan keduanya.

Terakhir, kd-tree relatif mudah diimplementasikan, dan saya yakin Anda dapat menemukan banyak pustaka C ++. Dari yang saya ingat, R-tree jauh lebih rumit, dan mungkin berlebihan jika yang Anda butuhkan hanyalah pencarian tetangga terdekat yang sederhana.

dlras2
sumber
1
Jawaban yang bagus, detail kecil "satu-satunya jaminan tetangga terdekat hanya setiap item di pohon Anda ditempatkan di simpul sekecil mungkin" Maksud saya dalam jawaban saya iterasi semua item dalam node yang sama dan tetangga, sehingga Anda memutar lebih dari 10 alih-alih 10.000.
Roy T.
1
Sangat benar - saya kira "hanya" adalah kata yang agak kasar. Pasti ada cara untuk membujuk quadtrees ke pencarian tetangga terdekat tergantung pada bagaimana Anda menerapkannya, tetapi jika Anda tidak menggunakannya karena alasan lain (seperti deteksi tabrakan,) saya akan tetap menggunakan pohon kd-lebih dioptimalkan.
dlras2
Saya ingin mencatat bahwa saya membuat implementasi yang berhubungan dengan masalah biru hijau hitam. Periksa bagian bawah.
clankill3r
18

sqrt() bersifat monotonik, atau mempertahankan pesanan, untuk argumen non-negatif jadi:

sqrt(x) < sqrt(y) iff x < y

Dan sebaliknya.

Jadi jika Anda hanya ingin membandingkan dua jarak tetapi tidak tertarik dengan nilai aktualnya, Anda cukup memotong sqrt()-step dari Pythagoras-stuff Anda:

pseudoDistanceB = (A.x - B.x + (A.y - B.y
pseudoDistanceC = (A.x - C.x + (A.y - C.y
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

Ini tidak seefisien hal oct-tree, tetapi lebih mudah untuk diimplementasikan dan meningkatkan kecepatan setidaknya sedikit

HumanCatfood
sumber
1
Metrik itu juga disebut sebagai jarak euclide kuadrat .
moooeeeep
10

Anda harus melakukan partisi spasial, dalam hal ini Anda membuat struktur data yang efisien (biasanya sebuah octree). Dalam hal ini setiap objek berada di dalam satu atau lebih spasi (kubus) Dan jika Anda tahu di ruang mana Anda berada, Anda dapat mencari O (1) spasi mana yang merupakan tetangga Anda.

Dalam hal ini objek terdekat dapat ditemukan dengan terlebih dahulu mengulangi semua objek di ruang Anda sendiri mencari yang mana yang paling dekat di sana. Jika tidak ada seorang pun di sana Anda dapat memeriksa tetangga pertama Anda, jika tidak ada seorang pun di sana Anda dapat memeriksa tetangga mereka, dll ...

Dengan cara ini Anda dapat dengan mudah menemukan objek terdekat tanpa harus mengulangi semua objek di dunia Anda. Seperti biasa peningkatan kecepatan ini memang membutuhkan sedikit pembukuan, tetapi ini sangat berguna untuk semua jenis barang jadi jika Anda memiliki dunia yang besar itu pasti layak untuk menerapkan partisi spasial dan satu octree.

Seperti biasa, lihat juga artikel wikipedia: http://en.wikipedia.org/wiki/Octree

Roy T.
sumber
7
@ultifinitus Untuk menambahkan ini: Jika game Anda adalah 2D, Anda dapat menggunakan QuadTrees alih-alih Octrees.
TravisG
1

Mungkin mencoba mengatur data spasial Anda dalam RTree, yang seperti sejenis btree untuk hal-hal di luar angkasa dan memungkinkan pertanyaan seperti "tetangga N terdekat" dll ... http://en.wikipedia.org/wiki/Rtree

Patrick Hughes
sumber
0

Berikut ini adalah implementasi java saya untuk mendapatkan yang terdekat dari quadTree. Ini berkaitan dengan masalah dlras2 yang menggambarkan:

masukkan deskripsi gambar di sini

Saya pikir operasinya sangat efisien. Hal ini didasarkan pada jarak ke quad untuk menghindari pencarian di quads lebih jauh dari yang terdekat saat ini.

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

public T getClosest(float x, float y) {

    Closest closest = new Closest();
    getClosest(x, y, closest);

    return closest.item;
}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

protected void getClosest(float x, float y, Closest closestInfo) {


    if (hasQuads) {

        // we have no starting point yet
        // so get one
        if (closestInfo.item == null) {
            // check all 4 cause there could be a empty one
            for (int i = 0; i < 4; i++) {
                quads[i].getClosest(x, y, closestInfo);
                if (closestInfo.item != null) {
                    // now we have a starting point
                    getClosest(x, y, closestInfo);
                    return;
                }

            }
        }
        else {

            // we have a item set as closest
            // we should check if this quad is
            // closer then the current closest distance
            // let's start with the closest from index

            int closestIndex = getIndex(x, y);

            float d = quads[closestIndex].bounds.distToPointSQ(x, y);

            if (d < closestInfo.dist) {
                quads[closestIndex].getClosest(x, y, closestInfo);
            }

            // check the others
            for (int i = 0; i < 4; i++) {
                if (i == closestIndex) continue;

                d = quads[i].bounds.distToPointSQ(x, y);

                if (d < closestInfo.dist) {
                    quads[i].getClosest(x, y, closestInfo);
                }

            }

        }

    }
    else {

        for (int i = 0; i < items.size(); i++) {

            T item = items.get(i);

            float dist = distSQ(x, y, getXY.x(item), getXY.y(item));

            if (dist < closestInfo.dist) {
                closestInfo.dist = dist;
                closestInfo.item = item;
                closestInfo.tree = this;
            }

        }
    }

}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


class Closest {

    QuadTree<T> tree;
    T item;
    float dist = Float.MAX_VALUE;

}
clankill3r
sumber
ps Saya masih berpikir lebih baik menggunakan kd-tree atau sesuatu, tapi ini mungkin bisa membantu orang.
clankill3r
lihat juga ini: bl.ocks.org/llb4ll/8709363
clankill3r