Zum Inhalt springen

Scotland Yard Datenbank?


Tina92

Empfohlene Beiträge

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

post-83103-14430449523048_thumb.jpg

Danke für eure Hilfe!

Link zu diesem Kommentar
Auf anderen Seiten teilen

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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

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 :-)

Link zu diesem Kommentar
Auf anderen Seiten teilen

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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

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 von flashpixx
Link zu diesem Kommentar
Auf anderen Seiten teilen

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...