Scotland Yard Datenbank?

[Tina92]

Hallo an alle,

vielleicht kann mir jemand weiterhelfen.

Ich möchte das Scotland Yard Spiel programmieren.

Möchte dafür eine Datenbank anlegen und komme nicht weiter.

Meine Frage ist folgende:

Im Spiel gibt es Stationen von denen man mit Bus, Bahn oder Taxi auf eine andere Station fahren kann.

Jede Station hat mehrere Verbindungen zu einer Station und zu jeder Verbindung gibt es auch noch mehrere Möglichkeiten dort hin zu fahren.

Wie genau baue ich die Tabellen dafür auf.

Das schwere an dem Spiel sind die vielen Möglichkeiten für die Züge.

Ich habe euch auch noch ein Bild vom Spiel

Danke für eure Hilfe!

[Wuwu]

Hallo tina,

Ich denke mit den beiden suchworten graphentheorie und algorithmus solltest du auf den richtigen weg kommen.

[flashpixx]

Wie WuWu schreibt, solltest Du Dir zunächst Gedanken über die Repräsentation der Daten machen. Karten wie in diesem Fall werden als Graphen repräsentiert und d.h. Du hast ein quadratisches Wachstum der Datenmenge bezüglich der Knoten im Graphen. Ich rate dabei ganz dringend von einem "klassischen relationellen Datenbankmodell" ab, denn Graphen lassen sich in "Tabellenstruktur" nur sehr schlecht speichern und vor allem verarbeiten. Es gibt Graphdatenbanken, die für solche Zwecke deutlich besser geeignet sind bzw. es gibt für relationelle Datenbanken Addons, die eben Graphen deutlich effizienter speichern kann. Bei Graphdatenbanken ist aber ein Zugriff klassisch mit SQL nicht möglich

[lilith2k3]

Learn, Develop, Participate - Neo4j, the Graph Database

Wobei eine "Datenbank" ein wenig "overdone" wäre. Bei dem Spiel stehen alle Knoten und Kanten fest. Insofern brauchst Du keine externe Datenbank. Du könntest Dir eine Repräsentation der Karte selbst schreiben ...

[pr0gg3r]

Bei dem Spiel stehen alle Knoten und Kanten fest. Insofern brauchst Du keine externe Datenbank. Du könntest Dir eine Repräsentation der Karte selbst schreiben ...

Stimmt, man könnte eine Klasse "Knoten" erstellen, bei der jede Instanz eines Knoten eine eindeutige ID erhält. In jedem Knoten sind die Beziehungen zu den anderen Knoten in einem Listen-Attribute gespeichert. Ob du das dann "hardcodest" oder über eine Datenbank oder eine Text oder eine XML-Datei einliest, ist trivial.

[sas86ks]

Interessantes Projekt.. Würde mich freuen, wenn du uns auf dem Laufenden hälst und ggf. deinen Code veröffentlichst. Vorausgesetzt du möchtest das natürlich.

Viel Spaß / Erfolg

[flashpixx]

Stimmt, man könnte eine Klasse "Knoten" erstellen, bei der jede Instanz eines Knoten eine eindeutige ID erhält. In jedem Knoten sind die Beziehungen zu den anderen Knoten in einem Listen-Attribute gespeichert. Ob du das dann "hardcodest" oder über eine Datenbank oder eine Text oder eine XML-Datei einliest, ist trivial.

Siehe Repräsentation von Graphen im Computer

Wobei das Problem hier schon liegt, dass man das Straßennetz mehrfach vorliegen hat, einmal für Bus, dann für Taxi, für Boot und einmal U-Bahn, bei quadratisch wachsender Datenmenge mit vielen nicht-sparse Elementen durchaus problematisch.

Dadurch, dass man ja Wege finden muss braucht man auch entsprechende Algorithmen für die Auswertung mit einer Gewichtung für die Verkehrsmittel ( Dijkstra-Algorithmus ). Wenn Spieler und/oder Mr X vom Rechner gesteuert werden sollen, ist das Problem durchaus nicht mehr trivial.

[Tina92]

Danke euch allen für die Antworten,

bin immer noch am überlegen welcher Aufbau am geschicktesten ist.

lilith2k3 du hast geschrieben, ich könnte eine Repräsentation der Karte schreiben. Wie genau würdest du da vorgehen?

Ich habe mir überlegt ein mehrdimensionales Array zu schreiben, um damit die Felder fest zu legen

Danke im Voraus :-)

[flashpixx]

Ich habe mir überlegt ein mehrdimensionales Array zu schreiben, um damit die Felder fest zu legen

Ein Array ist recht ineffizient und verbraucht viel Speicher. Ich rate zu einer sparse Datenstruktur

[XspYroX]

Bestimmt sehe ich das völlig ineffizient, aber...

Wäre es bie dieser, noch überschaubaren, Menge an Möglichkeiten nicht auch Möglich eine Struktur nach folgendem Muster anzulegen? :

[sTATION 1]

<transport_bus_destinations> 10,12,3 </transport_bus_destinations>

<transport_taxi_destinations> 10,12,4,6 </transport_taxi_destinations>

<transport_metro_destinations> 4,25 </transport_metro_destinations>

[sTATION 2]

<transport_bus_destinations> ...

...

...

Somit könnte direkt geprüft werden, ob der Zug von STATION 1 per BUS zum Feld 9 valide wäre (wäre er in meinem Beispiel nicht).

In meinen Augen wäre da nur der Aufwand, diese "Config" oder "Datenbank" am Anfang anzulegen. Aber schwer wäre das nicht, da man stur der Reihe nach die Stations durchgeht.

Wie gesagt: Vermutlich nicht das genialste, aber es wäre leicht und soo groß wäre die Datenbank auch nicht (zumal man sich damit Rechenlast spart, da kein wirklicher Algorithmus verwendet wird.

Nur so eine Idee

LG

XspYroX

[flashpixx]

Ich denke die Problematik, die Du hier ansprichst, ist für andere interessant, darum führe ich das etwas aus:

Wir nehmen einmal Deine XML, in der wir das Straßennetz abspeichern. Du hast dann ein Problem, dass Du in der XML Stationen erzeugen kannst, die nicht in Deinem Straßennetz vorhanden sind ( Erreichbarkeitsproblem in Graphen bzw Zusammenhang (Graphentheorie) ). Du musst also sicherstellen können, dass Dein Graph zusammenhängend ist, d.h. jeder Punkt erreichbar ist. Mit XML alleine ist das nicht machbar.

Das zweite Problem, was daraus resultiert, wäre, wenn Du einen gerichteten Graphen hast, d.h. Du kannst von einer Station nur in eine Richtung fahren, dann entsteht das Problem der Traps, d.h. ich kann an eine Station gelangen von der ich nicht mehr weg komme (Sackgasse). Dies solltest Du auch verhindern, wenn Du so etwas machst.

Als drittes eher praktisches Problem bei XML hast Du, dass Du in Deiner Node z.B. für Bus formal eintragen kannst, zu der keine Station existiert, d.h. Du musst also auch sicherstellen, dass Deine XML inhaltlich valide ist.

Als weiteres Problem bei XML ist, dass Du es parsen bzw. den gesamten Baum im Speicher halten musst. Damit hast Du aber das Problem der Referenzen zwischen Deinen XML Nodes und den Graphpunkten nicht gelöst, denn wenn ich auf einer XML Node stehe und ich weg will, muss ich die passende Zielnode beim Wechsel aus dem Speicher holen, sprich ich muss bei SaX den Parser anweisen "such mal die passende Node" (Aufwand).

Als nächstes ist dann noch die Frage, wie Du die Informationen an den Spieler hängst, denn ein Spieler muss ja wissen, auf welchem Feld er steht. Du musst also immer eine Referenz oder Kopie auf Deine XML an den Spieler hängen, so dass Du hier bei großen Straßennetze durchaus viel Speicheraufwand hast. Wenn ich da jetzt den Gedanken weiter spinne und z.B. das ganze über Netz auch spielen möchte, dann muss ich mir ja auch überlegen, wie ich das Straßennetz für alle Spieler gleich aussehen lasse, eine XML kann ich leicht per Hand verändern, so dass jeder Spieler sich lokal seine Karte verändern kann. Wenn ich dann noch zulasse, dass Spieler gleichzeitig ziehen können und die Karte z.B. über einen Webservice bereit stelle, dann habe ich 2 Anfragen der Spieler bei der für jeden Zugriff ein XML Prozess gestartet wird, der die XML parsen muss. Für große Anzahl an Spielern und große Karten, ist das nicht mehr praktikabel.

Auch bei mehreren Spielern pro PC, solltest Du Dir überlegen, wie Du diese XML Daten passend verarbeitest, denn Du hast nur die Möglichkeit den Baum einmal zu lesen, ein Baum ist aber kein Graph, d.h. Du brauchst noch irgendwie eine Transformation des Baumes in das Straßennetz oder Du musst das in "Echtzeit" machen, was durchaus auch nicht unkritisch ist.

Was man ja gerne hätte, ist, dass der Spieler weiß wo er steht, d.h. er hat irgendwie eine Position, diese Position verweist dann auf einen Knoten im Straßennetz. Ich kann den Knoten fragen "welche Verbindungen erlaubst Du wohin", ebenso kann ich die Person fragen "wo stehst Du gerade". Der Knoten wiederum braucht nicht das komplette Straßennetz speichern, er muss lediglich eine Liste mit Knoten speichern, auf die man sich bewegen kann, d.h. allerhöchstens eine Adjazenzliste. Rein technisch braucht er noch nicht mal das, denn bei sehr vielen Verkehrsmitteln und vielen Verbindungen wäre das durchaus Speicherbedarf der dann für alle Spieler anfällt. Er muss nur eine Referenz auf ein Graphdatenbankobjekt speichern, dass dann in Abhängigkeit von seiner aktuellen Position die Liste mit den Nachbarknoten liefert, d.h. die Adjazenzliste muss ich allenfalls temporär halten (diese Liste kann ich dann nochmals reduzieren, wenn ich z.B. die Abfrage so erstelle, dass ich das Verkehrsmittel vorgebe).

Zusätzlich kann ich damit auch ohne Probleme sehr große Netze mit sehr vielen unterschiedlichen Verkehrsverbindungen darstellen (z.B. Flugzeug, Bahn, U-Bahn, Bus, Taxi, zu Fuß), weiterhin kann ich auch gerichtete Graphen erzeugen, weil mir die Datenbank ggf abnehmen kann dafür zu sorgen, dass meine Knoten im Graphen immer erreichbar sind.

Graphstrukturen sollten immer sehr gut durchdacht werden, denn durch das quadratische Wachstum der Datenmenge kommt man sehr schnell an die physischen Grenzen seines Rechners, wenn man es naiv macht.

[flashpixx]

Was mir dazu noch einfällt ist, dass Du Dir das Spiel sogar mit realen Daten erzeugen kannst DE:Öffentlicher Verkehr - OpenStreetMap Wiki bzw http://wiki.openstreetmap.org/wiki/DE:%C3%96pnvkarte

Bearbeitet 8. April 2013 von flashpixx

[XspYroX]

Was mir dazu noch einfällt ist, dass Du Dir das Spiel sogar mit realen Daten erzeugen kannst DE:Öffentlicher Verkehr - OpenStreetMap Wiki bzw DE:Öpnvkarte - OpenStreetMap Wiki

Gute Idee

Und dann als Browsergame und Rundenbasierend. Würde mir sogar echt gefallen

[flashpixx]

Wäre durchaus möglich, theoretisch kann man aber auch ein 3D Game machen, denn OSM liefert ja auch Gebäudetypen etc. d.h. man könnte immer den Ausschnitt der Straße in dem man sich befindet real in 3D z.B. via Irrlicht Engine - A free open source 3D engine rendern, d.h. durch die Straßen kann ich dann laufen und wenn ich eben schneller voran kommen will, nehm ich halt andere Verkehrsmittel (wenn man dann möchte kann man ja auch ein bisschen in die Ego-Shooter-Perspektive gehen). Für die Benutzung der Verkehrsmittel muss man Geld bezahlen, wobei man das ja dann wieder daran koppeln kann, dass man Sachen für Leute transportieren muss, bzw. irgendwelche Subchallenges hat.

Zusätzlich kann man ja auch ein Kommunikationssystem (a.k. Telefon) erstellen, so dass man sich zum Telefonieren treffen kann (was dann einen Chat ermöglicht).

Nimmt man als Grundlage nicht eine Stadt, sondern z.B. die komplette Weltkarte und dazu dann mehrere Jäger und mehrere gejagte, dann ist das durchaus interessant, wenn man dann auch z.B. die Reisezeit entsprechend berechnet.

Für die Gejagten kann man ja dann auch noch diverse Möglichkeiten einbauen, wie sie sich z.B. verstecken können.

Ich denke da so in die Richtung Agentenspiel.

Rundenbasiertes Spiel halte ich für irgendwie nicht so schön, annähernd Echtzeit fände ich viel interessanter.

Bearbeitet 8. April 2013 von flashpixx