J'ai actuellement un jeu simple de type Tetris et j'ai rencontré un problème que je ne peux pas résoudre.
Contrairement à Tetris où il n'y a qu'une seule forme tombante, j'ai plusieurs formes potentiellement entrelacées qui doivent tomber; J'ai besoin de calculer leurs positions finales. Considérer ce qui suit:
Pour calculer la position finale de la forme verte, je numérise simplement vers le bas pour chaque carré jusqu'à ce que je frappe un autre carré ou le bord de la planche. Terminé
Pour des formes multiples et simples, je monte ma planche. Ainsi, le rouge n'a pas besoin de bouger, l'orange descend de un, le vert de trois. Terminé
Je ne sais pas comment traiter les formes vertes et rouges imbriquées. En utilisant la logique du # 2, nous finirions par «coincés» flottant dans les airs. Si je recherche la forme verte, je rencontre le rouge et ne bouge donc pas, et vice-versa pour le rouge. La solution pourrait être de traiter les deux formes comme une seule.
Semblable à # 3, dans ce scénario, je pourrais également réussir en traitant les objets comme un seul.
Contrairement aux n ° 3 et n ° 4, je ne pouvais pas traiter la forme comme une seule car la forme orange finirait par flotter d'un carré trop haut ...
Une autre variante du problème # 6.
Il pourrait y avoir d'autres scénarios où j'ai de nombreuses formes qui s'entrelacent dans des scénarios de plus en plus complexes, mais je pense que ce qui précède couvre les parties les plus fondamentales du problème.
J'ai l'impression qu'il y a une solution élégante que je n'ai pas encore rencontrée / imaginée et je serais très reconnaissant de toute perspicacité, idées ou ressources.
SOLUTION
La solution que j'ai trouvée est en effet élégante, basée sur la réponse de @ user35958 ci-dessous, j'ai créé la fonction récursive suivante (pseudo code)
function stop(square1, square2){
// Skip if we're already stopped
if(square1.stopped){
return;
}
// Are we comparing squares?
if(!square2){
// We are NOT comparing squares, simply stop.
square1.stopped = true;
} else {
// Stop IF
// square1 is directly above square2
// square1 is connected to square2 (part of the same complex shape)
if(square1.x == square2.x && square1.y == (square2.y+1) || isConnected(square1, square2)){
square1.stopped = true;
}
}
// If we're now stopped, we must recurse to our neighbours
stop(square1, squareAbove);
stop(square1, squareBelow);
stop(square1, squareRight);
stop(square1, squareDown);
}GIF animé montrant chaque passage de la solution
Pour résumer:
- Lors de "l'arrêt" d'un carré, nous arrêtons également:
- N'IMPORTE QUEL carré au-dessus. TOUJOURS.
- Carré voisin auquel nous sommes connectés (c'est-à-dire la même forme).
- Nous arrêtons toute la rangée du bas et la fonction revient à travers les carrés.
- Nous répétons jusqu'à ce que tous les carrés soient arrêtés.
- Ensuite, nous animons.
la source
Réponses:
Eh bien, vous n'avez pas exactement besoin de traiter les formes comme s'il y avait une distinction entre les formes en mouvement et les formes au repos. Une forme (A) pourrait détecter une forme (B) directement en dessous et si elle bouge, alors la forme B pourrait alors voir s'il y a quelque chose directement en dessous, et s'il y a une forme au repos, alors A et B se reposent maintenant, et s'il n'y a rien, ils descendent tous les deux, mais s'il y a une forme en mouvement, alors cette nouvelle forme sera traitée par A et B comme A traité B, donc c'est en quelque sorte récursif. Gardez à l'esprit que pour chaque étape, les formes les plus basses doivent d'abord vérifier les formes en dessous.
Donc, pour le problème n ° 6, la forme verte est la forme la plus basse en mouvement, et cela verrait que la seule forme qui est directement en dessous est la forme rouge, donc la forme rouge ne détecterait rien directement en dessous, et ils se déplaceraient vers le bas . Une fois que la forme verte est adjacente à la forme orange, elle se reposerait, et la forme rouge se déplacerait vers le bas, puis détecterait la forme verte au repos, et elle se reposerait également.
la source
Il semble que le problème avec les cas # 5 et # 6 provient d'une seule racine: vous n'effectuez qu'une seule passe de contrôle de mouvement. Vous devriez continuer à déplacer les choses vers le bas (appelons cela un "passage de gravité") jusqu'à ce que vous ne sachiez rien bouger.
Par exemple, dans le cas 6, c'est ce qui se passerait si vous utilisiez plusieurs passes:
Cette stratégie de passes de gravité multiples pourrait également résoudre le problème n ° 5, même si cela n'aidera pas les cas n ° 3 et n ° 4 où il semble que vous devez les traiter comme une seule pièce.
Pour distinguer quand deux pièces ou plus doivent être traitées comme une seule pièce, je pense que l'algorithme le plus simple est de vérifier s'il y a des "trous" dans l'espace combiné de toutes les pièces. S'il y en a, il peut être traité comme plusieurs pièces.
la source