[Bascom] Micromouse kłopot z zapisaniem mapy

[zuba1]

Witam.Przymierzam się właśnie do robota micromouse 😃 .Kłopot brzmi tak: nie wiem jak zrobić mapę w czasie przejazdu a potem za jej pomocy wyznaczyć najkrótszy dystans do mety a tym bardziej jak powrócić na start.Zastanawiałem się na pewnymi tabelami o których wyczytałem w Google i na forbocie.https://www.forbot.pl/forum/topics20/micromouse-metody-przeszukiwania-labiryntu-vt2246.htm.Niemam pojęcia jak napisać tę tabelę a co gorsze ją odczytać proszę o pomoc z góry dzięki

 'Robot "mały" procesor atmega8(L) rok2012 by zuba1

                   $regfile = "m8def.dat"
$crystal = 8000000

Config Pinc.0 = Input
Config Pinc.1 = Input
Config Pinc.2 = Input
Config Pinc.3 = Input

Config Portd.5 = Output
Config Portd.1 = Output
Config Portd.2 = Output
Config Portd.3 = Output
Config Portd.4 = Output

'silniki
Led Alias Portc.5
Lewoprzud Alias Portd.1
Lewotyl Alias Portd.2
Prawoprzud Alias Portd.3
Prawotyl Alias Portd.4

'czujniki
Czl Alias Pind.3                                            'czujnik lewy
Czp Alias Pind.1                                            'czujnik prawy
Cz Alias Pinc.2                                             'czujnik przedni
'klawisze
Sw1 Alias Pinc.0
Set Pinc.0
'menu
Dim Tryb As Byte
'wybieranie kierunku jazdy
Dim Losuj As Byte

Led = 1

Tryb = 0

Cls                                                         'ta komenda inicjalizuje obsluge LCD i go czysci
Upperline                                                   'ustaw kursor w gornej linii
Lcd "witaj"

Lowerline                                                   'ustaw kursor w dolnej linii
Lcd ""
Wait 1
Cls                                                         'ta komenda inicjalizuje obsluge LCD i go czysci
'******************************************************
Do

If Sw1 = 1 And Tryb = 0 Then
Waitms 30
Gosub Szukanie
End If

Upperline                                                   'ustaw kursor w gornej linii
Lcd "wybierz"

Lowerline                                                   'ustaw kursor w dolnej linii
Lcd "tryb [" ; Tryb ; "]"

Waitms 100

Loop

'**************************************************************

Szukanie:
Cls

Upperline                                                  'ustaw kursor w gornej linii
Lcd "micro"

Lowerline                                                  'ustaw kursor w dolnej linii
Lcd "mouse"

Do
'miejsce na program

If Losuj > 1 Then Losuj = 0

'1=nic 0= wykryte
'podstawowe ruchy
If Czl = 1 And Cz = 0 And Czp = 1 Then
Gosub Go
Incr Losuj
End If

If Czl = 0 And Cz = 1 And Czp = 1 Then
Gosub Lewo
Incr Losuj
End If

If Czl = 1 And Cz = 1 And Czp = 0 Then
Gosub Prawo
Incr Losuj
End If

'**************
'zawansowane
If Czl = 1 And Cz = 0 And Czp = 0 And Losuj = 0 Then
Gosub Prawo
Incr Losuj
End If

If Czl = 1 And Cz = 0 And Czp = 0 And Losuj = 1 Then
Gosub Go
Incr Losuj
End If

If Czl = 0 And Cz = 0 And Czp = 1 And Losuj = 0 Then
Gosub Lewo
Incr Losuj
End If

If Czl = 0 And Cz = 0 And Czp = 1 And Losuj = 1 Then
Gosub Go
Incr Losuj
End If
'*******************************
If Czl = 0 And Cz = 0 And Czp = 0 Then
Gosub Prawo
Incr Losuj
End If

If Czl = 1 And Cz = 1 And Czp = 1 And Losuj = 0 Then
Gosub Go
Incr Losuj
End If

If Czl = 1 And Cz = 1 And Czp = 1 And Losuj = 1 Then
Gosub Prawo
Incr Losuj
End If

Loop
Return


  End
'***************************************************************************
  Stopp:
  Lewoprzud = 0
  Lewotyl = 0
  Prawoprzud = 0
  Prawotyl = 0
  Return

  Go:
  Lewoprzud = 1
  Lewotyl = 0
  Prawoprzud = 1
  Prawotyl = 0
  Return

  Tyl:
  Lewoprzud = 0
  Lewotyl = 1
  Prawoprzud = 0
  Prawotyl = 1
  Return

  Lewo:
  Lewoprzud = 0
  Lewotyl = 1
  Prawoprzud = 1
  Prawotyl = 0
  Return

  Prawo:
  Lewoprzud = 1
  Lewotyl = 0
  Prawoprzud = 0
  Prawotyl = 1
  Return

[Treker (Damian Szymański)]

Mapę tablicy można zbudować na tablicach dwuwymiarowych, których w Bascomie nie masz. Z tego co pamiętam, można w nim zrealizować to na mechanizmie wektorów, ale nigdy dokładniej się tym nie interesowałem.

[zuba1]

Czyli jak to zrobić aby zapisać poszczególne kroki ???

[ Dodano: 26-03-2012, 22:00 ]

wpadłem na pomysł aby każdy czujnik miał swoją własną zmienną typu bit a potem zapisywał to w tablicy ciągu 256 jedynek i zer kłopot był by z ustaleniem kolejności odczytu nie wiem jak to zrobić

[Treker (Damian Szymański)]

Wszystko jest w artykule, który sam podlinkowałeś w pierwszym poście. Akurat to o czym mówisz jest stosunkowo proste w porównaniu do regulatorów i algorytmów jakie należałoby użyć do tego, aby mysz poruszała się równo w labiryncie i nie obijała się o ściany,

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[zuba1]

Oto drugie się nie martwię zarazie chcę opanować obsługę i pracę tablicy nie wiem tylko jak kolejno zapisywać dane.Nie wiem też jak je odczytać i ułożyć trasę.

[Treker (Damian Szymański)]

Chyba jednak tego nie przeczytałeś:

https://www.forbot.pl/forum/topics20/micromouse-metody-przeszukiwania-labiryntu-vt2246.htm

Zwróć uwagę na WIELKI punkt: Sporządzanie mapy labiryntu w pamięci robota

[mog123]

zuba1 - Poczytaj o mapowaniu pikseli w bitmapach.

przykładowo:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

reprezentuje labirynt 4x4.

odwołując się do komórki ij w przypadku użycia tablic dwuwymiarowych zrobisz to tak:

odczytana_komorka = Labirynt[j];

Z powyższego przykładu, aby odwołać się do 6 to za i (licząc od 0 do 3) podstawiasz 1, tak samo za j podstawiasz 2. Czyli Labirynt[1][2] = 6;

W przypadku indeksowania jednowymiarowego (oszczędniejszego) - Robisz to na zasadzie offsetu, gdzie offset to szerokość labiryntu. I tym samym odnosząc się do komórki i,j robisz to tak:

odczytana_komorka = Labirynt[offset*i+j];

podstawiając za szerokość labiryntu 4, oraz wczesniejsze i=1 oraz j=2 otrzymujemy Labirynt[1*4+2] = 6;

Mam nadzieję że rozjaśniłem.

[BlackJack]

W BASCOM nie ma tablic wielowymiarowych co nie znaczy że się nie da stworzyć tablicy dwuwymiarowej na podstawie jednowymiarowej.

Załużmy że chcemy mieć tablicę 16x16, czyli 256 elementów.

Deklarujemy więc tablicę:

DIM TAB[256] as Byte

Teraz tak element [1][5] ([X][Y]), będzie miał adres = 5, bo jest to pierwszy wiersz i piąty element.

Natomiast element [2][5] będzie miał adres = 16+5 czyli 21. Jak teraz to ugryźć.

Otóż napisać sobie odpowiednią procedurę dostępu i pierwsze indeksy które nazwiemy sobie X liczyć od zera. Dla Zera adresem jest wartość Y, dla wartości większych od zera, jest to podstawa czyli 16 podniesiona do X + y.

PS, dokończę później oderwały mnie inne sprawy.

[rasta]

[...]

Dla Zera adresem jest wartość Y, dla wartości większych od zera, jest to podstawa czyli 16 podniesiona do X + y.

PS, dokończę później oderwały mnie inne sprawy.

Raczej razy X ;]

Prościej:

1 2 3

4 5 6

7 8 9

zamieniasz na:

1 2 3 4 5 6 7 8 9

element [j] w pierwszej tablicy to element [i*liczba_kolumn+j] w drugiej, przy założeniu, że elementy numerowane są od 0.

[MatManiak]

zuba1 - Poczytaj o mapowaniu pikseli w bitmapach.

przykładowo:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

reprezentuje labirynt 4x4.

odwołując się do komórki ij w przypadku użycia tablic dwuwymiarowych zrobisz to tak:

odczytana_komorka = Labirynt[j];

Z powyższego przykładu, aby odwołać się do 6 to za i (licząc od 0 do 3) podstawiasz 1, tak samo za j podstawiasz 2. Czyli Labirynt[1][2] = 6;

W przypadku indeksowania jednowymiarowego (oszczędniejszego) - Robisz to na zasadzie offsetu, gdzie offset to szerokość labiryntu. I tym samym odnosząc się do komórki i,j robisz to tak:

odczytana_komorka = Labirynt[offset*i+j];

podstawiając za szerokość labiryntu 4, oraz wczesniejsze i=1 oraz j=2 otrzymujemy Labirynt[1*4+2] = 6;

Mam nadzieję że rozjaśniłem.

Sprecyzuj "oszczędniejsze". Jak rozumiem, podany przykład z tablicą dwuwymiarową jest w C, bo jak Treker napisał wyżej, w BASCOMie nie ma czegoś takiego jak labirynt[j]. Zatem, w C/C++ jak zdefiniuję sobie 2 tablice:

char t1[4][4];
char t2[16];

to obydwie tablice zajmują 16 bajtów pamięci, a wyrażenie:

(sizeof(t1)==sizeof(t2)) 

jest równie TRUE. Nie wiem więc co miałeś na myśli pisząc, że robienie tylko jednego indeksowania jest oszczędniejsze - ja bym napisał wręcz na odwrót, bo jak sam napisałeś, by odwołać się do komórki i,j muszę wykorzystać mnożenie:

t2(offset*i+j)

a jak wiadomo, mnożenie na mikrokontrolerach jest kosztowne, w każdym bądź razie na pewno kosztowniejsze niż odwołanie do tablicy dwuwymiarowej, która zajmuje tyle samo pamięci.

Chyba, że ja czegoś nie wiem, to chętnie się dowiem, dlaczego rozwiązanie z offsetem jest oszczędniejsze i w jakim aspekcie (czas? pamięć?) 😉

[koval_blazej]

ja bym napisał wręcz na odwrót, bo jak sam napisałeś, by odwołać się do komórki i,j muszę wykorzystać mnożenie:

a jak wiadomo, mnożenie na mikrokontrolerach jest kosztowne, w każdym bądź razie na pewno kosztowniejsze niż odwołanie do tablicy dwuwymiarowej, która zajmuje tyle samo pamięci.

Procesor myślisz jak znajduje odpowiednią komórkę jak nie poprzez identyczną procedurę z mnożeniem, skoro jedyną informacją jest wskaźnik na pierwszy element? Wychodzi w sumie na to samo.

Jeśli już faktycznie chcemy tak starannie oszczędzać tych obliczeń procesorowi, trzeba by myśleć o wskaźnikach.

[BlackJack]

No kurcze. Zapomniałem wam tu napisać, jak w BASCOM zrobić z tablicy 1 wymiarowej dwuwymiarową. Wieczorem, albo jutro postaram się nadrobić. Trzeba sobie napisać odpowiednią procedurę mapującą.

[marek1707]

Myślę Koledzy, że niepotrzebnie kruszycie kopie. Optymalizacja programu jest ważnym krokiem ale konieczność jej przeprowadzenia oceniana jest pod koniec pracy, gdy już działają algorytmy, gdy program liczy poprawne wyniki ale jest za wolny. I to za wolny w stosunku do rzeczywstych wymagań. Jeśli coś liczy się długo ale wystarczająco krótko by to zakceptować, jest dobre. Bardzo słusznie, że marwicie się o biedny procesor. Rzeczywiście, pisząc rozrzutny program bardzo łatwo "zajechać" go (procesor) tak, że nie zostanie już mocy obliczeniowej choćby na sterowanie silnikami. Ale pozwólcie sobie przekonać się o tym później. Być może poświęcacie czas i środki na rzeczy zupełnie drugorzędne. Zuba1, najpierw napisz prawidłowy, dobrze działający program. Napisz go tak, jak najlepiej umiesz i w taki sposób, by był dla Ciebie jak najlepiej zrozumiały. Bo program, wbrew pozorom wcale nie jest pisany dla komputera. Programy w językach wysokiego poziomu piszemy dla nas samych. Przecież tylko z powodu ogromu pracy, jaki kosztowało napisanie, przetestowanie i późniejsza konserwacja programów w językach asemblera (lub wcześniej binarnych) zostały języki algorytmiczne stworzone. One są dla nas. Przy obecnym poziomie kompilatorów i optymalizatorów wiele z drobnych zadań już dawno zostało z nas zdjęte. Jednym z nich jest właśnie dostęp do tablic. Czy ktoś z Was pochylił się nad kodem wynikowym choćby z GCC? Niezależnie od tego, czy jawnie użyjemy wskaźnika, czy nazwy tablicy (która de facto jest wskaźnikiem) w połączeniu z jednym nawiasem kwadratowym liczącym trochę na okrągło index do tablicy "dwuwymiarowej" czy też wprost wstawimy dwie pary nawiasów kwadratowych i tak wszystko wyląduje na wejściu optymalizatora jako kod pośredni wyrażający w dość abstrakcyjny sposób to, co chcemy zrobić. Może jakiś przykład będzie dobrym obrazem tego, o czym piszę.

Stwórzmy dwie zmienne, x i y do których gdzieś wcześniej policzyliśmy współrzędne komórki, do której chcemy się dobrać. Aby "zmusić" kompilator do ich użycia dodaję atrybut volatile. Inaczej optymalizator po prostu "zobaczy" co w nich jest, policzy to sobie na piechotę wcześniej i zwróci się "od razu" do dobrej komórki bez tej całej zabawy w liczenie adresów. To samo z dwiema tablicami: pierwsza dwuwymiarowa i druga jednowymiarowa ale będziemy w programie udawać, że dwu- więc będzie jawne mnożenie przy obliczaniu indeksu:

#define SIZE_X	4
#define SIZE_Y	4

volatile static uint8_t
 x,
 y,
 test2[SIZE_Y][SIZE_X],
 test1[SIZE_Y*SIZE_X];

m = test2[y][x];
n = test1[SIZE_X*y + x];

To teraz popatrzmy jak wygląda rzeczywisty ciąg instrukcji dla tak różnych sposobów dostępu:

	m = test2[y][x];
   5366:	e0 91 e3 02 	lds	r30, 0x02E3
   536a:	f0 e0       	ldi	r31, 0x00	; 0
   536c:	80 91 e4 02 	lds	r24, 0x02E4
   5370:	ee 0f       	add	r30, r30
   5372:	ff 1f       	adc	r31, r31
   5374:	ee 0f       	add	r30, r30
   5376:	ff 1f       	adc	r31, r31
   5378:	e8 0f       	add	r30, r24
   537a:	f1 1d       	adc	r31, r1
   537c:	ed 52       	subi	r30, 0x2D	; 45
   537e:	fd 4f       	sbci	r31, 0xFD	; 253
   5380:	e0 81       	ld	r30, Z

n = test1[SIZE_X*y + x];
   5382:	e0 91 e3 02 	lds	r30, 0x02E3
   5386:	80 91 e4 02 	lds	r24, 0x02E4
   538a:	f0 e0       	ldi	r31, 0x00	; 0
   538c:	ee 0f       	add	r30, r30
   538e:	ff 1f       	adc	r31, r31
   5390:	ee 0f       	add	r30, r30
   5392:	ff 1f       	adc	r31, r31
   5394:	e8 0f       	add	r30, r24
   5396:	f1 1d       	adc	r31, r1
   5398:	ed 53       	subi	r30, 0x3D	; 61
   539a:	fd 4f       	sbci	r31, 0xFD	; 253
   539c:	e0 81       	ld	r30, Z

Widzicie jakieś różnice, bo ja nie. Przyjrzyjmy się temu, co tak naprawdę nasza ATmega będzie robić:

Najpierw do pary rejestrów R31:R30 pobrała wartość zmiennej y. Ta zmienna jest 8-bitowa, więc do R30 załadowała sobie zawartość komórki pamięci o adresie 0x02E3 (tam kompilator, a właściwie linker przydzielił miejsce dla tej zmiennej) a do "starszego" rejestru R31 załadowała po prostu zero:

    5366:	e0 91 e3 02 	lds	r30, 0x02E3
   536a:	f0 e0       	ldi	r31, 0x00	; 0

Zaraz potem do R24 pobrała zawartość zmiennej x z komórki o adresie 0x02E4:

   536c:	80 91 e4 02 	lds	r24, 0x02E4

Teraz przyszedł czas na policzenie przesunięcia (offsetu) czyli "odległości" naszej komórki od początku tablicy. Najpierw mnożymy indeks y razy 2. Najprościej zrobić to dodając go (16-bitowo) do samego siebie. Dwie proste instrukcje napierw dodają R30 do R30 (umieszczając wynik w R30) a za chwilę dodają (z ew. przeniesieniem z poprzedniego dodawania - dlatego "adc") R31 do R31:

5370:	ee 0f       	add	r30, r30
5372:	ff 1f       	adc	r31, r31

Dwie takie operacje jedna po drugiej dadzą nam w sumie mnożenie przez 4:

    5374:	ee 0f       	add	r30, r30
5376:	ff 1f       	adc	r31, r31

Przyszedł czas na uwzględnienie współrzędnej x. Ta samą metodą procesor dodaje ją do wartości już naliczonej w R31:R30. Ponieważ nie istnieje instrukcja dodawania po "prostu zera", GCC przechowuje sobie takie bardzo przydatne zero zawsze w rejestrze R1

    5378:	e8 0f       	add	r30, r24
537a:	f1 1d       	adc	r31, r1

Tym sposobem w R31:R30 znalazła się liczba będąca przesunięciem naszej komórki wsględem początku tablicy, czyli wartość wyrażenia ((SIZE_X * y) + x). Teraz to już wystarczy dodać do tego adres początku tablicy i mamy gotowy adres komórki. Niestety tak jak nie istnieje (w AVR) instrukcja dodawania zera z przeniesieniem, tak nie istnieje instrukcja dodawania żadnej innej liczby użytej jako argument natychmiastowy. GCC użyło.. odejmowania. Wystarczy przecież odjąć liczbę ujemną, prawda? No to do dzieła. Pierwsza instrukcja odejmuje coś od R30, druga odejmuje coś innego od R31, oczywiście z ew. pożyczką wynikłą z poprzedniego odejmowania. Dlatego raz jest SUBI a raz SBCI:

    537c:	ed 52       	subi	r30, 0x2D	; 45
   537e:	fd 4f       	sbci	r31, 0xFD	; 253

A co one odjęły? Popatrzmy: pierwsza użyła liczby 45, druga 253. Jeśli przedstawimy to szesnastkowo i złożymy w liczbę 16-bitową dostaniemy 0xFD2D. W arytmetyce uzupełnieniowej do 2 jest to liczba ujemna. Po zmianie znaku (wystarczy kalkulator Windows i operacja 0-FD2D) mamy wynik: 0x02D3 i to jest właśnie rzeczywisty adres jaki został dodany do naszego "offsetu" - tam leży nasza tablica. Na koniec trzeba w końcu coś z niej pobrać. Tutaj wychodzi, dlaczego GCC uparcie używało pary R31:R30. Otóż ta para rejestrów (a także R26:R27 i R28:R29) mogą być wykorzystane jako 16-bitowe rejestry adresowania pamięci RAM. Wtedy nazywają się X, Y lub Z:

    5380:	e0 81       	ld	r30, Z

Tym sposobem zawartość komórki tablicy "zaindeksowanej" dwoma zmiennymi x,y wylądowała w rejestrze R30.

Dokładnie taki sam ciąg instrukcji będzie procesor wykonywał, gdy chcąc "zoptymalizować" program będziemy udawać tablicę dwuwymiarową jednym indeksem ale z mnożeniem w środku. Mnożenie 8x8 wcale nie jest kosztowne. AVRy mają do tego specjalne instrukcje które wcale nie są wolniejsze od innych. Dlaczego GCC nie użyło mnożenia? Bo ma ono jedną wadę: można mnożyć przez siebie dowolne rejestry ale wynik zawsze ląduje w parze R1:R0. To zaburza proces gospodarki rejestrami i wynikami pośrednimi w nich przechowywanymi i zawsze jakoś "przeszkadza". Możecie sami zrobić próby z kilkoma różnymi wymiarami tablic. Wymiar 4 był komfortowy, bo mnożenie przez 4 można było zastąpić podwójnym dodawaniem do samego siebie ale nawet dla dziwnych wymiarów GCC znajduje takie sposoby dodawania, by jakoś z mnożenia się wykpić. Np. jeśli wymiar będzie 10, zostaną zrobione 3 kolejne dodawania do samego siebie (czyli x8) i na końcu dodany zostanie wynik pośredni z pierwszego dodawania (czyli x2). W sumie będzie x10 🙂 Oczywiście mamy możliwość sterowania procesem optymalizacji - ja miałem jego poziom ustawiony na 2. Jeżeli natomiast ustawię na s (speed) to dla co bardziej wydziwionych wymiarów GCC przestanie bawić się w dodawania i po prostu pomnoży. Wszystkie te mikrokawałki kodu pobierane są z biblioteki albo "pisane" na bieżąco przez tę część optymalizatora, która odpowiada za gospodarkę rejestrami. Jedno (bibliteka) i drugie (GCC) robi to tak optymalnie jak tylko dane zadanie zrobić można. Pozwólmy mu się wykazać. Dużo łatwiej jest popsuć program używając złego algorytmu niż złego sposobu wykonywania takich "mikrooperacji". Lepiej poświęcić czas na zrobienie dobrego zalewania wodą labiryntu niż kilka dni zstanawiać się, ilu wymiarów tablicy użyć. Niech struktury danych jakich używacie dobrze pasują do algorytmów. To naprawdę zwiększa czytelność programów, które bądź co bądź piszemy dla siebie 🙂 Jeśłi ktoś nie wierzy, niech usiądzie po roku do modyfikacji kodu napisanego (nawet przez siebie) w C czy Pascalu i w języku asamblera. Który jest dla ludzi?