spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Du versuchst einen Zyklus in einem Graphen zu finden. Über das Problem haben sich schon viele andere vor dir Gedanken gemacht Deine Matrix kannst du ja relativ einfach in einen Graphen überführen. Dabei kannst du dann selbst sagen, dass für die Diagonalen keine Kanten angelegt werden. Ist es das was du genau suchst? Oder geht es dir eigentlich eher um die Felder die nicht im Graphen sind und du möchtest nun genau den Verlauf darum haben? Wenn es darum geht, könntest du mal Floodfill angucken. Du nimmst ein zufälliges Feld, welches kein Weg ist, füllst dann die Fläche, dabei erhälst du dann genau deinen Raum. Wenn du jetzt wissen möchtest, ob auch diagonal kein weiterer Raum angrenzt, könntest du ja auch so schon relativ einfach die Tiles rund um den Raum abfragen. Damit hättest du dann schon eine Lösung für dieses Problem. Vielleicht habe ich dich aber auch nicht richtig verstanden.

Du ersetzt durch Floodfill alle . durch O. Die X bleiben wie sie sind, und die übrig gebliebenen . sind dann deine Innengebiete. Floodfill ist sehr einfach und hat lineare Laufzeit zum Matrixvolumen, ein schlechter Graphenalgorithmus wäre vermutlich komplexer.
Du musst dir nur noch überlegen, von wo du überall Floodfill starten musst. Vielleicht von sämtlichen Randpixeln, vielleicht nur von einer Ecke, du musst dir halt überlegen, wie du "Innen" definieren willst.