En 2D, comment trouver efficacement l’objet le plus proche d’un point?

35

J'ai un moteur de jeu assez important et j'aimerais une fonctionnalité permettant de trouver le plus proche d'une liste de points.

Je pourrais simplement utiliser le théorème de Pythagore pour trouver chaque distance et choisir la distance minimale, mais cela nécessite une itération complète.

J'ai également un système de collision, où je transforme essentiellement des objets en objets plus petits sur une grille plus petite (un peu comme une mini-carte) et si des objets existent dans le même espace quadrillé, je vérifie les collisions. Je pouvais le faire, augmentant l’espacement de la grille pour vérifier la proximité. (Plutôt que de vérifier chaque objet.) Cependant, cela prendrait une configuration supplémentaire dans ma classe de base et encombrerait l'objet déjà encombré. Est-ce que ça vaut le coup?

Y at-il quelque chose d’efficace et de précis que je pourrais utiliser pour détecter l’objet le plus proche, sur la base d’une liste de points et de tailles?

ultifinitus
la source
Stockez les versions au carré des positions x et y afin que vous puissiez faire le théorème de Pythagore sans avoir à faire le carré coûteux à la fin.
Jonathan Connell
3
Ceci s'appelle une recherche de voisin le plus proche . Il y a beaucoup d'écriture sur Internet à ce sujet. La solution habituelle consiste à utiliser une sorte d' arborescence de partitionnement de l' espace .
BlueRaja - Danny Pflughoeft Le

Réponses:

38

Le problème avec un quad / octet dans les recherches du voisin le plus proche est que l'objet le plus proche peut se trouver juste au-delà de la division entre les nœuds. Pour les collisions, ça va, car si ce n'est pas dans le nœud, on s'en fiche. Mais considérons cet exemple 2D avec un quadtree:

Quadtree example

Ici, même si l'élément noir et l'élément vert se trouvent dans le même nœud, l'élément noir est le plus proche de l'élément bleu. La réponse d’ultifinitus ne peut garantir que chez le voisin le plus proche, seul chaque élément de votre arborescence est placé dans le plus petit nœud possible pouvant le contenir, ou dans un nœud unique, ce qui conduit à des quadtrees plus inefficaces. (Notez qu'il existe de nombreuses façons d'implémenter une structure qui pourrait être appelée quad / octree - des implémentations plus strictes pourraient mieux fonctionner dans cette application.)

Une meilleure option serait un kd-tree . Les Kd-trees ont un algorithme de recherche très efficace que vous pouvez implémenter et peuvent contenir un nombre quelconque de dimensions (donc "k").

Une animation fantastique et informative de Wikipedia: kd-tree recherche le plus proche voisin

Si je me souviens bien, le plus gros problème lié à l’utilisation des kd-trees est qu’ils sont plus difficiles à insérer / supprimer tout en maintenant l’équilibre. Par conséquent, je recommanderais d'utiliser un arbre kd pour les objets statiques tels que les maisons et les arbres, qui est très équilibré, et un autre qui contient des joueurs et des véhicules, qui doivent être équilibrés régulièrement. Recherchez l'objet statique le plus proche et l'objet mobile le plus proche, puis comparez-les.

Enfin, les kd-trees sont relativement simples à implémenter, et je suis sûr que vous pourrez y trouver une multitude de bibliothèques C ++. D'après ce que je me souviens, les R-arbres sont beaucoup plus compliqués et probablement exagérés si tout ce dont vous avez besoin est une simple recherche du plus proche voisin.

dlras2
la source
1
Bonne réponse, petit détail "une seule garantie que le voisin le plus proche, seul chaque élément de votre arborescence est placé dans le plus petit nœud possible" 10.000
Roy T.
1
Très vrai - je suppose que "seulement" était un mot plutôt dur. Selon la manière dont vous les implémentez, il existe certainement des moyens d'incorporer les quadtrees dans les recherches au plus proche voisin, mais si vous ne les utilisez pas déjà pour d'autres raisons (telles que la détection de collision), je resterais avec l'arborescence kd plus optimisée.
dlras2
Je voulais noter que j'ai mis en œuvre une implémentation qui traite du problème noir vert bleu. Vérifiez le fond.
clankill3r
18

sqrt() est monotone, ou préservant l'ordre, pour les arguments non négatifs, ainsi:

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

Et vice versa.

Donc si vous voulez seulement comparer deux distances mais que leurs valeurs réelles ne vous intéressent pas, vous pouvez simplement couper le pas sqrt()de votre truc de Pythagore:

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!
}

Ce n'est pas aussi efficace que l'octogone, mais c'est plus facile à implémenter et ça augmente la vitesse au moins un peu

HumanCatfood
la source
1
Cette métrique est également appelée distance euclidienne au carré .
moooeeeep
10

Vous devez faire un partitionnement spatial, dans ce cas, vous créez une structure de données efficace (généralement un octree). Dans ce cas, chaque objet se trouve dans un ou plusieurs espaces (cubes). Si vous savez dans quels espaces vous êtes, vous pouvez rechercher O (1) quels espaces sont vos voisins.

Dans ce cas, l'objet le plus proche peut être trouvé en parcourant d'abord tous les objets de votre propre espace en cherchant lequel est le plus proche. S'il n'y a personne, vous pouvez vérifier vos premiers voisins. S'il n'y a personne, vous pouvez vérifier leurs voisins, etc.

De cette façon, vous pouvez facilement trouver l'objet le plus proche sans avoir à parcourir tous les objets de votre monde. Comme d'habitude, ce gain de vitesse nécessite un peu de comptabilité, mais il est vraiment utile pour toutes sortes de choses, donc si vous avez un monde immense, il vaut vraiment la peine de mettre en œuvre un partitionnement spatial et un octree.

Comme d'habitude, voir aussi l'article de Wikipédia: http://en.wikipedia.org/wiki/Octree

Roy T.
la source
7
@ultifinitus Pour ajouter à cela: Si votre jeu est en 2D, vous pouvez utiliser QuadTrees au lieu d’Octrees.
TravisG
1

Essayez peut-être d’organiser vos données spatiales dans un RTree, ce qui est un peu comme un arbre pour des éléments dans l’espace et permet des requêtes telles que "N voisins les plus proches", etc ... http://en.wikipedia.org/wiki/Rtree

Patrick Hughes
la source
0

Voici mon implémentation Java pour obtenir le plus proche d'un quadTree. Il traite du problème que dlras2 décrit:

entrez la description de l'image ici

Je pense que l'opération est vraiment efficace. Il est basé sur la distance à un quad pour éviter de chercher dans les quads plus loin que le courant le plus proche.

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

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
la source
ps Je pense toujours qu'il vaut mieux utiliser un arbre kd ou quelque chose du genre, mais cela pourrait aider les gens.
clankill3r
Regardez aussi: bl.ocks.org/llb4ll/8709363
clankill3r