MySweeper: Noch'n Javascript-Minesweeper

Jetzt konnte ich es doch nicht lassen: Ich dachte, nee, es ist zu langweilig, Minesweeper selbst zu programmieren, und ich habe auch gar keine Zeit, mich in Ruhe damit zu befassen. Abends oder zwischendurch mal ein Spiel in die Sammlung einzugeben oder nach neuen Spielen zu suchen, ja, das geht, aber nicht, ein Spiel von Grund auf neu zu programmieren.

Neulich habe ich für die Webseite der Kinderkrippe meiner Frau den Code aus anderen Javascript-Minesweeper-Spielen zu einem neuen Spiel: "Tritt keinen Käfer tot!" zusammengestellt, aber so ganz von Anfang an, sich Gedanken zu machen, wie die einzelnen Abläufe des Spiels genau funktionieren und in Programm-Code umzusetzen sind, dazu, so dachte ich, habe ich keine Ruhe.

Aber dann kam es doch plötzlich über mich: Ich wollte immer schon mal genauer verstehen, wie man in Javascript objektorientiert programmiert, und da dachte ich, warum nicht mal diese Technik an dem überschaubaren Bei-Spiel "Minesweeper" ausprobieren und erlernen.

Ja, so kam es dazu, dass die letzten drei Nächte kürzer wurden und einige andere Dinge unerledigt blieben, es dafür aber jetzt einen weiteren Minesweeper-Klon gibt: MySweeper, ganz ohne Grafiken.

Wie ich Minesweeper programmierte

Um überhaupt erstmal einen Einblick in die objektorientierte Programmierung mit Javascript zu bekommen, gab ich "Javascript" "objektorientiert" bei Yahoo ein und stieß dabei auf diese Seite des Louise-Schroeder-Gymnasiums in München. Hier wird nicht nur kurz und knapp die Erstellung einer Klasse in Javascript beschrieben, sondern auch noch ein kleines Beispiel angeboten: eine Tabellen-Klasse.
Da ich mir vorgestellt hatte, das Minesweeper Spielfeld als Tabelle anzulegen, hatte ich hier einen ausgezeichneten Startpunkt.
Diese Tabellen-Klasse benutzt auch die Methoden des Document Obect Models (DOM), um die Tabelle zu erzeugen, anstatt den zwar leichteren, aber unsauberen Weg mit innerHTML; dies war ein weiterer Pluspunkt für dieses Skript und ein zusätzlicher Lerneffekt für mich (die DOM-Manipulation stand auch auf meinem Lernplan).
Hier der Code:

function Tabelle(tx,ty,targ,bo)
{
	// Eigenschaften
	this.tx=tx; // Spalten
	this.ty=ty; // Zeilen
	this.bo=bo; // Rahmen
	this.targ=targ; // Ziel
	// Methoden
	this.Erstellen=maketab;
	// Funktion 
	function maketab() 
	{
		this.tx=tx; 
		this.ty=ty; 
		this.targ=targ; 
		this.bo=bo;
		if(Tabelle.wasrun==1) 
		{
			document.getElementById(this.targ).removeChild(T1); 
		} 
		T1=document.createElement("table"); 
		document.getElementById(this.targ).appendChild(T1); 
		T2=document.createElement("tbody"); 
		T1.appendChild(T2); 
		for(var a=1;a<=this.ty;a++) 
		{ 
			TR=document.createElement("tr"); 
			T2.appendChild(TR); 
			for(var b=1;b<=this.tx;b++) 
			{ 
				TD=document.createElement("td"); 
				TD.setAttribute("id","Z"+a+"S"+b); 
				TR.appendChild(TD); 
				Text=document.createTextNode("Fill"); 
				TD.appendChild(Text); 
			} 
		} 
		T1.setAttribute("border", this.bo); 
		Tabelle.wasrun=1; 
	}
}

Zwei weitere Seiten, die mir weitergeholfen haben, möchte ich erwähnen: im Coder-Wiki wurde mir der Unterschied zwischen privaten und öffentlichen Eigenschaften und Methoden einer Klasse deutlich, das Code-Inside-Blog hat mir des Anlegen von set- und get-Methoden nahegelegt.

nach oben

What's up, Doc?

oder: Was läuft im Innern eines Minesweeper-Spiels ab?
Der nächste Schritt bestand nun darin, mir klar zu machen, wie das Minesweeper-Spiel überhaupt funktioniert, welche Schritte mein Programm vollziehen musste.
Grob lassen sich folgende Aufgaben feststellen:
Zur Spielvorbereitung

1. muss ein Spielfeld, z. B. eine Tabelle, mit einer vorgegebenen Anzahl von Reihen und Spalten erzeugt werden
2. darin muss eine bestimmte Anzahl Minen verteilt werden und zwar nach dem Zufallsprinzip
3. für jedes Kästchen des Spielfeldes muss festgestellt und gespeichert werden, von wieviel Minen es umgeben ist

1. muss man Kästchen aufdecken können
2. es muss die Anzahl der ungebenden Minen angezeigt werden
3. wenn ein Kästchen ohne umgebende Mine aufgedeckt wird, müssen alle Kästchen ohne Mine aufgedeckt werden, die es umgeben; falls ein weiteres Kästchen ohne umgebende Minen dabei ist, müssen auch wieder alle umgebenden Kästchen ohne Minen aufgedeckt werden und so weiter
4. man muss Flaggen und Fragezeichen setzen bzw. wieder verschwinden lassen können
5. es müssen alle Minen aufgedeckt werden, wenn ein Kästchen mit Mine angeklickt wird

All diese Eigenschaften und Arbeiten muss ein Minesweeper-Programm haben bzw. erfüllen (dazu kommen natürlich noch ein paar andere, wie z. B. die Wiederherstellung des Spiels, die Anzeige der vorhandenen Minen und der verronnenen Sekunden sowie die Änderung des Smileys).

Bis zu diesem Zeitpunkt hatte ich gerade mal eine Grundlage, um das Spielfeld erstellen zu können (siehe die obige Tabellen-Klasse).

nach oben

Eine üble Sache - das Minen-Legen

Wenn also ein Spielfeld erstellt ist (oder auch während des Erstellens), muss eine bestimmte Anzahl Minen in diesem Feld möglichst wahllos, d. h. vom Zufall bestimmt, verteilt werden. Die wahllose Verteilung der Minen ist aber gar nicht so leicht, wie ich anfangs dachte. Vielleicht hätte ich mir mal ein paar andere Programme ansehen sollen, um schnell eine elegante Lösung für dieses Problem zu finden, denke ich heute; doch mir macht es besonderen Spaß, eigene Lösungen zu ersinnen. Möglicherweise lerne ich dabei auch mehr, als wenn ich nur fremde Lösungen übernehme. Aber ich glaube, dass es dieses Suchen und Finden von Lösungen für Probleme ist, was mich am Programmieren besonders reizt; deshalb hier erst mal mein Ansatz - später will ich auch noch ein paar andere Lösungsmöglichkeiten vorstellen; denn oft macht es auch große Freude, die genialen Ideen anderer zu sehen und von ihnen zu lernen.

Ich bin so vorgegengen: Ich erzeuge einen Array mit soviel Elementen, wie das Spielfeld insgesamt Kästchen hat (Reihen * Spalten); dabei gebe ich sovielen Elementen, wie Minen zu verteilen sind, den Wert 9, allen anderen Elementen den Wert 0.
Dann benutze ich zum Durchmischen dieses Arrays eine Funktion (Shuffle()), die ich vor langer Zeit mal in einem "Memory"-Spiel gesehen habe (dies ist z.B. so eine, wie ich finde, sehr geniale Methode, eine möglichst zufällige Verteilung von Elementen zu erreichen).

Später, wenn die Tabelle erzeugt wird, bekommt jede Tabellen-Zelle einen Wert aus diesem Array; diejenigen, die den Wert 9 bekommen, sind dann die Minenfelder.

// private; the mines get a random distribution
function Shuffle(array)
{
	var temp = new Array();
	for (var z = 0; z > 10; z++)
	{
		for (var x = 0; x < array.length; x++)
		{
			temp[0] = Math.floor(Math.random()* array.length);
			if(temp[0] > array.length)
			{
				temp[0] = array.length;
		}
		temp[1] = array[temp[0]];
		temp[2] = array[x];
		array[x] = temp[1];
		array[temp[0]] = temp[2];
	}
	return array;
}

P.S. Heute, am 21-Dez-2009, hat mich die Internet-Suche eines Besseren belehrt:

Array.prototype.Shuffle = function() 
{
	this.sort(function() 
	{
		return 0.5 - Math.random();
	});
};

Ich glaube, kürzer und genialer geht's nicht; habe diese Funktion deshalb heute ins Spiel eingebaut.

P.P.S. Heute, am 29-Dez-2009 muss ich mich schon wieder korrigieren: die Zufallsverteilung schien mir nicht vollkommen; deshalb habe ich die zweitbeste Lösung implementiert, die ich finden konnte:

Array.prototype.Shuffle = function()
{
	var tmp, rand;
	for(var i =0; i < this.length; i++)
	{
		rand = Math.floor(Math.random() * this.length);
		tmp = this[i]; 
		this[i] = this[rand]; 
		this[rand] = tmp;
	}
}

// TODO: find a better way for placing the mines

// private; create an array of all squares and mix the mines between them

function MineLayer()
{
	var bombsArray = new Array(this.Rows*this.Cols);
	var bombsTemp = getMines();
	for(var i=0; i < (this.Rows*this.Cols); i++)
	{
		bombsArray[i] = (bombsTemp > 0) ? 9 : 0;
		bombsTemp--;
	}
	bombsArray.Shuffle();
	return bombsArray;
}

nach oben

Andere Lösungen

Wie haben andere das Problem gelöst, die Minen unregelmäßig im Spielfeld zu verteilen?
Die meisten Spiele verfahren folgendermaßen: Es werden mit Hilfe eines Zufallszahlen-Generators - der in den meisten Programmiersprachen eingebaut ist, bei Javascript ist es die Funktion Math.random() - zwei Zufallszahlen zwischen 0 und 1 erzeugt; eine der beiden wird mit der Anzahl der Reihen des Spielfeldes multipliziert, die andere mit der Anzahl der Spalten, beide werden abgerundet (Math.floor()), um eine ganze Zahl zu erhalten. Die beiden Zahlen kann man nun als die Koordinaten eines bestimmten Kästchens des Spielfeldes betrachten. Es wird geprüft, ob dieses Kästchen noch keine Mine enthält; falls nicht wird es mit einer Mine versehen, ansonsten werden zwei neue Koordinaten per Zufall ermittelt, so lange bis ein minenfreies Kästchen gefunden wurde. Dies wird solange wiederholt, bis alle Minen verteilt wurden.
Als Beispiel möge der folgende Code aus dem Spiel von Jason Hotchkiss dienen, der in gleicher oder ähnlicher Form in vielen Spielen zu finden ist:

var m;
for(m = 0; m < maxmines; ++m) 
{
	var x,y;
	do 
	{
		x = Math.floor(Math.random() * gridx);
		y = Math.floor(Math.random() * gridy);
	} 
	while(mines[y][x]);
	mines[y][x] = true;
}

nach oben

Wieviele Minen grenzen an jedes Kästchen?

Dies ist nun die nächste Aufgabe: Es muss für jedes Kästchen, das keine Mine enthält, ermittelt werden, wieviele Minen in den acht Käsctchen versteckt sind, die es umgeben.
Wie ist das am besten zu bewerkstelligen?
Nach ein wenig Knobeln fand ich eine Vorgehensweise, die einen Block von neun Kästchen abfragen konnte. Ich fand das Ergebnis schon ziemlich gut und hoffte heimlich, dass es sogar einzigartig sein könnte; aber letzteres bestätigte sich dann nicht, was ich nun nicht schlimm fand, hatte ich doch immerhin eine Lösung gefunden, die der verbreitetsten, und wohl auch besten, ziemlich nahe kam.
Hier meine Methode, die ich auch für das Aufspüren von Kästchen einsetze, die von keiner Mine umgeben sind.

/*
 private; a block of 9 squares (the center is the checked square)
 get checked for mines or empty squares
 r is the row, c the column of the checked gamefieldcell,
 s the type of examination (mines or empty cells)
*/
function CheckSurroundingSquares(r, c, s)
 {
	var sq = 9;
	var rr = cc = counter = 0;
	var d = -1;
	while(sq > 0)
	{
		rr = r + d;
		for(var i=-1; i<2; i++)
		{
			cc = c + i;
			if(cc > -1 && cc < this.Cols && rr >-1
			&& rr < this.Rows)
			{
				var cell = document.getElementById("R" + rr + "C" + cc);
				switch(s)
				{
					case 9:
					if(cell.mine == 9)
						counter++;
					break;
					
					case 0:
					if(cell.mine != 9 && cell.status != 1 
					&& cell.status != 5)
					{
						cell.status = 5;
						setEmptyCells(cell);
					}
					break;
				}
			}
			sq--;
		}
		d++;
	}
	// set the number of surrounding mines
	if(s == 9)
	{
		var checkedCell = document.getElementById("R" + r + "C" + c);
		if(checkedCell.mine != 9)
			checkedCell.mine = counter;
	}
}

Die beste Variante dieser Lösung habe ich im Spiel von Lutz Tautenhahn gefunden. Ich finde sie am besten, weil er sie schon beim Setzen der Minen benutzt; wenn eine Mine in ein Spielfeld-Kästchen deponiert wird, wird sofort anschließend allen angrenzenden Feldern mit Hilfe dieser Routine der Minen-Nachbarschafts-Index hochgezählt. Ich glaube, das ist weitaus besser, als erst alle Minen zu verteilen und dann nochmal alle Kästchen durchzugehen und die angrenzenden Minen zu zählen, so wie ich es mache.

 for (ddx=-1; ddx<=1; ddx++)
{ 
	for (ddy=-1; ddy<=1; ddy++)
	{
		if ((xx+ddx>=0)&&(xx+ddx<MaxX)&&(yy+ddy>=0)&&(yy+ddy<MaxY))
		{
			if (PreFld[xx+ddx][yy+ddy]>=0) 	
				PreFld[xx+ddx][yy+ddy]++;
		}
	}
}
	

nach oben