schwierigkeiten mit Wegsuche

[philip (Gast)]

Ich möchte Stellpult für die Modellbahn bauen, auf welchem ich das 
Startgeleise wähle und danach das Zielgeleise. Mit einer Wegsuche sollte 
dann ein Weg gefunden und die Weichen sowie die LEDs die die 
WEichenstellung anzeigen geschalten werden.
Nun aber scheitere ich an der Wegsuchefunktion.
teilweise scheint das ganze zu funktionieren, mit entsprechenden Display 
angaben konnte ich sehen, dass das Programm auch schon bis zu einem Fund 
gelaufen ist und die sortSS() ausführen konnte. Aber es gelangt nie zum 
Pkt. an welchem es "Weg nicht gefunden" oder "gestellt" ausgeben könnte. 
Das programm stürzt immer vorher ab (reset). Ein reset durch den 
watchdog ist ausgeschlossen, da dies auch geschieht, wenn dieser 
Ausgeschatet ist.
Hardware: ATmega64

Code (Wegsuchefunktionen etc. - das komplette Prog ist im Anhang):




//----------------------------------------------------------------------
// HAUPTPROGRAMM
//----------------------------------------------------------------------
int main ()            // Hauptprogramm, startet bei Power ON und Reset
{
...      // Schleifenende Mainloop
}
//----------------------------------------------------------------------
// Funktionen
//----------------------------------------------------------------------
void routingRT(railtrack *start, railtrack *end)   //rückgabewert: #Wege
{
    TCCR3B=0x00;        //TIMER3 gestoppt (Autokorrektur)
    wdt_reset();
    nofSS=0;            // #SwichSets (mögliche Wege) (GLOBALE VAR)
    bool ifany=false;   // bleibt false, falls kein Weg gefunden wird, 
wird true, wenn schon
    switchSet way;      // weg, wird bei jedem Schritt, bei dem 
geschalten werden muss erweitert und beim finden des Weges in globales 
Array abgespeichert
    way.nofSP=0;        // initialiesierung von way
    lcd_clrscr();
    if(start->a!=null)
    {
        if(end->a!=null && 
routingSP(start->a,start->a_main,end->a,way,0))
            ifany=true;
        if(end->b!=null && 
routingSP(start->a,start->a_main,end->b,way,0))
            ifany=true;
    }
    wdt_reset();
    if(start->b!=null)
    {
        if(end->a!=null && 
routingSP(start->b,start->b_main,end->a,way,0))
            ifany=true;
        if(end->b!=null && 
routingSP(start->b,start->b_main,end->b,way,0))
            ifany=true;
    }
    resetTbits(); // zurücksetzen von den 'tried'-bools (diese zeigen 
an, ob ein Wegstück bereits ausprobiert wurde)
    wdt_reset();
    lcd_clrscr();
    if(!ifany)
        lcd_puts("keinen Weg gefunden!");
    else{

            setSSSP(&arrSS[0]); //stellt Weichen & Anzeige entsprechend
            if(nofSS==1)
            {
                lcd_puts("gestellt");
                zustand=0;
                //TODO Timer3->Display zurücksetzen//
            }
            else
            {
                lcd_puts("gestellt\nNEXT");
                zustand=0;

            }
    }


}
bool routingSP(switchpoints *start,bool main, switchpoints 
*end,switchSet way,uint8_t i)
{
    lcd_putc('(');      //nur zum nachvollziehen des scheiterns des 
Programms.. hat leider nicht geholfgen :-(
    if(start->tried)    //abbruch
        return false;

    start->tried=true;  //'tried' zeigt an, ob ein Wegstück bereits 
versucht wurde
    wdt_reset();
    bool ifany=false;
    if(!main)                   // komme ich von einer der beiden 
abzweigenden Richtung? (ich muss die Weiche (bei einer Modellbahn) nicht 
schalten)
    {
        if(start->main==end)    //ist die an der Hauptrichtung 
angeschlossene Weiche bereits das Ziel?
        {
            arrSS[nofSS]=way;   //Abspeichern des wegs
            sortSS();
            nofSS++;
            return true;
        }
        if(routingSP(start->main,start->m_main,end,way,i))
            ifany=true;
    }else{                      // ich komme von der Hauptrichtung (ich 
kann abzweigen -> muss Weiche schalten)
        if(start->ahead==end)   //...analog, hier muss ich einfach erst 
noch die Weiche stellen und dann abspeichern
        {
            way.arrSP[i]=start;
            way.arrDIR[i]=0;
            arrSS[nofSS]=way;
            sortSS();
            nofSS++;
            return true;
        }
        if(start->branch==end)
        {
            way.arrSP[i]=start;
            way.arrDIR[i]=1;
            arrSS[nofSS]=way;
            sortSS();
            nofSS++;
            return true;
        }
        way.arrSP[i]=start;     //stellen der Weiche (im Array)
        way.arrDIR[i]=0;
        if(routingSP(start->ahead,start->a_main,end,way,i+1))
            ifany=true;
        way.arrDIR[i]=1;

        if(routingSP(start->branch,start->b_main,end,way,i+1))
            ifany=true;
    }

        return ifany;
        lcd_putc(')');
}
Hoffe, dass jemand helfen kann - bin etwas verzweifelt.
Gruss philp

[Oliver (Gast)]

Ich habe jetzt nicht alles gelesen, und schon gar nicht verstanden, aber 
wenn ich das richtig sehe, rufst du deine Routingfunktion (wie erwartet) 
rekursiv auf. Bei knappen SRAM auf einem AVR kann das schnell 
schiefgehen. Unerklärliche Abstürze sind ein INdiz für 
Speicher-Overflow.

Da solltest du mal eine längere debug-Phase einplanen, und im Simulator 
den Speichernzustand überwachen.

Oliver

[Thomas B. (Firma: Druckerei Beste) (virtupic)]

Was soll deine Wegsuche denn finden? Irgendeinen Weg? Oder einen nach 
irgendeinem Kriterium optimalen (z.B. den kürzesten) Weg? Für letzteres 
gibt's den Dijkstra-Algorithmus mit haufenweise Implementierungen im 
Netz in den verschiedensten Sprachen zum Abtippen und laufen lassen.

Doch, habe ich auf dem PC schon gemacht. Funktioniert.

virtuPIC
/ggadgets for tools & toys

[philip (Gast)]

ich möchte alle möglichen Wege finden - das sind meistens aber nicht so 
viele (1-3 schätze ich mal - so gross ist die Modellbahnanlage leider 
eben nicht). Da ich meistens eben doch den kürzesten wirklich brauche, 
sortiere ich die Wege dann nach ihrer Länge (# zu stellender Weichen). 
Möchte ich einen anderen Weg stellen, so hab ich dafür ein Taste, mit 
der ich der Reihe nach alle stellen kann.

An das RAM-Problem hab ich auch schon gedacht. hoffte aber dass die 4kB 
des ATmega64 ausreichen. (Immerhin braucht das gesammte Programm ja kaum 
mehr platz (im Flash)). Ausserdem hab ich nur 10 Weichen, die maximale 
Rekursionstiefe sollte aber noch kleiner sein (sind ja nicht alle 
hintereinander).

Was für Simulatoren könnt ihr mir empfehlen? Hab bis jetzt eben noch nie 
ein so Speicheraufwändiges Programm geschrieben.

[Oliver (Gast)]

Algorithmen testen am besten zunächst auf einem PC, mit einem 
ausgewachsenem Entwicklungssystem (TurboC, BorlandC, Visual C++, Watcom, 
...). Unter linux gcc/gdb.

AVR-Simulation entweder im AVRStudio, VMLAB, oder "in echt" mit Studio 
und JTAG-Debugger.

Ich würde die Routingberechnung aus der ISR rausnehmen. Genauso 
LCD-Ausgaben. Die dauern alle so lange, das stellt das ISR-Konzept auf 
den Kopf. Überhaupt sind mir da viel zu viele ISRs in dem Programm.

Oliver
P.S. Wenn du in C programmierst, warum nennst du deine Source dann .cc?

[philip (Gast)]

ja, das ISR-Konzept missbrauche ich etwas. Aber grundsätzlich sollte mir 
das ja keine Probleme bereiten?

das mit dem .cc hat die IDE vermutlich so vorgeschlagen - und ich werds 
voreilig und ohne Überlegungen so übernommen.

[Stefan B. (stefan)]

Programmiere eine z.B. serielle Ausgabe in das Programm bei der du 
während der Suche mitbekommst, wieviele Wege gefunden werden. Dann bist 
du nicht auf Schätzungen angewiesen. Du kannst auch eine Anzeige des 
Stackpointers einbauen, um zu Ende gehendes SRAM zu entdecken.

Ich würde mir nicht alle Wege merken und am Schluss sortieren. Wenn beim 
daruffolgenden Lauf ein kürzerer WQeg gefunden wird, kann das Programm 
den Weg aus dem vorhergehenden Suchlauf schon vergessen. Das spart 
Platz.

[philip (Gast)]

ich möchte am Ende eben ALLE Wege kennen, da meistens - aber nicht immer 
- der kürzere der Beste ist.
Wie kann ich den Stackpointer ausgeben? Auf mein Display?
mit den Simulatoren komm ich irgendwie nicht so klar

[Thomas B. (Firma: Druckerei Beste) (virtupic)]

Suchst du alle Wege zu gegebenem Start- und Zielpunkt oder je einen Weg 
zu allen Punktpaaren oderalle Wege zwischen allen Punktpaaren? "Punkt" 
heißt hier so was wie "Stelle, an der ein Zug halten kann."

Den jeweils "optimalen" (kürzesten, schnellsten...) Weg zwischen allen 
Punktpaaren findest du mit dem... ach, wie heißt er gleich... ich 
glaube... Floyd-Warshall-Algorithmus.

Alle Wege zwischen zwei Punkten erfordern besonderes Design der 
Datenstruktur, weil du Schleifen fahren kannst.

virtuPIC
/ggadgets for tools & toys

[Thomas B. (Firma: Druckerei Beste) (virtupic)]

Noch was. Dijkstra und Floyd-Warshall (er heißt tatsächlich so!) laufen 
in Schleifen mit wenig Stack-Verbrauch. Die Repräsentation der Strecke 
kann aber einiges verbrauchen...

virtuPIC
/ggadgets for tools & toys

[Stefan B. (stefan)]

philip wrote:

> Wie kann ich den Stackpointer ausgeben? Auf mein Display?

Ja zum Beispiel auf dein Display.

Oder - so würde ich es machen - als fortlaufender Logtext über UART auf 
eine serielle Schnittstelle eines mitprotokollierenden PCs.

Das Display würde ich für die regulären Programminfos reserviert halten 
und die serielle Schnittstelle zur Programmentwicklung (Debuggen) 
nutzen.

An den Stackpointer kommst du über das Makro AVR_STACK_POINTER_REG aus 
<avr/io.h> (bzw. dem darin includierten <avr/common.h>).

Den Wert kannst du als char * interpretieren (casten) und z.B. 
hexadezimal in einen String formatieren lassen (ltoa oder sprintf) und 
dann ausgeben (puts oder passende uart_puts...). Wie Zahlen ausgegeben 
werden können gibt es eine FAQ hier in der Artikelsammlung...

[philip (Gast)]

hab mich jetzt für eine iterative variante der Suche entschieden und 
diese auch soweit zum laufen gebracht (noch ein zwei kleine bugs, aber 
das kommt schon noch)
Dennoch würde mich - auch für zukünftige Projekte - die Sache mit der 
Debugausgabe über UART interessieren, gibts da irgendwo eine kleine 
Anleitung dazu?