Raum modellieren.
-
Hi!
Ich sollte für eine Simulation so etwas wie ein 'Spielfeld' erstellen, also einen Raum (2-, 3- oder höherdimensional). Dieser sollte natürlich uhm.. diskret sein, also immer schön unterteilt in 'spielfelder'. Da ich nur ein Gymnasiast bin, fehlen mir hier Mathematik- und Datenstrukturen-Kenntnisse...
Wie kann man sowas (objektorientiert) umsetzen? Das Ding an sich sollte dynamisch sein, zur Laufzeit vergrösserbar.
Und ich habe das Gefühl, dass ein simples mehrdimensionales Array nicht die Lösung ist (zur info: ich programmiere das in Java)Danke für irgendwelche Ideen...
Raphael
-
wenn du kein mehrdimensionales array willst, was willst du dann?
-
na ich möchte, dass jedes Element dieses Array z.B. durch eine Methode alle seine räumlichen Nachbarn zurückliefert. Und diese Struktur sollte auch nach 'allen Seiten' wachsen können zur Laufzeit...
-
Nun ja, irgendwie is deine Beschreibung arg schwammig um dir konkret helfen zu können. Aber im Momemt hört es sich so an, als wäre ein Baum eine geeignete Datenstruktur.
-
du willst hashlisten (kann anders heissen) und etwas handarbeit. so eine "wer sind meine nachbarn" methode musst du selber schreiben.
-
Kann man doch ne schöne Klasse draus bauen. Man muss zwar nicht direkt, aber irgendwo "unten" wohl doch Arrays verwenden. Kenne mich allerdings nicht besonders mit Java und was das da so anbietet aus. Soll die Dimension zur Laufzeit auch inkrementiert werden können?
-
bloodlord, scheinbar ja.
hashlisten sind da ganz brauchbar, zumal man riesige bereiche abdecken kann, ohne dabei unbenutzte bereiche als speicher manifestieren zu muessen. lookup ist i.d.R. optimiert, also log n. wenn du dir ueber die dimensionen klar bist, kannst du ja dann eine hashliste von hashlisten von hashlisten (mit jeweils einer zahl als key) oder eine einzige hashliste mit einem 3-tupel als key fuer einen 3d raum basteln.
<werbung>in D sind hashlisten in der sprache verankert und imho einfacher als alle c++ stl hashlisten zu benutzen</werbung>
-
c++ stl hashlisten
zeigt schon das du keine ahnung hast.
-
LOL! schrieb:
c++ stl hashlisten
zeigt schon das du keine ahnung hast.
jep, ich hab wenig bis keine ahnung von c++.
-
Könntest du kurz begründen, wieso eine Hashliste gegenüber einem Baum besser ist, wenn er beliebig viele Nachbarn zu einem Knoten verwalten muss?
-
kann ich nicht, weil ich mich mit graphentheorie nicht beschaeftigt habe. wenn du bessere ratschlaege geben kannst, dann tu das bitte. ich jedenfalls werde nichts und niemanden verteidigen. ich bin schliesslich atheist.
-
Wenn er eine Struktur braucht die zu einem Knoten beliebig viele Nachbarn (er sprach ja von mehreren Dimensionen) speichern will, so ist ein offensichtlich Baum eine sehr geeignete Struktur. Ein Hashliste ist letztlich auch nur eine Liste mit optimiertem Zugriff und imo nicht so sehr dafür geeignet.
-
wie wuerde das funktionieren, dass ich koordinaten habe und dazu den knoten will?
-
Ich wuerde auch zum Baum raten. Im Zusammenhang mit 'Nachbarn' waere ein kd-tree oder ein R-tree vielleicht was Passendes.
Studenten unter sich.
-
Apollon schrieb:
Ich wuerde auch zum Baum raten. Im Zusammenhang mit 'Nachbarn' waere ein kd-tree oder ein R-tree vielleicht was Passendes.
Studenten unter sich.
Unter einem Baum verstehe ich etwas, was keine Zyklen beinhaltet. Ist vielleicht ein bischen zu eingeschränkt hier. Ganz allgemein muss man sich hier wohl irgendeine Datenstruktur für einen Graphen bauen, die man dann vielleicht mit einer entsprechenden spezialisierten Schnittstelle wrappt.
Ich habe mir soetwas mal in der Art gebaut:
1. Eine Hash-Tabelle, in der ich von den Werten der einzelnen Knoten zu den Knoten kommen kann.
2. In jedem Knoten eine Liste mit den Nachbarn.
Dann sollte man eigentlich alles haben, was man braucht.
-
Nur wenn Du des Nachbars-Nachbarn sowie des Nachbars-Nachbars-Nachbarn usw. haben willst. Kann mir aber nicht vorstellen, dass sowas fuer Raummodellierung wichtig ist.
-
Apollon schrieb:
Nur wenn Du des Nachbars-Nachbarn sowie des Nachbars-Nachbars-Nachbarn usw. haben willst. Kann mir aber nicht vorstellen, dass sowas fuer Raummodellierung wichtig ist.
Naja, vielleicht habe ich euch falsch verstanden. Wie wollt ihr denn den Baum ansetzen? Was ist die Wurzel, was sind die Söhne, was die Blätter usw.?
-
Ich habe angenommen, dass es ihm mehr um effizientes Culling sowie effiziente Kollisionserkennung geht, als um Wegfindung oder Fluss.
Was mir so eben einfaellt: Er spricht sogar vom mehrdimensionalen Raeumen ( > 3). Vielleicht waere sogar Bitmap-Indexing was fuer ihn.
-
Apollon schrieb:
Ich habe angenommen, dass es ihm mehr um effizientes Culling sowie effiziente Kollisionserkennung geht, als um Wegfindung oder Fluss.
Kann ich seinen Beiträgen nicht entnehmen. Wie kommst du plötzlich auf so Computergrafik-Sachen und so? Aus meiner Sicht will er ein diskretes Spielfeld in einer Datenstruktur realisieren. Zum Beispiel ein Spielfeld eines Schach-Spiels oder so. Da hast du also einzelne Felder mit entsprechenden Nachbarschaftsbeziehungen "Feld rechts vom aktuellen" und so. ...nur will er das dann halt noch n-dimensional und erweiterbar haben, damit er wohl sowas sagen kann wie "Erzeuge ein neues Feld oberhalb des aktuellen" oder "Ziehe diese Spielfigur in der 4. Dimension ein Feld zurück".
-
Ich schrieb ja, dass ich es angenommen habe (ohne konkreter indizien).