Acest repo conține un proiect C care rezolvă problema planificării unui traseu pentru un rover care pornește dintr-o poziție cunoscută într-o hartă 2D de 100×100 pixeli și trebuie să ajungă la o țintă. Harta este generată din canalul roșu al unei imagini RGB (100×100). Canalul roșu este normalizat la [0,1] și scalat la înălțimi între 0m și 3m. Fiecare pixel pe axele orizontală/verticală corespunde 0.1m în lumea reală.

Proiectul include:

• generare imagine/text (simulare hartă) — generate.c, generate.h
• prelucrare canal roșu / blur / salvare matrice — prelucrate_matrix.c / prelucreate_matrix.c / prelucreate_matrix.h
• planificare drum (BFS minimal + Dijkstra cu heap) — main.c
• coadă de prioritate (min-heap) — heap.c, heap.h
• Makefile cu reguli utile

Problema (cerințe)

• Rover-ul pornește de la (1,1)
• Traseul trebuie găsit până la un punct țintă.
• Panta maximă permisă este 30° (folosim pragul normalizat pentru diferența de înălțime; în cod e MAX_HEIGHT).
• Se poate alege mișcare pe 4 sau 8 direcții (codul folosește 8 vecini de tip king move implicit).
• Harta este rezultatul extragerii canalului roșu, normalizat, eventual blur-at.
• Ca extensie: se poate utiliza un cost map mai avansat ținând cont de gradient.

Fișiere importante

• generate.c, generate.h — generează o imagine RGB 100×100 (vector image_data) cu valori aleatoare, salvează output.ppm (P6) și image.txt (valori R G B) și produce matrix.txt = canalul roșu blur-uit normalizat (100×100 double). srand(time(NULL)) este folosit pentru a varia rezultatele.
• prelucreate_matrix.c, prelucreate_matrix.h — funcții utilitare pentru citit image.txt/matrix.txt și scris imagini PPM (save_ppm_image), folosite de main.c și generate.c.
• prelucrate_matrix.c — (există variante în repo): prelucrare pentru extract red channel + blur + salvare text.
• heap.c, heap.h — implementare de min-heap folosită ca priority queue în Dijkstra. Elementele stocate sunt item_t { double d; int v; } (d = distanță, v = index nod). API: heap_create, heap_push, heap_pop, heap_empty, heap_free.
• main.c — implementează două strategii:
  • lee(...) — BFS/Lee (discrete steps) pentru a găsi un drum minim în număr de pași (folosește matrice matrix_viseted etc.)
  • dijkstra(...) — algoritm Dijkstra pe graf implicit (fiecare pixel = nod). Înălțimea pixelului e h = normalized_red * 3.0 (0..3m). Costul de intrare într-un vecin v este max(0, height[v] - height[u]) (adică doar efortul la urcare), sau un cost mai avansat poate include gradient.

Cum se compilează și rulează

Folosește Makefile (există 3 reguli cerute): generate (numai generator), main (numai planificator) și both (ambele). Exemple:

make generate     # compilează ./generate
./generate        # produce output.ppm, image.txt, matrix.txt

make main         # compilează ./main (linkează și generate utilities)
./main            # folosește matrix.txt + image.txt și produce output_dijkstra.ppm

make both         # compilează ambele
make run          # compilează ambele și rulează (dacă Makefile definește run)

make clean        # sterge fisierele create de program, imaginile pmp si matricele

Input / Output

• image.txt — textual: R G B triplete pentru fiecare pixel (folosit de prelucrate/main).
• matrix.txt — 100×100 valori double (normalizate) obţinute din canalul roşu şi blur.
• output.ppm, output_dijkstra.ppm — imagini PPM (P6) vizuale: generate salvează imaginea aleatorie, main salvează aceeaşi imagine peste care se suprapune traseul rezultat pe canalul rosu (se poate observa cum pe masura ce se aproprie de punctul de finish, se accentueaza intensitatea culorii).
• la iesirea de la consola, se vor afisa 2 drumuri sub forma de perechi de puncte: drumul cu distanta minima si drumul cu inaltimea urcata minima

Detalii algoritmice

1. Normalizare & scalare

• Canalul roşu este extras ca valori între 0..255. Se normalizează la [0,1] prin împărţire la 255.0. Height = normalized * 3.0 (metri).

2. Blur

• Se aplică un blur 3×3 (medie) pe canalul binarizat/roşu pentru a reduce zgomotul: pentru fiecare pixel se face media vecinilor (cu verificare de limită pe margini). Implementarea din generate.c folosește un buffer temporar temp_matrix (size 100*100) pentru a calcula media.

3. Graful și Dijkstra

• Model de noduri: fiecare pixel i,j e nodul indexat idx = i * 100 + j.
• Vecini: pentru 8‑neighbours folosim offset‑urile (di,dj) = { (1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1) }.
• Cost de a intra într-un vecin v din u: cost(u->v) = max(0, height[v] - height[u])
  • astfel coborârile nu costă, urcările au cost egal cu dif de înălţime.
• Prag vertical: în cod e folosit MAX_HEIGHT, inaltimea maxima pe care o poate urca robotul echivalent pantei de 30 de grade. Acesta este 0.58m, iar avand in vedere ca avem normalizata matricea [0,1] - [0, 3m], in cod constanta ajunge 0.19

4. Heap (priority queue)

• Foloseşte heap_t *h creat cu heap_create(cap). Elementele sunt item_t { double d; int v; }.
• heap_push(h, alt, v) inserează elementul prin "sift up" (variabile folosite: i, p, it, h->a).
• heap_pop(h, &d, &u) scoate rădăcina, înlocuieşte cu last = h->a[--h->size] şi "sift down" (i, l, r, smallest, last). Implementarea foloseşte metoda de copiere (copy‑down) mai degrabă decât swap‑uri repetate.

5. Reconstrucţia traseului

• prev[v] stochează predecesorul imediat (indexul nodului) — pentru a reconstrui traseul se porneşte de la target şi se urmează prev[] până la sursă.
• Dacă dist[target] rămâne INF (evaluat ca e.g. >= 1e299) atunci nu există drum.