Hrvatsko društvo za robotiku - Uvod u robotiku - vježbe

...
	uint8_t maze[30][30][5];
...

Kako robot napreduje po labirintu, otkriva pozicije zidova i drugih objekata. Za uspješno izvršenje zadatka, on ih mora pamtiti - spremati u varijable.

Budući da je labirint dio kvadra, polje (array) je struktura podataka za pohranu koja na prvi pogled izgleda najbolja. Recimo nešto kao na lijevoj strani: baza je kvadrat 30 x 30 polja², visine 5. Recimo da ne očekujemo labirint veći od onog koji bi stao u ovaj kvadar. U svaki element polja (array) spremimo zidove, koristeći kompresiju iz prethodne vježbe i zadatak je riješen. Je li na najbolji način? Vidite li probleme?

Prvi je problem što je polje (array) (pažnja, ovdje je "polje" homonim) veliko, ali i dalje moguće premalo. Mi ne znamo s kojeg polja (pločice) kreće robot, tako da je razumno staviti ga u sredinu labirinta (polja - array). Niti znamo s kojeg kata kreće, tako da ga je razumno staviti na 3. kat. Nakon ovih akcija je labirint ograničen na širinu od 15 polja (pločica) i visinu 3. Znači, bilo bi razumno uzeti još veće polje (array) ili imati algoritam (dodatna, bitna komplikacija), koji korigira početnu poziciju robota, ako dođe do ruba polja (array).

Uočite i da je količina potrošene memorije raste s trećom potencijom proporcionalnog povećanja bridova kvadra.

Problem je što treba velika količina memorije, koja će velikom većinom biti neiskorištena.

To nije sve. Robot mora pamtiti sliku labirinta, kakvu je vidio, bar u trenutku kad je bio na posljednjem srebrenom polju. Što odmah povećava potrebnu memoriju još 2 puta.

ESP32 ima dosta RAMa, tako da bi ovo na kraju i moglo proći, do neke mjere. Za manje mikrokontrolere je ovakav pristup katastrofalan.

...
class Tile {

	uint8_t _wall; // 1 byte stores statuses for all 2 ...
	uint8_t _surface; // 1 byte stores surface and other ...
	Tile* _chain; // Pointer to the next tile in chain.
	...
}

U skladu s dosadašnjom praksom izbjegavanja objašnjavanja kompliciranih pojmova, ovdje ćemo u par crta objasniti pojam koji nam treba.

"Tile" je klasa, unutar datoteke "mrm-robot-maze.h", pojam koji će opisati jednu pločicu labirinta.

Dio opisa je "_wall", varijabla koja sprema izgleda zidova, "_surface" (kakav je pod) i, najzanimljiviji, "_chain".

Potonji je veza kojom možemo programski doći do sljedeće pločice. Ovdje se ne radi o prolazu (putu bez zidova), nago načinu na koji su pločice nanizane jedna iza druge s ciljem da ih programski možemo sve obići.

...
class Tile {

...
	
public:
	static Tile* first; // Static member variable (one ...
...
}

Da bismo došli do vezane liste, treba nam samo početak iste, koji se nalazi u varijabli "first". "first" nam kaže kako programski možemo doći do prve pločice, njen "_chain" kako do sljedeće, itd. Sve dok "_chain" ne pokaže na ništa - znači došli smo do kraja liste.

Taktika bi sad bila da, kako napredujemo po labirintu, i nalazimo nove pločice, da ih sve ubacujemo u ovaj niz.

Da bismo našli što je na nekoj poziciji labirinta, svaki put prođemo cijelu listu programski. Nećemo u ovom času objašnjavati kako to učiniti, nego se koncentrirajmo na gornji problem, potrošnju memorije. Kako se pamte samo polja koja su stvarno dio labrinta, potrošnja drastično opada.

Ako želimo vratiti situaciju u trenutak kad je robot prvi put došao da neko polje, samo u njemu stavimo da je "_chain" ništa i tako odrežemo svu budućnost. Znači da se možemo vratiti na bilo koje polje bez da išta posebno spremamo!

Naoko bi ovo šetanje po listi moglo biti skupo što se tiče brzine obrade, ali nije. Uvijek je najbolje provjeriti mjerenjem.