Descripción detallada de los algoritmos desarrollados - Kenichih48/Proyecto-2-Datos-2 GitHub Wiki

Se desarrollo un algoritmo que, recibiendo una matriz, calcula un camino del punto inicial hasta el punto requerido utilizando pathfinding A*. Eso se hace primero calculando los valores de H para cada uno de los elementos de la matriz, luego obteniendo la posicion incial y desde este punto calculando los valores correspondientes a G y F para los nodos adyacentes al nodo actual. Una vez calculados todos estos valores, se añaden los nodos a la lista de nodos abiertos y se mueve a la siguiente posicion la cual se agrega a los nodos cerrados, lo que se hace de forma recursiva hasta llegar al punto requerido.

void checkSurrounding(){ 
    for(int i = currentY-1; i < currentY+1;i++){
        List currentList = this->field.at(i);
        for (int j = currentX-1; i < currentX + 1; i++){
            Node currentNode = currentList.at(i);
            if(i < currentY && j != currentX ){
                currentNode.setG(14);
            } else if(i < currentY && j == currentX ){
                currentNode.setG(10);
            } else if(i == cuerrentY){
                currentNode.setG(10);
            } else if(i > currentY && j != currentX ){
                currentNode.setG(14);
            } else if(i > currentY && j == currentX ){
                currentNode.setG(10);
            }
            currentNode.setF(currentNode.getG() + currentNode.getH());
            this->openList.append(currentNode)
        }
    }
}

Utilizando backtracking, se calculaba la ruta del tiro de la computadora, utilizando la primera ruta encontrada. El algoritmo es recursivo y va lo más lejos posible en cada ruta hasta llegar a un punto de bloqueo y si ve que la ruta de fijo no llegará al final, se devolverá y probará una ruta alternativa. En resumen, probará cada ruta metódicamente hasta encontrar una que funcione. En este caso se utilizó una versión especializada del backtracking para laberintos, donde se toman los lugares que tienen jugadores como ocupados, y los demás lugares como abiertos, el marco de cada equipo.

El algoritmo inicia recibiendo la matriz del tablero, donde puede leer en dónde están los jugadores, los marcos, y cuales espacios son libres. El algoritmo parte de las "coordenadas" recibidas, las cuales indican la posición actual de la bola, y comenzará a calcular una ruta posible de la bola hasta el marco del rival.

El algoritmo trabajará con una matriz solución, el cual inicia con todos los nodos o bloques marcados como "0" para indicar que es un bloque que no forma parte de la ruta solución, y para cada bloque que sí se considera como parte de la solución, en esta matriz solución se marcará el bloque con un "1".

El algoritmo como caso inicial siempre intentará ir en la dirección del marco del otro jugador, es decir hacia la derecha si el marco del jugador está ahí, o a la izquierda si el marco del jugador está ahí. Cada bloque al que se va, se marcará como un bloque parte de la solución, y esto asegura que el bloque no se reusara. Usando un ejemplo donde el marco del jugador está a la izquierda, el algoritmo intentará ir en esa dirección. En el caso de que sea imposible ir hacia la izquierda, se intentará ir un bloque hacia abajo. Si ir hacia abajo es imposible, se intentará ir hacia arriba. Y si no se puede ir hacia arriba, el algoritmo desmarcará el bloque actual como parte de la solución y se irá hacia atrás, o hará "backtracking". En cada una de estas direcciones, ir hacia un bloque ya marcado cuenta como un bloque "bloqueado" por la idea no es ciclar entre dos mismos bloques y nunca encontrar una solución.

Una vez encontrado la solución, el algoritmo retornará la matriz solución, el cual contiene la ruta, y esta se mostrará en el cliente antes de tirar la bola por la ruta. En el caso de que la solución no exista, el algoritmo lo indicará, y significa que sin importar en qué dirección se lanza la bola, este no llegará al marco.

Demostración de los intentos de ir en cada dirección e ir marcando cada nodo:

// Revisar si el bloque ya es parte de la solución
          if (matriz[x][y] == 1)
              return false;
       
        // marcar al bloque actual como parte de la solución 
        matriz[x][y] = 1;
 
        //moverse hacia el marco del jugador
        if (Backtrack(
                tabla, x + 1, y, sol)
            == true)
            return true;
 
        //en caso de no poder ir hacia la izquierda, probar hacia abajo
        if (Backtrack(
                tabla, x, y + 1, sol)
            == true)
            return true;


       
        //probar en dirección el marco de la computadora
        if (Backtrack(
                tabla, x - 1, y, sol)
            == true)
            return true;
 
        //probar hacia abajo
        if (Backtrack(
                tabla, x, y - 1, sol)
            == true)
            return true;
 
        //en caso de que ninguna de las direcciones diera true, el bloque se marca que no es viable y se devuelve, haciendo "backtrack"
        matriz[x][y] = 0;
        return false;
    }
 
    return false;

Se desarrollo un algoritmo genetico que se encargara de recibir una matriz de una imagen desordenada y por medio de mutaciones y cruces el algoritmo es capaz de elegir las mejores mutaciones y cruces en una generacion para poder ordenar la imagen a la imagen original. El crossover se basa en agarrar las imagenes con posiciones muy cercanas a la original y cambiarlas para que se asemeje mas la imagen original en la matriz, mientras que la mutacion se basa en cambiar aleatoriamente dos imagenes de posiciones.

//Functions of the genetic algorithm
void sortFitness(List<MatrixNode<int>*>* list)
void loadFitness(Matrix<int>* matrix)
Matrix<int>* crossover(Matrix<int>* matrix, List<MatrixNode<int>*>* list)
void mutation(int numPieces, Matrix<int>* matrix)

//Crossover
matrix = crossover(matrix,listFitness);

//Mutation
if(listMutations->getSize() != 0) {
    listMutations->delAll();
    listMutations = new List<int>();
}
mutation(numPieces,matrix);

//Adds new generation
listGenerations->addData(matrix);
generation++;

//Calculates the function fitness of the new generation
listFitness->delAll();
listFitness = new List<MatrixNode<int>*>();
loadFitness(listGenerations->getDataPos(generation));
...

Se desarrollo un algoritmo que se encargara de recibir la cantidad de piezas que se requiere partir la imagen y crear una matriz con las piezas creadas y desordenas para que el algoritmo genetico se encargara de ordenarlas y que el algoritmo de dibujar la matriz pudiera leer dicha matriz de piezas.

Matrix<int>* utility(int num, Matrix<int> *matrix)
{
    List<int> *listInOrder = new List<int>();
    List<int> *listNotOrder = new List<int>();
    bool listUsed[num];
    vector <int> listDividers;

    for(int x = 1; x <= num; x++)
    {
        if(num % x == 0)
        {
            listDividers.push_back(x);
        }
    }

    int x = 0;
    while(x < listNotOrder->getSize())
    {
        for(int i = 0; i < matrix->getRows(); i++){
            for(int j = 0; j < matrix->getCols(); j++){
                MatrixNode<int>* node = matrix->getNodePos(i,j);
                node->setData(listNotOrder->getDataPos(x));
                x++;
            }
        }
    }
    return matrix;
}
...

Se desarrollo un algoritmo que recibiera una matriz y desplagara en pantalla dicha matriz con la imagen establecida por el usuario. Dicho algoritmo se encarga de leer las posiciones de las piezas de la imagen y desplegarlas en su orden dado por la matriz (interfaz grafica).

void loadPuzzle(Matrix<int>* matrix)
{
    //Clear the previous tempMap and map
    tempMap.clear();
    puzzleMap.clear();

    //Travel the matrix
    for(int i = 0; i < matrix->getRows(); i++)
    {
        for(int j = 0; j < matrix->getCols(); j++)
        {
            MatrixNode<int>* node = matrix->getNodePos(i,j);
            tempMap.push_back(node->getData());
        }
        puzzleMap.push_back(tempMap);
        tempMap.clear();
    }
}

for (int i = 0; i < puzzleMap.size(); i++) {
    for (int j = 0; j < puzzleMap[i].size(); j++) {
         sf::Vector2f positionMap = sf::Vector2f(j * row, i * col);
         sf::Vector2f rect = sf::Vector2f(row, col);
         sf::Vector2f positionRect = listPosImages->getDataPos(puzzleMap[i][j]);
         Piece *p = new Piece(positionMap, puzzleTexture, rect, positionRect);
         window.draw(p->piece);
    }
}
...