Comment puis-je détecter des «pièces» dans un jeu à défilement horizontal 2D?

Je cherche à créer un système qui reconnaît certains types de bâtiments et de pièces que vous pouvez créer dans le jeu, comme la façon dont Terraria détecte les "résidences". Dans ce jeu, une maison peut être construite dans un monde basé sur des tuiles en construisant une zone de blocs remplissant un ensemble de conditions:

1. La zone est complètement isolée de "l'extérieur" par des blocs placés par les joueurs.
2. La zone peut contenir un rectangle 5x7.
3. il y a au moins une table, une source de lumière et une chaise dans la zone fermée.
4. Il y a une porte qui sort de la zone.
5. Terraria a à la fois une couche de tuiles de premier plan et d'arrière-plan. Tout l'arrière-plan de la zone doit être rempli de blocs placés par les joueurs.

Comment puis-je détecter efficacement quand un joueur a construit une zone de taille appropriée, et comment puis-je vérifier efficacement que la zone contient tous les meubles / composants requis?

Exemple d'une zone intérieure répondant à toutes les exigences de logement:

Je ne connais pas Terraria, mais cela peut être facilement fait en utilisant un algorithme de remplissage .

Au lieu de pixel, vous vérifiez les tuiles et pour chaque tuile vérifiée, vous évaluez si l'algorithme peut continuer à vérifier d'autres tuiles, tout en stockant dans un tableau ou une liste les objets trouvés pendant le processus.

L'algorithme commence à la tuile où se trouve le personnage. Vous pouvez commencer chaque 1 seconde, 2 ... c'est une question de peaufinage pour trouver le meilleur intervalle.

C'est également une bonne idée d'empêcher l'algorithme de fonctionner trop longtemps, ce qui peut être accompli en limitant le nombre de tuiles que l'algorithme peut exécuter par exécution, sinon votre algorithme entraînera de longs décalages lorsque le personnage se trouve dans une zone ouverte.

modifier

Comme indiqué dans les commentaires, vous pouvez utiliser d'autres approches pour savoir quand démarrer l'algorithme, comme lorsque le joueur change une tuile, ou les tuiles ayant une am I modified?variable qui, si true, démarre l'algorithme. Cependant, vous devez être prudent avec cette approche:

• Que faire si une tuile qui fait partie de la pièce, mais pas une tuile où se trouve votre personnage, est modifiée? Peut-être que la tuile a été changée par un autre joueur, ou un événement d'environnement, ou la durée de vie de la tuile a pris fin. Votre personnage ne sera pas au courant de la modification et n'exécutera pas l'algorithme pour détecter la salle mise à jour, une situation sujette aux erreurs.

Vous pouvez implémenter une sorte d'approche pour détecter ces modifications sur des tuiles où votre personnage n'est pas, mais l'exécution de l'algorithme à intervalles est l'approche la plus simple et la moins sujette aux erreurs. Assurez-vous simplement de ne pas exécuter le remplissage sur chaque image.

Fin du montage

Comme l'a dit @Ferreira da Selva, essayez l'algorithme de remplissage d'inondation. Cependant, vous pouvez utiliser plusieurs critères différents lors de l'exécution de l'algorithme pour déterminer s'il est inclus.

Par exemple, pour chaque tuile, vous vérifiez s'il y a une tuile d'arrière-plan, et s'il n'y en a pas, alors vous savez qu'elle n'est pas incluse. Ou vous pourriez lui faire effectuer une exécution différée en la séparant sur un certain nombre de trames, allégeant ainsi la charge sur le processeur et réduisant le décalage. Ou vous pouvez créer une limite de taille de pièce que le joueur devra respecter.

L'utilisation d'une combinaison de ceux-ci vous permettrait de le faire plus efficacement et efficacement.

Il y a 2 problèmes difficiles en informatique. Nommer les choses, invalider le cache et les erreurs hors-ligne.

Il s'agit d'un problème d'invalidation du cache.

Si vous avez un enregistrement de "est-ce à l'intérieur", chaque fois qu'un bloc est placé ou supprimé, il est assez facile de le mettre à jour et sa région via un remplissage d'inondation.

Pour optimiser cela, vous voudrez peut-être avoir un ensemble de niveaux d '«insiduité».

Une "cellule" est une région entourée de blocs placés par les joueurs (jusqu'à une certaine taille).

Une "pièce" est une cellule avec des tuiles de fond.

"Inside" est une pièce avec une porte, une lumière et une chaise.

Lorsque vous placez un bloc de premier plan placé par le joueur, faites une marche dans le sens horaire / antihoraire pour voir si une nouvelle cellule est formée. Lorsque vous supprimez un bloc de premier plan placé par le joueur, examinez s'il casse des cellules - si c'est le cas, voyez si une nouvelle cellule est formée en fusionnant les deux.

Lorsqu'une nouvelle cellule est formée ou non, vérifiez qu'il s'agit d'une pièce ou d'un intérieur.

Les cellules peuvent garder une trace du nombre de tuiles d'arrière-plan dont elles ont besoin pour être une pièce. Ensuite, un simple comptage lorsqu'une cellule est formée, une tuile d'arrière-plan est ajoutée ou supprimée de la cellule, peut déterminer s'il s'agit d'une pièce.

De même, les cellules peuvent garder une trace du nombre de chaises et de sources lumineuses (et en fait des objets de toutes sortes) à l'intérieur. Ensuite, la vérification intérieure est triviale.

Un décompte des entrées peut également être effectué.

Nous augmentons donc la carte avec des "cellules". Lorsque des tuiles sont ajoutées ou supprimées, nous vérifions la cellule de l'emplacement et incrémentons / décrémentons le nombre dans la cellule.

Utilisez la marche dans le sens horaire / antihoraire pour définir l'intérieur et l'extérieur d'une cellule lorsqu'un bloc de premier plan est ajouté ou supprimé. Comme la taille des cellules est limitée, cette promenade prendra un nombre limité d'étapes.

En prime, vous avez maintenant un moyen bon marché de parler des pièces "opulentes", ou "la pièce est bénie par une fontaine sainte", ou de toute autre chose au sujet d'une pièce, car les pièces ont un compte de chaque type d'objet en elles. (Ou, comme les salles sont limitées en taille, faites simplement une itération; cela supprime un cache).

Chaque emplacement se trouve dans au plus une cellule, vous pouvez donc stocker l'identifiant de cellule de chaque emplacement sur la carte principale.

Lorsque vous utilisez l'algorithme de remplissage, créez également une variable qui augmentera avec chaque tuile vérifiée, donc si elle est supérieure à 35 (7 * 5, la taille maximale de la pièce), elle arrête juste de vérifier!