spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo Community,

ich brauch Hilfe bei folgender Sache:
Ich hab' über ein Koordinatensystem Punkt in gleichen Abstand (immer ganzzahlig > 0) erzeugt, diese kann man verbinden per Mausklick (immer 2 benachbarte, aber nur horizontal oder vertikal) und jetzt möchte Zyklen finden.
Dazu würde ich gerne Graphenalgorithmen nutzen, weiß aber nicht, wie ich die Punkte, die in einem 2-dimensionalen Array zu einem Graphen konvertiere.

Hier mal ein Beispiel 2x2
o - Punkte aus dem Array
| - Kanten
x - freie Felder/Zwischenräume

o--o--o
|xxxxx|
oxxoxo
|xxxxx|
o--o--o

Hier wären beispielweise alle Außenpunkte miteinander verbunden, der Graph ist ungerichtet, die Nummerierung der Knoten ist ebenfalls egal.

Das Ganze hat folgenden Hintergrund. Jede Verbindung zwischen zwei Punkten ist 'ne Labyrinth-Mauer - der äußere Zyklus ist bei Spielstart immer vorhanden. Also sobald genau zwei Zyklen vorhanden sind, sprich es sind im inneren nicht alle Felder erreichbar, soll eine Fehlermeldung erscheinen.


Ich wär euch sehr dankbar, wenn mir jemand das allgemeien Vorrgehen nennen kann, wie man Punkte zu einem Graphen konvertiert.



Mit freundlichen Grüßen


GrafGraph

Hi, danke.

Die Adjazenzliste sieht gut aus.

Kurze Nachfrage - Zyklensuch-Algos wie Floyd's Hase-und-Igel sind auf solche Listen anwendbar?

Ich würde dann auch meinen Graph gerichtet darstellen und nur Nicht-Außenpunkte als Startknoten zulassen.