|
|
|
|
Mit so Performance-Geschichten habe ich mich noch nie richtig beschäftigt, ich bin erstmal froh, wenn ich meinen Code richtig zum Laufen kriege.
/ Macht's denn Sinn, da nen gefühlten Wert zu wählen? Ein Grid mit 100x100 nodes kommt schnell zusammen, und wenn dann noch viele Hindernisse rumstehen, werden auch viele von denen ausgelesen, wenn ein actor z.B. von links unten nach rechts oben laufen will. Wenn ich da jetzt ne list oder ein dictionary vorsorglich mit ner capacity von 500 initialisiere, ist das aber doch die meiste Zeit über völlig für die Katz, oder?
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von Ameisenfutter am 03.07.2018 19:57]
|
|
|
|
|
|
Eigentlich brauchst du auch nur eine list, die du immer wieder für den aktuellen PathRequest nutzt. Du müsstest niemals in runtime allocaten. Dein system sitzt dann halt auf ein bisschen Speicher, ja, aber das braucht es dann halt auch.
e: also ein openSet und ein closedSet, welche vor jedem Request gecleared werden.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von freakadelle am 03.07.2018 20:03]
|
|
|
|
|
|
Die dictionaries müssen schon immer wieder neu initialisiert werden, weil die scores ja nicht global gültig sind, sondern ja für jeden Pfad neu vergeben werden. Dabei vergleicht der ja ständig, ob ein neuer Wert geringer ist als der alte.
/ Hmjo, also die sets z.B. gleich mit ner capacity von n nodes im grid initialisieren oder wie?
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von Ameisenfutter am 03.07.2018 20:05]
|
|
|
|
|
|
Naja wenn du dir den Speicherverbrauch erlauben kannst, ist es besser als CPU Spikes
|
|
|
|
|
|
|
| Zitat von Ameisenfutter
Die dictionaries müssen schon immer wieder neu initialisiert werden, weil die scores ja nicht global gültig sind, sondern ja für jeden Pfad neu vergeben werden. Dabei vergleicht der ja ständig, ob ein neuer Wert geringer ist als der alte.
| |
Ja aber brauchst du die dict-werte beim nächsten path request noch? Also wieso nicht einfach immer die alten werte im gleichen dict überschreiben. Du musst nur neu initialisieren, wenn du daten kopieren willst. Nachdem der pfad durch ist sind die aber obsolete.
e: ich würde mehr in classes auslagern. Zb eine Path class die der prozess returnen kann. Soabdl die geschrieben ist, kannst du alles andere überschreiben, statt es jeden such-prozess neu zu erstellen
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von freakadelle am 03.07.2018 20:11]
|
|
|
|
|
|
Puh, da muss ich eine Weile drüber nachdenken, wie ich das umsetze.
/ Würdet ihr denn einen zentralen pathfinder pro scene benutzen und dem dann Aufträge von jedem actor zuschicken? Bisher habe ich das so gedacht, dass jeder actor einen eigenen pathfinder hat. Wenn die jetzt aber auch noch vorsorglich Speicher belegen, ist das irgendwie nicht mehr so klug, oder?
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Ameisenfutter am 03.07.2018 20:12]
|
|
|
|
|
|
Eigentlich gehts erstmal nur drum alles mit "new" aus der Method (runtime allocation = bad) und oben in die class zu packen.
Immer wenn deine A_Star-Method durch ist bleiben deine dicts bestehen und warten vom GarbageCollector gelöscht zu werden. Du benutzt die garnichtmehr, weil sie local sind. Stattdessen kannst du sie aber auch am ende einfach clearen und beim nächsten call nochmal benutzen. Dabei wird kein neuer memory allocated, was performance kostet und den GarbageCollector belastet.
Wenn du das gemacht hast, DANN kannst du dir auch übelegen wieviel memory du einmalig brauchst. Das sind zwei unterschiedliche Dinge.
e: Genau. Der pathfinder sollte global sein (viele nennen die system "Manager" oder so). Dem schickst du eine PathRequest class mit start und ziel drin. Die packt der manager in eine queue. (Und merkt sich entweder woher der request kam, oder der requester hat ne referenz im request selbst, oder er schickt einen callback-action mit oder doer) Wieviele Queue items du pro frame bearbeitest bleibt dir überlassen. Wenn ein pfad gefunden ist schreibt der manager den in eine Path class die er dem requester zurückschickt. Zu dem Zeitpunkt sind halt jetzt alle deine dicts obsolete, also wieso im nächsten request neue erstellen? Einfach alles clearen und die alten benutzen.
e: Sorry, bin grad aufm Sprung, aber Denkanstöße haste ja jetzt
|
[Dieser Beitrag wurde 4 mal editiert; zum letzten Mal von freakadelle am 03.07.2018 20:20]
|
|
|
|
|
|
Oge, das hab ich gerafft. Werde ich in der nächsten session mal versuchen, umzusetzen. Bisher habe ich auch noch kaum mit eigenen classes gearbeitet. Eigentlich nur, wenn ich mir irgendwelche neuen Objekttypen wie "Actor" oder "Skill" zusammengeschustert hab.
/ Danke auf jeden Fall. Gibt doch noch viel zu lernen.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Ameisenfutter am 03.07.2018 20:20]
|
|
|
|
|
|
| Zitat von Ameisenfutter
Gibt doch noch viel zu lernen.
| |
Immer erst Benchmarken
|
|
|
|
|
|
|
| Zitat von freakadelle
Eigentlich gehts erstmal nur drum alles mit "new" aus der Method (runtime allocation = bad) und oben in die class zu packen.
Immer wenn deine A_Star-Method durch ist bleiben deine dicts bestehen und warten vom GarbageCollector gelöscht zu werden. Du benutzt die garnichtmehr, weil sie local sind. Stattdessen kannst du sie aber auch am ende einfach clearen und beim nächsten call nochmal benutzen. Dabei wird kein neuer memory allocated, was performance kostet und den GarbageCollector belastet.
Wenn du das gemacht hast, DANN kannst du dir auch übelegen wieviel memory du einmalig brauchst. Das sind zwei unterschiedliche Dinge.
e: Genau. Der pathfinder sollte global sein (viele nennen die system "Manager" oder so). Dem schickst du eine PathRequest class mit start und ziel drin. Die packt der manager in eine queue. (Und merkt sich entweder woher der request kam, oder der requester hat ne referenz im request selbst, oder er schickt einen callback-action mit oder doer) Wieviele Queue items du pro frame bearbeitest bleibt dir überlassen. Wenn ein pfad gefunden ist schreibt der manager den in eine Path class die er dem requester zurückschickt. Zu dem Zeitpunkt sind halt jetzt alle deine dicts obsolete, also wieso im nächsten request neue erstellen? Einfach alles clearen und die alten benutzen.
e: Sorry, bin grad aufm Sprung, aber Denkanstöße haste ja jetzt
| |
Manchmal bin ich mir echt nicht (mehr) sicher ob freakadelle ein 3D Mensch oder Programmierer ist.
e/ Im besten Falle: Technical Artist!
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Murica am 03.07.2018 20:36]
|
|
|
|
|
|
Würde ich mich bewerben, dann als System- oder Technical Designer
Da ich aber selbstständig bin mache ich:
- Game Code (+ Networked)
- Technical Design (Mainly Tools)
- System Design (+ Content Implementation, zb Vehicles oder AI)
- Game Design (Das kann ja eh jeder ...)
- Level Design
- Technical Art (Rigging, Skinning)
- Hard Surface Art (Quasi alles 3D was nicht organisch ist. www.bliss-art.net (Vehicles ))
- Low Poly Characters (Die gehn schon)
- Animation (Nur Basics)
Game Developer halt. Sound, Zeichnen, sculpten oder environment art (also landschaften etc) hab ich nie gemacht
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von freakadelle am 03.07.2018 23:20]
|
|
|
|
|
|
Krass, das Escape - Public Enemy Ding ist von dir? Nice, das habe ich damals echt gefeiert.
|
|
|
|
|
|
|
Thx, teilweise Radkappenpolitur aka Insulaner ausm Forum hier war noch dabei und ein weiterer Crytek-Kollege
|
|
|
|
|
|
|
| Zitat von freakadelle
- Hard Surface Art (Quasi alles 3D was nicht organisch ist. www.bliss-art.net (Vehicles ))
| |
Sekunde, hattest du bei Crytek nicht 24/7 Bäume gemacht, oder verwechsel ich dich da gerade
|
|
|
|
|
|
|
| Zitat von Murica
| Zitat von freakadelle
- Hard Surface Art (Quasi alles 3D was nicht organisch ist. www.bliss-art.net (Vehicles ))
| |
Sekunde, hattest du bei Crytek nicht 24/7 Bäume gemacht, oder verwechsel ich dich da gerade
| |
Das klingt wie das eine Studio was für Forza Horizon 3 nur die Vegetation gemacht hat.
An dem Spiel waren gefühlt so 700-800 Leute beteiligt, und eines der im stundenlangen Abspann genannten Studios hat NUR Pflanzen und Gestrüpp einer bestimmten Detailstufe gefertigt
"Bringt mir... ein schönes GEBÜSCH!"
|
|
|
|
|
|
|
Ich habe meinen PathManager jetzt soweit umgeschrieben, dass
- clients ihm request schicken können, die anschließend gequeued werden und der manager pro frame x requests abarbeitet
- dictionaries und lists nicht mehr lokal declared werden und nach einem abgearbeiteten request erhalten bleiben.
Wie genau muss ich die jetzt clearen, damit die capacity erhalten bleibt, die Einträge aber gelöscht und nicht mehr ausgelesen werden? Und muss ich dann an dem part hier etwas ändern?
|
Code: |
// and check if that node has already been discovered
if (openSet.Contains(neighbor.position) == false)
{
// if not, we add it to openSet, set its gScore to tentative_gScore and calculate its fScore
// Note that dictionary.Add() throws an exception if it tries to add a duplicate key (which shouldn't happen)
openSet.Add(neighbor.position);
gScore.Add(neighbor.position, tentative_gScore);
fScore.Add(neighbor.position, CalculateFScore(start, neighbor.position, gScore[neighbor.position]));
// this is the best path yet. Remember it!
cameFrom.Add(neighbor.position, nodeWithSmallestFScore);
}
else
{
// if the node has already been discovered, we have to check if the tentative gScore is smaller than its current gScore
if (tentative_gScore < gScore[neighbor.position])
{
// and if it is, we have to reset its gScore, recalculate its fScore
gScore[neighbor.position] = tentative_gScore;
fScore[neighbor.position] = CalculateFScore(start, neighbor.position, gScore[neighbor.position]);
// this is the best path yet. Remember it!
cameFrom[neighbor.position] = nodeWithSmallestFScore;
}
} |
|
Der Algorithmus schaut dabei mit if(dict.keys.contain), ob eine node schon entdeckt wurde und ob bei der aktuellen Betrachtung ein niedrigerer score herauskam als bei vorherigen Betrachtungen. Wenn die node noch gar keinen Eintrag hatte, wird einer angelegt.
/ lel, list.clear() macht wohl genau das.
| Capacity remains unchanged. To reset the capacity of the List<T>, call the TrimExcess method or set the Capacity property directly. Decreasing the capacity reallocates memory and copies all the elements in the List<T>. Trimming an empty List<T> sets the capacity of the List<T> to the default capacity. | |
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Ameisenfutter am 04.07.2018 15:27]
|
|
|
|
|
|
Ich denke du wirst früher oder später noch Probleme kriegen, das alles in unterschiedlichen dicts aus value types zu speichern. Dein Grid ist ja quasi nur erreichbar über einen key (welcher btw ein struct ist, was viel langsamer ist als irgendein integer-type)
Einfacher zu maintainen wäre es, wenn dein Grid eine class wäre, die selbst alle grid-knoten referenzierbar hält. In deinem Falle würde das zb mit nem zweidimensionalen array gehn, weil du in nem simplen x-y generierten grid arbeitest, richtig? Aber das ist ein sonderfall, dass du grid-knoten nachbarn findest indem du halt eine unit oder einen index "weiter" gehst.
Flexibler wärst du wenn erstmal jeder grid-knoten eine "Node" class wäre. In der hast du dann member wie "position", "gCost", "extraCost", "isClosed" etc etc. Und zusätzlich aber auch eine liste aller nachbarn, die von dieser Node aus erreichbar sind.
Dein Ansatz ist auch möglich, aber kommt mir für den Anfang eher weniger hilfreich vor.
Du hast dann quasi immer eine Gird class, die du einmal generierst (nachbarn suchen etc) und immer wieder als ausgangspunkt hernehmen kannst.
Wenn du einen PathRequest bearbeitest, dann bearbeitest du natürlich eine kopie des grids. (Diesen Speicher kannst du vorher einmal allocaten und immer wieder frei machen).
A* schaut sich dann also nicht in meheren dicts um, sondern schiebt nur "Node"s vom openSet ins closedSet, bis du am ende eine sorted list aus "Node"s hast. Das ist dein pfad.
Der Vorteil hierbei ist, dass du mehr mit den Nodes machen kannst. Für ein 2.5D Jump'n'Run habe ich zB ein grid generiert und bei der Generierung allen Nodes, die wenige Nachbar-Nodes haben eine extraCost gegeben, damit die Agents tendentiell nicht an Wänden entlanglaufen, ausser es geht nicht anders. Sowas wird mit deinen verteilten Datensätzen unnötig komplex.
|
Code: |
public class Node
{
public List<Node> neighbours;
public float cost = 1;
public float gCost; //Distance from start
public float hCost; //Distance to end
public float FCost { get { return gCost + hCost; } }
public bool isClosed = false;
} |
|
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von freakadelle am 04.07.2018 15:57]
|
|
|
|
|
|
| Zitat von freakadelle
Thx, teilweise Radkappenpolitur aka Insulaner ausm Forum hier war noch dabei und ein weiterer Crytek-Kollege
| |
Meinten Sie: [XeNoN]
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von X-Tender am 04.07.2018 16:28]
|
|
|
|
|
|
Nö, das sind zwei vollkommen unterschiedliche Menschen. Xenon war davor schon bei Blizzard
|
|
|
|
|
|
|
Ok, hätte ja sein können
|
|
|
|
|
|
|
| Zitat von freakadelle
Du hast dann quasi immer eine Gird class, die du einmal generierst (nachbarn suchen etc) und immer wieder als ausgangspunkt hernehmen kannst.
| |
Das Grid ist ne class (Unity kann eigene 2D Tilemaps seit 2017). Die Zellen bzw. nodes habe ich auch schon gespeichert (die Liste habe ich jetzt auf zweidimensional umgestellt, was in Unity ein bisschen fummelig ist, weil der Inspector keine mehrdimensinalen arrays mag), aber vorher nicht für den pathmanager benutzt, weil das mit dem Koordinatensystem halt so easy klappt. Die grid class von Unity kann world coordinates in grid coordinates umwandeln und umgekehrt, das grid benutzt immer ganze Zahlen, unabhängig davon, wie groß die cell size ist.
list<class> in derselben class geht auch nicht, weil Unity ein depth limit von 7 bei serialized classes hat (das gibt dann ja einen cycle, cell -> neighbor -> cell -> neighbor -> cell -> neighbor etc).
Ich bastel den PathManager jetzt mal so um, dass der das array mit den Zellen (Knotenpunkte sind immer die Mittelpunkte der Zellen) benutzt, anstatt alles nur über Koordinaten anzusteuern, dann kann ich die Eigenschaften der Zellen auch leichter für die Wegfindung abrufen.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Ameisenfutter am 05.07.2018 12:28]
|
|
|
|
|
|
| Zitat von Ameisenfutter
list<class> in derselben class geht auch nicht, weil Unity ein depth limit von 7 bei serialized classes hat (das gibt dann ja einen cycle, cell -> neighbor -> cell -> neighbor -> cell -> neighbor etc).
| |
Muss ja nicht serialized sein. Wenn du das aber doch möchtest kannste den nodes auch IDs verteilen und die speichern, statt der referenz
|
|
|
|
|
|
|
Dann muss ich mein grid aber ja auch nach den IDs durchsuchen. Da kann ich doch dann auch einfach direkt nach den entsprechenden Koordinaten suchen?
/ Und: Macht es echt so viel Sinn, dass ich die Nodes in einem mehrdimensionalen array speichere?
Dann sucht er halt weniger, weil er zuerst nach der passenden X-Koordinate sucht und dann nach der passenden Y-Koordinate. Der Code wäre aber viel aufgeräumter, wenn ich die Liste eindimensional mache, weil ich dann halt immer nur einen loop bräuchte statt 2.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Ameisenfutter am 05.07.2018 14:02]
|
|
|
|
|
|
Ja, aber nur weil dein grid speziell/uniform ist. Sobald du ein irreguläres grid nutzt geht das nichtmehr so einfach die nachbar nodes zu finden. Mein grid damals wurde zB auch an Wänden generiert. Da willst du eigentlich zwangsläufig die referenzen aller nachbar-nodes in jeder node haben. Kannst ja nicht einfach "eine unit drüber/drunter/links/rechts" gucken und davon ausgehn dass da was ist.
Ausserdem ist ein dict mit nem int/hash als key immernoch schneller als mit nem Vector-Struct
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von freakadelle am 05.07.2018 14:05]
|
|
|
|
|
|
Puh.
Ja, mal gucken, was ich da noch rausholen kann.
|
|
|
|
|
|
|
Vergleiche es am besten auf 100x größeren Grids oder so, damit du auch wirklich sichtbare Ergebnisse bekommst.
Wie isn das 2D Zeugs bei Unity so? Brauchbar oder genauso broken wie bei Unreal?
Bin grad auf der Engine Suche für ein 2D Projekt.
|
|
|
|
|
|
|
Kenne Unreal nicht, aber Unity hat dahingehend dick nachgeliefert. Als ich angefangen hab, gab's noch keine Tilemaps und so, da haben alle noch mit externen Programmen gearbeitet. Jetzt finde ich das eigentlich alles ganz intuitiv.
|
|
|
|
|
|
|
e: Nope, mein Fehler, hab mich verscrollt
https://www.youtube.com/watch?v=-L-WgKMFuhE
Schau dir die Serie mal an. Der gibt sich wirklich Mühe mit seinen Tutorials. Denke der kann das alles auch besser erklären als hier über posts verteilt
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von freakadelle am 05.07.2018 14:17]
|
|
|
|
|
|
Grad nen 2 tägigen Unity-Kurs hinter mir. Mir qualmt der Kopf...
|
|
|
|
|
|
|
| Zitat von Murica
Vergleiche es am besten auf 100x größeren Grids oder so, damit du auch wirklich sichtbare Ergebnisse bekommst.
Wie isn das 2D Zeugs bei Unity so? Brauchbar oder genauso broken wie bei Unreal?
Bin grad auf der Engine Suche für ein 2D Projekt.
| |
Schau dir mal https://godotengine.org/ an. Das kann zwar inzwischen auch 3D aber war ursprünglich eine 2D Engine. Sollte 2D entsprechend halbwegs können.
|
|
|
|
|
|
Thema: Das pOT erstellt Spiele 4 ( code code durrrr ) |