Mathematisches Problem, ges.: Anzahl wege über ein Schachbrett

Hallo liebe Leser,

warscheinlich ist das nicht gerade das richtige Forum für solche Fragen, aber bevor ich mich wieder woanders registrieren muss, probiere ich es trotzdem hier.
Ich schreibe im Moment eine Android App, bei der ein beliebig großes 2-dimensionales Feld aus Buttons angezeigt wird.
Man soll auf 2 verschiedene Buttons klicken und dann wird ein zufälliger Weg dazwischen ausgerechnet und eingefärbt.
Bei größeren Feldern dauert das ziemlich lange und ich brauche eine Anzeige, die eine Schätzung abgibt, wie lange die Suche voraussichtlich noch dauern wird.
Dazu müsste ich ausrechnen, wie viele mögliche Wege es von meinem Startpunkt zu jedem beliebigen anderen Punkt auf dem Feld gibt, da ich im schlimmsten Fall alle diese Möglichkeiten durchprobiere.
Dabei ist zu beachten, dass ich mich von jedem Punkt nur in vertikaler oder horizontaler Richtung bewegen kann, also nicht schräg.
Wenn mir dazu jemand eine Formel sagen könnte, wäre ich schon mal glücklich.
Um es ganz genau zu machen, gibt es aber noch eine weitere Einschränkung.
Zwei Wegstücke verlaufen niemals parallel direkt nebeneinander. D.h. zwischen zwei Wegabschnitten ist immer mindestens eine freie Reihe Buttons. Zwei Wegstücke können sich nur in einem Fall berühren, nämlich wenn sich zwei Ecken schräg gegenüber liegen. Diese berühren sich dann in genau einem Punkt.
Ich hoffe das war verständlich, wenn nicht, bitte fragen.
Hoffentlich kann mir jemand helfen!

LG
Garrarufa

Garrarufa meinte:

Man soll auf 2 verschiedene Buttons klicken und dann wird ein zufälliger Weg dazwischen ausgerechnet und eingefärbt.

Zum Vergrößern anklicken....

Hallo Garrarufa,

ist wohl nicht einfach zu verstehen, was Du meinst. Der Weg zwischen zwei bestimmten Buttons ist nie zufällig, sondern immer eindeutig (jedenfalls wenn man den kürzesten oder wenigstens den kürzesten ohne "Diagonalen" wählt). Oder ich habe was nicht verstanden.

Wenn ich das richtig verstanden habe, würde ich wohl einfach mit einem klassischen Koordinatensystem (x-, y-Achse etc.) arbeiten. Jeder Button hat eine eindeutige Position und mit der kann man dann ziemlich leicht per Differenzbildung der beiden Positionsangaben die Entfernung berechnen. Das nur mal als kleiner "Denkansatz". Vielleicht werde ich dem Problem auch gar nicht gerecht, weil ich es nicht wirklich verstanden habe .

Viel Erfolg und Spaß bei der Arbeit!

@ Elefant:
Danke für die Antwort. Leider hilft mir das nicht großartig weiter, weil es ja gerade darum geht, dass nicht der kürzeste Weg, sondern ein zufälliger, generiert wird. D.h. er kann auch im Zickzack und vor und zurück laufen. Einzige Einschränkung: der Weg darf sich nicht irgendwo schneiden oder tangieren. Höchstens zwei Ecken dürfen sich berühren.

Ohje ! Das klingt aufwendig.

Vielleicht ein paar Ideen:

Die Zufallsstrecke zerlegen: damit ergeben sich Teilstrecken der gesamten Zufallsstrecke. Von jeder Teilposition gibt es vielleicht nur vier weitere Zielpositionen (nach oben, unten, rechts und links). Das ganze kann man dann wohl in verschachtelten Schleifen laufen lassen.

Sehr schwierig finde ich im Augenblick allerdings die Einschränkung mit der Überschneidung. Wie sagt man dem Programm, dass eine Überschneidung passiert ?

Ich würde mir wahrscheinlich Hilfe in Spezialforen holen (vielleicht bei Spieleprogrammieren oder bei LandkartenExperten (Routenplaner?)). Die haben wohl ähnliche Algorithmen.

@ Elefant:
Also den Algorithmus dafür zu programmieren ist jetzt nicht das große Problem, hab das schon gemacht und funktioniert auch. Meine Frage bezog sich nur darauf, ob mir jemand eine Formel nennen kann, mit der ich ausrechnen kann, wie viele Möglichkeiten ich mit meinem Algorithmus maximal durchprobieren muss, um auf eine Lösung zu kommen.