en Java (swing), disons que j'ai un jeu 2D où j'ai différents types d'entités à l'écran, telles qu'un joueur, des mauvais gars, des alimentations, etc. lorsque le joueur se déplace sur l'écran, dans l'ordre Pour effectuer une vérification efficace de ce qui se trouve à proximité immédiate du joueur, je penserais que je voudrais un accès indexé aux choses qui sont près du personnage en fonction de leur position.
Par exemple, si le joueur 'P' étapes sur Element 'E' dans l'exemple suivant ... p>
Map<Point, Entity> map = new HashMap<Point, Entity>();
3 Réponses :
inefficient depuis que je ne connais pas sa position de point à l'avance
Suis-je correct, cet objet d'entité n'a pas d'informations de position? Je suggérerais d'ajouter ça. Ou, sinon, vous pouvez avoir une carte des positions actuelles de l'entité MAP
Soit vous venez de reformuler le problème à portée de main, soit vous n'avez pas compris la question de manière approfondie, car il n'y a pas de solution fournie ici. Sur la base des 2 méthodes proposées dans le poste d'origine, l'objet ne contient pas ou ne contient pas les informations de position. De même, la carte dépend de quelle approche a été prise. Quoi qu'il en soit, le problème initial de la recherche d'un terrain d'entente n'est nulle part dans votre réponse.
Partitionnement de l'espace pourrait être efficace.
Vous pouvez soit faire des divisions fixes, telles qu'une grille uniforme, soit une grille pondérée si vous êtes excepté là-bas pour avoir des points chauds sur votre carte où les choses se font inhabituellement cluster. Pour chaque partition occupée, créez un conteneur de toutes les entités qu'il contient.
L'insertion est une durée constante. L'enlèvement est une fraction pratiquement infinieimale de N (votre nombre total d'entités) en supposant n est très vaste et vous avez configuré vos partitions efficacement. Les look-up de proximité partagent le même runtime comme des déménagements. Toujours techniquement O ( N ) aussi petit la fraction, cependant. Cela deviendrait apparent si une partition deviendrait jamais encombrée inhabituellement.
Pour obtenir une liste de toutes les entités dans les unités X d'une entité, vous devez d'abord obtenir une liste de toutes les partitions remplacées par un carré de 2 x de la place carrée centrée sur votre entité. Si vous utilisez une partition de grille, cela est assez trivial. Ensuite, vous bouclez à travers toutes les entités de ces partitions et renvoyez chacun avec une distance de x ou moins à l'entité en question.
Une méthode plus compliquée de partitionnement consiste à un espace de partition dynamique dans un arbre, garantissant qu'aucune partition ne peut contenir plus d'un nombre donné d'entités. Si une partition devient pleine, vous le divisez le long de la moyenne spacienne et créez deux deux partitions spatiales de manière à ce que chacun détient la moitié des entités de la partition d'origine. Cela rend les insertions et les recherches ont une runtime logarithmique car vous ne pouvez plus découvrir les partitions souhaitées en temps constant, mais les déménagements deviennent une durée constante compte tenu des populations de partitions plafonnées.
Merci pour les conseils, je vais faire la recherche d'espace partitionnement plus.
Je saisis deux implémentations de montants pour tenir 1 000 000 entités ajoutées au hasard à une zone de 1920x1080. À l'aide d'un réseau de conteneurs 1080x1920, j'ai eu 0,004 ms pour l'insertion, 0,003 ms lors de la suppression et 0,004 ms pour demander une liste de tous les conteneurs dans une zone 3x3. À l'aide de la partition d'espace binaire dynamique, j'ai eu 0,007 ms inserts, 0,003 ms de déménagements MS et 0,007 MS requêtes pour les partitions intersectant une région 3x3. La performance et l'utilisation de la mémoire sur le BSP devraient être encore meilleures pour des entités non uniformément distribuées.
S'il y a un mappage individuel entre GUAVA a un Vous pouvez également gérer votre propre carte entité et point , et que vous souhaitez pouvoir cartographier dans les deux sens, un bimap est le plus Structure de données naturelle.
bimap implémentation, qui prend en charge un BIMAP Vue opérationnelle. C'est seulement une vue, donc ce n'est pas coûteux du tout.
mappe carte