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

Tremaux

Cilj

Tremauxov algoritam za kretanje po labirintu.

Algoritam i inicijalizacija

void RobotMaze::decide(){
	...
	actionMove->direction = Direction::NOWHERE; // Initialize direction.
	...
}
Funkcija "decide()" implementira Tremauxov algoritam.

On glasi: ako postoji slobodan izlaz na novo polje, izaberi bilo koji. Ako ne postoji, vrati se na polje s kojeg si došao.

Na taj način se obiđu sva polja labirinta.

Na početku postavimo da varijabla "direction" ne pokazuje nikamo.

Traženje slobodnog smjera

void RobotMaze::decide(){
	...
	actionMove->direction = Direction::NOWHERE; // Initialize direction.
	for (uint8_t i = 0; i < 4; i++) {
		Direction dir = (Direction)i; 
		if (tileCurrent->wallGet(dir) == WallStatus::NO_WALL && 
				tileContaining(x(dir), y(dir)) == NULL) {
			actionSet(actionMove); 
			actionMove->direction = dir;
			break;
		}
	}
	...
}
"for" broji od 0 do 3.

U sljedećem redu brojeve pretvaramo u smjerove, tako da "for" nabraja (sprema u varijablu "i") sva 4 smjera: gore, dolje, lijevo i desno.

"if" ispituje ima li u tom smjeru zida i jesmo li već posjetili ovu pločicu.

Potonja se provjera izvršava funkcijom "tileContaining()", koja prođe cijeli lanac spremljenih polja i pogleda ima li u njemu pločica s koordinatama pločice koja je u traženom smjeru.

Ako nema zida i nismo posjetili pločicu, to je smjer u kojem ćemo ići dalje.

Kao sljedeća akcija se sprema pokret prema naprijed u smjeru koji proučavamo.

Kao smjer kretanja se sprema nađeni smjer i prekida se "for".

Ako u "for"u nije nađen nijedan smjer, na kraju će u "actionMove->Direction" biti zapisano da nema smjera i na taj način ćemo znati da nema slobodnog puta do novog polja - ne možemo više napredovati.

Povratak na prethodno polje

void RobotMaze::decide(){
	...
	if (actionMove->direction == Direction::NOWHERE) {
		if (tileCurrent->breadcrumb == Direction::NOWHERE) {
			end();
			mrm_8x8a->bitmapCustomStoredDisplay(LedSign::MAZE_LED_PAUSE);
			motorGroup->stop();
			print("END\n\r");
		}
		else {
			print("Go back\n\r");
			actionMove->direction = tileCurrent->breadcrumb; 
			actionSet(actionMove);
		}
	}
}
"if" će biti izvršen ako nije nađen slobodan smjer.

Ako ne postoji smjer povratka (unutarnji "if"), znači da smo na prvoj pločici i obilazak labirinta je gotov.

Ispišemo da se to dogodilo.

U slučaju da postoji put natrag, postavimo za sljedeću akciju kretanje naprijed u smjeru mrvica kruha, koje pokazuju put vraćanja na prethodno polje.

Broj koraka

void RobotMaze::decide(){
	...
	
	if (stepCount++ >= MAZE_MAX_STEPS) {
		motorGroup->stop();
		end();
	}
}
Završni "if" nije potreban za algoritam, nego služi za testiranje programa. Ako želimo da robot stane nakon određenog broja koraka, upišemo "MAZE_MAX_STEPS".

Zadatak: broj koraka

Ispišite na 8x8 displej koliko je robot prošao pločica.

Primjedbe



Projekt "Uvod u robotiku" sufinanciran je iz Europskog socijalnog fonda, poziv "Jačanje kapaciteta organizacija civilnoga društva za popularizaciju STEM-a". Relevantne stranice: Sadržaj vježbe za virtualne radionice isključiva je odgovornost Hrvatskog društva za robotiku.