/* 
  Pràctica de PS Quadrimestre Tardor 2004-2005 <EDAMAZE>
  Autors:
          Daniel Clemente Laboreo <www.danielclemente.com>
          Francesc Xavier Morales Pascual <www.xavimorales.biz>
*/

// dedalus.cpp: construcció de laberints perfectes


#include "particio.hpp"
#include "dedalus.hpp"

/************ COMENTARI DE LA FUNCIÓ CONSTRUIR ***********************
  Per aconseguir l'excavació del laberint fins a obtenir-ne un de perfecte usem l'algorisme de Kruskal, 
  el qual serveix realment per obtenir un "arbre de recorregut mínim" per a un graf. Aquest algorisme és 
  apropiat per al que volem fer perquè uneix els vertex del graf de forma que no es formin cicles i cerca 
  el camí que té un cost més baix. Aquesta última part no ens interesa molt ja que tenim cost igual per a
  totes les portes, però és molt útil per a aconseguir un laberint perfecte.
  L'algorisme consisteix en tenir un bosc d'arbres, inicialment de n arbres (tants com vertex), i que a cada pas
  n'uneix dos d'aquests arbres, de forma que aquests queden units en el mateix grup. En cas que estiguessin 
  en el mateix arbre seria innecessari agrupar-los i per tant no els uneix evitant cicles.
  Bàsicament l'algorisme funciona així:
    1. Es construeix el bosc amb cada node en un arbre separat
    2. Fins que no hem afegit n-1 vertex agafem un de la cua, el que té menys cost. Si forma un cicle el rebutjem i sinó llavors l'afegim
    
  L'algorisme acaba quan ja tenim tots els nodes units a UN sol arbre.
  
  Podem aplicar aquest sistema en el nostre laberint. El nostre bosc serà una partició de cambres, 
  però per poder-les distingir unes de les altres ens basarem en la seva posició al laberint, creant
  una partició de posicions. L'iniciarem amb totes les posicions formant grups independents i de forma 
  aleatoria buscarem una cambra i un sentit en el que obrir la porta. Mirarem si les dues cambres 
  adjacents formen part del mateix grup i en cas negatiu unirem els dos grups a la vegada que obrim 
  una porta al laberint entre les cambres. Fet això, repetim el procés fins que ens queda un sol grup.
***********************************************************************/

void dedalus::construir(laberint& M) throw(error) {
  // Construim un laberint perfecte si no està encara excavat
  nat i, j;
  nat nfiles, ncolum;
  cambra tancada;
  posicio actual, contigu;

  // creem una partició de posicions amb la que treballem per saber si podem unir dues cambres i si hem acabat
  particio<posicio> parts;
  util::Random r;
  paret p;
  tancada = cambra(0,0,0,0); // la utilitzarem per comparar les cambres del laberint amb la que té totes les portes tancades (aquesta)

  nfiles = M.num_files();
  ncolum = M.num_columnes();

  //comprovem que totes les cambres estan tancades, recordem que la primera posició és la <1,1>
  for(i=1;i<=nfiles;++i) {
    for(j=1;j<=ncolum;++j) {
      if(tancada!=M(make_pair(i,j)))
        throw error(nom_mod, EstaExcavat, MsgEstaExcavat);
    }
  }

  // afegim cada cambra (representada per la seva posició) com a un grup separat de la partició
  for(i=1;i<=nfiles;++i) {
    for(j=1;j<=ncolum;++j) {
      parts.afegir(make_pair(i,j));

    }
  }

  // mentre tinguem més d'un grup a la partició hem de seguir unint, perquè significa que encara no hem unit totes les cambres
  while (parts.size() >1) {

    //obtenim un valor aleatori de fila i un altre de columna
    i = (nat)((double)nfiles*r())+1;
    j = (nat)((double)ncolum*r())+1;
    actual = make_pair(i,j);

    //obtenim una paret aleatòria
    p = paret((int)(4*r()));

    //calculem els índex de la cambra adjacent a aquesta paret
    switch((int)p) {
    case paret::NORD:
      --i;
      break;
    case paret::EST:
      ++j;
      break;
    case paret::SUD:
      ++i;
      break;
    case paret::OEST:
      --j;
      break;
    }


    // Si la cambra contígua està fora del laberint (hem intentat obrir una paret exterior) provem amb una nova cambra
    if( i<1 || i>nfiles || j<1 || j>ncolum )
      continue;

    contigu = make_pair(i,j);

    //Si tenen representants diferents significa que podem obrir la porta sense por a crear un cicle
    if (parts.representant(actual)!=parts.representant(contigu)) {
      parts.unir(actual,contigu);
      M.obre_porta(p,actual);
    }
  } // Fi del while

  // Laberint excavat i perfecte
}