BSQ Epitech Project

Authorized functions

The list of authorized functions are only :

• open
• read
• write
• close
• malloc
• free
• stat

Description

The goal of the project is to find the biggest square on a map while avoiding obstacles.

The file map is passed as parameter to the program.

Goal

The goal of the project is to find the biggest square of '.' in the map and replace it by 'x'.

Tutorial

The project is splited into 3 parts:

• Load the map.

• Search inside the map the biggest square.

• Display with good performences.

First of all, I would precise that the project can be done by two 2 different way :

• By using string.

• By using array.

Using string is really hard because you need to have a perfect master’s degree of calculation handling for locating hisself in the map. This method let generally place to a lot of mistakes, but in case of success, it is really powerfull and generate great performances.

Using arrays is really easy because you can locating yourself easily in the map. This method don’t let generally place to mistakes and have great performances.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

typedef struct save_important_values {
    /* content 
    exemple:
    unsigned short width;
    unsigned short height;
    unsigned short save_i;
    unsigned short save_j;
    unsigned short biggest_square;
    */
} var_saver_t;

1
2
3
4

    var_saver_t *saver = malloc(sizeof(var_saver_t));

    if (!saver)
        return (84);

1

    var_saver_t saver;

Lets see now how to realise the BSQ project with the array method !

Load

First of all you will have to use the open and read functions, so check the man open and man read.

Create a function that will open the file, generate an array based on the readed file and realise an error gestion.

The prototype of the function can be written like so : unsigned short **load_map(char *file_path). In case of error the function will return NULL.

So lets begin your load_map function !

Open, read and stat file

To read the entire map stocked in a file you will need to get the file size.

The stat structure give you a lot of information about a file. For more information about stat, check the documentation.

1
2
3
4
5
6
7
8
9

off_t size_file(char const *file_path)
{
    off_t size;
    struct stat buf;

    if (stat(filepath, &buf) == -1)
        return (-84);
    return buf.st_size;
}

Here you get the size of the file thanks to buf.st_size. You every time sould carefull of return values.

The next step is to open the file with readable option O_RDONLY.

1
2
3
4

    int fd = open(filepath, O_RDONLY);

    if (fd == -1)
        return (NULL);

Now, you have a valid fd, the size of the file. You only need to read the file and stock it in a string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

unsigned short **load_map(char *file_path)
{
    int fd = open(filepath, O_RDONLY);
    off_t size = size_file(file_path);
    char *map_file;

    if (fd == -1 || size == -1)
        return (NULL);
    map_file = malloc(sizeof(char) * (size + 1));
    if (!map_file || read(fd, map_file, size) == -1)
        return (NULL);
    map_file[size] = '\0';
}

Create your array

Now you have your map stocked in a string and you want to transform it into an array. So, you should extract the first line and code a string to unsigned short ** function.

I let you find the way to get the first line of your map and stock it in a variable, and how to get the length of your map’s lines.

Lets create your array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

unsigned short **string_to_short_array(char *my_map, unsigned short width, unsigned short height, off_t size)
{
    unsigned short **map = malloc(sizeof(unsigned short *) * height);

    if (!map)
        return NULL;
    // The size is your first line
    for (int j = 0, i = 0; my_map[i] != '\0' ; ++j) {
        map[j] = malloc(sizeof(unsigned short) * width);
        for (int k = 0; my_map[i] != '\n' && my_map[i] != '\0'; ++i, ++k) {
            // Do some gest error for verifying length's lines validity.
            // Do some gest error for verifying characters validity.
            map[j][k] = (my_map[i] == '.') ? 1 : 0;
        }
        i += (map[i] != \0) ? 1 : 0;
    }
    return map
}

The code is a bit complexe but it is a great optimisation, because you allocate and fill the content into the allocated memory dirrectly. In the first for loop you’re alocating the map with the line’s width. In the second for loop you are putting characters in the map.

Now your load_map function should look something like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

unsigned short **load_map(char *file_path)
{
    int fd = open(filepath, O_RDONLY);
    off_t size = size_file(file_path);
    char *map_file;
    unsigned short **map;

    if (fd == -1 || size == -1)
        return (NULL);
    map_file = malloc(sizeof(char) * (size + 1));
    if (!map_file || read(fd, map_file, size) == -1)
        return (NULL);
    map_file[size] = '\0';
    // Do some error gestion and get the witdth and height
    close(fd);
    return (string_to_short_array(my_map, width, height, size));
}

If you print the content of your map you should have this result without colors:

Search

Now that you have stocked your map, the emplementation of the reverse minesweeper will be easier.

The principle of the reverse minesweeper is to look specific arounded cases to determine possibilities. We could represent this like that:

What I mean here is that you need first to check if the central case is a valid case and after check the validity of every left, top and left top surronding cases.

In your case you have a unsigned short ** map, that we will represent by this exemple:

• A 3 length biggest square.

• An obstacle.

So now lets implement the algorithm !

As we said previously you need to look around specific cases, I lied. You can’t look every surronding cases, because if you look in a part of the array that doesn’t exit, you are going to crash (segfault). So lets start at a position where you are not going to crash !

You’re going to create two for loops, one to travel into the unsigned short ** and another to travel into the unsigned short *.

1
2
3
4

    for (int i = 1; i < height; ++i) {
        for (int j = 1; j < width; j++) {
        }
    }

Like so, thanks to these two loops you can easily travel in your array. All you need now is to look around. So create a function that will look on the left, top and left top cases. This function need to find the minimum short in these tree cases to put it in the current case and increment it by one. Look the exemple below and you will understand.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void find_the_minim(unsigned short **tab, int i, int j)
{
    int save_min = tab[i][j - 1];

    if (tab[i - 1][j] < save_min)
        save_min = tab[i - 1][j];
    if (tab[i - 1][j - 1] < save_min)
        save_min = tab[i - 1][j - 1];
    if (save_min != 0)
        tab[i][j] = save_min + 1;
}

All you need now is to put this in the loop and it is practically done ! If I represent it you would have:

Now you have an unsigned short ** resolved biggest square, but you want to print only the biggest one in a map ! So, you need to keep in memory the place where you founded the biggest one. You can put in a struct the variables i and j from where you founded the biggest square.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void reverse_minesweeper(unsigned short **tab, save_index_t *index)
    index->biggest_square = 1;
    index->i = 0;
    index->j = 0;
    for (int i = 1; i < height; ++i) {
        for (int j = 1; j < width; j++) {
            find_the_minim(tab, i, j)
            if (tab[i][j] > index->biggest_square) {
                index->i = i;
                index->j = j;
                index->biggest_square = tab[i][j]
            }
        }
    }

Perfect ! You have an index on the biggest square. You can now display the map !

Display

Display your map is quite easy but also quite difficult because it is where the performance will be the worst. So, you have three choices:

• Display character by character

• Display line by line

• Display the whole map

For best performances you have choose the whole map ! 😂 You are going to use the map from the begining, but before you need to change your map with the founded square !

Remember, you have an unsigned short **map (wich is usless now), a char *map (from the loading), a struct with i, j and the length of the biggest square, the height of your map and the width of each line. Thank to that you can create a formula to access each element of your string you want. It is going to be two for loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void modify_by_biggest_square(char *map, save_index_t *index)
{
    for (int i = 0, counter = 0;
    counter < index->biggest_square; ++counter, --index->i) {
        // Don't forget the '\n' in the width !
        i = index->i * width
        for (int j = index->j, scounter = 0;
        scounter < index->biggest_square; --j, ++scounter)
            map[i + j] = 'x'
    }
}

See you the light at the end of the tunnel ?

All you need now is to my_putstr(map) or printf("%s", map).

You have finished your project well done !

Bonus ideas

• Print the position of the biggest square

• Print in color

• Print with a grafical library

• Do for other shapes

• Optimisation by using multiple hearts of your processor

Exemple :