Statemachine für Toolset

[muckelzwerg]

Ich arbeite gerade an einem Toolset für grafische Werkzeuge. Also Pinsel, Stifte usw.
Deren Verhalten soll nun durch einen "Zustandsautomaten" abgebildet werden. Die "" deshalb, weil es kein der Theorie nach korrekter Automat sein muss, sondern letztlich darum geht, das Verhalten einigermaßen zu sortieren.
Im Prinzip stehe ich da jetzt vor der Variante eine Zustandsklasse zu verwenden, deren eval() Funktion die aktuelle Situation auf dem Zeichenbrett verarbeitet und einen Folgezustand zurückgibt. (kann auch wieder der aktuelle Zustand sein)
Das funktioniert auch, ist aber ziemlich "dreckig", weil man von Außen gar nicht mehr weiß, wie der Automat aufgebaut ist. Eigentlich ist das mehr eine Art Token-Passing.


Einfaches Beispiel:
Z0: Maus drücken -> Z1 + "nichts machen"
Z1: Maus mehr als X bewegen -> Z2 + "Linie beginnen"
Z1: Maus innerhalb von Y ms anheben -> Z0 + "Blinksignal am Cursor Zeichnen"
Z1: Maus nach Y ms anheben -> Z0 + "nichts machen"
Z2: Maus bewegen -> Z2 + "Linie fortsetzen"
Z2: Maus anheben -> Z0 + "Linie beenden"

Das sind in etwa die logischen Zustände aus einem noch ziemlich einfachen Beispiel.
Die primitive Variante macht daraus 3 Zustände, deren eval() Funktionen dann aber nicht komplett statisch sind (lässt sich mit externen Properties verbessern) und bei denen man von Außen nicht weiß, wie der Automat funktioniert.
Wenn ich jetzt korrekter mit Invarianten bzw. von Außen gesteuerten Übergängen arbeiten will, bekomme ich statt 3 Zuständen mit je einer eval() Funktion, für jede Zeile eine Übergangsfunktion in der die eigentliche Arbeit stattfindet.
Dafür wird es aber ziemlich eklig, die Übergänge zu formulieren. Deren Bedingungen können sich ja überschneiden. Klassischerweise gilt dann "wer zuerst kommt ...". Um da noch Ordnung reinzubekommen, muss ich dann wieder umständliches "wenn x UND y NICHT dann ..."

Hat jemand Ideen, wie sich sowas angenehm umsetzen lässt? Mir gehts weniger um eine theoretisch korrekte Variante, als um eine bei der man von Außen einigermaßen sehen kann, wie der Automat aufgebaut ist (bzw. die Struktur vorgeben kann) und die Funktionen im Inneren nicht zu komplex werden.

 

[Ariol]

Was verstehst du unter anheben der Maus? Hast du bereits Code, den man sich diesbezüglich ansehen könnte?

Eventuell wäre ja sowas möglich (Pseudocode):

int zustand = 0;
long time = 0;
position start;
position end;

void eval(event)
{
    switch(zustand)
    {
        case 0:
        {
            if(event==mousepressed)
            {
                start=currentPosition;
                time=currentTimeMillis;
                zustand=1;
            }
            return;
        }
        case 1:
        {
            if(event==mousemoved)
            {
                zustand=2;
            }
            else //anheben
            {
                zustand=0;
            }
            break;
        }
        case 2:
        {
            if(event==mousemoved)
            {
                end=currentPosition;
                drawline(start, end);
            }
            else //anheben
            {
                zustand=0;
                long delay=currentTimeMillis-time;
                if(delay <= Y)
                    drawBlinkingCursor(start)
            }
            break;
        }
    }
}

Wobei ich glaube ich konnte deinem Text nicht so wirklich entnehmen worum es geht...

 

[muckelzwerg]

Dann beschreib ich nochmal etwas genauer, worum es geht.
Die Variante mit dem Switch ist wohl der Klassiker. Das kann man noch etwas weiter ausbauen, mit Zustandsklassen usw.
Entscheidend ist aber, dass die Auswahl des Nachfolgezustandes in der "Arbeitsfunktion" des aktuellen Zustandes getroffen wird.
Der Graph ist nicht außerhalb als Steuerinformation vorhanden.
Genau das hätte ich aber gerne.

Man kann natürlich so einen Graphen mit einem Designtool beschreiben und daraus Javacode (den "Switch") erzeugen lassen. Aber während der Ausführung wird dann nach wie vor innerhalb des aktuellen Zustandes entschieden wie es weitergeht.
Deswegen sehe ich das eigentlich eher als Token-Passing, weil der aktive Zustand an einen anderen die Kontrolle abgibt.

Wenn man das nun auftrennen will, hat man eine äußere Abhandlung und Steuerung des Graphen und eine Menge von "Arbeitsfunktionen" die wirklich nur ihren Job machen, wie verschiedene Objekte zeichnen usw.
Und dafür sehe ich bisher kaum eine schöne und gleichzeitig relativ bodenständige Lösung.

Man braucht eine Tabelle mit den Übergängen.
- Der aktuelle Zustand ist eine Variable, ein Enum ... das ist einfach.

- Der Nachfolgezustand ist vom gleichen Typ und steht auch einfach in einer Spalte der Tabelle.

- Die Bedingung für den Übergang von Zustand X nach Zustand Y ist letztlich ein beliebiger Java-Ausdruck.
Hier wird es schon eklig. Ich kann ja nicht einfach "if( Timer.getValue() < 0 ) in die Tabelle schreiben. Man kann Bibliotheken wie jel/jexl verwenden, um solche Ausdrücke zu kompilieren, das ist aber schon relativ viel Aufwand und eben von diesen libs abhängig.

- Die Datenbasis für die Bedingungen muss ebenfalls verwaltet werden. Bei der Switch-Variante steht dem aktiven Block alles zur Verfügung, was er im Sichtbereich hat und was er selbst angelegt hat.
Den Timer kann ich aber nicht einfach ins Nirgendwo setzen und ich kann mich auch nicht darauf verlassen, dass eine Arbeitsfunktion ihn korrekt erzeugt.
Also müsste in der Tabelle eigentlich auch sowas drinstehen wie "Von Z0 nach Z1 ... erzeuge Timer ...".


Gedanken:
Wenn man die Datenbasis als <String, Object> Liste umsetzen könnte, dann wäre das noch einigermaßen anständig zu benutzen.
Wenn man bei den Bedingungen nur Elemente mit true und false erlaubt, dann könnte man sogar eine <String, boolean> liste Verwenden und die Ausdrücke wären recht leicht zu prüfen. (Liste durchlaufen, bis eine der Vorbedingungen false ist)
Da hätte man wenig stress mit flexiblen Ausdrücken und Vergleichsoperatoren usw.
In diesem Fall müsste man aber dafür sorgen, dass alle relevanten Situationen auch zu dem Eintragen eines passenden Werts in der Datenbasis führen. Also wenn der Timer abläuft, wird ein "TimerXYExpired" eingetragen.
Das würde gehen, leidet aber daran, dass man eben keine numerischen Infos mehr zur Verfügung hat. Ich könnte dann keine Zwischenwerte mehr verwenden. Sowas wie "Timer == 0.5" für einen Übergang und "Timer <= 0" für einen weiteren Übergang.

Bei der umfangreichen Variante würde eine Zeile der Tabelle etwa so aussehen.
<Zustand, Bedingung, Aktion auf Datenbasis, neuer Zustand, Arbeitsfunktion>
Zustand - Enum
Bedingung - kompilierter Javaausdruck
Aktion Datenbasis - "Callback" zu entsprechender Funktion
neuer Zustand - Enum
Arbeitsfunktion - "Callback"

Man könnte noch die Arbeitsfunktionen wieder in die Zustände hineinlegen und statt Enums wirkliche Objekte verwenden. Dann fiele die Spalte "Arbeitsfunktion" weg und beim Abhandeln einer Regel würde
1.) Bedingung prüfen
2.) wenn true -> Datenbasis modifizieren (Timer etc)
3.) Zustand.eval() aufrufen (--> zeichnet Linie, Kreis ...)


Dazu kommt dann noch der Stress mit Prioritäten bei den Übergängen, wenn z.B. MOUSEDOWN und "TIMEREXPIRED" beide gesetzt sind und die Frage, welche Informationen für Datenbasis evtl. zwangsweise aus den Arbeitsfunktionen kommen müssen.


Ist es jetzt klarer geworden?

 

[Marco13]

Mir nicht. Ich hatte schon den ersten Beitrag gelesen, aber es war mir nicht klar, was du meinstest, und habe deswegen mal nicht geantwortet. Mit dem zweiten ist es nicht wirklich klarer geworden. Es scheint, als wärst du schon "sehr weit drin" in diesem konkreten Problem.
Wäre es möglich, mit ein paar Zeilen Code anzudeuten, was du gerne machen und wie du das am Ende gerne anwenden würdest (bei denen die fraglichen Teile auch Pseudocode sein können) ?

 

[muckelzwerg]

... doppelbeitrag, sorry.

 

[muckelzwerg]

Code gibts dazu noch nicht, weil ich ja gerade nach einer Möglichkeit suche, es umzusetzen. Ich bastel es mal theoretisch zusammen.

// Die einfache Variante einer Übergangsregel
StateRule{
    State in;
    Condition con;
    State out;
}

// Zustandsobjekt mit Arbeitsfunktion (Zeichne Linie, verzerre Objekt, filtere Pixel ...)
// Die konkreten Zustände werden dann abgeleitet.
State{
    eval(DrawingContext){
    }
}

// Die Menge aller Zustände. Die werden irgendwo zusammengebaut --> das eigentliche "Toolset".
// Genaugenommen braucht man die Liste auch nur zur Übersicht, hauptsache die Zustände werden erzeugt.
List<State> states = generateStates();

// Hier werden alle Regeln (Zustandsübergänge) bspw. aus einer Textdatei erzeugt.
// Das hier ist die Tabelle mit den Übergängen, die ich verarbeiten möchte, ohne dass die eigentlichen Arbeitsfunktionen da mitmischen.
List<StateRule> rules = generateRules();

generateRules(){
    StateRule r = new StateRule( states.get("Z0"), new Condition("MOUSEDOWN"), states.get("Z1"));
    List.add( r );
    r = new StateRule( states.get("Z1"), new Condition("MOUSEUP"), states.get("Z0"));
    List.add( r );
    r = new StateRule( states.get("Z1"), new Condition("TIMEREXPIRED"), states.get("Z0"));
    List.add( r );
    ...
}


// Der eigentliche Ablauf ist dann eine Schleife, die nach dem ersten Treffer in der Regelmenge sucht
foreach(Rule in RuleSet){
    if( CurrState == r.inState() && r.con(Data) == true ){
        CurrentState = r.outState();
        break;
    }
    CurrentState.eval(CurrentDrawingContext);
}

So in etwa sollte es aussehen. Hier sieht man doch schon den Knackpunkt mit den Bedingungen. Das Condition-Objekt muss ja irgendwie mal die spezifizierte Bedingung evaluieren. Solange es da nur um "MOUSEDOWN" geht, kann man eine Map mit booleans nehmen und schauen, ob MOUSEDOWN als "true" eingetragen ist.
Wenn die Ausdrücke aber komplexer werden "if( Clickcounter == x)" oder "if( timer < 50)", dann muss man diese Ausdrücke ja irgendwie berechnen können.
Dafür fallen mir nur solche Bibliotheken wie jel und jexl ein.

Da stellt sich die Frage, ob es nicht einen Mittelweg gibt, der etwas mehr kann als nur
"MOUSEDOWN == true && TIMEREXPIRED == TRUE && ..." - Bedingungen zu verarbeiten, ohne gleich mit selbstmodifizierendem Code zu arbeiten.
Man könnte einen "einfachen" Parser verwenden, um die gängigen Vergleichsoperatoren von Hand in entsprechende Zweistellige Bedingungen zu Übertragen.
Also Klassen für EqualsCondition(), LessThanCondition(), GreaterThanCondition() bauen.
(oder eine einzelne Klasse mit passenden statischen Funktionen, darauf kommt es letztlich nicht an).

Dann braucht es noch eine Datenbasis auf die bei der Evaluation der Bedingungen zugegriffen werden kann. Da könnte man wohl mit einer <String, Object> Map arbeiten.
Die Bedingung wird dann mit Namen der Parameter angegeben und das zugehörige Objekt macht ein .get(leftOperand) auf die Map.
Mit noch ein bisschen Drumrum für Castingfehler und nichtgesetzte Werte, wird dann im wesentlichen
"return ( leftOperand == rightOperand )" ausgeführt, wenn Con.true() aufgerufen wird.
(oder ein anderer Operator, je nach dem welche Bedingung es ist.)


Soweit sollte das gehen. Ist etwas ärgerlich mit der Parserei, aber wenn ich bei Methoden bleiben will, die mir auch in anderen Sprachen allgemein zur Verfügung stehen, kann ich sowas wie jel wohl nicht benutzen.
Aber DANN kommt halt noch die Frage, was ich mit dem befüllen der Datenbasis mache.
Irgendwo muss der Timer ja mal erzeugt werden.
Beim Switch-Klassiker, würde das einfach in dem Block passieren, der auch die Linie malt. Das soll aber eben nicht sein.
Wenn ich solche Anweisungen auch noch in die StateRule einbauen will, dann wird es nochmal schwieriger.
Da müssen ja sogar Objekte angelegt werden.
Entweder ich verwende da einen Callback, der dann eben genau den Code ausführt, denn ich brauche (timer anlegen, timer in Datenbasis registrieren ...)
oder ich muss wieder eine Menge von Funktionen wie "registerTimer(Name, time)" anbieten, die dann über Pseudocode "REGISTERTIMER T1 50" in den StateRules verwendet werden können.
Beides hat Vor- und Nachteile, beides ist nicht so wirklich attraktiv.


JETZT besser?

P.S.: Es geht bei dem Projekt letztlich um das Entwickeln von Eingabemethoden. Überlegungen wie
"Hmmmm, wir könnten auch mit dem zweiten Mausklick in Zustand X anstelle von Z gehen und wenn dann der Timer abläuft, dann erst wechseln wir in Zustand Y ..." sind da gängig.
Außerdem gibt es verschiedene Benutzerschnittstellen mit unterschiedlichem Funktionsumfang. Da bietet es sich natürlich an, einfach das RuleSet zu wechseln, weil man da doch viel mehr Übersicht hat, als bei einer BlackBox in der irgendwas geswitched wird.

 

[Marco13]

Hmja, OK, dann scheint das im Grunde schon so zu sein, wie es von Anfang an klang, aber... jetzt kann man da sicherer sein Es gibt vielleicht ein paar Details und Optionen, aber nichts weltbewegendes. Der einzige (???) wirkliche "Knackpunkt" scheint die Notwendigkeit zu sein, Bedingungen in Form einer "Text-Eingabe" zu beschreiben, ist das richtig?

Falls dem so ist: Du hast ja schon angedeutet: Man kann sich entweder einen Satz "vorgefertigter" Bedingungen und Optionen definieren, so dass in der Datei dann sowas steht wie

{ ...State0... } Condition[MOUSE_DOWN, 0]  { ...State1... }
{ ...State3 Reference[TIMER,'SomeTimer',13:21] } Condition[TIMER, 'SomeTimer', 13:25]  { ...State4... } 
...

Schon an dieser Andeutung sieht man, dass das auf eine Form einer Domänenspezifischen Sprache rauslaufen würde: Man müßte eine Grammatik definieren, z.B. dass eine Referenz auf einen Timer die Form hat
Reference[ TIMER,Name,Zeit im Format hh:mm ]
und so. Diese Sprache könnte entweder nur eine kleine Teilmenge der möglichen, denkbaren Conditions beschreiben, oder ... sie wäre Turing-Vollständig
Die Alternative hast du auch schon angedeutet: Die Bedingung könnte ein beliebiger Java-Ausdruck sein, oder irgendwas, was mit JEXL verarbeitet wird.
In jedem Fall ist das Anbieten der Option, (fast) beliebige Conditions zu definieren, mit viel Aufwand verbunden. Entweder, weil man selbst Grammatik schreiben und Lexer und Parser bauen muss, oder weil man sowas wie JEXL einbinden muss, oder weil man sowas wie Java Scripting Programmer's Guide verwende muss (da braucht man AFAIK ein JDK, ein JRE reicht nicht).

Ist das Auslesen dieser Bedinungen aus einer Datei eine "harte" Anforderung? Das ganze wäre ja vielleicht(!) und in mancher Hinsicht(!) viel einfacher, wenn man die Bedingungen über Klassen bzw. Interfaces definieren könnte. Der Benutzer (d.h. der Programmierer, der dieses ToolSet benutzen will) könnte dann die Conditions als Implementierungen eines Java-Interfaces anbieten. Die Klasse, die diese Conditions anbietet, könnte ja z.B. zur Laufzeit über einen ServiceLoder o.ä. geladen werden...

 

[muckelzwerg]

Nein das Auslesen aus einer Datei ist nicht so wichtig. Es wäre zwar schön, aber das kann ich auch anders machen.
Es ist ja nicht sooo viel Aufwand den Automaten extern (vielleicht sogar mit einem angenehmen Tool) zu bauen und dann daraus JavaCode zu erzeugen.
Grundsätzlich hab ich dagegen nicht unbedingt was, solange der Automat (bzw. die Tabelle) für den Ablauf erhalten bleibt und er nicht in einen Switch-Block übersetzt wird.
Es ist aber auch völlig in Ordnung die Regeln im Code anzugeben, so wie ich das oben gemacht habe. Das macht erstmal nichts.

Der "Knackpunkt" ist, dass diese Automaten/Toolsets/Regeln ja wirklich entwickelt werden. An denen wird viel gebastelt und ausprobiert. Und dann laufen die später auch auf unterschiedlicher Hardware und Software. Das heißt ich muss irgendwann die gleiche Fingerübung nochmal für IOS und Android machen.
Und wenn ich da in Java eine superduper Lösung mit jel gebaut habe, tu ich mir ja nur selbst weh.
(jel ist bei meinen Test bisher übrigens deutlich schneller gewesen, als jexl)

Vielleicht sammeln wir mal ein bisschen.

- Beliebige (sprachabhängige) Ausdrücke
pro: sehr mächtig, angenehm zu nutzen weil es wie ein gewöhnliches "if(...)" gebaut wird
contra: nur mit zusätzlichen libs oder viel Aufwand zu machen, evtl. große Probleme bei der Portierung

- nur booleans
pro: bietet wohl jede umgebung an, leicht zu nutzen weil es bloß eine große Konjunktion von Parametern ist,
leicht zu implementieren weil nur eine liste mit booleans abgeklappert werden muss
contra: deutlich weniger mächtig, keine expliziten Parametertests möglich, evtl. fieses Gebastel um zusätzliche Ereignisse wie "TIMEREXPIRED" zu erzeugen

- Strings, Numbers und Booleans mit eigenen Klassen für die Ausdrücke
pro: einigermaßen mächtig und trotzdem noch akzeptabler Aufwand(?), sollte recht gut portierbar sein
contra: nicht ganz so mächtig wie freie Ausdrücke, keine Bedingungen der Form "if( Object.getValue() ..."


Bei der letzten Variante müsste ich mit einer Hashmap aus Strings und Objects auskommen.
Da sollte zumindest mal das Auslesen und Evaluieren einigermaßen gut zu implementieren sein.
Das Eintragen von neuen Infos ist dann die Schwierigkeit.

Was ist denn, wenn ich eine Klasse erzeuge, die Bedingungen und Datenaktualisierungen als Funktionen enhält?
Eine Instanz würde dann einem Ruleset entsprechen. Für jede Regel gibt es eine Funktion "prüfeBedingungX()" und eine Funktion "aktualisiereDaten()".
Dann hätte ich die volle Sprachmächtigkeit und könnte auch problemlos z.B. ein Timerobjekt erzeugen und in die Datenbasis ablegen.
Ich müsste auch keine eigenen Sprachen definieren, keine Ausdrücke kompilieren und hätte die Bedingungen trotzdem einigermaßen beieinander.
Da hab ich dann doch "die große Freiheit"? In Java kann ich z.B. anonyme Klassen von Condition und DataUpdate ableiten und direkt überschreiben, was sie tun sollen. Da brauche ich die Funktionen nicht in der Ruleset-Klasse ablegen.
Bei anderen Umgebungen könnte ich z.B. Callbacks verwenden.
Und wenn alle Stricke reißen, dann muss eben wirklich für jede Bedingung eine eval-Funktion im Ruleset implementiert werden und es gibt ein großes "If..." welches die Namen/Nummern der Bedingungen auf die zugehörigen Funktionen überträgt.
Sowas sollte doch eigentlich überall recht gut machbar sein, egal ob PC oder Smartphone oder ...?

 

[Marco13]

Die genaue Rolle der angdeuteten "Ruleset"-Klasse erschließt sich mir nocht nicht. FALLS ich es richtig verstanden habe, ist das die Klasse, die die Infrastruktur bereitstellt, und im Prinzip das regelt, was du oben als Pseudocode angedeutet hast. Das "generateRules" würde dabei eben nicht direkt in der Klasse gemacht werden, sondern von außen - das ist ja der kritische Teil. Ich hatte gedacht, dass das wirklich so laufen sollte wie

RuleSet ruleSet = new RuleSet();

State s0 = getStateFromSomewhere();
State s1 = getStateFromSomewhere();
Condition condition = ... // <-- Das ist der spannende Teil

// Aber hier kommt nur noch sowas wie
ruleSet.add(s0, condition, s1);
// oder so..

Und genau darauf wollte ich hinaus mit der Frage, ob die Conditions nicht im Code definiert sein können, weil dann wären es ja genau die anonymen Klassen, die du auch angedeutet hast:

State s0 = getStateFromSomewhere();
State s1 = getStateFromSomewhere();
Condition condition = createThisVerySpecialCondition(s0, s1);

...

private Condition createThisVerySpecialCondition(final State s0, final State s1)
{
    return new Condition()
    {
        public boolean isFulfilled() 
        {
           return s0.getTimerValue() > 42 && ui.isMouseDown() && s1.getTimerValue() < s0.getTimerValue();
        }
    });
}

(ähnlich könnten auch die States oder "Updates" implementiert sein und erstellt werden). Zur Verallgemeinerung könnte es dann ein
interface RulesFactory { List<Rule> createRules(); }
oder so geben, das könnte man sich dann noch überlegen...

 

[muckelzwerg]

Genau da bin ich gerade dran. Es ist keine Schönheit, aber es entwickelt sich momentan ganz gut.
Nur habe ich die Möglichkeit mit den anonymen Klassen nicht in jeder Umgebung. Aber da könnte ich dann ja zur Not konkrete Klassen bzw. statische Methoden für bauen. Ist dann noch weniger schön, aber das sollte wirklich überall machbar sein.

Mit "von Außen" meine ich, dass die Statemachine ihren Job macht, ohne dass die Arbeitsfunktionen Einfluss auf die Verzweigung nehmen.
Es kann ja passieren, dass ich eine neue Kante in den Automaten einfügen will. Da hab ich keine Lust in der "zeichneLinie()"-Funktion was zu ändern, bzw, im Block der diese Funktion anwirft.
Stattdessen bau ich eine neue Regel, die den Übergang "von Außen" erzeugt.
Ich kann dann auch so Späße machen, wie einen "AnyState" der immer trifft. Wenn dann die Bedingung (z.B. "SYSTEM_RESET") erfüllt ist, kann ich aus jedem Knoten direkt rausspringen, ohne dass ich das irgendwo in den Blöcken einbauen muss.


Das Erzeugen aus einer externen Textdatei wird sich vermutlich doch recht leicht erschlagen lassen. Ich hab vor einer Weile 2D-Widgets gebaut, die ich mit LUA-Script berechnen lasse.
Das kann ich ja bei den Regeln genauso machen. Dann brauche ich die Funktionen nicht überschreiben, sondern lade nur das jeweils passende Skript. Wenn ich da ein wenig bastel, bekomme ich vermutlich sogar einen ganzen Automaten einigermaßen schön in einem einzigen Skript unter.