Algorithme de remplissage d'espace vide (avec des blocs)

Squix

Bonjour chers modeurs,

Je me suis récemment attelé à la création d’un nouveau mod. Dans celui-ci j’ai un seau qui permet de remplir toute une zone vide (comme un trou) automatiquement.

Ex : Je fais un trou de 5x6x2, je clique une fois avec mon seau sur l’un des blocs du rebord et tout le trou se remplit d’eau.

Pour réaliser cela j’ai commencé par faire un algo basique qui vérifie si les blocs situés respectivement au nord, au sud, à l’est et à l’ouest du bloc cliqué sont vides.
Si oui, il place un bloc d’eau à cet endroit.

#Language Algo

posBlocCliqué = blocCliqué.position

SI posBlocCliqué.blockNord() EST de type AIR
ALORS placerBloc(posBlocCliqué.blockNord)

SI posBlocCliqué.blockSud() EST de type AIR
ALORS placerBloc(posBlocCliqué.blockSud)

SI posBlocCliqué.blockEst() EST de type AIR
ALORS placerBloc(posBlocCliqué.blockEst)

SI posBlocCliqué.blockOuest() EST de type AIR
ALORS placerBloc(posBlocCliqué.blockOuest)

Voici ce que ça donne en 1.8 (NOTE: cela fonctionne uniquement si l’on clique sur un bloc au sol pour l’instant) :


@Override
public boolean onItemUse(ItemStack item, EntityPlayer pl, World w,
BlockPos pos, EnumFacing side, float arg5, float arg6, float arg7) {

 if(w.isRemote)
 {

   pl.addChatComponentMessage(new ChatComponentText("Side clicked = " + side.name()));

   switch(side) {

    case UP:
    pl.addChatComponentMessage(new ChatComponentText("UpSide"));
    fillSystem(w, pos, side);
    break;

   }

 }

 else {

   Boolean blockAdded = w.setBlockState(new BlockPos(pos.getX(),pos.getY() + 1,pos.getZ()), Blocks.water.getDefaultState(), '3');
   System.out.println("DEBUG : mainBlockAdded = " + blockAdded);

 }

  return super.onItemUse(item, pl, w, pos, side, arg5, arg6, arg7);
}

public void fillSystem(World w,BlockPos pos, EnumFacing side) {

 if(side == EnumFacing.UP) {

  BlockPos currentBlockPos = new BlockPos(pos.getX(),pos.getY()+1,pos.getZ());

  if(w.getBlockState(currentBlockPos.north()) == Blocks.air.getDefaultState()) {
   w.setBlockState(currentBlockPos.north(), Blocks.water.getDefaultState(), '3');
  }

  if(w.getBlockState(currentBlockPos.south()) == Blocks.air.getDefaultState()) {
   w.setBlockState(currentBlockPos.south(), Blocks.water.getDefaultState(), '3');
  }

  if(w.getBlockState(currentBlockPos.west()) == Blocks.air.getDefaultState()) {
   w.setBlockState(currentBlockPos.west(), Blocks.water.getDefaultState(), '3');
  }

  if(w.getBlockState(currentBlockPos.east()) == Blocks.air.getDefaultState()) {
   w.setBlockState(currentBlockPos.east(), Blocks.water.getDefaultState(), '3');
  }
 }
}

Ce code fonctionne sans aucun problème, voici ce que ça donne en jeu :

C’est bien beau tout ça, mais je dois maintenant faire en sorte que l’algo remplisse tout le trou, et pour cela je dois le rendre plus complexe :


#Language Algo

posBlocCliqué = blocCliqué.position

Nombre blockY = blocCliqué.Y + 1;

Nombre blockX = blocCliqué.X

Nombre blockZ = blockCliqué.Z

blocPasVideNord = OUI

blocPasVideSud = OUI

blocPasVideEst = OUI

blocPasVideOuest = OUI

# Vérification Est

TANT QUE blocPasVideEst :

blockX++

posBlocVerifie = blockX, blockY, blockZ

SI posBlocVerifie EST de type AIR
 ALORS placerBloc(posBlocVerifie, eau)
SINON
 blocPasVideEst = NON

# Vérification Ouest

TANT QUE blocPasVideOuest :

blockX–

posBlocVerifie = blockX, blockY, blockZ

SI posBlocVerifie EST de type AIR
 ALORS placerBloc(posBlocVerifie, eau)
SINON
 blocPasVideOuest = NON

# Vérification Sud

TANT QUE blocPasVideSud :

blockZ++

posBlocVerifie = blockX, blockY, blockZ

SI posBlocVerifie EST de type AIR

 ALORS placerBloc(posBlocVerifie, eau)

SINON
 blocPasVideSud = NON

# Vérification Nord

TANT QUE blocPasVideNord :

blockZ–

posBlocVerifie = blockX, blockY, blockZ

SI posBlocVerifie EST de type AIR

 ALORS placerBloc(posBlocVerifie, eau)

SINON
 blocPasVideNord = NON

Et le code Java :


public void fillSystem(World w,BlockPos pos, EnumFacing side) {

if(side == EnumFacing.UP) {

Integer blockX = pos.getX();

Integer blockY = pos.getY() + 1;

Integer blockZ = pos.getZ();

Boolean NorthBlockNotEmpty = true;

Boolean SouthBlockNotEmpty = true;

Boolean EastBlockNotEmpty = true;

Boolean WestBlockNotEmpty = true;

//EAST CHECK

 while(EastBlockNotEmpty) {

 blockX++;

 BlockPos checkedBlock = new BlockPos(blockX,blockY,blockZ);

 System.out.println("Checking for block at : " + blockX + ", " + blockY + ", " + blockZ +" with Blockstate : " + w.getBlockState(new BlockPos(blockX,blockY,blockZ)));

 if(w.getBlockState(checkedBlock) == Blocks.air.getDefaultState()) {
 w.setBlockState(checkedBlock, Blocks.water.getDefaultState(), '3');
 }

 else {
 EastBlockNotEmpty = false;
 }
 }

blockX = pos.getX();

//WEST CHECK

 while(WestBlockNotEmpty) {

 blockX–;

 BlockPos checkedBlock = new BlockPos(blockX,blockY,blockZ);

 System.out.println("Checking for block at : " + blockX + ", " + blockY + ", " + blockZ +" with Blockstate : " + w.getBlockState(new BlockPos(blockX,blockY,blockZ)));

 if(w.getBlockState(checkedBlock) == Blocks.air.getDefaultState()) {
 w.setBlockState(checkedBlock, Blocks.water.getDefaultState(), '3');
 }

 else {
 WestBlockNotEmpty = false;
 }
 }

blockX = pos.getX();

//SOUTH CHECK

 while(SouthBlockNotEmpty) {

 blockZ++;

 BlockPos checkedBlock = new BlockPos(blockX,blockY,blockZ);

 System.out.println("Checking for block at : " + blockX + ", " + blockY + ", " + blockZ +" with Blockstate : " + w.getBlockState(new BlockPos(blockX,blockY,blockZ)));

 if(w.getBlockState(checkedBlock) == Blocks.air.getDefaultState()) {
 w.setBlockState(checkedBlock, Blocks.water.getDefaultState(), '3');
 }

 else {
 SouthBlockNotEmpty = false;
 }
 }

blockZ = pos.getZ();

//NORTH CHECK

 while(NorthBlockNotEmpty) {

 blockZ--;

 BlockPos checkedBlock = new BlockPos(blockX,blockY,blockZ);

 System.out.println("Checking for block at : " + blockX + ", " + blockY + ", " + blockZ +" with Blockstate : " + w.getBlockState(new BlockPos(blockX,blockY,blockZ)));

 if(w.getBlockState(checkedBlock) == Blocks.air.getDefaultState()) {
 w.setBlockState(checkedBlock, Blocks.water.getDefaultState(), '3');
 }

 else {
 NorthBlockNotEmpty = false;
 }
 }

 System.out.println("DEBUG: Filling done");

}

}

Et le résultat en jeu :

Maintenant ma question c’est comment faire pour remplir TOUS les trous, et pas seulement ceux en forme de croix …
Je pense qu’il s’agit d’un bon défi pour cette communauté et que cela pourrait être utile pour quelqu’un ^^

Squix

DiabolicaTrix

Je crois que la meilleure façon serait de vérifier chaque bloc qui est placé, tu places le premier bloc, et tu vérifies le nord/sud/est/ouest. Ensuite, pour chacun de ces blocs, tu fais la même chose jusqu’à ce qu’il n’y ait plus de blocs.

Squix

@‘DiabolicaTrix’:

Je crois que la meilleure façon serait de vérifier chaque bloc qui est placé, tu places le premier bloc, et tu vérifies le nord/sud/est/ouest. Ensuite, pour chacun de ces blocs, tu fais la même chose jusqu’à ce qu’il n’y ait plus de blocs.

C’est aussi ce à quoi j’ai pensé mais je ne vois pas comment le mettre en oeuvre niveau code. Aurais tu un exemple ?

robin4002

Il suffit de faire une fonction récursive qui check si le bloc est de l’air, si oui tu mets de l’eau puis la fonction s’appelle elle même pour x + 1, x - 1, z + 1 et z - 1.
(uniquement dans le cas ou tu viens de remplacer de l’air par de l’eau, pas dans tous les cas ! sinon tu vas te retrouver avec un stackoverflow).

RedRelay

@‘robin4002’:

Il suffit de faire une fonction récursive qui check si le bloc est de l’air, si oui tu mets de l’eau puis la fonction s’appelle elle même pour x + 1, x - 1, z + 1 et z - 1.
(uniquement dans le cas ou tu viens de remplacer de l’air par de l’eau, pas dans tous les cas ! sinon tu vas te retrouver avec un stackoverflow).

Tu risques le stackoverflow même si tu ne remplace que l’air par l’eau.
Dans ce genre d’algo en Java il vaut mieux utiliser une boucle ou utiliser le pattern visitor

Mokona78

1 - Initialiser un HashSet de BlockPos avec la position de départ
2 - Tant qu’il y a des éléments dans le HashSet
2.1 - Prendre un élément de HashSet qui devient l’élément courant (un BlockPos)
2.2 - L’effacer du HashSet
2.3 - Ajouter au HashSet tous les voisins valides (voir plus loin) de l’élément courant
2.4 - Faire l’action à partir de l’élément courant (ici ajouter l’eau)
2.5 - Fin de la boucle, retour en 2.
3 - Fini

Voisins Valides

Tous les voisins dans les directions voulues (4 voisins directs et celui du dessous a priori)
et qui contiennent du vide.

Notes :

Concernant le container, le Set (ici HashSet) permet d’éviter les doublons sans avec à faire de test, mais l’interface n’est pas faite pour accéder à un seul élément (c’est faisable, mais pas très beau). On peut remplacer par un Vector (éventuellement décoré en Pile), accéder aux éléments est plus facile, on peut le faire dans l’ordre, c’est plus compact en mémoire, mais il faut tester les doublons soit même (donc beaucoup de parcours de vector, pas top).

Ou alors se lancer dans une structure qui allie les deux (ou en trouver une quelque part).

En raffinement, les voisins déjà parcourus peuvent être mis en cache. À tester pour voir si c’est plus rapide.___Sinon, à propos de “w.setBlockState(checkedBlock, Blocks.water.getDefaultState(), ‘3’);”, ça ne te râle pas dessus ?

Le ‘3’ est censé être un int, non ? (enfin en 1.9 en tout cas. Où c’est aussi la valeur par défaut grâce à une seconde méthode sans le troisième argument et où il est donc inutile de spécifier 3).

RedRelay

@‘Mokona78’:

1 - Initialiser un HashSet de BlockPos avec la position de départ
2 - Tant qu’il y a des éléments dans le HashSet
2.1 - Prendre un élément de HashSet qui devient l’élément courant (un BlockPos)
2.2 - L’effacer du HashSet
2.3 - Ajouter au HashSet tous les voisins valides (voir plus loin) de l’élément courant
2.4 - Faire l’action à partir de l’élément courant (ici ajouter l’eau)
2.5 - Fin de la boucle, retour en 2.
3 - Fini

Voisins Valides

Tous les voisins dans les directions voulues (4 voisins directs et celui du dessous a priori)

et qui contiennent du vide.

Notes :

Concernant le container, le Set (ici HashSet) permet d’éviter les doublons sans avec à faire de test, mais l’interface n’est pas faite pour accéder à un seul élément (c’est faisable, mais pas très beau). On peut remplacer par un Vector (éventuellement décoré en Pile), accéder aux éléments est plus facile, on peut le faire dans l’ordre, c’est plus compact en mémoire, mais il faut tester les doublons soit même (donc beaucoup de parcours de vector, pas top).

Ou alors se lancer dans une structure qui allie les deux (ou en trouver une quelque part).

En raffinement, les voisins déjà parcourus peuvent être mis en cache. À tester pour voir si c’est plus rapide.

Sinon, à propos de “w.setBlockState(checkedBlock, Blocks.water.getDefaultState(), ‘3’);”, ça ne te râle pas dessus ?

Le ‘3’ est censé être un int, non ? (enfin en 1.9 en tout cas. Où c’est aussi la valeur par défaut grâce à une seconde méthode sans le troisième argument et où il est donc inutile de spécifier 3).

J’utiliserai 2 hashsets de BlockPos.

1 - Initialiser le HashSet 1
2 - Initialiser le HashSet 2
3 - Ajouter la position de départ dans le HashSet 1
4 - Pour tout les éléments du HashSet 1
4.1 - Effectuer l’action sur l’élément du HashSet 1
(– Si on utilise un cache :
4.2 - Pour tout les voisins (excepté le block du haut) de l’élément du HashSet 1
4.2.1 - Si le voisin n’est pas dans le HashSet 1, on l’ajoute dans le HashSet 2
– Si on n’utilise pas de cache :
4.2 - On ajoute tout les voisins valides de l’élément du HashSet 1 dans le HashSet 2
– )
4.3 - On permute HashSet 1 et HashSet 2
4.4 - On vide HashSet 2
5 - Fini

J’ai pas testé, c’est une idée a la volé que j’imagine sur le tas et il est 4h du matin.
Il y a peut-être des erreurs absurdes ^^

robin4002

@‘RedRelay’:

Tu risques le stackoverflow même si tu ne remplace que l’air par l’eau.

Ah oui en effet je n’y avais plus pensé, si la zone à remplir est très grande la JVM ne va pas aimer.

SCAREX

T’es sûr que ton code fonctionne ? De ce que je vois tu ne l’exécutes uniquement côté client donc essaie de mettre à jour le block

Mokona78

Du coup, tu t’en es sorti ?

Squix

Pour l’instant je n’ai pas vraiment le temps de dév, mais je vous tient au courant ^^

Jodge

Hum…

Assez intéressant comme question… Le principe de la fonction récursive est la bonne, mais il faut pensé à ajouter des limites :

nombre maximum d’appel pour évité l’érreur stack overflow
distance max pour évité de remplir une seul ligne, mais une zone entière (ex : limite de 5000 blocks, distance max = racine(5000) pour pouvoir remplir, le cas échant, le carré complet et non une ligne de 5000 blocks).

Ça m’as intrigué, et je me suis demandé comment réagissant minecraft au multi-thread.
A mon grand regret, cela fonctionne mal. Il semble que Minecraft ne fasse fonctionner qu’un thread à la fois, ce qui fige le jeu pendant le processus.
(s’il pouvais exécuté plusieurs thread, il aurai pus remplir une zone d’eau théoriquement infinis en démarrant un nouveau Threadh tous les 1000-2000 block, et donc ne pas avoir d’erreur sur la durée, tous en évitant le freeze)

Néanmoins, en appliquant le principe de MultiThread, j’ai créer une class qui peut théoriquement remplir des zones de 100 x 100 sans planté (je dis bien théoriquement, j’ai pas fait de test précis).

Comme chaque Thread créer sont propre carré, java ne plante pas sur une boucle infinis lorsque l’on atteins les 10 000 itérations.
C’est encore modifiable (démarré de façon consécutive un nouveau Thread pour agrandir la zone, sans jamais dépasser les 50*50 par Thread), c’est certainement améliorable & optimisable, mais si ça peut t’aider ou te servir de base :

package com.example.examplemod;

import net.minecraft.block.Block;
import net.minecraft.init.Blocks;
import net.minecraft.util.EnumFacing;
import net.minecraft.world.World;

public class RecursifExample
{

public static void fill(World world, int xOrigine, int yOrigine, int zOrigine, int limit, Block water, Block air)
{
ThreadRecursif fillerNorth = new ThreadRecursif(world, xOrigine, yOrigine, zOrigine, limit, water, air, EnumFacing.NORTH);
ThreadRecursif fillerSouth = new ThreadRecursif(world, xOrigine, yOrigine, zOrigine, limit, water, air, EnumFacing.SOUTH);
ThreadRecursif fillerEast = new ThreadRecursif(world, xOrigine, yOrigine, zOrigine, limit, water, air, EnumFacing.EAST);
ThreadRecursif fillerWest = new ThreadRecursif(world, xOrigine, yOrigine, zOrigine, limit, water, air, EnumFacing.WEST);
}
public  static void fill(World world, int xOrigine, int yOrigine, int zOrigine, int limit, Block water)
{
fill(world, xOrigine, yOrigine, zOrigine, limit, water, Blocks.air);
}
public  static void fill(World world, int xOrigine, int yOrigine, int zOrigine, int limit)
{
fill(world, xOrigine, yOrigine, zOrigine, limit, Blocks.water);
}
public  static void fill(World world, int xOrigine, int yOrigine, int zOrigine)
{
fill(world, xOrigine, yOrigine, zOrigine, 2500); // limit of block per thread
}

public static class ThreadRecursif extends Thread
{
int xOrigine;
int yOrigine;
int zOrigine;

int limitSize;
int limit;
int actual;

Block air;
Block water;

EnumFacing direction;

World world;

public ThreadRecursif(World world, int xOrigine, int yOrigine, int zOrigine, int limit, Block water, Block air, EnumFacing direction)
{
this.world = world;

this.xOrigine = xOrigine;
this.yOrigine = yOrigine;
this.zOrigine = zOrigine;

this.limit = limit;
this.actual = 0;
this.limitSize = (int)Math.sqrt(limit); // 2500 = 50²

this.air = air;
this.water = water;

this.direction = direction;

start();
}

public void start()
{
updateOrigineBlock(xOrigine, yOrigine, zOrigine);
}

public boolean swapBlock(int x, int y, int z)
{
if( Math.abs(xOrigine - x) < limitSize && Math.abs(zOrigine - z) < limitSize)
{
if(world.getBlock(x, y, z) == air)
{
world.setBlock(x, y, z, water);
return true;
}
}
return false;
}

public void updateOrigineBlock(int x, int y, int z)
{
swapBlock(x, y, z);
switch(direction)
{
case NORTH:
updateBlock(x, y, z - 1);
break;
case SOUTH:
updateBlock(x, y, z + 1);
break;
case EAST:
updateBlock(x + 1, y, z);
break;
case WEST:
updateBlock(x - 1, y, z);
break;
default:
break;
}
}

public void updateBlock(int x, int y, int z)
{
if(actual < limit)
{
if(swapBlock(x, y, z))
{
actual++;
this.yield();
switch(direction)
{
case NORTH:
updateBlock(x, y, z - 1);
updateBlock(x - 1, y, z);
break;
case SOUTH:
updateBlock(x, y, z + 1);
updateBlock(x + 1, y, z);
break;
case EAST:
updateBlock(x + 1, y, z);
updateBlock(x, y, z - 1);
break;
case WEST:
updateBlock(x - 1, y, z);
updateBlock(x, y, z + 1);
break;
default:
break;
}

// final check (use for fill block never checked cause of rotation)
updateBlock(x, y, z - 1);
updateBlock(x - 1, y, z);
updateBlock(x, y, z + 1);
updateBlock(x + 1, y, z);

} // block can't be replace
}
else // we reach limit for this thread, so we launch one again
{
// not a good idea to start a new thread without security
//ThreadRecursif newFiller = new ThreadRecursif(world, xOrigine, yOrigine, zOrigine, limit, water, air, direction);
}

} // end of Update
} // end of Thread

}

Mokona78

Hello,

je prédis à cet algorithme une vie très brève. Comme tu as pu le voir, Minecraft n’est pas thread safe. Modifier le contenu d’un chunk pendant que le thread principal de Minecraft est en train de les mettre à jour puis de faire le rendu, ça peut, au choix, corrompre le monde, ou tout simplement crasher.

Autre potentiel problème, si l’on imagine qu’on passe à travers les mailles du filet et que par chance, ça fonctionne. Si le remplissage se fait durant plusieurs update, alors l’eau va commencer à s’étendre et remplir l’air. Le remplissage sera alors incomplet.

Pour ce second problème, c’est assez simple à corriger : il ne faut pas chercher que les blocks d’air, mais aussi les blocks d’eau non générateurs.

Pour le remplissage en parallèle, en y réfléchissant un peu je vois deux méthodes. La première, sans thread, basé sur mon précédent algorithme proposé, est de, à chaque update, ne mettre à jour qu’un nombre limité de blocks. À faire dans le main thread bien entendu. Mon précédent algorithme se prête bien à ça. Un algorithme récursif beaucoup moins bien.

Une seconde méthode, qui peut ou peut ne pas être plus efficace (il faut tester), est de, à chaque update, dupliquer l’information nécessaire d’un certain nombre de chunks (seules les positions et l’état du block nous intéressent). Puis lancer un thread qui va travailler sur cette copie et générer une liste de modifications à apporter au monde (une liste de BlockPos par exemple).

Lors d’un update de monde, dans le thread principal, on vérifie si le traitement est terminé. S’il l’est, on applique la liste des modifications bêtement.

C’est scalable avec plusieurs chunks par plusieurs threads. Il est possible aussi, pour éviter le coût des threads, d’utiliser des workers… Mais là, ma connaissance du monde Java ne me permet pas de dire ce qui est le plus efficace. Il faudrait sortir un profiler et vérifier.

En résumé : la parallélisation est possible, mais une fois dans un thread, accéder à une structure mutable de Minecraft est une erreur.

Folgansky

Il y a des mods ou plugins qui existent et qui évitent de générer une structure d’un seul coup (je pense à schematica) mais de le faire par paquets de 1000 ou 2000 blocs, ce qui se fait doucement mais sûrement.

Un schematic d’un million de blocs ne fait plus freeze pendant 10minutesle temps que tout soit paste mais le paste dure 10minutes, petit à petit.

Désolé de ne donner qu’un avis d’amateur ^^

Jodge

@Mokona78 : J’ai pas cherché à ajouté quelconque sécurité, je voulais plutôt testé le fonctionnements en multi thread (voir si il y avais moyen de parallélisé des actions). Sur Eclipse (j’ai testé que dans un environnement de développement), le jeux se freeze, et un seul thread fonctionne à la fois (Thread principal inclus). Du coup, l’intérêt du multi thread est réduit à néant, donc j’ai pas cherché à continué…
Le bout de code que j’ai donné peu servir pour extraire le code final de l’algo récursif de remplissage. Ou données des idées stupides à certain x)

Une autre solution à laqu’elle je pensai est de créer un block fantôme. Lorsque se block est update (à voir pour forcer un update), il place un autre block similaire à lui sur tout les coté possible, puis se remplace par un block d’eau. Cette solution à l’avantage de ne pas avoir de limitation sur les boucles, mais nécessite un block temporaire, un update forcé des blocks, et sans doute des protections pour les chunck non chargé…

Mokona78

Ah oui ça peut donner un bel effet visuel en plus avec le bloc spécial bien choisi.