J'ai eu des problèmes pour déterminer efficacement si de grandes pièces sont scellées dans des pièces 3D à base de voxel. J'en suis à un point où j'ai fait de mon mieux pour résoudre le problème sans demander de l'aide, mais pas assez pour abandonner, alors je demande de l'aide.
Pour clarifier, scellé étant qu'il n'y a pas de trous dans la pièce. Il existe des scelleurs à oxygène qui vérifient si la pièce est scellée et scellent en fonction du niveau d'entrée d'oxygène.
En ce moment, voici comment je le fais:
- En commençant par le bloc au-dessus de la tuile de scellant (l'évent est sur la face supérieure du scellant), faites une boucle récursive dans les 6 directions adjacentes
- Si la tuile adjacente est une tuile pleine, sans vide, continuez à travers la boucle
- Si la tuile adjacente n'est pas pleine, ou est une tuile sous vide, vérifiez si ce sont des blocs adjacents qui sont récursivement.
- Chaque fois qu'une tuile est vérifiée, décrémenter un compteur
- Si le nombre atteint zéro, si le dernier bloc est adjacent à une tuile à vide, retournez que la zone est descellée
- Si le nombre atteint zéro et que le dernier bloc n'est pas une tuile à vide, ou si la boucle récursive se termine (plus aucune tuile à vide) avant que le compteur ne soit nul, la zone est scellée
Si la zone n'est pas scellée, exécutez à nouveau la boucle avec quelques modifications:
- Vérification des blocs adjacents pour la tuile "air respirable" au lieu d'une tuile sous vide
- Au lieu d'utiliser un compteur décrémentant, continuez jusqu'à ce qu'aucune tuile adjacente "air respirable" ne soit trouvée.
- Une fois la boucle terminée, définissez chaque bloc vérifié sur une tuile à vide.
Voici le code que j'utilise: http://pastebin.com/NimyKncC
Le problème:
J'exécute cette vérification toutes les 3 secondes, parfois un scellant devra faire une boucle à travers des centaines de blocs, et un grand monde avec de nombreux scelleurs à oxygène, ces multiples boucles récursives toutes les quelques secondes peuvent être très difficiles sur le CPU.
Je me demandais si quelqu'un ayant plus d'expérience avec l'optimisation peut me donner un coup de main, ou au moins me diriger dans la bonne direction. Merci beaucoup.
Réponses:
La meilleure solution reposera sur plusieurs facteurs, comme la taille prévue de la pièce.
Approche 1:
Vous pouvez utiliser un A * pour trouver un chemin de l'évent à la tuile au-dessus de l'évent / l'évent lui-même ou à une tuile qui est connue sous le nom de vide. Si un chemin est trouvé, la pièce est descellée. Ce n'est pas si différent de votre approche actuelle mais devrait être plus rapide. Une fois trouvé, faites un "remplissage par inondation" pour définir les carreaux comme vide.
Approche 2:
Peut-être que votre structure extérieure est moins compliquée - étant donné qu'il y a une surface sous laquelle se trouvent les pièces, vous n'avez pas besoin de vous déplacer dans les 6 directions, vous devez donc voyager le long de la surface, marquer chaque tuile comme le vide que vous voyagez.
la source
Lorsque vous effectuez votre recherche récursive, vous assurez-vous que vous ne vérifiez pas le même voxel plusieurs fois? Je ne pourrais pas dire de la façon dont vous avez décrit votre algorithme, mais vous devriez avoir une sorte d'indicateur pour indiquer si vous avez déjà récursivement développé un voxel, donc vous ne le faites pas plus d'une fois.
Et comme l'a dit Byte56, vous ne devez également vérifier les fuites que lorsque les choses changent. Cela pourrait considérablement réduire la quantité de travail que vous effectuez, selon la fréquence des changements. Vous pouvez même mettre en cache des informations entre des appels successifs à l'algorithme, ce qui peut banaliser la quantité de calculs que vous effectuez après le premier appel.
Éditer:
J'ai regardé une partie de votre code. Il semble que vous utilisez une LinkedList pour indiquer si un voxel a déjà été vérifié, comme dans mon premier paragraphe. Vous pouvez obtenir de meilleurs résultats si vous utilisez autre chose qu'une LinkedList pour cela. Essayez peut-être un HashSet ou quelque chose? Cela devrait réduire la complexité de votre méthode de vérification de O (n) à O (1).
la source