zuba1 Napisano Marzec 26, 2012 Udostępnij Napisano Marzec 26, 2012 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) Marzec 26, 2012 Udostępnij Marzec 26, 2012 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 Marzec 26, 2012 Autor tematu Udostępnij Marzec 26, 2012 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) Marzec 26, 2012 Udostępnij Marzec 26, 2012 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,
zuba1 Marzec 26, 2012 Autor tematu Udostępnij Marzec 26, 2012 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) Marzec 26, 2012 Udostępnij Marzec 26, 2012 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 Marzec 26, 2012 Udostępnij Marzec 26, 2012 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 Marzec 27, 2012 Udostępnij Marzec 27, 2012 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 Marzec 27, 2012 Udostępnij Marzec 27, 2012 [...]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 Marzec 29, 2012 Udostępnij Marzec 29, 2012 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 Marzec 30, 2012 Udostępnij Marzec 30, 2012 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 Marzec 31, 2012 Udostępnij Marzec 31, 2012 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 Marzec 31, 2012 Udostępnij Marzec 31, 2012 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?
Pomocna odpowiedź
Bądź aktywny - zaloguj się lub utwórz konto!
Tylko zarejestrowani użytkownicy mogą komentować zawartość tej strony
Utwórz konto w ~20 sekund!
Zarejestruj nowe konto, to proste!
Zarejestruj się »Zaloguj się
Posiadasz własne konto? Użyj go!
Zaloguj się »