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
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
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
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.
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?
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.
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.
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
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
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
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...
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?