Speicherreservierung ja/nein?

Spartaner

Hallo zusammen!

Es geht immer noch um meine Kampfsimulation.

Also die Grundlagen der Speicherreservierung sind mir bekannt. (evtl. kennt da ja jemand ein gutes Tutorial zu?) Erst nochmal kurz, was ich nun vor habe:

Beispiel: Der Nutzer will folgendes erstellen

1000 Schiffe des Typs Jäger
50 Schiffe des Typs Schlachtschiff
150 Schiffe des Typs Kreuzer

Ich habe meine Klasse c_ship. Dem Konstruktor übergebe ich den Typ des zu erstellenden Raumschiffes.

Jetzt bin ich mir allerdings nicht sicher was ich genau machen soll. Es gibt viele verschiedene Schiffe, die jeweils in großer Menge vorhanden sein können (s.o.). Welche Schiffstypen erstellt werden, bestimmt natürlich der Nutzer und die Menge auch.

Nun muss ich später in meiner Schadensberechnung jeweils die Liste eines Typs (z.b. Kreuzer) durchgehen um die Schadenszuweisung vorzunehmen. Ist ein Schiff zerstört, muss ich es natürlich aus der Liste "streichen".

Was macht man da am besten? Erstelle ich mir für jeden Schiffstyp ein vector, den ich dann mit Instanzen fülle? Oder reserviere ich für jedes Schiff Speicher auf dem Heap? Oder gibt es dafür noch bessere Lösungen?

Ich möchte hier jetzt keinen fertigen code haben. Es geht mir eher darum, wie ich mein "Problem" am besten lösen kann.

Ceos

am besten wäre es natürlich wenn du nur eine instanz ertellst (nur wenn alle schiffe desselben typs identisch sind) dann einen "anzahl" Parameter hinzufügst und diesen mit formeln berechnest also sowas wie:
Kreuzer->HP = 100;
KreuzerFlotte(erbt von Kruezer und hat Parameter Anzahl bekommen)->Anzahl = 100;
KreuzerFlotte->MaxHP = 10000;
GegnerFlotte->Schaden = 5000;

5000Schd/10000HP = 50 Kreuzer übrig

so hast du nur eine instanz und kannst dennoch tausende schiffe berechnen ohn das der speicher gleich umkippt.

Spartaner

Danke für die schnelle Antwort!

Ceos schrieb:

am besten wäre es natürlich wenn du nur eine instanz ertellst (nur wenn alle schiffe desselben typs identisch sind) dann einen "anzahl" Parameter hinzufügst und diesen mit formeln berechnest also sowas wie

Also die Schiffe eines Typs (z.b. Kreuzer) sind komplett identisch. Dafür übergebe ich ja meinem Konstruktor der Schiffsklasse den Typ des Schiffes.

c_ship ship1("Kreuzer");

Da der errechnete Schaden, den z.b. die Kreuzer erleiden, nicht einfach nacheinander verteilt wird, wäre es ein Problem, wenn ich einen Anzahl Parameter einfüge. Die Schadensverteilung erfolgt nach der Gaussschen Normalverteilung. Deshalb muss zu jedem Zeitpunkt genau wissen, wieviel Hüllenpunkte jedes einzelne Schiff hat. Dies wäre ja nicht möglich, wenn ich nur eine Variable für die "Gesamthülle" hätte.

viande

Du solltest dir kurz überlegen, was du machen willst:
1. Willst du häufig neue Schiffe erstellen? Dann nimm eine Liste.
2. Willst du nur selten/oder noch besser gar nicht neue Schiffe erstellen? Dann reicht ein Array aus.

Zu 1) Ein Array hat das Problem, dass die Größe begrenzt ist bzw. man erst freie Felder finden muss. Daher ist in diesem Fall eine Liste angebracht, weil man in konstanter Zeit einfügen kann, während es beim Array im Schnitt lineare Zeit benötigt. Das bezieht sich auf das bereits laufende Spiel, nciht die Initialisierung.

Zu 2) Wenn man selten neue Elemente einfügt, eignen sich Arrays eher als Listen, weil sie 1. weniger Speicher verbrauchen und 2. bei direkten Zugriffen einen konstanten Zeitfaktor haben. Wenn du allerdings nur über die Schiffe iterierst, ist das irrelevant(abgesehen von den Indirektionen bei einer Liste).

Edit: Speicher sollte in dieser Größenordnung kein Problem sein. Außer jedes Schiff sollte sein eigenes, persönliches Video erhalten . Ansonsten wirst du kaum mehrere Millionen Schiffe in deinem Spiel haben

Spartaner

Also der Benutzer gibt am Anfang eine Anzahl von Schiffen ein. Nachträglich kommen keine mehr dazu! Es werde halt "bloß" während des Kampfes einzelne schiffe vernichtet und müssen somit aus der Liste entfernt werden. Da der Schaden ja per Normalverteilung ermittlet wird, kann auch z.b. das 50. Schiff von 100 als erstes zerstört werden.

Um einem Array zur Laufzeit die Größe zuzuweisen, müsste ich dafür ja Speicher auf dem Heap reservieren. Da hatte ich aber folgendes Problem.

c_ship *pship1 = NULL;

pship1 = new c_ship("Kreuzer"); 
// dies ist ja nicht möglich
pship1 = new c_ship("Kreizer")[1000];

Da ich ja den Konstruktor auf jeden Fall aufrufen muss, um den Schiffstyp festzulegen, ist diese Lösung scheinbar nicht zu verwenden.

Ceos

könntest du nicht einfach eine schleife und ein int-vector für die HP nehmen ?

[EDIT] ich beziehen mich hierbei noch immer auf die klasse/template Flotte die von der jeweiligen schiffsart ableitet (ein template würde sich hier wirklich hervorragend eignen)

for (vector<int>::iterator ITR = ShipArray.begin(); ITR != ShipArray.end();) {
    if (ZUFALLSSCHADEN > ITR->leftHP) {
        ITR = ShipArray.delete(ITR);
    }
    else {
        ITR->leftHP -= ZUFALLSSCHADEN;
        ITR++;
    }    
    // Heißt soviel wie wenn zufällig erteilter schaden größer der verbleibenden HP
    // dann schiff zerstört ansonsten HP abziehen und iterator inkrementieren
}

so sparst du dir den unsinnig vergeudeten speicher der für jedes einzelne objekt nötig wäre und benutzt nur das bisschen speicher das pro schiffs eigenschaft nötig ist.

ZUFALLSSCHADEN berechnest du dir nach deinem verteilungschema oder wie auch immer ^^

DEvent

Benutze einfach std::vector und lasse deine grauen Zellen an wichtigerem arbeiten.

Btw, musst du unbedingt die Schiffe aus dem Vector löschen? Reicht es nicht, alle Schiffe die Hp <= 0 haben, als tote Schiffe zu betrachten?

Spartaner

viande schrieb:

Edit: Speicher sollte in dieser Größenordnung kein Problem sein. Außer jedes Schiff sollte sein eigenes, persönliches Video erhalten . Ansonsten wirst du kaum mehrere Millionen Schiffe in deinem Spiel haben

Nene, Videos sind nicht enthalten. Es ist eine reine Simulation, wo nur Texte enthalten sind. Allerdings können durchaus 100000 Schiffe vorhanden sein.

@ Ceos: Ich kenne nicht alle Funktionen die vector liefert. ShipArray.delete();
löscht dies einfach das Elemt aus dem vector?

@ DEvent: Klar, darüber könnte man vorher eine Abfrage machen. Bloß wenn ich schon extra dafür Speicher reservieren sollte, dann würde es ja auch Sinn machen, wenn ich diesen direkt wieder freigebe und das Schiff aus der Liste entferne. Oder sollte man den Speicher einfach komplett am Ende der Simulation freigeben.

Ceos

ich hab mir da mal was ausgetüftelt und wollt mal deine meinung dazu wissen btw. die meinung der anderen zur effizienz (syntax und vollständigkeit sollen bitte vernachlässigt werden, da ich das nur einfach mal so geschrieben habe)

Ship.h

typedef struct {
	int HP;
	int Dmg;
} TShipSpecs;

class Ship
{
public:
	Ship();
	~Ship();
private:
	TShipSpecs ShipSpecifications;
	virtual void initSpecs();
};

Ship.cpp

Ship::Ship()
{
	initSpecs();
}

Kreuzer.h

class Kreuzer : public Ship
{
public:
	Kreuzer();
	~Kreuzer();
	void dealDmg(int Dmg);
private:
	void initSpecs();
};

Kreuzer.cpp

Kreuzer::Kreuzer()
{
	super();
}

void Kreuzer::initSpecs()
{
	ShipSpecifications.HP = 100;
	ShipSpecifications.Dmg = 0;
}

void Kreuzer::DealDmg(int Dmg)
{
	ShipSpecifications.Dmg += Dmg;
}

KreuzerVerband.h

class KreuzerVerband :: public Kreuzer
{
public:
	KreuzerVerband(int number);
	~KreuzerVerband();
	int Number;
	void dealGaussDmg(int Dmg);
private:
	vector<TShipSpecs> ShipHPList;
};

KreuzerVerband.cpp

KreuzerVerband::KreuzerVerband(int number)
{
	super();
	Number = number;
	for (int i=0; i < Number; i++) {
		ShipHPList.push_back(Kreuzer::ShipSpecifications);
	}
}

void KreuzerVerband::dealGaussDmg(int Dmg)
{
	for (vector<TShipSpecs>::iterator ITR = ShipHPList.begin();ITR != ShipHPList.end; ) {
		int dmgtodeal = Dmg - GAUSSFORMEL-ZUFALLSSCHADEN;
		Dmg -= dmgtodeal;
		ShipSpecifications = *ITR;
		dealDmg(dmgtodeal);
		if (ShipSpecifications.Dmg > ShipSpecifications.HP) {
			ITR = dmgtodeal.erase(ITR);
			Number--;
		}
		else {
			ITR++;
		}
	}
}

Ceos

es war nicht delete(iterator where) es war erase(iterator where)

[EDIT] sorry for doppelpost hab den falschen button gedrückt

Spartaner

Guten Morgen!

@ Ceos: Erst mal vielen Dank für die Mühe, die du dir gemacht hast!

Wie ich ja schon sagte, habe ich nur die Schiffsklasse (c_ship). Da jeder Schiffstyp die selben Fähigkeiten und Eigenschaften hat (halt nur andere Werte), ist es nicht nötig, dass ich für jeden Schiffstyp eine eigene abgeleitete Klasse schreiben muss. Vor allem würde dies, zumindest für mich, sehr unübersichtlich werden, da ich insgesamt über 15 Schiffstypen habe, wo nochmals über 20 Verteidigungsanlagen hinzu kommen. Das würde ja bedeuten, dass ich zusätzlich ca. 60 Dateien in meinem Projekt zu verwalten hätte.

Das mag sicherlich für große Projekte nicht viel sein, doch denke ich dass dies hier nicht nötig ist.

Ich war am überlegen, um einen Verband von mehreren Schiffen eines Typs zu erstellen, eine zusätzliche Klasse (c_fleet) zu erstellen.
In dieser Klasse werden einfach vectoren des jeweiligen Schiffstyps zur Verfügung gestellt.

// c_fleet.hpp

#inlcude "c_ship"
#include <vector>

class c_fleet
{
   private:
      std::vector<c_ship> Kreuzer;
      std::vector<c_ship> Schlachtschiff;
        // usw.
   public:
      c_fleet();
      ~c_fleet();

};

// c_fleet.cpp

c_fleet::c_fleet(int Kreuzer, int Schlachts, // usw...)
{
   c_ship cKreuzer("Kreuzer")

   for(int i = 1; i < Kreuzer; i++)
   {      
      Kreuzer.push_back(cKreuzer);   
   } 
   // für jeden Typ erneut
}

Wäre das eine annehmbare Möglichkeit?

Gruß Spartaner

CStoll

Wenn die Schiffe alle technisch identisch sind, reicht eigentlich ein vector aus, um alle unterzubringen. Das dürfte es dann auch leichter machen, Flächeneffekte darzustellen, die die gesamte Flotte betreffen. Aber da stellt sich dann letztendlich die Design-Frage: Wie soll das Schießen gesteuert werden?
(schießt du "irgendwo in die gegnerische Flotte rein", "auf ein beliebiges Typ-X Schiff", "auf GENAU DIESES Schiff",...? oder hast du eventuell Waffen, die mehrere Schiffe gleichzeitig treffen können?)

THX 1138

Zum Entfernen aus Vectoren nach bestimmten Kriterien empfiehlt sich remove_if in Verbindung mit erase

Spartaner

@ THX 1138: Das werde ich mir direkt mal ansehen, Danke!

CStoll schrieb:

Wenn die Schiffe alle technisch identisch sind, reicht eigentlich ein vector aus, um alle unterzubringen

Diesen Gedanken hatte ich auch schon gehabt. Bloß stelle ich es mir etwas unübersichtlich vor, wenn in meinem vector die Elemente 1 bis 50 Kreuzer sind, die Elemente 50 bis 67 sind Schlachtschiffe usw.

Aber da stellt sich dann letztendlich die Design-Frage: Wie soll das Schießen gesteuert werden?

Die Funktion zur Berechnung des Schadens werde ich noch in die Klasse der Waffen einfügen.
Das Schießen an sich läuft wie folgend ab. Jede Waffe hat ihr Lieblingsziel (Prioritätenliste). Jetzt geht die Waffe meines Schiffes diese Liste durch und vergleicht sie mit den Schiffen der gegnerischen Flotte. Der Schiffstyp der als erstes in der Liste vor kommt, wird unter beschuß genommen.
Dazu wird zunächst der Schaden ermittelt, den die Waffe anrichtet und dann wird dieser auf alle Schiffe der gegnerischen Flotte (des angegebenen Schiffstyps) verteilt (nach der Normalverteilung). So werden dann alle Waffen aller Schiffe durchgegangen. Ist die Berechnung des Schadens und der Treffer dann bei allen Schiffen geschehen, werden die zerstörten Schiffe aus der Flotte "gestrichen", so dass dann in der nächsten Runde die entsprechend geringere Anzahl an Schiffen vorhanden ist.

Ceos

naja son ungleich sind deine und meine idee gar nicht, nur das ich dabei des speichers wegen nicht ganze instanzen sondern eher nur die statuswerte die verändert werden könnten in vektoren packen wollte, des speichers wegen

... bis 100000 Schiffe ...

[EDIT] Mühe warr das kein :p war ja nur n gedankenspiel .... soll das eventuell nen OGamesimulator oder was verwandtes werden ? wenn ich deine schiffsklassen und die anzahl der arten so anseh erinnert mich das stark daran ;p

Spartaner

Ceos schrieb:

soll das eventuell nen OGamesimulator oder was verwandtes werden ? wenn ich deine schiffsklassen und die anzahl der arten so anseh erinnert mich das stark daran ;p

Es wird ein Kampfsimulator für Horizon (ein anderes Browsergame). Ich hab ja früher nie was von Browsergames gehalten. Aber wie dann immer mehr von meinen Arbeitskollegen damit angefangen haben, hab ich mir das auch mal angesehen und bin jetzt seit knapp 7 Monaten dabei.

CStoll

Spartaner schrieb:

CStoll schrieb:

Wenn die Schiffe alle technisch identisch sind, reicht eigentlich ein vector aus, um alle unterzubringen

Diesen Gedanken hatte ich auch schon gehabt. Bloß stelle ich es mir etwas unübersichtlich vor, wenn in meinem vector die Elemente 1 bis 50 Kreuzer sind, die Elemente 50 bis 67 sind Schlachtschiffe usw.

Ach, so schwer ist das auch wieder nicht. Dazu mußt du die Schiffstypen nur geordnet (z.B. nach Maximal-Hitpoints oder nach Schiffstyp) in den Vektor reinpacken und kannst dir dann per equal_range() einen bestimmten Flottenteil raussuchen lassen (z.B. equal_range(ships.begin(),ships.end(),"Kreuzer") liefert alle Kreuzer deiner Flotte.

Die Funktion zur Berechnung des Schadens werde ich noch in die Klasse der Waffen einfügen.
Das Schießen an sich läuft wie folgend ab. Jede Waffe hat ihr Lieblingsziel (Prioritätenliste). Jetzt geht die Waffe meines Schiffes diese Liste durch und vergleicht sie mit den Schiffen der gegnerischen Flotte. Der Schiffstyp der als erstes in der Liste vor kommt, wird unter beschuß genommen.
Dazu wird zunächst der Schaden ermittelt, den die Waffe anrichtet und dann wird dieser auf alle Schiffe der gegnerischen Flotte (des angegebenen Schiffstyps) verteilt (nach der Normalverteilung). So werden dann alle Waffen aller Schiffe durchgegangen. Ist die Berechnung des Schadens und der Treffer dann bei allen Schiffen geschehen, werden die zerstörten Schiffe aus der Flotte "gestrichen", so dass dann in der nächsten Runde die entsprechend geringere Anzahl an Schiffen vorhanden ist.

Auch eine Möglichkeit - und mit einem vector recht gut umsetzbar:

vector<string> m_prio;//Namen der "Lieblingsgegner" in fallender Reihenfolge
pair<vector<c_ship>::iterator,vector<c_ship>::iterator> ship_range;
for(vector<string>::iterator pos=m_prio.begin();pos!=m_prio.end();++pos)
{
  ship_range = equal_range(ships.begin(),ships.end();*pos);
  if(ship_range.first!=ship_range.second()) break;
}

for(vector<c_ship>::iterator tgt=ship_range.first;tgt!=ship_range.second;++tgt)
  attack(*tgt);

Spartaner

CStoll schrieb:

Ach, so schwer ist das auch wieder nicht. Dazu mußt du die Schiffstypen nur geordnet (z.B. nach Maximal-Hitpoints oder nach Schiffstyp) in den Vektor reinpacken und kannst dir dann per equal_range() einen bestimmten Flottenteil raussuchen lassen (z.B. equal_range(ships.begin(),ships.end(),"Kreuzer") liefert alle Kreuzer deiner Flotte.

Das klingt interessant. Liege ich da richtig, dass diese Funktion einfach den letzten Eintrag im vector zurückliefert? Wenn z.b. bis zum Element 50 Kreuzer enthalten sind, so soll die Funktion eine 50 zurückliefern?

pair<vector<c_ship>::iterator,vector<c_ship>::iterator> ship_range;

Das verstehe ich nicht richtig. Ist dass so eine Art "Doppel-vector"? Könntest du mir deinen Codeschnipsel vielleicht etwas genauer erklären?

THX 1138

Schau dir mal equal_range an
equal_range liefert ein pair Iteratoren zurück, die den Bereich der Schiffe abdecken, die dem gewünschten Namen entsprechen. Also vom ersten bis eine nach dem letzten
Dieser Range wird in der zweiten Schlaufe durchiteriert.

PS: Nein ich habe keine Aktien von SGI...

CStoll

Spartaner schrieb:

CStoll schrieb:

Ach, so schwer ist das auch wieder nicht. Dazu mußt du die Schiffstypen nur geordnet (z.B. nach Maximal-Hitpoints oder nach Schiffstyp) in den Vektor reinpacken und kannst dir dann per equal_range() einen bestimmten Flottenteil raussuchen lassen (z.B. equal_range(ships.begin(),ships.end(),"Kreuzer") liefert alle Kreuzer deiner Flotte.

Das klingt interessant. Liege ich da richtig, dass diese Funktion einfach den letzten Eintrag im vector zurückliefert? Wenn z.b. bis zum Element 50 Kreuzer enthalten sind, so soll die Funktion eine 50 zurückliefern?

Nein, equal_range liefert nicht die Anzahl der gefundenen Elemente, sondern ein Paar von Iteratoren - d.h. ship_range.first zeigt auf den ersten Kreuzer deiner Flotte, ship_range.second auf den ersten Nicht-Kreuzer.

Edit@THX: Das heißt übrigens immer noch "Schleife"

THX 1138

CStoll schrieb:

Edit@THX: Das heißt übrigens immer noch "Schleife"

Uups, sch**ss Helvetismen.