"Route-finding" - Processing

ID	Autor	Duplicat din	Ultima modificare
`#3929`	Steopoaie Vlad (Hefa)	-	Miercuri, 27 mai 2020, 10:47
                          /*******************
                       Fa click pe un patratel alb
                          *******************/

class Queue{
   constructor(){
     this.front = 0;
     this.back = 0;
     this.storage = {};
   }
  
  Push(element){
    this.storage[this.back++] = element;
  }
  
  Front(h){
    if(h === "x")
      return this.storage[this.front].x;
    else
      return this.storage[this.front].y;
  }
  
  Empty(){
    if(this.front === this.back)
      return true;
    else
      return false;
  }
  
  Pop(){
    this.front++;
  }
}

//valori pentru start si finish
var is = 1, js = 1, ix = 1, jx = 1;
var speed = 5;
//elementele elipsei
var ellipseX, ellipseY, elSize;

//matricea care se va desena
var grid = [
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1],
    [ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,1, 0, 0, 0, 1, 0, 1, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,1, 1, 1, 0, 1, 0, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0,1, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0,1, 1, 1, 0, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0,0, 0, 1, 0, 1, 0, 0, 0, 1, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0,1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1],
    [ 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,0, 0, 1, 0, 0, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0,1, 1, 1, 0, 1, 1, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0,1, 0, 0, 0, 0, 0, 1, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,0, 0, 1, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,1, 1, 1, 1, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,0, 0, 1, 0, 0, 0, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0,0, 0, 0, 0, 1, 0, 0, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,1, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1],
    [ 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,1, 0, 0, 0, 0, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0,1, 0, 1, 0, 1, 0, 1, 0, 1, 1,1],
    [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0,1, 0, 1, 0, 1, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,1, 1, 1, 1, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,0, 0, 0, 0, 1, 0, 0, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1,1, 1, 1, 1, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1],

];

//matricea in care se face algoritmul
var Alee = [
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1],
    [ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,1, 0, 0, 0, 1, 0, 1, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,1, 1, 1, 0, 1, 0, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0,1, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0,1, 1, 1, 0, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0,0, 0, 1, 0, 1, 0, 0, 0, 1, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0,1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1],
    [ 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,0, 0, 1, 0, 0, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0,1, 1, 1, 0, 1, 1, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0,1, 0, 0, 0, 0, 0, 1, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,0, 0, 1, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,1, 1, 1, 1, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,0, 0, 1, 0, 0, 0, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0,0, 0, 0, 0, 1, 0, 0, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,1, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1],
    [ 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,1, 0, 0, 0, 0, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0,1, 0, 1, 0, 1, 0, 1, 0, 1, 1,1],
    [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0,1, 0, 1, 0, 1, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,1, 1, 1, 1, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,0, 0, 0, 0, 1, 0, 0, 0, 1, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1,1, 1, 1, 0, 1, 1, 1, 0, 1, 0,1],
    [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 1, 0, 0, 0,1],
    [ 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1,1, 1, 1, 1, 1, 0, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 0,1],
    [ 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,1],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1],

];

var n = 31, m = 31;

var di = [1, -1, 0, 0], dj = [0 ,0, -1, 1];

var distW, distH;

function setup(){
  createCanvas(410, 410);
  //setez matricea cu valori mai mici decat zero ex: -3
  for(let i = 0; i < n; i++)
    for(let j = 0; j < m; j++)
        Alee[i][j] = -3 * Alee[i][j];
  //dimensiunile patratelelor desenate
  distW = (width - 40) / n;
  distH = (height - 40) / m;
  
  elSize = width / (n / 0.5);
  ellipseY = height / 13.8 + distH * (is - 1);
  ellipseX = width / 13.8 + distW * (js - 1);
  noStroke();
}

//verifica daca i si j sunt in matrice
function Inside(i, j)
{
  return i >= 0 && i < n && j >= 0 && j < m;
}


// deseneaza X
function DrawX(x, y)
{
  stroke("red");
  strokeWeight(width / 160);
  line(x + width / 160, y + height / 160, x + distW - width / 160, y + distH  - height / 160);
  line(x + width / 160, y + distH - height / 160, x + distW - width / 160, y + height / 160);
  noStroke();
}

//algoritmul suprem
function Lee(is, js){
    
    var Q = new Queue();
    Q.Push(createVector(is, js));
    Alee[is][js] = 1;
    while(!Q.Empty())
    {
      let i = Q.Front("x");
      let j = Q.Front("y");
      for(let k = 0; k < 4; k ++){
        let iv = i + di[k]; 
        let jv = j + dj[k];
        if(Inside(iv, jv) && Alee[iv][jv] === 0)
        {
          Q.Push(createVector(iv, jv));
          Alee[iv][jv] = Alee[i][j] + 1;
        }
      }
      Q.Pop();
    }
}



draw = function(){
    background("black");
    //gridul
    for(let i = 0; i < n; i++){
       for(let j = 0; j < m; j++){
           if(grid[i][j] === 1){
             fill(120, 120, 120);
           }
           else
           {
             fill(255, 255, 255);
           }
           rect(width / 40 + distW * j, height / 40 + distH * i, distW, distH);
         if(grid[i][j] === "x")
         {
             DrawX(width / 40 + distW * j, height / 40 + distH * i);
         }
    }
    }
  
  //eilipsa
  fill("red");
  ellipse(ellipseX, ellipseY, elSize, elSize); 
  
  //tin minte in ce parte merg ajutandu-ma de variabilele urmatoare
  var inci = 0, incj = 0;
  for(let k = 0; k < 4; k ++)
  {
    let i = is + di[k];
    let j = js + dj[k];
    //verific vecinii (cel care e cu o unitate mai mic este cel corect)
    if(Inside(i, j) && Alee[is][js] === Alee[i][j] + 1)
    {
      inci = di[k];
      incj = dj[k];
      break;
    }
  }
    //daca pozitia elipsei este mai "mica" decat patratelul vecin fac un pas ori viteza
    //daca una din variabile contine 1 sau -1 cealalta este 0 neaparat
    //am inmultit cu variabilele in cazul can sunt negative si semnul inegalitatii trebuie schimbat
    if(ellipseX * incj  < (width / 13.8 + distW * (js - 1 + incj)) * incj || ellipseY * inci < (height / 13.8 + distH * (is - 1 + inci) )* inci)
    {
      ellipseX += incj * speed;
      ellipseY += inci * speed;
    }
    else{
      //daca conditia de sus nu e adevarata inseamna ca am ajuns la pozitia dorita 
      //deci modivic pozitia din matrice
      //sa nu uitam ca daca una din variabile contine 1 sau -1 cealalta este 0 neaparat
      is += inci;
      js += incj;
      ellipseX = width / 13.8 + distW * (js - 1);
      ellipseY = height / 13.8 + distH * (is - 1);
    }
}

function mouseClicked(){
  //fac copie la pozitile de final
  let cix = ix, cjx = jx;
  //daca mouse-ul este apasat inseamna ca pozitia X-ului se modifica
  //am notat cu "x" in matrice elementul unde trebuie desenat X si unde trebuie sa se ajunga
  grid[ix][jx] = 0;
  //parcurg matricea pe coloane si verific unde se incadreaza mouseX
  for(let j = 0; j < m; j ++){
     if(mouseX < width / 40 + distW * j)
     {
       //scad 1 deoarece coordonatele patratelor incep din partea stanga
       jx = j - 1;
       break;
     }
  }
  //analog cu cea de sous doar ca parcurg pe randuri
  for(let i = 0; i < n; i ++){
     if(mouseY < height / 40 + distH * i)
     {
       ix = i - 1;
       break;
     }
  }
  //daca valoarea de mai jos e mai mica decat 0 inseamna ca s-a facut clic pe zid
  //restabilim valoarea initiala a X-ului
  if(Alee[ix][jx] < 0)
  {
    ix = cix;
    jx = cjx;
  }
  //punem in grid pozitia in matrice a X-ului
  grid[ix][jx] = "x";
  //curatam matricea in care se face algoritmul
  for(let i = 0; i < n; i ++)
    for(let j = 0; j < m; j ++){
      if(Alee[i][j] > 0)
        Alee[i][j] = 0;
    }
  //pronim algoritmul de la punctul de finish
  Lee(ix, jx);
}