Mercurial > public > maze-solver
changeset 1:edee16cfda92
algo working but inefficient
| author | Dennis <denniscmartin@protonmail.com> |
|---|---|
| date | Sun, 16 Oct 2022 14:13:37 +0200 |
| parents | 41a299d2b278 |
| children | 64d0988b0911 |
| files | CMakeLists.txt README.md algo.c algo.h build_library.sh main.c main.py mazes/small_maze.png |
| diffstat | 8 files changed, 274 insertions(+), 62 deletions(-) [+] |
line wrap: on
line diff
--- a/CMakeLists.txt Fri Oct 14 17:11:49 2022 +0200 +++ b/CMakeLists.txt Sun Oct 16 14:13:37 2022 +0200 @@ -1,6 +1,12 @@ cmake_minimum_required(VERSION 3.23) project(maze_solver C) +set(LIBPNG_DIR /usr/local/Cellar/libpng/1.6.38) # Set LIBPNG_DIR var to library path +include_directories(${LIBPNG_DIR}/include) # Add include folder +link_directories(${LIBPNG_DIR}/lib) # Link lib folder + set(CMAKE_C_STANDARD 99) -add_executable(maze_solver main.c) +add_executable(maze_solver main.c algo.c algo.h) + +target_link_libraries(maze_solver png) # Link libraries
--- a/README.md Fri Oct 14 17:11:49 2022 +0200 +++ b/README.md Sun Oct 16 14:13:37 2022 +0200 @@ -0,0 +1,8 @@ +# maze-solver + +A maze solver written in C. + +## Resources +- [Libpng example](http://zarb.org/~gc/html/libpng.html) +- [Libpng manual](http://www.libpng.org/pub/png/libpng-1.2.5-manual.html) +- [Inspired by Dr Mike Poung (Computerphile video)](https://www.youtube.com/watch?v=rop0W4QDOUI) \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/algo.c Sun Oct 16 14:13:37 2022 +0200 @@ -0,0 +1,151 @@ +// +// Created by Dennis Concepción Martín on 15/10/22. +// + +#include "algo.h" + +int isWhite(unsigned x, unsigned y, png_bytep* pRows) { + png_byte *pRow = pRows[y]; + png_byte *pPixel = &pRow[x * 4]; + + int r = pPixel[0]; + int g = pPixel[1]; + int b = pPixel[2]; + + if (r == 255 && g == 255 && b == 255) { + return 1; + } else { + return 0; + } +} + + +void wallFollower(png_bytep* pRows, unsigned int width) { + unsigned int x = 0; + unsigned int y = 1; + char direction = 'R'; + + while (x < width && y < width) { + + // Set pixel to color red + printf("x: %d, y: %d is white\n", x, y); + + if (x == width - 1 && y == width - 2) { + exit(0); + } + + switch (direction) { // NOLINT(hicpp-multiway-paths-covered) + case 'R': + + // Check if down position is white + if (isWhite(x, y + 1, pRows)) { + ++y; + direction = 'D'; + } + + // Check if right position is white + else if (isWhite(x + 1, y, pRows)) { + ++x; + direction = 'R'; + } + + // Check if up position is white + else if (isWhite(x, y - 1, pRows)) { + --y; + direction = 'U'; + } + + // Turn 180 + else { + --x; + direction = 'L'; + } + + break; + + case 'L': + + // Check if up position is white + if (isWhite(x, y - 1, pRows)) { + --y; + direction = 'U'; + } + + // Check if left position is white + else if (isWhite(x - 1, y, pRows)) { + --x; + direction = 'L'; + } + + // Check if down position is white + else if (isWhite(x, y + 1, pRows)) { + ++y; + direction = 'D'; + } + + // Turn 180 + else { + ++x; + direction = 'R'; + } + + break; + + case 'U': + + // Check if right position is white + if (isWhite(x + 1, y, pRows)) { + ++x; + direction = 'R'; + } + + // Check if up position is white + else if (isWhite(x, y - 1, pRows)) { + --y; + direction = 'U'; + } + + // Check if left position is white + else if (isWhite(x - 1, y, pRows)) { + --x; + direction = 'L'; + } + + // Turn 180 + else { + ++y; + direction = 'D'; + } + + break; + + case 'D': + + // Check if left position is white + if (isWhite(x - 1, y, pRows)) { + --x; + direction = 'L'; + } + + // Check if down position is white + else if (isWhite(x, y + 1, pRows)) { + ++y; + direction = 'D'; + } + + // Check if right position is white + else if (isWhite(x + 1, y, pRows)) { + ++x; + direction = 'R'; + } + + // Turn 180 + else { + --y; + direction = 'U'; + } + + break; + } + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/algo.h Sun Oct 16 14:13:37 2022 +0200 @@ -0,0 +1,14 @@ +// +// Created by Dennis Concepción Martín on 15/10/22. +// + +#ifndef MAZE_SOLVER_ALGO_H +#define MAZE_SOLVER_ALGO_H + +#include <png.h> +#include <stdio.h> +#include <stdlib.h> + +void wallFollower(png_bytep* pRows, unsigned int width); + +#endif //MAZE_SOLVER_ALGO_H
--- a/build_library.sh Fri Oct 14 17:11:49 2022 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1 +0,0 @@ -cc -fPIC -shared -o main.so main.c \ No newline at end of file
--- a/main.c Fri Oct 14 17:11:49 2022 +0200 +++ b/main.c Sun Oct 16 14:13:37 2022 +0200 @@ -1,22 +1,102 @@ -#include <stdio.h> +#include "algo.h" + +int main(int argc, char* argv[]) { + char* fileName; + int numberOfPhases; + unsigned int width, height; + + png_structp pngStruct; + png_infop pngInfo; + png_byte colorType; + png_byte bitDepth; + png_bytep* pRows; + + if (argc < 2) { + printf("Incorrect arguments\n"); + abort(); + } + + // Get user arguments + fileName = argv[1]; -int main(int argc, char *argv[]) { -// int i; + // Add path to filename + asprintf(&fileName, "mazes/%s", fileName); + + FILE *fp = fopen(fileName, "rb"); + + if (!fp) { + printf("Error opening image named %s\n", fileName); + abort(); + } -// printf("There are %d arguments\n", argc); + // Allocate and initialize a pngStruct for reading PNG file + pngStruct = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); + + if (!pngStruct) { + printf("png_create_read_struct failed\n"); + abort(); + } + + // Allocate and initialize a pngInfo structure + pngInfo = png_create_info_struct(pngStruct); + + if (!pngInfo) { + printf("png_create_info_struct failed\n"); + } -// for (i = 0; i < argc; i++) { -// printf("Arg %d: %s\n", i, argv[i]); -// } + /* + * When libpng encounters an error, it expects to longjmp back to your routine. + * Therefore, you will need to call setjmp and pass your png_jmpbuf(pngStruct). + * More about setjmp -> https://es.wikipedia.org/wiki/Setjmp.h + */ + + if (setjmp(png_jmpbuf(pngStruct))) { + printf("Error during init_io\n"); + abort(); + } + + png_init_io(pngStruct, fp); // Initialize the default input/output functions for the PNG file + png_set_sig_bytes(pngStruct, 0); // Set signature bytes + png_read_info(pngStruct, pngInfo); // Read info + + width = png_get_image_width(pngStruct, pngInfo); + height = png_get_image_height(pngStruct, pngInfo); + colorType = png_get_color_type(pngStruct, pngInfo); + bitDepth = png_get_bit_depth(pngStruct, pngInfo); + + numberOfPhases = png_set_interlace_handling(pngStruct); + png_read_update_info(pngStruct, pngInfo); - int abc[5][4] ={ - {0,1,2,3}, - {4,5,6,7}, - {8,9,10,11}, - {12,13,14,15}, - {16,17,18,19} - }; + printf("Image width: %d\n", width); + printf("Image height: %d\n", height); + printf("Color type: %d\n", colorType); + printf("Bit depth: %d\n", bitDepth); + printf("Number of phases: %d\n", numberOfPhases); + + // Read file + if (setjmp(png_jmpbuf(pngStruct))) { + printf("Error during read_image"); + abort(); + } + + pRows = (png_bytep*) malloc(sizeof(png_bytep) * height); + for (int y = 0; y < height; y++) { + pRows[y] = (png_byte *) malloc(png_get_rowbytes(pngStruct, pngInfo)); + } + + // Read the image into memory + png_read_image(pngStruct, pRows); + fclose(fp); + + wallFollower(pRows, width); + + // Cleanup heap allocation + for (int y = 0; y < height; y++) { + free(pRows[y]); + } + + free(pRows); return 0; } \ No newline at end of file
--- a/main.py Fri Oct 14 17:11:49 2022 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -import os -import ctypes -import sys - -from PIL import Image - -PATH = os.getcwd() - - -def main(): - with Image.open(f'{PATH}/mazes/maze.png') as image: - width, height = image.size - pixels = image.load() - - print('') - print(f'Image name: {sys.argv[1].split(".")[0]}') - print(f'Image format: {image.format}') - print(f'Image width: {width} pixels') - print(f'Image height: {height} pixels') - - matrix = [] - for y in range(height): - row = [] - for x in range(width): - r, g, b, _ = pixels[x, y] - if (r, g, b) == (0, 0, 0): - row.append(0) - elif (r, g, b) == (255, 255, 255): - row.append(1) - else: - print(f'Incorrect pixel color at x: {x}, y: {y}') - exit(1) - - matrix.append(row) - - dll = ctypes.CDLL(f'{PATH}/main.so') - dll.main.argtypes = [ctypes.c_int, ctypes.POINTER(ctypes.c_char_p)] - args = (ctypes.c_char * 1)([b'123']) - dll.main(len(args), args) - - -if __name__ == '__main__': - if len(sys.argv) == 2: - main() - else: - print('Incorrect arguments')