Navigation System in C

A terminal-based program that simulates a robot automatically finding its path through a maze using BFS (Breadth-First Search), with a step-by-step animation. Built in C as part of Hack Club Stardance.

What it does

The program places a robot (x) at position (0,0) and finds the shortest path to the destination (D) in the bottom-right corner, through a maze of obstacles (#). The path is then animated tile by tile in the terminal, and replayed at a faster speed once the robot arrives.

Two versions

File	Maze	Size
navegacaoauto_v2.c	read from standard input	any, chosen at runtime
navegacaoauto.c	hardcoded in eh_obstaculo()	fixed 10×10

navegacaoauto_v2.c is the current one, and the one the build system and the release binaries use. navegacaoauto.c is kept because it is what the earlier releases shipped.

Running it

v2 asks for the dimensions, then reads that many rows:

$ robot-maze
Linhas: 5
Colunas: 5
Introduz o mapa linha a linha (usa '.' para livre e '#' para obstaculo):
.....
###.#
....#
.####
.....

Any character that is not . or # is treated as free space. The program exits with a message if the maze has no route, or if either corner is walled in.

Feeding it from a pipe or a file works the same way:

printf '5\n5\n.....\n###.#\n....#\n.####\n.....\n' | robot-maze

How it works

The pathfinding uses BFS (Breadth-First Search):

1. Starting at (0,0), the algorithm explores all reachable cells layer by layer
2. Each visited cell records its parent — where it came from
3. Once the destination is reached, the path is reconstructed backwards through the parent matrix
4. The path is reversed, then animated step by step using clear() and usleep()

Because BFS expands cells in order of distance from the start, the first route that reaches the destination is necessarily the shortest one.

In v1 the maze layout lives in eh_obstaculo(), completely separate from the pathfinding logic — changing the maze only requires editing that one function. v2 moves it to a heap-allocated grid read at startup instead.

Build & Run

make            # -> build/robot-maze
./build/robot-maze

The build uses -std=gnu17 -Wall -Wextra -O2 and is warning-free on GCC 16 and on mingw-w64. -std=c17 specifically does not work: usleep() is an XSI function that glibc hides under strict ISO mode.

Without make:

gcc navegacaoauto_v2.c -o robot-maze

Windows

Cross-compiled from Linux with mingw-w64:

sudo pacman -S mingw-w64-gcc            # Arch
sudo apt install gcc-mingw-w64-x86-64   # Debian / Ubuntu

make windows                            # -> build/robot-maze.exe

If the toolchain is not on $PATH, point CROSS at it:

make windows CROSS=/path/to/bin/x86_64-w64-mingw32-

The .exe is linked -static, so it runs on a plain Windows install with no runtime DLLs next to it. Compiling on Windows directly also works, under MinGW or MSYS2:

gcc navegacaoauto_v2.c -o robot-maze.exe

Packages

make packages   # -> dist/*.deb, dist/*.pkg.tar.zst, dist/*-src.tar.gz

make deb builds the Debian package with ar and tar rather than dpkg-deb, so it works on a machine with no dpkg installed. make arch runs makepkg against packaging/PKGBUILD, which pins a git tag — so that tag has to exist on the remote first.

Installing

Pre-built binaries and packages are in Releases.

# Debian, Ubuntu, Mint
sudo apt install ./robot-maze_3.0.1_amd64.deb

# Arch, Manjaro, EndeavourOS
sudo pacman -U robot-maze-3.0.1-1-x86_64.pkg.tar.zst

# Anything else
sudo make install       # -> /usr/local/bin/robot-maze
sudo make uninstall

make install honours PREFIX and DESTDIR.

Limits

• Dimensions are capped at 1000×1000. The cap keeps linhas * colunas inside an int, so no allocation size can overflow, and a board bigger than that is not animatable in a terminal anyway.
• A row longer than the declared width is truncated and the excess discarded, so it cannot bleed into the next row.
• A row shorter than the declared width — or input that ends early — is padded with free space.
• Non-numeric dimensions are rejected instead of being read as whatever was on the stack.

Every allocation is checked and the maze is freed on every exit path. Verified with AddressSanitizer, UndefinedBehaviorSanitizer and LeakSanitizer over eleven inputs, including a 300-column maze, truncated input, a blocked start and an unreachable destination.

What I learned

• How BFS works and why it guarantees the shortest path
• How to implement a queue manually in C using arrays
• How to use a parent matrix to reconstruct a path after traversal
• Why BFS gives you the path backwards and how to reverse it
• How usleep() and terminal clearing create smooth terminal animations

Challenges

The biggest challenge was understanding BFS before writing a single line of code. I spent most of the time drawing it on paper, watching explanations, and trying to wrap my head around how the parent matrix actually works. The moment it clicked was thinking of it as water spreading through a maze — it fills every reachable cell layer by layer until it hits the destination.

The second challenge was path reconstruction. BFS naturally gives you the path backwards from destination to start, so reversing it correctly before animating took a few tries to get right.

Tech stack

• C (gnu17; v1 was written to C99)
• Standard library only: stdio.h, stdlib.h, string.h, unistd.h / windows.h
• Compiled with GCC, cross-compiled for Windows with mingw-w64

License

MIT. See LICENSE.