Puis-je dessiner étape par étape mon retour en arrière en utilisant Processing?

D'après la documentation :

Lors de la structuration d'un programme, il est logique d'appeler redraw () dans événements tels que mousePressed (). C'est parce que redraw () ne s'exécute pas draw () immédiatement (il définit uniquement un drapeau indiquant qu'une mise à jour est nécessaire).

Redraw ne fait pas dessiner l'écran. Il définit un drapeau qui doit être appelé draw (), ce qui se produit à la fin de la boucle. Une solution consiste à renommer draw () en drawScreen () et à l'appeler au lieu de redraw () .

La façon dont il est avec le traitement, c'est que vous simulez des boucles en tournant la fonction draw vers le corps de cette boucle et effectuez toute l'initialisation dans la fonction setup .

p> Pour simuler une récursion, vous pouvez la transformer en boucle puis faire ce qui précède, généralement cela peut être fait en utilisant une pile et vous remplacez essentiellement la pile du système par la vôtre; J'ai fait quelques lectures (consultez cette question pour quelques réflexions) et J'ai trouvé qu'il serait très facile de transformer la récursion en boucle avec une pile si l'appel récursif est à la fin du corps de la fonction.

Maintenant, le problème ici, c'est que vous avez du code après l'appel récursif qui devrait être exécuté après le retour de l'appel, mais en y regardant, il s'agit simplement de annuler les modifications apportées aux variables globales, nous pouvons surmonter cela si nous considérons ces variables comme une partie de l'état (pas très efficace et ne sera pas bien mis à l'échelle, mais dans votre cas, il le fera) donc la partie undo ne sera pas nécessaire et l'appel récursif sera la dernière chose dans la fonction body (laissons la boucle for interne pour le moment).

Pour ce faire, j'ai défini une classe appelée State et c'est comme suit ..

import java.util.Stack;

final int GRID_SIZE = 8;
float cellH, cellW;
PImage img;

Stack<State> stack;

void setup() {
  size(500, 500);
  frameRate(5);

  cellH = (float) height / GRID_SIZE;
  cellW = (float) width / GRID_SIZE;

  img = loadImage("queen.png");

  stack = new Stack<State>();
  State state = new State();
  state.r = -1;
  state.c = -1;
  stack.push(state);

  noLoop();

}

void draw() {
  // stop if the stack is empty
  if (stack.size() == 0) {
    noLoop();
    return;
  }

  State current = stack.pop();
  drawGrid(current);

  // stop when a solution is found
  if (current.r == GRID_SIZE - 1) {
    noLoop();
    return;
  }

  for (int c = GRID_SIZE - 1; c >= 0; --c) {
    State next = new State(current);

    if (!next.isValid(current.r+1, c)) continue;
    next.c = c;
    next.r = current.r + 1;
    next.affect();

    stack.push(next);
  }

}

void drawGrid(State state) {
  float cellH = height / GRID_SIZE;
  float cellW = width / GRID_SIZE;

  background(255);
  for (int r = 0; r < GRID_SIZE; ++r) {
    for (int c = 0; c < GRID_SIZE; ++c) {
      if ((r&1) != (c&1)) fill(0);
      else  fill(255);
      rect(c*cellW, r*cellH, (c+1)*cellW, (r+1)*cellH);
    }
  }

  PVector pos[] = state.getPositions();
  for (PVector vec : pos) {
    image(img, vec.x * cellW + cellW * 0.1, vec.y * cellH + cellH * 0.1, cellW * 0.8, cellH * 0.8);
  }
}

// to resume the search after a solution is found
void keyPressed() {
  if (key == ' ') loop();
}

il contient tout ce qui serait nécessaire pour représenter l'état de cette récursivité, maintenant le code ressemblerait à quelque chose comme ..

stack.push(initialState);
while(stack.size() != 0) {
    State currentState = stack.pop();
    // do stuff ...
    stack.push(nextState);
}

Nous pouvons considérer le corps de la fonction draw comme le corps de cette boucle while et utilisez noLoop () pour l'arrêter lorsque la pile est vide, ainsi le code final serait quelque chose comme ..

    class State {
      private final int SIZE = 8;
      private boolean grid[][], visC[], visR[], visMD[], visSD[];

      int r, c;

      State() {
        visC = new boolean[SIZE];
        visR = new boolean[SIZE];
        visMD = new boolean[2*SIZE];
        visSD = new boolean[2*SIZE];
        grid = new boolean[SIZE][SIZE];
      }

      State(State other) {
        this();
        cpyArr(other.visMD, this.visMD);
        cpyArr(other.visSD, this.visSD);
        cpyArr(other.visC, this.visC);
        cpyArr(other.visR, this.visR);

        for (int i = 0 ; i < other.grid.length ; ++i)
          for (int j = 0 ; j < other.grid[i].length ; ++j)
            this.grid[i][j] = other.grid[i][j];

        this.r = other.r;
        this.c = other.c;
      }

      void cpyArr(boolean from[], boolean to[]) {
        for (int i = 0 ; i < from.length ; ++i) to[i] = from[i];
      }

      boolean isValid(int r, int c) {
        return (r < SIZE && c < SIZE && !visR[r] && !visC[c] && !visMD[SIZE + r - c] && !visSD[r + c]);
      }

      // actually update this sate with r and c
      void affect() {
        grid[r][c] = visC[c] = visMD[SIZE + r - c] = visSD[r + c] = true;
      }

      PVector[] getPositions() {
        ArrayList<PVector> ret = new ArrayList<PVector>();
        for (int i = 0; i < SIZE; ++i)
          for (int j = 0; j < SIZE; ++j)
            if (grid[i][j]) ret.add(new PVector(j, i));
        return ret.toArray(new PVector[0]);
      }
    }

Notez que partie de la boucle for interne que nous avons laissée pour plus tard, elle est inversée donc le premier état à exécuter est le même que le premier état que le retour en arrière aurait exploré.

Maintenant, mettez une belle image pour la ressource queen.png dans le fichier de données, le résultat est très joli ...

J'ai essayé de le résoudre en utilisant un Thread et cela m'a donné un excellent résultat, alors voici mon code:

int cellH = 38, cellW = 38, n = 8;
PImage img;
boolean [][] grid;
boolean [] visC, visMD, visSD;
boolean firstTime = true;

Thread thread;

void setup(){
  size(560, 560);
  cellH = 560/n;
  cellW = 560/n;

  grid = new boolean[n][n];
  visC = new boolean[n];
  visMD = new boolean[2*n];
  visSD = new boolean[2*n];
  img = loadImage("queen.png");
  thread = new Thread(new MyThread());

  thread.start();
}

void draw(){
  if(thread.isAlive())
    drawGrid();
  else{
    noLoop();
    endRecord();
    return;
  }
}

void drawGrid(){
  background(255);
  for(int r = 0 ; r < n ; ++r){
   for(int c = 0 ; c < n ; ++c){
     if((r&1) != (c&1)) fill(0);
     else  fill(255);
     rect(c*cellW, r*cellH, (c+1)*cellW, (r+1)*cellH);
     if(grid[r][c] == true)
       image(img, c*cellW, r*cellH, cellW, cellH);
   }
  }
}

boolean backTrack(int r){
  if(r == n)  return true;
  else{
    for(int c = 0 ; c < n ; ++c){
      if(!visC[c] && !visMD[n+r-c] && !visSD[r+c]){
        //Do
        grid[r][c] = visC[c] = visMD[n+r-c] = visSD[r+c] = true;

        try{
          Thread.sleep(200);
        }catch(InterruptedException e){System.out.println(e);}  

        //Recurse
        if(backTrack(r+1))  return true;
        //Undo
        grid[r][c] = visC[c] = visMD[n+r-c] = visSD[r+c] = false;

        try{
          Thread.sleep(200);
        }catch(InterruptedException e){System.out.println(e);}
      }
    }
  }
  return false;
}

class MyThread implements Runnable{    
  public void run(){    
    backTrack(0);    
  }
}  

Et voici le résultat: p >