4. Wie speichere ich am besten Wegpunkte

Wie speichere ich am besten Wegpunkte

  • ?

    Ich möchte für verschiedene Wegpunkte (Objekte) die Information speichern, ob sie miteinander verbunden sind. Im Moment verwende ich ein 2dimensionales Array:

    bool isConnected[NUMBER_OF_WAYPOINTS][NUMBER_OF_WAYPOINTS];

    Das Problem ist, dass ich alle Beziehungen doppelt drin habe, also a ist mit b verbunden und b mit a.
    Was für Möglichkeiten habe ich denn sonst noch? Das wichtigste ist der schnelle Zugriff.

    0
  • ?

    Mach doch eine List.

    NULL->A->B->C->D->...

    Nachteil: Verknüpfungen mit dem Vorgänger sind nicht möglich.

    IF ( B VERKNÜPFT MIT A ) <- geht nicht

    oder

    NULL<-A<->B<->C<->D<->...

    So ist es schon besser.

    0
  • S

    Was is'n das für'n "Game"?? N Virus?!?
    Oder DOS-only?? 😃

    0
  • ?

    Wie kommst du auf Dos only

    0
  • T

    Am besten mit Hilfe von 2 Arrays:

    Das erste Array ist eine Liste mit Knoten und deren Nachfolger. z.B. hast Du einen Knoten (oder Wegpunkt) 1 und einen Knoten 2 usw.

    Die Liste koennte dann z.B. so aussehen:

    Knoten      1  1  1  2  2 ...
Nachfolger  2  3  6  4  5 ...

    Das heisst, dass 2, 3 und 6 Nachfolger von 1 ist, dass 4 Nachfolger von 2 ist und 5 auch Nachfolger von 2 ist.

    In der 2 Liste verwaltest Du diese 1 Liste. Diese Liste wird Indexliste genannt. Sie dient vor allem dem schnellen Zugriff. Die Indexliste zur oberen Liste wuerde dann so aussehen:

    Knoten 1  2  ...
Start  0  3  ...

    d.h. die Infos fuer Knoten 1 beginnen in der oberen Liste bei Arrayeintrag 0, die Eintraege fuer Knoten 2 beginnen dann bei Arrayeintrag 3.

    Entsprechend kann man auch Vorgaengerlisten bilden.

    0
  • ?

    Optimizer schrieb:

    Wie kommst du auf Dos only

    Von wegen 16-Bit-Teilsystem un' so... 🙂

    0
  • ?

    Optimizer schrieb:

    Ich möchte für verschiedene Wegpunkte (Objekte) die Information speichern, ob sie miteinander verbunden sind. Im Moment verwende ich ein 2dimensionales Array:

    bool isConnected[NUMBER_OF_WAYPOINTS][NUMBER_OF_WAYPOINTS];

    Das Problem ist, dass ich alle Beziehungen doppelt drin habe, also a ist mit b verbunden und b mit a.
    Was für Möglichkeiten habe ich denn sonst noch? Das wichtigste ist der schnelle Zugriff.

    Sind das wirklich doppelte Beziehungen? Also sind alle Verbindnugen symmetrisch? Dann speichere doch einfach nur die Werte der Adjazenzmatrix über der Diagonale.

    0
  • ?

    Ja, kommt sehr auf die Eigenschaften Deines Graphen an. Ist er z.B. "dicht" besetzt und ungerichtet, dann auf jeden Fall Matrixdarstellung, dabei nur die obere Dreiecksmatrix. Ist er nicht "dicht" besetzt und ist er auch noch entsprechend gross, dann Listendarstellung.~tOmUsA

    0
  • R
    Mod

    " Das wichtigste ist der schnelle Zugriff."
    in welchem Zusammenhang denn? Von einem Wegpunkt aus alle Verbindungen finden, oder grundsätzlich alle Verbindungen zu finden?

    Ich denke mir, dass falls du nur zwischendurch prüfen möchtest, ob eine Verbindung vorhanden ist, kann das über Mathe schneller sein, z.B. über den maximalen Radius schonmal die meißten Punkte ausschliessen oder etwas änliches. Oder was plannst du? 🙂

    rapso->greets();

    0
  • ?

    Ich muss möglichst schnell alle Wegpunkte mit allen prüfen können, ob sie verbunden sind.

    0
  • R
    Mod

    Wenn es in relation zu den Wegpunkten nur wenige Verbindungen gibt, und du schnell alle Verbindungen haben möchtest von einem Wegpunkt aus gesehen, dann könnte es optimaler sein an jedem Punkt ein array von Zeigern auf die verbundenen Wegpunkte zu haben, wobei du dann natürlich nicht weniger Redundanz hast, aber vielleicht trotzdem weniger Speicherverbrauch... je nacht Wegpunkte zu Verbindungen verhältniss.

    rapso->greets();

    0
  • V

    also in der matrix of bool sinds 16 bit pro möglicher kante. legt man nen vector<bool> drunter, sinds 2 bits. das auf 1 bit zu reduzieren, indem man nicht nur das obere dreieck nimmt, sondern die matrix auch zusammenstacht, tut wohl nicht not. die zugriffszeit ist O(1), also recht optimal.
    mit verzeigerungen in verketteten listen hat man O(anzahl der kanten pro punkt), was durchaus lahmer klingt. wenn ich mal von festen wegpunkten ausgehe, reicht ne einfach verkettete liste, was bei struct Kante{Punkt* ziel;Kante* nachfolger} 64 Bit pro existierender Kante macht. Sie sind außerdem zeigerbedingt immer gerichtet, also sind 128 nötig.
    Also wirds vom Speicher her erst billiger mit den Listen, wenns 64-mal so viele mögliche Kanten gibt, wie echt existierende. Und dann sind die Zugriffe immernoch bei O(was großes).
    Warum nicht die Matrix falten, wenn sie einem zu leer ist? Also Hashtable von Punktepaaren (sind ja Kanten). Da die Punktepaare immer aufsteigend geordnet sein können, fliegt Faktor 2 raus, den benutzen wir, um die Hashtable luftig zu halten. Also auch 128 Bits pro existierender Kante, aber schneller Zugriff (zwar O(1) aber deutlich lahmer als vector).
    Darüber würde ich mir aber erst Gedanken machen, wenns klemmt. Möglichkeiten gibts da viele, so daß man jede Klemmung schon wegkriegen wird. Die Matrix ist einfach der beste Anfang.

    0
  • R
    Mod

    angenommen man hat 65536 Wegpunkte (z.B. bei einer 2D-Map eines Strategiespiels), wenn nun jeder Wegpunkt mit weniger als 1/16 der anderen eine Verbindung hat (was durchaus realistisch ist bei einem Terrain), dann kann man sich zu jedem Wegpunkt ein array von 16bit zeigern relativ zum ersten wegpunkt speichern (index) und hat weniger Speicherverbraucht.

    wenn man nun für einen Wegpunkt alle Verbindungen haben möchte (wie ich aus der Ausssage Optimizers entnehme), wäre nichts schneller, denn man hätte ja gleich ein Array von allen.
    Das maskieren von bits würde wegfallen (was garnicht mal unbeachtlich an der Performance ziehen kann)
    zusätzlich legen alle Verbindungen lokal beieinander für einen Wegpunkt, das ist sehr wichtig bei großen Speichermengen, weil dort die Cachehits für die Performance sorgen.

    aber das muss man wohl benchen um Gewissheit zu haben.

    rapso->greets();

    0
  • ?

    Schade, das ich bei der ganzen Diskussion nur Bahnhof verstehe aber interessant klingt es trotzdem. 😃

    0
  • ?

    So WIRKLICH verstanden hab ich auch nicht alles.
    Um mal mehr Informationen zu geben, ich habe maximal 100 Wegpunkte, weil ich nur alle Hindernisse im näheren Umkreis in die Wegfindung einbeziehe. Deshalb sind die Wegpunkte auch sehr oft miteinander verbunden.
    Ich brauch halt einfach eine Möglichkeit, sehr schnell zu testen, ob zwei Punkte miteinander verbunden sind. Dazu möchte ich die Punkte alle einmal miteinander testen und das Ergebnis dann schnell speichern (und wenn es geht, nicht doppelt) und schnell abfragen können.

    0
Anmelden zum Antworten