Déterminer si la structure créée par le joueur correspond à un modèle dans un jeu basé sur des blocs 3D

Avertissement: c'est l'une de ces redoutables questions de style Minecraft, mais je pense que c'est plus une question de structures de données et d'algorithmes

Je suis vraiment nouveau dans les structures de données 3D et je me demande quelle est la meilleure façon de stocker et de faire correspondre une structure de bloc 3D.

À l'heure actuelle, le joueur est capable de placer des blocs dans n'importe quel espace arbitraire et lorsque ces blocs correspondent à une structure prédéfinie, un événement se produit. La façon dont je le fais actuellement est lorsqu'un joueur place un bloc, le jeu vérifie récursivement chaque bloc adjacent pour trouver le bloc avec les coordonnées x, y, z les plus basses et fait de ce bloc le bloc racine. Ensuite, il vérifie le reste des blocs, basé sur le bloc racine, pour s'assurer qu'ils correspondent à un certain modèle. Le problème est que plus le modèle devient compliqué, plus mon code (terriblement inefficace) l'est aussi.

Je pense que la meilleure façon de le faire est de stocker un type de matrice qui définit la structure, puis de faire correspondre la matrice à chaque fois qu'un joueur place un bloc. Existe-t-il déjà des structures / algorithmes de données qui correspondent à ce type de problème?

Pour être honnête, je prendrais la solution simple.

Faites une matrice qui définit la structure. Chaque fois qu'un bloc est modifié, essayez d'appliquer cette matrice à tous les emplacements qui auraient pu créer la nouvelle structure. Cela va être des emplacements largeur * profondeur * hauteur, car le joueur aurait pu terminer n'importe quel point sur la structure, mais cela ne devrait pas être trop mauvais car la plupart de ces emplacements vont quitter tôt lorsque le premier contrôle échoue.

Fondamentalement, vous avez une matrice 3D et vous la comparez à une autre matrice 3D, à un tas de compensations.

À partir d'ici, vous pouvez faire un tas d'optimisations totalement facultatives. Par exemple, si votre structure est extrêmement clairsemée - c'est-à-dire que le joueur construit une grande tour avec une sphère en haut, mais peu vous importe si le bas de la tour est entouré d'arbres - vous pouvez en faire une liste de blocs au lieu d'une matrice. (Je générerais la liste à partir de la matrice - la matrice sera beaucoup plus facile à maintenir directement.)

Si vous vouliez être super intelligent, divisez la structure en types de blocs. Si vous savez que le joueur vient de changer le bloc 1,2,3, et que vous savez que placer votre structure aux coordonnées 0,0,0 nécessiterait que le bloc 1,2,3 soit en obsidienne, et le bloc 1,2,3 est en bois , alors vous n'avez même pas besoin d'essayer le bloc 1,2,3. Générez tous les décalages possibles pour la structure étant donné que le joueur vient de placer un type spécifique de bloc. Ensuite, lorsque le joueur place ce bloc, vérifiez simplement les décalages possibles prégénérés.

Mais, sérieusement, tout cela est optimisé. Faites simplement une matrice, puis comparez votre matrice avec le style mondial de force brute. En supposant que vous faites quelque chose de Minecrafty, les gens ne placent vraiment pas autant de blocs - quelques blocs au plus par seconde. À moins que vous ayez des centaines de structures énormes, vous pourrez tester cela facilement.

Eh bien, vous venez avec un problème intéressant. Je suggérerais quelque chose comme ceci: utilisez vos blocs comme pixels et faites une détection de collision par / pixel, où tous les blocs doivent correspondre pour renvoyer une vraie collision.

Cela fonctionnerait bien, mais assurez-vous de ne le faire que lorsque les objets / blocs changent. Je recommanderais donc un système d'événements simple pour passer une modification à un vérificateur d'objets, qui peut certainement utiliser votre algorithme. Ce qui ferait alors tout ce que vous voulez que cet objet fasse. Je recommanderais également de vérifier la hauteur et la largeur avant d'exécuter l'algorithme, car s'il n'est pas assez haut / trop haut, il ne correspondra évidemment pas.

En ce qui concerne une structure de données, un simple vecteur ferait l'affaire, ou peut-être une structure de données personnalisée.

Question interessante.