labyrinth

This university project aims to solve a labyrinth.

The labyrinth is generated by a python script called generateur.py. Then it's stored into a matrix to compute and find the solution.

File architecture :

Labyrinth
├── P2
│   ├── generateur.py
│   ├── labyrinth.c
│   ├── labyrinth.h
│   ├── main.c
│   └── makefile
├── P3
│   ├── generateur.py
│   ├── labyrinth.c
│   ├── labyrinth.h
│   ├── main.c
│   └── makefile
└── README.md

Recursivity (P2)

First goal is to solve this labyrinth using recursivity : the principe used is backtracking. We first allocate a huge vector of slots and, for each visited slot, the recusive function will add the coordinates of the actual visited slot. If the recusive function is in a no-way, it will return and erase every slot until it finds another path to explore. every explored slot is written into the matrix and then considered as a wall.

Multi-threading (P2)

Second goal is to implement a recursive function using threads. There is a #define NB_THREAD keyword to determine how many threads the program is allowed to use. Depending on this number, at each intersection, the function will call itself inside a recursive function or inside a thread (if there are more than one direction). The important thing to note is that the recursive function needs to be called after all the threads functions. For each thread there is a corresponding path. If a thread is in a no-way, it will end itself and delete his path. During his lifetime, a thread will write his pthread_t id into an history of all the threads so that it can be properly join at the end. The threaded function (which is also used in recusivity) does not takes arguments nor returns a value. Everything is kept into a shared variable called global_args. A thread can know his path by knowing his positiong in the ids array and using this index in the res array.

There are several mutexes :

• acces_ids : allow one thread to write and read in ids and res arrays
• acces_laby : allow one thread to write and read in the labyrinth
• acces_out : allow one thread to use the printf function at a time
• acces_ids_history : allow one thread to write and read in the history of threads
• solution_trouvee : is locked until a thread finishes and find the solution

Process Race (P3)

Last goal was to fork inside the program, each fork would have an entry and an exit. The labyrinth also have a common slot called "door". each fork starts at its own entry. The two forks waits for each other to leave the door and then they each go to their own exit. The return of this function is an array of two paths. The first being the father and the second, its son.