GRID-Map erstellen

Heute ist Stammtischzeit:
Jeden Donnerstag 20:30 Uhr hier im Chat.
Wer Lust hat, kann sich gerne beteiligen. ;)
  • Mein Problem was ich bereits seit einigen Wochen habe, betrifft mehrere Programmiersprachen, deshalb passt es nicht so richtig in einen bestimmten Bereich.

    Mein Problem dreht sich ums erstellen einer sog. GRID-MAP im Bezug auf den ersten Link in meiner Signatur.

    Eine GRID-Map ist im Prinzip wie folgt aufgebaut:

    Ein Raum wird in viele kleine Quadrate eingeteilt sog. Nodes, und als X und Y Koordinaten festgelegt.
    Dann werden die Quadrate in denen Objekte bzw Hindernisse stehen rot markiert bzw mit einer 1 versehen. Quadrate mit einer 0 dürfen befahren werden, mit einer 1 nicht:
    Nicht befahrbare Quadrate haben den Wert 255
    Befahrbare Quadrate haben den Wert 0
    Der Roboter selbst hat den Wert 254
    Das Ziel wohin der Roboter fahren soll hat den Wert 1

    Auf Englisch und mit Bildern wird das auch hier beschrieben: http://www.societyofrobots.com/programming_wavefront.shtml


    Arduino / C / C++:
    Dabei habe ich zum einen Probleme überhaupt erst mal eine MAP zu erstellen da ich nicht weiß wie das Grundgerüst aussehen müsste, und zum anderen wie ich in diesem Array dann Werte verändern kann...

    Grafik / Java / PHP:
    Diese ganzen Zahenwerte des Arduino's will ich grafisch darstellen, in etwa so wie hier: http://www.societyofrobots.com/images/sensors_IRSLAM.gif
    Dabei ist auch die Frage womit ich das am besten umsetzen kann.. Ich will da nicht auf ein Bild festlegen, die Erkundung muss nicht speicherbar sein, aber ich möchte später schon die erkundete Fläche betrachten und ggf bearbeiten können... Nur wie/womit ist mir halt nicht ganz klar :(


    Kann mir dabei jemand helfen?

  • C / C++: Das ist keine Map, das ist ein zweidimensionales Array

    Definition:

    Code
    unsigned char table[1000][1000] ;

    Zugiff:

    Code
    unsigned char x = table[5][10] ;
    table[10][5]     = 254 ;

    Wenn der Arduino nicht genug RAM hat, kann man die Anzahl Bits
    pro Position reduzieren. Dafuer steigt der Aufwand fuer den Code ...

    Einmal editiert, zuletzt von Tell (19. Oktober 2014 um 16:21)

  • Das mit dem Array ist imho schon mal der richtige Ansatz ...
    Zuerst wirst Du aber vermutlich die Grösse der einzelnen Segmente festlegen müssen. Durch schiefe Wände, Möbel oder Durchgänge, die nicht ganzzahlig in die Auflösung passen, stellt sich m.E. das erste Problem: halbe oder "schiefe" Teil-Raster.
    Je kleiner das Raster, umso geringer natürlich die Anzahl dieser Teil-Raster ... aber desto größer natürlich die Datenmenge.
    Auf dem Arduino würde ich dieses Gesamt-Grid gar nicht halten. Der hat einfach zu wenig RAM. Da der RPi aber wissen sollte, wo sich der Fahrzeug gerade befindet, würde ein kleiner Ausschnitt oder gar nur das näächste Segment da vollkommen ausreichen. Das wäre dann auch einfacher beim Neu-Erkunden, da der Arduino einfach nur den Wert des aktuellen Segments zurückliefern müsste.
    Die Datenhaltung ist da eine andere Sache ... klar - Du könntest das einfach in Zeilen und Spalten in einer Datei ablegen. Aber ich bin mir nicht sicher, ob es da nicht noch was clevereres gibt - evtl. mit DB-Tabellen ... mal seh'n, vieleicht fällt mir da im Laufe der Zeit noch was ein. Ich behalte es mal im Hinterkopf.

    viel Erfolg und vor allem Spass weiterhin bei Deinem Robbi,
    -ds-

  • Das es sich um ein Array handelt weiß ich schon, nur nicht wie ich dieses erstelle, wie groß das sein muss, wie ich das erweitere, wie ich darauf zugreife um eine gewisse Interaktion durch zu führen - aber vor allem wie ich das Visuell darstellen kann :-/ =(

    Bezüglich RAM is kein Problem, hab ne RAM-Erweiterung (Arduino EEPROM Shield With 256K AT24C256 -- für 6,60€) :D


    Naja, also lege ich mit

    Code
    unsigned char table[1000][1000] ;

    die Größe fest?
    Wobei die erste Zahl beispielsweise X und die zweite Y wäre?

    X=0 und Y=0 wäre zB unten rechts in der Ecke, X=1000 und Y=1000 wiederum wäre oben links in der Ecke :huh:

    Also in etwa so:

    Spoiler anzeigen

    Aber wie lege ich dann fest wo sich mein Gefährt befindet? Ich kenne doch die Ausmaße des Raumes noch gar nicht und kann somit nicht festlegen das sich mein Gefährt auf X=50 und Y=50 befindet :huh:

  • Naja, also lege ich mit unsigned char table[1000][1000] ; die Größe fest?
    Das gibt ein zweidimensionales Array mit je 1000 Einheiten in jede Richtung. Ob das
    genug ist, kann ich nicht entscheiden, das haengt von der Groesse der Einheiten
    und des Raumes ab.

    > Wobei die erste Zahl beispielsweise X und die zweite Y wäre?
    Genau

    > X=0 und Y=0 wäre zB unten rechts in der Ecke, X=1000 und Y=1000 wiederum wäre oben links in der Ecke
    0,0 wuerde ich als obere linke Ecke sehen, 999,999 (NICHT 1000) als untere rechte.

    Aber grundsaetzlich ist das egal, es muss nur immer gleich interpretiert werden.

    - - - - -

    > Ich kenne doch die Ausmaße des Raumes noch gar nicht und kann somit nicht festlegen
    > das sich mein Gefährt auf X=50 und Y=50 befindet
    Wenn die Ausmasse nicht bekannt sind, aber 1000 x 1000 Einheiten reichen, dann wuerde
    ich das Gefaehrt auf 499,499 setzen und losfahren.

    Sobald es an eine feste Begrenzung kommt, weiss man wo der Rand ist und kann den
    Inhalt vom Array entsprechend verschieben.

    - - - - -

    Wenn es gar keine feste Begrenzung gibt, kann das Array auch dynamisch alloziert werden.
    Bei zweidimensionalen Arrays muesste ich erst mal nachsehen wie das gemacht wird.

    Ich wuerde aber auf jeden Fall mit einem fixen Array anfangen, die ganze Vergroesserung
    und Umkopiererei machen den Code nicht klarer ...

    - - - - - -

    Die Darstellung koennte in Java mit einem Panel erfolgen wo die einzelnen Pixel ein Element
    darstellen. Ueber die Farbe der Pixel wird codiert was sich dort befindet.

    Die Frage ist schon eher wie die Daten aus dem C / C++ - Programm in die Visualisierung
    kommen ;)

  • Hallo zusammen,
    meigrafd:
    dies Ganze grafisch darzustellen erscheint mir nicht sonderlich schwierig zu sein ...
    da du aus der php-Ecke kommst:
    lege doch einfach eine Tabelle an (die Zeilen- und Spaltenanzahl kannst du aus dem Array 'nehmen') ...
    dann in einer Schleife den kompletten Array auslesen und das Tabellenfeld entsprechend einfärben lassen (Array-Wert = 0, bg=grün, Array-Wert = 254, bg=blau, Array-Wert=255, bg=rot).
    Wenn du pro Zelle 10x10 Pixel nimmst, hast du 1000x1000px (100-er-Array, reicht für PC-Monitor) ...

    Um die Position deines Gefährts (am Anfang) herauszufinden, wirst du wahrscheinlich nicht um eine Sensortechnik herumkommen ...

    Viel Erfolg !

    so long
    Perlchamp

    --- wer lesen kann, ist klar im Vorteil ---

    --- man sollte keine Dummheit zweimal begehen, die Auswahl ist schließlich groß genug ---

    --- der Fortschritt der Menschheit ist das Werk der Unzufriedenen ---

    --- Freude entsteht aus Mangel an Information ---

    --- Scheiße ist, wenn der Furz etwas wiegt ---

  • Moin,


    ...
    Wenn es gar keine feste Begrenzung gibt, kann das Array auch dynamisch alloziert werden.
    Bei zweidimensionalen Arrays muesste ich erst mal nachsehen wie das gemacht wird.

    Ich wuerde aber auf jeden Fall mit einem fixen Array anfangen, die ganze Vergroesserung
    und Umkopiererei machen den Code nicht klarer ...
    ...


    Es wäre aber aus meiner Sicht sinnvoll, gleich von Anfang an mit realloc() zu arbeiten ...
    Ein fixes Array per realloc() in der Grösse zu verändern, dürfte in die Hose gehen ;) ...

    Ich würde da eher mit einem 1x1 Array anfangen, und das Array in "Fahrtrichtung" erweitern.
    Wie ein Scanner halt - Spalte um Spalte und Zeile für Zeile. Bei Ausweichmanövern in die nächste Zeile ...
    Und dann jeweils mit realloc() die Länge der Zeile bzw. Anzahl der Zeilen vergrössern.
    Sind zwar ne Menge Systemcalls, aber die kann er schon ab ... und imho wird der Code einfacher.

    //NACHTRAG zur Verdeutlichung: Das 1x1 Array als Ausgangsbasis hat halt den Vorteil, dass Du den Startpunkt an jeder beliebigen Stelle im Raum haben kannst, weil Du keine Annahme über Länge und Breite machst ;) ...

    cu,
    -ds-

  • > Ein fixes Array per realloc() in der Grösse zu verändern, dürfte in die Hose gehen
    Garantiert !

    Aber der Code wird etwas einfacher. Wenn er das im Griff hat, kann er das dynamische
    Array probieren ...

    - - - - -

    Ein realloc von einem zweidimensionalen Array funktioniert aber hoechst wahrscheinlich
    sowieso nicht. Ich bin ziemlich sicher, dass die Library die Elemente im Array nicht
    entsprechend umordnet.

    Er wird ein alloc (oder new) machen muessen und die Elemente dann selbst umbeigen.

  • Hi Tell, Du solltest Thomas heissen ... :)


    ...
    Ein realloc von einem zweidimensionalen Array funktioniert aber hoechst wahrscheinlich
    sowieso ...
    ...


    Ich liebe Pointer in allen Variationen ... von Funktionspointern bis zu structs und unions. Flexibler geht's nicht, weil Du durch einen simplen cast alles draus machen kannst :) ...
    Also glaub mir, das funktioniert wunderbar ...
    Ist ja im Grunde nix anderes als ein dynamisches String-Array :) ...
    Du musst realloc() halt mehrstufig verwenden ... zum Verlängern der Zeile und dann das Pointer-Array jeweils um einen Pointer bis zur Anzahl der Zeilen ...
    Und dazu fiel mir auch die DB-Lösung ein: pro Raum eine Tabelle mit simplen Strings und pro "Zeile" kommt einfach ein String dazu ...
    Die Werte 0, 1, 255, ... werden einfach gemapped z.B. nach "0", "X", " ", ...
    Und die "Ausrichtung" (Zeile, Spalte - im Prinzip ist das ja wurscht, muss nur, wie Du schon sagtest, einheitlich sein) muss eh vom Gyro genommen werden.

    cheers,
    -ds-

  • Hm ich weiß leider immer noch nicht genau "wie" ich das dynamisch Visuell darstellen kann... Was kennt ihr um sowas einfach realisieren zu können?

    Also ich hab ja nun die Zellen Werte und Farben:
    [code=php]
    $Color['0'] = "lightgrey"; #background
    $Color['1'] = "green"; #ziel
    $Color['254'] = "blue"; #ropi himself
    $Color['255'] = "red"; #hindernis (barrier)
    $Color['256'] = "black"; #wand
    [/php]

    Aber womit stelle ich das nun "on the fly" dar? Da steh ich leider weiterhin etwas aufm Schlauch :-/


    Die Übermittlung der Daten übernimmt übrigens ein WebSocket über JavaScript, also die Kommunikation läuft bereits problemlos, darüber kann ich sehr schnell Daten abrufen...

  • Hi meigrafd, alter BastelWastel :) ...
    na ich würde das so wie eine Bitmap sehen.
    Nehmen wir das Mapping-Beispiel aus meinem letzten Post, dann kannst Du per select eine Zeile aus der DB lesen. Die sieht halt dann z.B. so aus: "0000R000XX00"
    Setzt Du jetzt statt "0" $Color['0'], statt "R" $Color['254'] und statt "X" $Color['255'] ein und malst einfach ein entsprechendes Kästchen ...
    Da Du die Anzahl der bekannten Zeilen/Spalten hast, stellt das erst mal kein Problem dar ... und da Du keine Annahmen über "weisse Flecken" machst, brauchst Du die auch gar nicht darstellen (weil die eh vermutlich nicht stimmen würden).
    Ob du allerdings "Hindernis" und "Wand" unterscheiden kannst, sei jetzt mal dahingestellt ;) ...
    cu,
    -ds-

  • dreamshader
    > Du musst realloc() halt mehrstufig verwenden ... zum Verlängern der Zeile und dann das
    > Pointer-Array jeweils um einen Pointer bis zur Anzahl der Zeilen ...
    Das geht, ist aber kein zweidimensionales Array.

    Zu realloc: und wie ist das wenn er auf -1, -1 geht ? :fies:

    meigrafd
    > Hm ich weiß leider immer noch nicht genau "wie" ich das dynamisch Visuell darstellen kann...
    > Was kennt ihr um sowas einfach realisieren zu können?
    Der Vorschlag von Perlchamp ist doch gut:

    HTML-Tabelle

    <td style="background-color: red;">&nbsp;</td><td style="background-color: green;">&nbsp;</td>

    Noch schoener kann man es machen wenn es ein <img src="robbi.gif" alt="robbi"> im td mit
    dem Wagen hat.

  • Hallo zusammen,
    meigrafd:
    ich verstehe das Ganze noch nicht so richtig ...
    was GENAU willst du machen ?
    sind deine sog. Räume fix (z.B. Wohnung[sgrundriss]) oder dynamisch (Natur) ?
    Wenn diese fix sind, verstehe ich das Problem nicht:
    => teile den Raum/die Räume in 5x5cm Quadrate ein => somit hast du die maximalen X- und Y-Werte deiner jeweiligen Tabelle (Raum) + 1 ...
    => belege diejenigen Zellen, welche nicht befahrbar sind (Möbel, Wand, etc.) mit dem entsprechenden Wert
    => somit hast du eigentlich deine Maps (Landkarten) erstellt ...
    => das ganze natürlich über ein assoziatives Array (php, perl), oder über ein Dictionary (python) realisieren (1_1;1) stünde für 1.Spalte, 1.Zeile, Wert:1, analog: (50_38;0) stünde für 50.Spalte, 38.Zeile, Wert:0
    => somit kann man das Array zwar beliebig erweitern, braucht man aber nicht, da Räume fix.
    => aufrufen kannst du das Array entweder über die Koordinaten (45_98) oder über den Wert (0,245,246) ... aber wem sage ich das ...
    => die Position deines Gefährts könntest du - da Raummaße bekannt - mittels Infrarotsensor ermitteln (?); dies wissen andere aber besser als ich ....

    viel Erfolg !

    so long
    Perlchamp

    --- wer lesen kann, ist klar im Vorteil ---

    --- man sollte keine Dummheit zweimal begehen, die Auswahl ist schließlich groß genug ---

    --- der Fortschritt der Menschheit ist das Werk der Unzufriedenen ---

    --- Freude entsteht aus Mangel an Information ---

    --- Scheiße ist, wenn der Furz etwas wiegt ---


  • ...
    Zu realloc: und wie ist das wenn er auf -1, -1 geht ? :fies:
    ...


    warum glaubst Du, dass ein String-Array kein zweidimensionales Array ist?
    Du kannst jedes Zeichen per data[x][y] ansprechen, oder nicht ;) ??
    ... und wie kommst Du auf -1,-1 :s
    Du kannst Strings ja auch vorne "verlängern" ...
    btw: wenn man das über eine DB realisiert, würde der gesamte realloc Kram sowieso hinfällig werden ;) ...

    cu,
    -ds-

  • Tell: Aber wie erzeuge ich das Bild was ich dann in die Seite einbaue? :D Also ein Bild in HTML einzubinden is ja nicht das Problem - es geht mir ums Erzeugen, wobei ich nicht einfach jedesmal ein fixes Bild erzeugen möchte sondern irgendwie wie bei einem Spiel die Daten dynamisch darstellen ... oder auch als Bild, wär mir letztlich dann auch egal solange ich einen Ansatz habe WIE ich das aber nun erstellen kann... Da stehe ich weiterhin aufm Schlauch

    Perlchamp: Nein, keine fixen Räume. Abmessungen usw sind unbekannt und müssen erst erkundet werden.

    Wie gesagt möchte ich sowas wie hier zu sehen: http://www.societyofrobots.com/images/sensors_IRSLAM.gif

    Theoretisiert hab ich das schon genug (gute gutenachtgeschichte für gf da für sie langweilig :D), nur an der Umsetzung, dem tatsächlichen WIE, daran haperts, da weiß ich nicht welche Möglichkeit besteht, welche Funktion ich nutzen kann - wie zeichne ich eine Linie in ein Bild ums plump auszudrücken ..analoges pixelbild..

  • dreamshader
    > ... zum Verlängern der Zeile und dann das Pointer-Array jeweils um einen Pointer bis zur Anzahl der Zeilen ...
    Das ist ein Array of Pointer to char und fuer jede Zeile ein Array mit chars. Genau genommen sind
    es also Zeilen + 1 einfache Arrays.

    Ein zweidimensionales Array ist ein Block mit dem ganzen Array drin.

    - - - - -

    > Du kannst jedes Zeichen per data[x][y] ansprechen, oder nicht
    Das schon, aber das Layout im Memory ist nicht das gleiche.

    - - - - -

    > .. und wie kommst Du auf -1,-1
    Nehmen wir die Ausgangslage mit einem Array von genau einem Element.
    Die Koordinaten gehen nach Rechts und Unten.

    Und jetzt faehrt der Wagen nach links oben, also zu den Koordinaten -1, -1 in
    seinem Array.

    Jetzt braucht er ein realloc mit einem Array das um eine Zeile hoeher und eine
    Spalte breiter ist. Die neuen Zellen braucht er aber in der neuen Zeile 0 und
    in der neuen Spalte 0.

    Er muss die Werte umbeigen und die Koordinaten so anpassen dass -1,-1 zu 0,0 wird.
    (Ja, ich weiss, man kann Arrays in C auch mit -1 adressieren wenn man den Pointer
    richtig setzt [wird aber schwierig bei zweidimensional, ganz besonders bei einem Array
    mit Pointern auf Arrays :fies:])

    - - - - -

    meigrafd
    Perlchamp schlug vor eine HTML-Tabelle mit farbigen Zellen zu nehmen. Das gibt auch
    ein Bild, aber auf einer Stufe die der Browser noch versteht.

    Das muesste einfach zu machen sein.

    Die Tabelle kann man auch dynamisch machen wenn man JavaScript dazu nimmt. Die neuen
    Daten holen und die Zellen entsprechend einfaerben. Auch wachsende Tabellen kann man so
    erzeugen.

    Mein Vorschlag war es dann, zum Beispiel den Wagen auch mit einem Bild in der Tabelle
    zu markieren, weil das besser aussieht.

    Als Variante: auf einen Canvas zeichnen. Den groesser zu machen habe ich allerdings
    noch nicht probiert ...

  • Hi Tell,


    ...
    Das schon, aber das Layout im Memory ist nicht das gleiche.
    ...


    Wer sagt das? Ein char[] ist ein String, ein char[][] ein Array von Strings ...
    Im Fall eines char** gebe ich Dir recht, aber sorry, spielt das von der Funktionalität her irgendeine Rolle? Es geht halt nur über den Umweg eines char** ...


    > .. und wie kommst Du auf -1,-1
    Nehmen wir die Ausgangslage mit einem Array von genau einem Element.
    Die Koordinaten gehen nach Rechts und Unten.
    Und jetzt faehrt der Wagen nach links oben, also zu den Koordinaten -1, -1 in
    seinem Array.


    Ich hab' manchmal ein Problem damit, meine Gedankengänge so zu formulieren, dass andere sie nachvollziehen können ... vielleicht liegt's ja daran ...

    Logisch wirst Du mal "umsetzen" müssen - da Du aber nur Pointer umhängen musst, hält sich das imho in Grenzen.
    Du musst auch einmal den aktuellen "Zeilenstring" mal rechts und mal links erweitern und auch da zwangsläufig umkopieren müssen.
    Da Du aber nach oben und unten, rechts und links flexibel, und zudem schrittweise unterwegs bist, ist das m.E. dann doch überschaubar.

    Ich würde sowieso eher zur DB-Lösung tendieren.
    Eine Tabelle pro Raum mit einem Feld für die Zeilennummer und einem String-Feld. Die Zeilennummer ist das Sortierkriterium und da kannst Du problemlos Zeilen anhängen oder davor einfügen. Da Du weisst, wieviele Schritte Du in der aktuellen Zeile zurückgelegt hast, kannst Du dann eine entsprechende Zeile mit z.B. "?" für unbekannt einfügen und dann wieder nach und nach aktualisieren.
    Problem ist nur, dass die Räume/Umgebung nicht rechteckig sind. Also wird man da wohl Füllzeichen am Anfang der Zeile einfügen müssen, damit die X-Positionen übereinstimmen.
    Das ganze hätte zudem den Vorteil, dass Du die Daten nicht im Speicher halten musst und im Falle eines Absturzes nicht orientierungslos bist.
    Ausserdem wäre es sicher einfach aus dieser Tabelle z.B. eine Bitmap mit entsprechenden Farben zu generieren und anzuzeigen.
    Naja, so in etwa halt ... müsste halt noch ein wenig ausgefeilt werden.

    Wie gesagt, ich bin mir sicher, das kriegt der Guhdsde schon hin,
    -ds-

  • Hallo zusammen,
    meigrafd:
    wenn es wirklich so, wie in der Zeichnung (bewegte Grafik) sein soll, dann ist das doch nur ein Grafik'trick', d.h. derjenige benutzt eine fixe map und läßt 'nur' einen Lichtspot mit festem Radius dem Gefährt folgen, alles andere ist schwarz - nun ja, wer's brauch' ...
    für die sichtbare Spur (Weg), die vom Gefährt 'gelegt' wird, verhält es sich derart, dass der Wert der Zellen, welche den Wert '254' haben/hatten, nicht mehr geändert wird, also bei '254' dauerhaft bleibt ...

    falls die Map wirklich nicht fix ist, wirst du wahrscheinlich nicht um Sensortechnik (Ultraschall, Infrarot, was auch immer) herumkommen ...
    dann wird das Ganze aber sehr schwierig werden, da dieser Sensor das Gelände 360° in einem festgelegten Radius Millimeter für Millimeter 'abtasten' müßte (Hindernisse erkennen, etc. - was passiert bei einem Graben ?, was ist zulässiges Gefälle/Steigung, in welcher Höhe muß der Sensor angebracht werden, um alles scannen zu können ?) ... einige Satelliten im All können das ja ;) ...

    na denn viel Spaß und Erfolg !

    so long
    Perlchamp

    --- wer lesen kann, ist klar im Vorteil ---

    --- man sollte keine Dummheit zweimal begehen, die Auswahl ist schließlich groß genug ---

    --- der Fortschritt der Menschheit ist das Werk der Unzufriedenen ---

    --- Freude entsteht aus Mangel an Information ---

    --- Scheiße ist, wenn der Furz etwas wiegt ---

Jetzt mitmachen!

Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!