Jump to content
Unity Insider Forum

Algorithmus für Bewegungen von Schachfiguren


Kokujou

Recommended Posts

Hi!
Angenommen man hat ein 8x8 2D-Feld in dem die Figuren gelistet sind und möchte jetzt überlegen, auf welches Feld sich die Dame bewegen will.
Natürlich ist das erste was mir einfällt,, einfach 8 for-schleifen zu machen und das Feld in jeder Richtung abzulaufen, um die Schleife zu unterbrechen, sobald eine Figur im Weg steht.

Meine Frage: Gibt es da einen eleganteren und etwas kürzeren weg? Ich hab schon überlegt vielleicht eine for-schleife mit 4 Zählern zu machen aber dann könnte man nicht mehr so gut unterbrechen. Außerdem wäre es dann etwas Laufzeitintensiver, da man trotzdem 4mal zählt aber jedes mal alle 4 abfragen macht, auch wenn die Figur längst blockiert wurde.

Ideen?

Link zu diesem Kommentar
Auf anderen Seiten teilen

Die 8 Richtungen musst du bei der Dame schon einzeln abfragen. Die Abfrage selber kannst du aber rekursiv machen.

Bau die eine Funktion für die Dame, die dir für jede Richtung die mögliche Weite zurück gibt. Je Richtung musst du diese Funktion aufrufen und bekommst dann auch je Richtung die maximale Weite zurück. Dadruch kennst du ja dann alle freien Felder dazwischen.
Natürlich musst du noch irgendwie die Abfragefelder begrenzen, damit du nicht ausserhalb des Spielfeldes abfragst.
 

//Aufruf mit annahmewerten
Vector2 rechtsHoch = new Vector2(1,1);
Vector2 myPosition = new Vector2(0,4);

int rechtsHochWeite= Felder(rechtshoch,myPosition);
print (rechtsHochWeite);

public int Felder(Vector2 richtung Vector2 position){

	Vector2 neuesFeld=position+richtung; 
    // hier drunter sollte noch abgefragt werden, ob das neue Feld überhaupt noch innerhalb des Spielfeldes ist.
	
	
    // freies feld gib ne 0 zurück
	if(feldarray(neuesFeld)==0){ 
		int anzah=1+Felder(richtung,neuesFeld); // selbstaufruf

		return anzahl;
	}
	else{
		return 0;
	}
}

 

Link zu diesem Kommentar
Auf anderen Seiten teilen

Hmmmm an Rekursivität hab ich gar nicht gedacht. Aber ich will nicht wirklich die Anzahl der freien Felder ermitteln. Ich habe folgendes:
Ein 2. 8x8 2D-Feld in dem jede Bewegung und die Art dieser eingetragen wird. heißt: Feld frei -> 1, Feld von Gegner besetzt -> 2, Feld von Freund besetzt -> 5, sonst -> 0. aber ich denke ich kann die Idee ausbauen und nutzen! Danke! :)

Link zu diesem Kommentar
Auf anderen Seiten teilen

Du könntest für jede Figur eine List an Feldern speichern an welche die Figur in einem Zug gelangen kann. Diese dann iterieren. Diese Liste ändert sich nur bei Bewegung der Figur.

foreach(Field f in possibleFields)
{
//do your voodoo
}

Denke das wäre wegen der KI Berechnung ganz sinnig so eine Liste zu speichern.

Eventuell geht das auch mit einem hardgecodetem Kernel. Ist ja klar, dass in welche Richtung sich jede Figur bewegen kann. Somit wäre es noch performanter.

https://en.wikipedia.org/wiki/Kernel_(image_processing)

Was du vorgeschlagen hast ist jetzt Längen/Breitensuche. Bin mir nicht sicher ob sich da mathematisch Unterschiede ergeben. Also ob es wahrscheinlicher ist beim Schach in einer Breitensuche eine "volles" Feld zu finden oder bei einer Längensuche. Ich würde schätzen, dass sich da nicht viel tut Laufzeittechnisch.

Um deine Aufgabe mal simpel zu beantworten. Bei einer Dame kannst du folgendes versuchen:

Enemy foundEnemy = null;
Position currentPos = //aktuelle Position
for(int i = 1; i<MAXDISTANZ; i++)
{
  foundEnemy = Spielfeld[currentPos.x,currentPos.y+i];//oben
  foundEnemy = Spielfeld[currentPos.x+i,currentPos.y+i];//rechts oben
  foundEnemy = Spielfeld[currentPos.x+i,currentPos.y];//rechts
  foundEnemy = Spielfeld[currentPos.x+i,currentPos.y-i];//rechts unten
  foundEnemy = Spielfeld[currentPos.x,currentPos.y-i];//unten
  foundEnemy = Spielfeld[currentPos.x-i,currentPos.y-i];//unten links
  foundEnemy = Spielfeld[currentPos.x-i,currentPos.y];//links
  foundEnemy = Spielfeld[currentPos.x-i,currentPos.y+i];//links oben
  if(foundEnemy != null)
    break;
}

Natürlich unter der Annahme, dass deine Datenstruktur dir nicht um die Ohren fliegt, wenn du außerhalb des Bereichs bist.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Also den Code versteh ich jetzt wirklich nicht.

So wie ich das verstehe bricht der Code ab wenn ein Feind gefunden wurde. Aber in JEDER richtung. anders gesagt wenn ein Fein in Abstand 1 gefunden wurde kann die Königin sich eigentlich gar nicht bewegen. Auch wenn links von ihr alles frei ist.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ach da hab ich dich falsch verstanden. Dachte irgendwie, dass du das möchtest. Im Nachhinein Quatsch.

Klar kann man den Code auch mit mehreren Zählvariablen umbauen und nicht abbrechen lassen...

int[] dir={-1,-1,-1,-1,-1,-1,-1,-1};
Position currentPos = //aktuelle Position
for(int i = 1; i<MAXDISTANZ; i++)
{
  if(dir[0] == -1) dir[0] = checkField(currentPos,i,0,1);
  if(dir[1] == -1) dir[1] = checkField(currentPos,i,1,1);
  if(dir[2] == -1) dir[2] = checkField(currentPos,i,1,0);
  if(dir[3] == -1) dir[3] = checkField(currentPos,i,1,-1);
  if(dir[4] == -1) dir[4] = checkField(currentPos,i,0,-1);
  if(dir[5] == -1) dir[5] = checkField(currentPos,i,-1,-1);
  if(dir[6] == -1) dir[6] = checkField(currentPos,i,-1,0);
  if(dir[7] == -1) dir[7] = checkField(currentPos,i,-1,1);
} 
int maxX = 7; int maxY = 7;
int checkField(Position cp, int i, int xdir, int ydir)
{  
  if(cp.x+i*xdir>maxX||cp.x+i*xdir<0) return -2; //stop iterating in this direction
  if(cp.y+i*ydir>maxY||cp.y+i*ydir<0) return -2; //stop iterating in this direction
  if(Spielfeld[currentPos.x,currentPos.y+i] == 2) return i;
  return -1; // keep searching
}

Hoffe, dass ich dich jetzt richtig verstanden habe. Das findet in jeder Richtung den nächsten Gegner.

Ist natürlich alles andere als schön. Die Rekursive Lösung fand ich schöner. Allerdings bin ich immernoch der Meinung, dass ein Kernel hier auch gut wäre, da er natürlich auf alle Figuren übertragbar wäre.

 

Link zu diesem Kommentar
Auf anderen Seiten teilen

Also wie gesagt meine aktuelle Variante ist diese:

                        case PFigur.Typ.Dame:
                            for (int i = Figur.position.y + 1; i <= 7; i++)
                            {
                                if (ignoreIndex.Contains(Feld[i][Figur.position.x]))
                                {
                                    movement[i, Figur.position.x] = 1;
                                }
                                else if (Feld[i][Figur.position.x] >= Enemy[0] && Feld[i][Figur.position.x] <= Enemy[1])
                                {
                                    movement[i, Figur.position.x] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[i, Figur.position.x] = 5;
                                    break;
                                }
                            }
                            for (int i = Figur.position.y - 1; i >= 0; i--)
                            {
                                if (ignoreIndex.Contains(Feld[i][Figur.position.x]))
                                {
                                    movement[i, Figur.position.x] = 1;
                                }
                                else if (Feld[i][Figur.position.x] >= Enemy[0] && Feld[i][Figur.position.x] <= Enemy[1])
                                {
                                    movement[i, Figur.position.x] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[i, Figur.position.x] = 5;
                                    break;
                                }
                            }
                            for (int i = Figur.position.x - 1; i >= 0; i--)
                            {
                                if (ignoreIndex.Contains(Feld[Figur.position.y][i]))
                                {
                                    movement[Figur.position.y, i] = 1;
                                }
                                else if (Feld[Figur.position.y][i] >= Enemy[0] && Feld[Figur.position.y][i] <= Enemy[1])
                                {
                                    movement[Figur.position.y, i] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[Figur.position.y, i] = 5;
                                    break;
                                }
                            }
                            for (int i = Figur.position.x + 1; i <= 7; i++)
                            {
                                if (ignoreIndex.Contains(Feld[Figur.position.y][i]))
                                {
                                    movement[Figur.position.y, i] = 1;
                                }
                                else if (Feld[Figur.position.y][i] >= Enemy[0] && Feld[Figur.position.y][i] <= Enemy[1])
                                {
                                    movement[Figur.position.y, i] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[Figur.position.y, i] = 5;
                                    break;
                                }
                            }

                            for (int i = Figur.position.x - 1, j = Figur.position.y + 1; (i >= 0 && j <= 7); i--, j++)
                            {
                                if (ignoreIndex.Contains(Feld[j][i]))
                                {
                                    movement[j, i] = 1;
                                }
                                else if (Feld[j][i] >= Enemy[0] && Feld[j][i] <= Enemy[1])
                                {
                                    movement[j, i] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[j, i] = 5;
                                    break;
                                }
                            }

                            for (int i = Figur.position.x - 1, j = Figur.position.y - 1; (i >= 0 && j >= 0); i--, j--)
                            {
                                if (ignoreIndex.Contains(Feld[j][i]))
                                {
                                    movement[j, i] = 1;
                                }
                                else if (Feld[j][i] >= Enemy[0] && Feld[j][i] <= Enemy[1])
                                {
                                    movement[j, i] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[j, i] = 5;
                                    break;
                                }
                            }

                            for (int i = Figur.position.x + 1, j = Figur.position.y + 1; (i <= 7 && j <= 7); i++, j++)
                            {
                                if (ignoreIndex.Contains(Feld[j][i]))
                                {
                                    movement[j, i] = 1;
                                }
                                else if (Feld[j][i] >= Enemy[0] && Feld[j][i] <= Enemy[1])
                                {
                                    movement[j, i] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[j, i] = 5;
                                    break;
                                }
                            }

                            for (int i = Figur.position.x + 1, j = Figur.position.y - 1; (i <= 7 && j >= 0); i++, j--)
                            {
                                if (ignoreIndex.Contains(Feld[j][i]))
                                {
                                    movement[j, i] = 1;
                                }
                                else if (Feld[j][i] >= Enemy[0] && Feld[j][i] <= Enemy[1])
                                {
                                    movement[j, i] = 2;
                                    break;
                                }
                                else
                                {
                                    movement[j, i] = 5;
                                    break;
                                }
                            }
                            break;

(Einrückung wegen Copy/Paste). Nur damit ihr eine Vorstellung habt. Und da das alles wirklich recht ähnliche Schritte sind hatte ich auf eine kleine Abkürzung gehofft. Wahrscheinlich werde ich also entweder die Rekursive Variante ausbauen, oder aber eine Funktion, die die schritte in eine Richtung macht und dann das für alle Wiederholen. Sieht zwar doof aus 4mal die gleiche Funktion aufzurufen aber hey. Vielleicht gehts ja in einer for-Schleife. Gibts ne Formel a la f(0)=0;0 f(1)=0;1 f(2)=1;0 etc..?

Link zu diesem Kommentar
Auf anderen Seiten teilen

int maxX = 7; int maxY = 7;
int[] dir={-1,-1,-1,-1,-1,-1,-1,-1};
Position currentPos = //aktuelle Position
List<Pair<int,int>> permutations = new List<Pair<int,int>>();
//your function yadda yadda
{
for(int a = -1; a <=1; a++)
{
 for(int b = -1; b <=1; b++)
 {
   if(a==0&&b==0) continue;
   permutations.add(new Pair(a,b));
 } 
}
for(int i = 1; i<MAXDISTANZ; i++)
{
  for(int p = 0;p<permutations.Count; p++)
  {
    Pair<int,int> p=permutations[p];
    if(dir[p] == -1) dir[p] = checkField(currentPos,i,p.a,p.b);
  }
}
                    }
                    
                    //other function
int checkField(Position cp, int i, int xdir, int ydir)
{  
  if(cp.x+i*xdir>maxX||cp.x+i*xdir<0) return -2; //stop iterating in this direction
  if(cp.y+i*ydir>maxY||cp.y+i*ydir<0) return -2; //stop iterating in this direction
  if(Spielfeld[currentPos.x,currentPos.y+i] == 2) return i;
  return -1; // keep searching
}

Eventuell so in der Art?

Link zu diesem Kommentar
Auf anderen Seiten teilen

diese funktion soll wohl ermitteln wie weit man sich in jede richtung bewegen kann hm? also bedeutend weniger steht da ja nicht.

Die Extra Funktion für checkField hätte nicht sein müssen, da es ja nur einmal aufgerufen wird. Löschen kann man die Permutationen ja leider nicht aus der liste hm? weil man ja listen nicht während des durchlaufens ändern kann >.> Die Permutationen könnte man vielleicht gleich füllen.

malzbies version ist allerdings bis jetzt die kürzeste. Deine ist vom Konzept her am einfachsten zu verstehen auch wenn ich bei dem Code ne weile gebaucht hab. Im Prinzip latschst du wieder in alle Richtungen. Nur mit ner abbruchbedingung.

 

Link zu diesem Kommentar
Auf anderen Seiten teilen

Stimmt, checkField hab ich einfach von oben kopiert jetzt kann man sie auch einfach in der Schleife lassen.

Statt aus der Liste zu löschen füge ich einfach etwas nur hinzu, wenn es in die Liste gehört.

Auch bei Malzbies Lösung wirst du allerdings die Richtung bestimmen müssen. Dafür kannst du natürlich den Permutationsteil von mir einbauen.

Hoffe wir konnten dir helfen? Ich fands auf jeden Fall spannend mal drüber nachzudenken.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ich suche immer neue Ansätze und algorithmen um meinen eklig langen code etwas zu kürzen und etwas kreativer zu gestalten :)
Darum bin ich froh über euer Feedback! Vielleicht mach ich ja mal n Thread auf wo ich den kompletten Schach_Code poste, damit jeder der Lust hat was dazu sagen kann aber...

Naja ich will nicht so aussehen wie der Typ der schreibt "hier ist wall of text, macht mal schön" XD
Und da es ja zu meiner Arbeit gehört will ich mir auch nicht zu sehr helfen lassen ^^

PS: Sind links zu Foren in ner Bachelor-Arbeit angebracht? XD

Link zu diesem Kommentar
Auf anderen Seiten teilen

Links zu Foren sind eher weniger angebracht. Abhängig vom Betreuer ist es auch relativ egal wie der Code aussieht solange er funktioniert.

Du solltest halt auch keinen Code aus dem Forum direkt benutzen. Aber das ist ja eh klar.

Ich hab noch keine Bachelorarbeit korrigiert in der eine Danksagung an Stackexchange war. Denke also, dass das nicht gemacht werden sollte.

Im Endeffekt solltest du den Kram ja auch selber lösen. Den Code kannst du posten wenn du die Arbeit benotet bekommen hast. Nicht, dass der Betreuer auf die Idee kommt Snippets mal zu googeln und dann hier herausfindet, dass die Schlüsselstellen von anderen kommen. Das wäre unvorteilhaft ;-)

Link zu diesem Kommentar
Auf anderen Seiten teilen

Naja ich formuliers mal so... Da ich viel in der MSDN oder halt hier nachgucke und recherchiere oder auch nachfrage ist das ja durchaus etwas was man Quelle nennen könnte.Natürlich kopiere ich den code nicht 1:1 ich ändere Dinge optimiere dinge und suche lediglich nach dem Basis-Algorithmus.

Und niemand kann ja schließlich ein Copyright auf einen Codeschnipsel anmelden. Und es ist ja nicht ne Danksagung aber wenn du  Ideen und Wissen aus einem Forum entnommen hast wo ist dann der Unterschied zu einem guten Buch? Nur dass in einem Forum mehrere Leute was schreiben und nicht nur einer ^_^

Link zu diesem Kommentar
Auf anderen Seiten teilen

für folgende Idee will ich jetzt aber ein goldenes Sternchen!

 

for (int j = -1; j < 2; j += 2)
	for (int i = 0; i < 4; i++)
	{
		double a = 1 - Math.Pow(0, i), b = i - 2 < -1 ? 1 : i - 2;
		Felder(new PFigur.Position((int)a*j, (int)b*j), Figur.position);
	}

mit

Action<PFigur.Position, PFigur.Position> Felder = null;
                    Felder = (Richtung, Position) =>
                    {
                        PFigur.Position newField = Position + Richtung;
                        if (newField.x >= 0 && newField.x < 8 && newField.y >= 0 && newField.y < 8)
                            if (ignoreIndex.Contains(Feld[newField.y][newField.x]))
                            {
                                movement[newField.y, newField.x] = 1;
                                Felder(Richtung, newField);
                            }
                            else if (Feld[newField.y][newField.x] >= Enemy[0] && Feld[newField.y][newField.x] <= Enemy[1])
                            {
                                movement[newField.y, newField.x] = 2;
                            }
                            else
                            {
                                movement[newField.y, newField.x] = 5;
                            }
                    };

 

Link zu diesem Kommentar
Auf anderen Seiten teilen

Archiviert

Dieses Thema ist jetzt archiviert und für weitere Antworten gesperrt.

×
×
  • Neu erstellen...