Aufteilung der Spielwelt

iop

Zum an/abmelden nehme ich die x, y und z Position der Matrix des Modells. Die ist halt eindeutig entweder hier oder dort. Wie bestimme ich denn am besten, wann das Objekt weit genug in dem einen oder anderen Quadrat ist? Das müsste ich doch dann andauernd prüfen... steigert das nicht den Aufwand gewaltig? Wie macht man das also am besten?

krabbels

Logisch gesehen reichen die Koordinaten dann nicht aus. Du könntest z.B. eine Box um das Modell bauen und schauen mit welchen "Quadraten" diese kollidiert. Anhschließend machst du ggf. einen genaueren Test. Anders wird es nicht gehen.

iop

Wenn mein Model in mehrern Quadraten angemeldet ist, muss ich mein ganzes System der Überprüfung überdenken. ..mist, warum fällt einem sowas nicht vorher auf..?!

Auf jeden Fall schonmal Danke bis hierher Krabbels

Lass das ganze nicht auf Coords, sondern wirklich einfach auf Objektzeigern basieren.

//Irgendwo
class Tank : public Unit
{
   //bla bla
};

//nochmal irgendwo
Tank tank(attack_dmg,speed, and_so_on,initial_position);

//Den Panzer übergibst du dann irgendwo an deine Verwaltungsklasse
WorldGridManager WGM;

WGM.AddUnit(&tank);

Der WorldGridManager schaut jetzt beim erstmaligen erzeugen des Panzers nach in welche "Zelle" der Panzer gehört. Während das Spiel läuft überprüft er einfach, ob der Panzer an die Kanten stößt und meldet ihn in der alten Zelle ab sobald er Komplett in der neuen ist.

class PlaneCell : public GridElement
{
    void Draw();
    void DoLogic();
    void RegisterUnit(Unit *unit);
    void UnregisterUnit(Unit *unit); //Vielleicht auch (std::string ID), wie du halt willst
    //Und so weiter
}

Der WGM wählt dann aus welche Zelle grad aktiv ist und so musst du dich um die anderen gar nicht kümmern.

iop

Travis schrieb:

Lass das ganze nicht auf Coords, sondern wirklich einfach auf Objektzeigern basieren.

Travis schrieb:

Während das Spiel läuft überprüft er einfach, ob der Panzer an die Kanten stößt und meldet ihn in der alten Zelle ab sobald er Komplett in der neuen ist.

Das ist ja im Prinzip das gleiche, was Krabbels schon beschrieben hat

Krabbels schrieb:

Du könntest z.B. eine Box um das Modell bauen und schauen mit welchen "Quadraten" diese kollidiert.

im Endeffekt muss man ja doch wieder irgendwo die Koordinaten des Models (halt des Vierecks um das Model) mit den Koordinaten der "Zellen/Quadrate" vergleichen.

Oder habe ich Dich falsch verstanden Travis?

iop schrieb:

Travis schrieb:

Lass das ganze nicht auf Coords, sondern wirklich einfach auf Objektzeigern basieren.

Travis schrieb:

Während das Spiel läuft überprüft er einfach, ob der Panzer an die Kanten stößt und meldet ihn in der alten Zelle ab sobald er Komplett in der neuen ist.

Das ist ja im Prinzip das gleiche, was Krabbels schon beschrieben hat

Krabbels schrieb:

Du könntest z.B. eine Box um das Modell bauen und schauen mit welchen "Quadraten" diese kollidiert.

im Endeffekt muss man ja doch wieder irgendwo die Koordinaten des Models (halt des Vierecks um das Model) mit den Koordinaten der "Zellen/Quadrate" vergleichen.

Oder habe ich Dich falsch verstanden Travis?

Klar, irgenwie musst du ja überprüfen ob dein Element an die Grenze der Zelle kommt, allerdings musst du dich dann gar nicht mehr um all die anderen Zellen in deiner Welt kümmern. Du hast in deiner Verwaltungsklasse nur einen Zeiger auf die Zelle die gerade aktiv ist und eine map, einen vector oder sonstwas aller anderen Zellen. Sobald eine aktive Zelle abgelöst werden muss änderst du nur den Zeiger.

Ganz ohna Abfragen gehts natürlich nicht.

jule37

ist jetzt ein super spontaner gedanke, aber wie wäre es wenn:
- das objekt selber weis, bei welchen zellen es angemeldet ist (hashmap von zellen)
- das objekt bei überschreiten einer grenze bescheid sagt (zum beispiel bei einer "zellen-manager-klasse") und in welche richtung es sich gerade bewegt
- der zellen manager wählt dann die zelle, die in dieser richtung mit der anderen zelle adjazent ist und markiert sie als belegt (bei vier bewegungsrichtungen wären das maximal vier vergleiche)
- zum schluss löscht das objekt die zelle, in der es nicht mehr ist aus seiner map und tut die neue rein

edit: der zellen-manager sollte auch zugriff auf die zellen-hashmap des objektes haben, damit man von überall erfahren kann, was grad belegt ist und sogar auch von wem es belegt ist. (durchschnitt der mengen der belegten felder aller objekte -> hat einen aufwand von O(n))

oder man legt gleich ganz konsequent einen kompletten graphen unter die szene - dann sind auch so sachen wie den kürzesten weg finden etc super fix implementiert (algorithmen gibt es überall im netz). das bedeutet dann: man hat einen mehraufwand an speicher, aber kann geschickter rechnen und mit etwas denkaufwand auch vergleiche einsparen.

keine garantie auf absolutes zutreffen dieser vorschläge, nur eine anregung

Quellcode

mal so doof gefragt, kannst du dein Objekt nicht gleich bei allen Nachbarn der Zelle anmelden... also 8?

hustbaer

Man könnte anstatt ein Objekt in mehreren Zellen anzumelden genauso alle benachbarten Zellen checken.
Allerdings geht das nur wenn es eine Obergrenze für die Grösse der Objekte gibts. Wenn ein Objekt zu gross werden kann funktioniert diese Technik auch nicht mehr, bzw. man müstte dann einfach zu viele Nachbarn checken, so dass der Nutzen dieser Optimierung wieder dahin wäre.

Ich bleibe dabei. Objekt bei einer Zelle anmelden, Kollision zwischen Linie zwischen 2 Eckpunkten und Objekt testen -> fertig.

rapso

iop schrieb:

Ich habe nun die Ebene Baumartig aufgeteilt, so dass ich auf der untersten Ebene 64 kleine Quadrate habe. Bewegt sich jetzt eins meiner Objekte von einem der Quadrate ins andere, wird es in dem verlassenen abgemeldet und in dem neuen angemeldet. Damit muss ich nun nicht alle Objekte überprüfen, ob sie angeklickt wurden, sondern nur die aus dem Quadrat, in dem "sich die Maus gerade befindet" (Picking).

wozu unterteilst du deine welt baumartig wenn sich alle objekte eh nur auf unterster ebene aufhalten?

Mein Problem ist jetzt, dass wenn ich auf ein Objekt klicke, welches sich aufgrund seiner Größe zwischen zwei Quadraten befindet (auch wenn es nur in einem Quadrat angemeldet ist) und die Kamera so steht, dass die Maus sich eigentlich über dem anderen Quadrat befindet, ich dieses Objekt nicht anklicken kann.

sortier das objekt bei jeder bewegung einfach in das kleinste quadrat in der hierarchie ein, in das es noch komplett rein passt.

iop

rapso schrieb:

wozu unterteilst du deine welt baumartig wenn sich alle objekte eh nur auf unterster ebene aufhalten?

Also ich möchte, dass sich mein Cursor in "c&c"-Manier je nach Situation verändert. Das heißt, wenn ein Objekt markiert ist und und der Cursor nur über Terrain steht, wird er zum "Wegpunktcursor", steht er über einem "feindlichen" Objekt, wird er zum "Angriffscursor" usw. Nun habe ich mein Terrain baumartig unterteilt, wodurch ich mit sieben Abfragen sehen kann, in welcher meiner untersten Zellen der Cursor steht. Danach brauche ich maximal zehn (die Anzahl auf die kleinste Zelle passneder Objekte) Abfragen, ob der Cursor über einem Objekt steht. Insgesamt maximal 17 Abfragen - egal wieviele Objekt auf meinem Terrain herumwuseln... Oder habe ich ein dickes Brett vorm Kopf und man könnte es viel schneller/besser lösen?

Qellcode schrieb:

mal so doof gefragt, kannst du dein Objekt nicht gleich bei allen Nachbarn der Zelle anmelden... also 8?

Hm, ja, das könnte ich wohl, allerdings lohnt sich das bei mir wahrscheinlich nicht (siehe Erklärung oben).

Generell muss ich im Endeffekt ja testen, wie TravisG es vorgeschlagen hat. rapso hat mich auf den Gedanken gebracht, einfach weiter so zu testen wie oben beschrieben plus eine Abfrage über eine Liste mit Objekten, die sich (noch) auf mehreren Zellen befinden. ..ist halt nur doof, wenn sich viele Objekte zwischen zwei Zellen befinden.. was meint ihr?

Hm, ich weiß gar nicht, ob ich das jetzt noch anschneiden soll, aber Jule37 sprach ja schon davon, einen kompletten Graphen unter die Szene zu setzen: der nächste anzugehende Punkt wäre in meiner Welt die Wegfindung, Dazu habe ich mir schon sehr viele Gedanken gemacht (unter aderem zur Wahl des Algorithmus, A* wirds wohl werden), mich aber noch nicht praktisch daran versucht. Habt ihr vielleicht Tips, worauf ich dabei in Zusammenhang mit meinen bisherigen Erzugnissen achten sollte?

Soweit erstmal und echt vielen Dank bis hierher!

rapso

iop schrieb:

rapso schrieb:

wozu unterteilst du deine welt baumartig wenn sich alle objekte eh nur auf unterster ebene aufhalten?

Also ich möchte, dass sich mein Cursor in "c&c"-Manier je nach Situation verändert. Das heißt, wenn ein Objekt markiert ist und und der Cursor nur über Terrain steht, wird er zum "Wegpunktcursor", steht er über einem "feindlichen" Objekt, wird er zum "Angriffscursor" usw. Nun habe ich mein Terrain baumartig unterteilt, wodurch ich mit sieben Abfragen sehen kann, in welcher meiner untersten Zellen der Cursor steht.

das ist doch nur ein grid auf unterster ebene, da brauchst du keine 7abfragen, du kannst einfach darin indizieren. du hast ja auch keinen tree wenn du in einem 1D array auf element x zugreifen willst, wozu dann einen baum wenn du in einem 2D array auf element x|y zugreifen willst.

Qellcode schrieb:

mal so doof gefragt, kannst du dein Objekt nicht gleich bei allen Nachbarn der Zelle anmelden... also 8?

Hm, ja, das könnte ich wohl, allerdings lohnt sich das bei mir wahrscheinlich nicht (siehe Erklärung oben).

Generell muss ich im Endeffekt ja testen, wie TravisG es vorgeschlagen hat. rapso hat mich auf den Gedanken gebracht, einfach weiter so zu testen wie oben beschrieben plus eine Abfrage über eine Liste mit Objekten, die sich (noch) auf mehreren Zellen befinden. ..

lol, nein, ich bin nicht schuld, das kannst du mir nicht unterschieben

lies nochmal genau "sortier das objekt bei jeder bewegung einfach in das kleinste quadrat in der hierarchie ein, in das es noch komplett rein passt."

um es mal ganz primitiv zu sagen

function ObjektAktualisieren(pObj)
{
  pObj->Unregister();
  pNode = pTree->Root();
  assert(pNode);
  while(pNode->HatKinder())
  {
    if(pNode->PasstInEinChildQuadrat(pObj)
      pNode = pNode->PassendesChildQuadrat(pObj);
    else
    {
      pObj->RegistrierBei(pNode);
      return;
    }
  }
  pObj->RegistrierBei(pNode);
}

(ja, geht schoener und kuerzer, soll aber anspruchslos lesbar sein )

btw. das ist natuerlich nur eine moeglichkeit es zu machen, die anderen hier im thread genannten sind genau so gut/schlecht.