source: code/branches/3DPacman_FS19/src/modules/pacman/getShortestPath.cc @ 12312

    #include "core/CoreIncludes.h"
    #include "core/XMLPort.h"
    //#include "getShortestPath.h"
    #include "PacmanGhost.h"


    #include "worldentities/ControllableEntity.h"
    using namespace std;

    namespace orxonox{

        struct graphVertex {

            Vector3 position;
            graphVertex *adjacentVertices[4]; //neighbooring vertices

            //would a vector of vector storing the neighboors not be more suitable ?

            int shortestDistanceToStart; //actual shortest distance to start point
            graphVertex* actuelPredecessor; //the predecessor giving the for now shortest 
                                            //path to start
            graphVertex* currentNearestNonVisitedNeighboor; 
            bool alreadyVisited;
            graphVertex(){ //default constructor
                position=0;
                shortestDistanceToStart= std::numeric_limits<int>::max();
                actuelPredecessor=NULL;
                alreadyVisited=false;
                for(int kl =0; kl <4;kl++){
                    adjacentVertices[kl]=NULL;  //first put all position in array listing neighboors to 0
                }
            }
            graphVertex(Vector3 wantedPosition){  //normal constructor
                position=wantedPosition;
                shortestDistanceToStart= std::numeric_limits<int>::max(); //default distance is infinity
                actuelPredecessor=NULL;
                alreadyVisited=false;
                for(int kl =0; kl <4;kl++){
                    adjacentVertices[kl]=NULL;  //first put all position in array listing neighboors to 0
                }
            }
            graphVertex* operator = (graphVertex *rightSide){
            this->position=rightSide->position;
            this->actuelPredecessor=rightSide->actuelPredecessor;
            return this;
        }

        };

        graphVertex listOfVertices[67];

        Vector3 getShortestPath(Vector3 start, Vector3 goal){
        //this function should then somehow produce the algorithm and call all other functions
        //and finally return the best neighboor of the actual position of the pacman
        

        if(start==goal){ // basic case
            return start;
        }
       

        for(int an=0; an < 67; an++){
      listOfVertices[an]=  graphVertex(possibleposition[an]); //same position order as in other file
        }

        graphVertex actualVertex= graphVertex(start);

        actualVertex.alreadyVisited=true;
        actualVertex.shortestDistanceToStart=0;
        findNeighboorVertices(actualVertex.position, *actualVertex.adjacentVertices); 
        // second parameter is an array !
        
        while(actualVertex.position!=goal){
            for(int h=0;h < 4; h++){
                if(actualVertex.adjacentVertices[h]!=NULL){
                    updateShortestDistanceToStart(actualVertex, *actualVertex.adjacentVertices[h]);
                } //we "update" the neighboors of our new visited vertex
            }
            

            actualVertex=findNextVertexToConsider(listOfVertices);
            actualVertex.alreadyVisited=true;
            if(actualVertex.position!=goal){
                findNeighboorVertices(actualVertex.position,*actualVertex.adjacentVertices); 
                //we find the neighboors of our new visited vertex
                }
        }

        //we should have reached our goal at this point

        while(actualVertex.actuelPredecessor->actuelPredecessor!=NULL){
            actualVertex=actualVertex.actuelPredecessor;
        }
        // the predecessor is our starting point, in other words we are now on an
        //adjacent vertex of the start

        return actualVertex.position; //we return the position of this adjacent vertex
    }

    int graphDistance(Vector3 start, Vector3 goal){

        Vector3 differenceVector= Vector3(abs(goal.x-start.x), 0,abs(goal.z-start.z));

        return differenceVector.x+differenceVector.z;
    }

    void updateShortestDistanceToStart(graphVertex &vertex, graphVertex &neighboor){
        //apply this method to all non visited neighboors of a vertex.
        // This method should always be run on a vertex after we marked it as visited.
        if(neighboor.alreadyVisited==false){ //we only consider non visited neighboors.
            if(neighboor.shortestDistanceToStart > vertex.shortestDistanceToStart + 
                graphDistance(vertex.position, neighboor.position)){

                neighboor.shortestDistanceToStart= vertex.shortestDistanceToStart + 
                graphDistance(vertex.position, neighboor.position);
                neighboor.actuelPredecessor = &vertex;
            }
        }

    }

    void findNearestNonVisitedNeighboor (graphVertex &vertex){ 
            //find nearest non visited neighboor of a given already visited vertex
        int shortestDistance = -1;
        graphVertex nearestNonVisitedNeighboor=graphVertex(); //by default there is not any.
        //Also, if all neighboors are already visited, we return NULL, i.e. there is no
        //nearest non visited neighboor.
        for(int i=0; i < 4; i++){
            if((vertex.adjacentVertices[i]!=NULL)&&(vertex.adjacentVertices[i]->alreadyVisited==false)){
                if(shortestDistance==-1){   //(concerns line above) we want a non visited neighboor
                    shortestDistance= graphDistance(vertex.position, vertex.adjacentVertices[i]->position);
                    nearestNonVisitedNeighboor=vertex.adjacentVertices[i];
                }
                else if(graphDistance(vertex.position, vertex.adjacentVertices[i]->position)<shortestDistance){
                    shortestDistance= graphDistance(vertex.position, vertex.adjacentVertices[i]->position);
                    nearestNonVisitedNeighboor=vertex.adjacentVertices[i];
                }
            }
        }
        vertex.currentNearestNonVisitedNeighboor = &nearestNonVisitedNeighboor;
    }


    graphVertex findNextVertexToConsider(graphVertex listOfVerticesP[]){ //find next, nearest from start, non visited vertex 

        int shortestDistance = -1;
        graphVertex nextVertexToConsider;

        for(int i=0; i < 67; i++){ //we loop over all possible positions 

            if(listOfVerticesP[i].alreadyVisited==true){ //vertex should already be visited 

                findNearestNonVisitedNeighboor(listOfVerticesP[i]); //we update nearest neighboor
                //of all visited vertices given that one of the nearest neighboor of a visited
                // vertex is now also visited because it was chosen as next optimal vertex

                if(listOfVerticesP[i].currentNearestNonVisitedNeighboor!=NULL){ //we want a candidate!
                if(shortestDistance==-1){ //our first possible candidate

            shortestDistance=graphDistance(listOfVerticesP[i].position, 
            listOfVerticesP[i].currentNearestNonVisitedNeighboor->position) + 
            listOfVerticesP[i].shortestDistanceToStart;

            nextVertexToConsider=listOfVerticesP[i].currentNearestNonVisitedNeighboor;

                }
                else if(shortestDistance > graphDistance(listOfVerticesP[i].position, 
                listOfVerticesP[i].currentNearestNonVisitedNeighboor->position) + 
                    listOfVerticesP[i].shortestDistanceToStart){

            shortestDistance=graphDistance(listOfVerticesP[i].position, 
            listOfVerticesP[i].currentNearestNonVisitedNeighboor->position) + 
            listOfVerticesP[i].shortestDistanceToStart;

            nextVertexToConsider=listOfVerticesP[i].currentNearestNonVisitedNeighboor;
                    }
                }
            }
            //we want after all to return the nearest non visited neighboor
        }

        return nextVertexToConsider;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////

    //if vertex already visited, call function on it and reapeat until you reach non visited vertex
    // ---> not sure if a good idea because we risk infinite loop

    //-215 -185 -135 -70 -20 0 20 70 135 185 215 

    //-195 -135 -85 -35 15 60 105 150 195 245

    void findNeighboorVertices(Vector3 actuelposition, graphVertex* adjacentVertices[]){      


            if(findpos(actuelposition,possibleposition[0])){
                // we should use listOfVertices[i] instead of possibleposition[i] I think
                // so that all neighboors are "the same"
                adjacentVertices[0]=&listOfVertices[1]; //graphVertex(possibleposition[1]);  //need to do it everywhere !!!
                adjacentVertices[1]=&listOfVertices[17]; //graphVertex(possibleposition[17]);
                adjacentVertices[2]=&listOfVertices[19]; //graphVertex(possibleposition[19]); //maybe a vector would be more suitable ?
            }
            else if(findpos(actuelposition,possibleposition[1])){
                adjacentVertices[0]=&listOfVertices[0]; //graphVertex(possibleposition[0]);
                adjacentVertices[1]=&listOfVertices[2]; //graphVertex(possibleposition[2]);
            }
            else if(findpos(actuelposition,possibleposition[2])){
                adjacentVertices[0]=&listOfVertices[1]; //graphVertex(possibleposition[1]);
                adjacentVertices[1]=&listOfVertices[3]; //graphVertex(possibleposition[3]);
            }
            else if(findpos(actuelposition,possibleposition[3])){
                adjacentVertices[0]=&listOfVertices[2]; //graphVertex(possibleposition[2]);
                adjacentVertices[1]=&listOfVertices[4]; //graphVertex(possibleposition[4]);
                adjacentVertices[2]=&listOfVertices[5]; //graphVertex(possibleposition[5]);
            }
            else if(findpos(actuelposition,possibleposition[4])){
                adjacentVertices[0]=&listOfVertices[3]; //graphVertex(possibleposition[3]);
                adjacentVertices[1]=&listOfVertices[6]; //graphVertex(possibleposition[6]);
            }
            else if(findpos(actuelposition,possibleposition[5])){
                adjacentVertices[0]=&listOfVertices[3]; //graphVertex(possibleposition[3]);
                adjacentVertices[1]=&listOfVertices[7]; //graphVertex(possibleposition[7]);
            }
            else if(findpos(actuelposition,possibleposition[6])){
                adjacentVertices[0]=&listOfVertices[4]; //graphVertex(possibleposition[4]);
                adjacentVertices[1]=&listOfVertices[9]; //graphVertex(possibleposition[9]);
                adjacentVertices[2]=&listOfVertices[26]; //graphVertex(possibleposition[26]);
            }
            else if(findpos(actuelposition,possibleposition[7])){
                adjacentVertices[0]=&listOfVertices[5]; //graphVertex(possibleposition[5]);
                adjacentVertices[1]=&listOfVertices[8]; //graphVertex(possibleposition[8]);
            }
            else if(findpos(actuelposition,possibleposition[8])){
                adjacentVertices[0]=&listOfVertices[7]; //graphVertex(possibleposition[7]);
                adjacentVertices[1]=&listOfVertices[9]; //graphVertex(possibleposition[9]);
            }
            else if(findpos(actuelposition,possibleposition[9])){
                adjacentVertices[0]=&listOfVertices[6]; //graphVertex(possibleposition[6]);
                adjacentVertices[1]=&listOfVertices[8]; //graphVertex(possibleposition[8]);
                adjacentVertices[2]=&listOfVertices[10]; //graphVertex(possibleposition[10]);
                adjacentVertices[3]=&listOfVertices[38]; //graphVertex(possibleposition[38]);
            }
            else if(findpos(actuelposition,possibleposition[10])){
                adjacentVertices[0]=&listOfVertices[9]; //graphVertex(possibleposition[9]);
                adjacentVertices[1]=&listOfVertices[11]; //graphVertex(possibleposition[11]);
                adjacentVertices[2]=&listOfVertices[45]; //graphVertex(possibleposition[45]);
            }
            else if(findpos(actuelposition,possibleposition[11])){
                adjacentVertices[0]=&listOfVertices[10]; //graphVertex(possibleposition[10]);
                adjacentVertices[1]=&listOfVertices[12]; //graphVertex(possibleposition[12]);
                adjacentVertices[2]=&listOfVertices[13]; //graphVertex(possibleposition[13]);
            }
            else if(findpos(actuelposition,possibleposition[12])){
                adjacentVertices[0]=&listOfVertices[11]; //graphVertex(possibleposition[11]);
                adjacentVertices[1]=&listOfVertices[14]; //graphVertex(possibleposition[14]);
            }
            else if(findpos(actuelposition,possibleposition[13])){
                adjacentVertices[0]=&listOfVertices[11]; //graphVertex(possibleposition[11]);
                adjacentVertices[1]=&listOfVertices[14]; //graphVertex(possibleposition[14]);
                adjacentVertices[2]=&listOfVertices[16]; //graphVertex(possibleposition[16]);
                adjacentVertices[3]=&listOfVertices[61]; //graphVertex(possibleposition[61]);
            }
            else if(findpos(actuelposition,possibleposition[14])){
                adjacentVertices[0]=&listOfVertices[12]; //graphVertex(possibleposition[12]);
                adjacentVertices[1]=&listOfVertices[13]; //graphVertex(possibleposition[13]);
                adjacentVertices[2]=&listOfVertices[15]; //graphVertex(possibleposition[15]);
            }
            else if(findpos(actuelposition,possibleposition[15])){
                adjacentVertices[0]=&listOfVertices[14]; //graphVertex(possibleposition[14]);
                adjacentVertices[1]=&listOfVertices[16]; //graphVertex(possibleposition[16]);
            }
            else if(findpos(actuelposition,possibleposition[16])){
                adjacentVertices[0]=&listOfVertices[13]; //graphVertex(possibleposition[13]);
                adjacentVertices[1]=&listOfVertices[15]; //graphVertex(possibleposition[15]);
                adjacentVertices[2]=&listOfVertices[62]; //graphVertex(possibleposition[62]);
            }
            else if(findpos(actuelposition,possibleposition[17])){
                adjacentVertices[0]=&listOfVertices[0]; //graphVertex(possibleposition[0]);
                adjacentVertices[1]=&listOfVertices[25]; //graphVertex(possibleposition[25]);
            }
            else if(findpos(actuelposition,possibleposition[18])){
                adjacentVertices[0]=&listOfVertices[19]; //graphVertex(possibleposition[19]);
                adjacentVertices[1]=&listOfVertices[24]; //graphVertex(possibleposition[24]);                
            }
            else if(findpos(actuelposition,possibleposition[19])){
                adjacentVertices[0]=&listOfVertices[0]; //graphVertex(possibleposition[0]);
                adjacentVertices[1]=&listOfVertices[18]; //graphVertex(possibleposition[18]);
                adjacentVertices[2]=&listOfVertices[20]; //graphVertex(possibleposition[20]);
                         }
            else if(findpos(actuelposition,possibleposition[20])){
                adjacentVertices[0]=&listOfVertices[19]; //graphVertex(possibleposition[19]);
                adjacentVertices[1]=&listOfVertices[21]; //graphVertex(possibleposition[21]);
                       }
            else if(findpos(actuelposition,possibleposition[21])){
                adjacentVertices[0]=&listOfVertices[20]; //graphVertex(possibleposition[20]);
                adjacentVertices[1]=&listOfVertices[22]; //graphVertex(possibleposition[22]);
                       }
            else if(findpos(actuelposition,possibleposition[22])){
                adjacentVertices[0]=&listOfVertices[21]; //graphVertex(possibleposition[21]);
                adjacentVertices[1]=&listOfVertices[23]; //graphVertex(possibleposition[23]);
                adjacentVertices[2]=&listOfVertices[31]; //graphVertex(possibleposition[31]);
                          }
            else if(findpos(actuelposition,possibleposition[23])){
                adjacentVertices[0]=&listOfVertices[22]; //graphVertex(possibleposition[22]);
                adjacentVertices[1]=&listOfVertices[30]; //graphVertex(possibleposition[30]);
                       }
            else if(findpos(actuelposition,possibleposition[24])){
                adjacentVertices[0]=&listOfVertices[18]; //graphVertex(possibleposition[18]);
                adjacentVertices[1]=&listOfVertices[29]; //graphVertex(possibleposition[29]);
                       }
            else if(findpos(actuelposition,possibleposition[25])){
                adjacentVertices[0]=&listOfVertices[17]; //graphVertex(possibleposition[17]);
                adjacentVertices[1]=&listOfVertices[26]; //graphVertex(possibleposition[26]);
                       }
            else if(findpos(actuelposition,possibleposition[26])){
                adjacentVertices[0]=&listOfVertices[6]; //graphVertex(possibleposition[6]);
                adjacentVertices[1]=&listOfVertices[25]; //graphVertex(possibleposition[25]);
                adjacentVertices[2]=&listOfVertices[27]; //graphVertex(possibleposition[27]);
                         }
            else if(findpos(actuelposition,possibleposition[27])){
                adjacentVertices[0]=&listOfVertices[26]; //graphVertex(possibleposition[26]);
                adjacentVertices[1]=&listOfVertices[28]; //graphVertex(possibleposition[28]);
                adjacentVertices[2]=&listOfVertices[37]; //graphVertex(possibleposition[37]);
                          }
            else if(findpos(actuelposition,possibleposition[28])){
                adjacentVertices[0]=&listOfVertices[27]; //graphVertex(possibleposition[27]);
                adjacentVertices[1]=&listOfVertices[29]; //graphVertex(possibleposition[29]);
                adjacentVertices[2]=&listOfVertices[36]; //graphVertex(possibleposition[36]);
                          }
            else if(findpos(actuelposition,possibleposition[29])){
                adjacentVertices[0]=&listOfVertices[24]; //graphVertex(possibleposition[24]);
                adjacentVertices[1]=&listOfVertices[28]; //graphVertex(possibleposition[28]);
                adjacentVertices[2]=&listOfVertices[30]; //graphVertex(possibleposition[30]);
                          }
            else if(findpos(actuelposition,possibleposition[30])){
                adjacentVertices[0]=&listOfVertices[23]; //graphVertex(possibleposition[23]);
                adjacentVertices[1]=&listOfVertices[29]; //graphVertex(possibleposition[29]);
                adjacentVertices[2]=&listOfVertices[34]; //graphVertex(possibleposition[34]);
                          }
            else if(findpos(actuelposition,possibleposition[31])){
                adjacentVertices[0]=&listOfVertices[22]; //graphVertex(possibleposition[22]);
                adjacentVertices[1]=&listOfVertices[32]; //graphVertex(possibleposition[32]);
                       }
            else if(findpos(actuelposition,possibleposition[32])){
                adjacentVertices[0]=&listOfVertices[31]; //graphVertex(possibleposition[31]);
                adjacentVertices[1]=&listOfVertices[33]; //graphVertex(possibleposition[33]);
                       }
            else if(findpos(actuelposition,possibleposition[33])){
                adjacentVertices[0]=&listOfVertices[32]; //graphVertex(possibleposition[32]);
                adjacentVertices[1]=&listOfVertices[34]; //graphVertex(possibleposition[34]);
                       }
            else if(findpos(actuelposition,possibleposition[34])){
                adjacentVertices[0]=&listOfVertices[30]; //graphVertex(possibleposition[30]);
                adjacentVertices[1]=&listOfVertices[33]; //graphVertex(possibleposition[33]);
                adjacentVertices[2]=&listOfVertices[35]; //graphVertex(possibleposition[35]);
                adjacentVertices[3]=&listOfVertices[42]; //graphVertex(possibleposition[42]);
                
            }
            else if(findpos(actuelposition,possibleposition[35])){
                adjacentVertices[0]=&listOfVertices[34]; //graphVertex(possibleposition[34]);
                adjacentVertices[1]=&listOfVertices[36]; //graphVertex(possibleposition[36]);
                adjacentVertices[2]=&listOfVertices[41]; //graphVertex(possibleposition[41]);
                          }
            else if(findpos(actuelposition,possibleposition[36])){
                adjacentVertices[0]=&listOfVertices[28]; //graphVertex(possibleposition[28]);
                adjacentVertices[1]=&listOfVertices[35]; //graphVertex(possibleposition[35]);
                       }
            else if(findpos(actuelposition,possibleposition[37])){
                adjacentVertices[0]=&listOfVertices[27]; //graphVertex(possibleposition[27]);
                adjacentVertices[1]=&listOfVertices[38]; //graphVertex(possibleposition[38]);
                       }
            else if(findpos(actuelposition,possibleposition[38])){
                adjacentVertices[0]=&listOfVertices[9]; //graphVertex(possibleposition[9]);
                adjacentVertices[1]=&listOfVertices[37]; //graphVertex(possibleposition[37]);
                adjacentVertices[2]=&listOfVertices[39]; //graphVertex(possibleposition[39]);
                         }
            else if(findpos(actuelposition,possibleposition[39])){
                adjacentVertices[0]=&listOfVertices[38]; //graphVertex(possibleposition[38]);
                adjacentVertices[1]=&listOfVertices[40]; //graphVertex(possibleposition[40]);
                adjacentVertices[2]=&listOfVertices[45]; //graphVertex(possibleposition[45]);
                          }
            else if(findpos(actuelposition,possibleposition[40])){
                adjacentVertices[0]=&listOfVertices[39]; //graphVertex(possibleposition[39]);
                adjacentVertices[1]=&listOfVertices[41]; //graphVertex(possibleposition[41]);
            }
            else if(findpos(actuelposition,possibleposition[41])){
                adjacentVertices[0]=&listOfVertices[35]; //graphVertex(possibleposition[35]);
                adjacentVertices[1]=&listOfVertices[43]; //graphVertex(possibleposition[43]);
                       }
            else if(findpos(actuelposition,possibleposition[42])){
                adjacentVertices[0]=&listOfVertices[34]; //graphVertex(possibleposition[34]);
                adjacentVertices[1]=&listOfVertices[43]; //graphVertex(possibleposition[43]);
                adjacentVertices[2]=&listOfVertices[54]; //graphVertex(possibleposition[54]);
                          }
            else if(findpos(actuelposition,possibleposition[43])){
                adjacentVertices[0]=&listOfVertices[41]; //graphVertex(possibleposition[41]);
                adjacentVertices[1]=&listOfVertices[46]; //graphVertex(possibleposition[46]);
                       }
            else if(findpos(actuelposition,possibleposition[44])){
                adjacentVertices[0]=&listOfVertices[40]; //graphVertex(possibleposition[40]);
                adjacentVertices[1]=&listOfVertices[66]; //graphVertex(possibleposition[66]);
                       }
            else if(findpos(actuelposition,possibleposition[45])){
                adjacentVertices[0]=&listOfVertices[10]; //graphVertex(possibleposition[10]);
                adjacentVertices[1]=&listOfVertices[39]; //graphVertex(possibleposition[39]);
                adjacentVertices[2]=&listOfVertices[49]; //graphVertex(possibleposition[49]);
                          }
            else if(findpos(actuelposition,possibleposition[46])){
                adjacentVertices[0]=&listOfVertices[43]; //graphVertex(possibleposition[43]);
                adjacentVertices[1]=&listOfVertices[47]; //graphVertex(possibleposition[47]);
                       }
            else if(findpos(actuelposition,possibleposition[47])){
                adjacentVertices[0]=&listOfVertices[46]; //graphVertex(possibleposition[46]);
                adjacentVertices[1]=&listOfVertices[52]; //graphVertex(possibleposition[52]);
                adjacentVertices[2]=&listOfVertices[66]; //graphVertex(possibleposition[66]);
                          }
            else if(findpos(actuelposition,possibleposition[48])){
                adjacentVertices[0]=&listOfVertices[49]; //graphVertex(possibleposition[49]);
                adjacentVertices[1]=&listOfVertices[51]; //graphVertex(possibleposition[51]);
                adjacentVertices[2]=&listOfVertices[66]; //graphVertex(possibleposition[66]);
                          }
            else if(findpos(actuelposition,possibleposition[49])){
                adjacentVertices[0]=&listOfVertices[45]; //graphVertex(possibleposition[45]);
                adjacentVertices[1]=&listOfVertices[48]; //graphVertex(possibleposition[48]);
                       }
            else if(findpos(actuelposition,possibleposition[50])){
                adjacentVertices[0]=&listOfVertices[51]; //graphVertex(possibleposition[51]);
                adjacentVertices[1]=&listOfVertices[61]; //graphVertex(possibleposition[61]);
                       }
            else if(findpos(actuelposition,possibleposition[51])){
                adjacentVertices[0]=&listOfVertices[48]; //graphVertex(possibleposition[48]);
                adjacentVertices[1]=&listOfVertices[50]; //graphVertex(possibleposition[50]);
                       }
            else if(findpos(actuelposition,possibleposition[52])){
                adjacentVertices[0]=&listOfVertices[47]; //graphVertex(possibleposition[47]);
                adjacentVertices[1]=&listOfVertices[53]; //graphVertex(possibleposition[53]);
                       }
            else if(findpos(actuelposition,possibleposition[53])){
                adjacentVertices[0]=&listOfVertices[52]; //graphVertex(possibleposition[52]);
                adjacentVertices[1]=&listOfVertices[58]; //graphVertex(possibleposition[58]);
                       }
            else if(findpos(actuelposition,possibleposition[54])){
                adjacentVertices[0]=&listOfVertices[42]; //graphVertex(possibleposition[42]);
                adjacentVertices[1]=&listOfVertices[55]; //graphVertex(possibleposition[55]);
                adjacentVertices[2]=&listOfVertices[57]; //graphVertex(possibleposition[57]);
                          }
            else if(findpos(actuelposition,possibleposition[55])){
                adjacentVertices[0]=&listOfVertices[54]; //graphVertex(possibleposition[54]);
                adjacentVertices[1]=&listOfVertices[56]; //graphVertex(possibleposition[56]);
                       }
            else if(findpos(actuelposition,possibleposition[56])){
                adjacentVertices[0]=&listOfVertices[55]; //graphVertex(possibleposition[55]);
                adjacentVertices[1]=&listOfVertices[57]; //graphVertex(possibleposition[57]);
                adjacentVertices[2]=&listOfVertices[65]; //graphVertex(possibleposition[65]);
                          }
            else if(findpos(actuelposition,possibleposition[57])){
                adjacentVertices[0]=&listOfVertices[54]; //graphVertex(possibleposition[54]);
                adjacentVertices[1]=&listOfVertices[56]; //graphVertex(possibleposition[56]);
                adjacentVertices[2]=&listOfVertices[58]; //graphVertex(possibleposition[58]);
                adjacentVertices[3]=&listOfVertices[64]; //graphVertex(possibleposition[64]);
                
            }
            else if(findpos(actuelposition,possibleposition[58])){
                adjacentVertices[0]=&listOfVertices[53]; //graphVertex(possibleposition[53]);
                adjacentVertices[1]=&listOfVertices[57]; //graphVertex(possibleposition[57]);
                adjacentVertices[2]=&listOfVertices[59]; //graphVertex(possibleposition[59]);
                          }
            else if(findpos(actuelposition,possibleposition[59])){
                adjacentVertices[0]=&listOfVertices[58]; //graphVertex(possibleposition[58]);
                adjacentVertices[1]=&listOfVertices[59]; //graphVertex(possibleposition[59]);
                adjacentVertices[2]=&listOfVertices[63]; //graphVertex(possibleposition[63]);
                          }
            else if(findpos(actuelposition,possibleposition[60])){
                adjacentVertices[0]=&listOfVertices[59]; //graphVertex(possibleposition[59]);
                adjacentVertices[1]=&listOfVertices[61]; //graphVertex(possibleposition[61]);
                adjacentVertices[2]=&listOfVertices[62]; //graphVertex(possibleposition[62]);
                          }
            else if(findpos(actuelposition,possibleposition[61])){
                adjacentVertices[0]=&listOfVertices[13]; //graphVertex(possibleposition[13]);
                adjacentVertices[1]=&listOfVertices[50]; //graphVertex(possibleposition[50]);
                adjacentVertices[2]=&listOfVertices[60]; //graphVertex(possibleposition[60]);
                          }
            else if(findpos(actuelposition,possibleposition[62])){
                adjacentVertices[0]=&listOfVertices[16]; //graphVertex(possibleposition[16]);
                adjacentVertices[1]=&listOfVertices[60]; //graphVertex(possibleposition[60]);
                       }
            else if(findpos(actuelposition,possibleposition[63])){
                adjacentVertices[0]=&listOfVertices[59]; //graphVertex(possibleposition[59]);
                adjacentVertices[1]=&listOfVertices[64]; //graphVertex(possibleposition[64]);
                       }
            else if(findpos(actuelposition,possibleposition[64])){
                adjacentVertices[0]=&listOfVertices[57]; //graphVertex(possibleposition[57]);
                adjacentVertices[1]=&listOfVertices[63]; //graphVertex(possibleposition[63]);
                adjacentVertices[2]=&listOfVertices[65]; //graphVertex(possibleposition[65]);
                          }
            else if(findpos(actuelposition,possibleposition[65])){
                adjacentVertices[0]=&listOfVertices[56]; //graphVertex(possibleposition[56]);
                adjacentVertices[1]=&listOfVertices[64]; //graphVertex(possibleposition[64]);
                       }
            else if(findpos(actuelposition,possibleposition[66])){
                adjacentVertices[0]=&listOfVertices[47]; //graphVertex(possibleposition[47]);
                adjacentVertices[1]=&listOfVertices[48]; //graphVertex(possibleposition[48]);
                       }
    }


}