RPG-Maker Quartier

Hier dreht sich alles um die RPG-Maker-Reihe von ASCII/Enterbrain. Der RPG-Maker ist ein Tool, mit dem du dir dein eigenes kleines Rollenspiel erstellen kannst. Du findest hier alles, was du dazu brauchst. Aber natürlich umfasst die Community noch mehr!
Aktuelle Zeit: Do Sep 19, 2019 4:24

Alle Zeiten sind UTC + 1 Stunde



Mitglieder in diesem Forum: Google [Bot] und 2 Gäste



Ein neues Thema erstellen Auf das Thema antworten  [ 721 Beiträge ]  Gehe zu Seite Vorherige  1 ... 41, 42, 43, 44, 45, 46, 47 ... 49  Nächste
Autor Nachricht
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 6:10 
Hallo! Ich habe folgendes Problem:

Einige Felder eines relativ großen zweidimensionalen Feldes werden zufällig (oder auch bestimmt) mit Werten gefüllt. Gehen wir der Einfachkeit halber davon aus, dass es sich nur um true und false handelt.
Bei der Überprüfung der belegten Felder und visuellen Darstellung des Feldes am Bildschirm ist es nun sehr unperformant jede Reihe und jede Spalte zu durchlaufen und zu betrachten. Eine mögliche Lösung wäre jeden Wert zusätzlich mit seinen Koordinaten in einer Liste einzutragen, um dann "nur" noch diese Liste zu durchlaufen. Allerdings könnte man dann diese Lösung auch weiterspinnen und gar kein tatsächliches Feld mehr benutzen.

Wie machen sowas unsere Profis hier? Die Anforderung ist später lediglich eine performante Darstellung einer zweidimensionalen Fläche zu haben, bei der unterschieden werden kann, ob ein Feld belegt ist, oder nicht. Prinzipiell.

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Technik-Freak
Technik-Freak
Benutzeravatar
Beiträge: 6635
Wohnort: Köln =0
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 7:44 
Warum sollte eine Liste performanter sein?

_________________
Bild

1,24€ die Minute


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 8:28 
Nehmen wir an ich habe ein 50 * 50 großes Feld mit einem Wert bei [49, 49]. Wenn ich alle Werte in einer Liste gespeichert habe, gehe ich per foreach durch die Liste, erkenne einen Eintrag und stelle ihn an Punkt [49, 49] des Bildschirms dar. Wenn ich keine Liste habe, erkenne ich erst bei der letzten Iteration durch alle 50 Zeilen und 50 Spalten einen gesetzten Wert. Liegt auf der Hand, wieso das in diesem Fall performanter ist, oder?

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Schweizer Reiter
Schweizer Reiter
Benutzeravatar
Beiträge: 379
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 9:22 
Dein Verfahren macht nur Sinn, wenn nur etwa 10% der Felder belegt sind.
Ist so eine Optimierung überhaupt notwendig?
Ist die Anwendung Zeitkritisch?

Wenn es nur 50*50 Felder sind für eine Bildschirmausgabe, sind die größeren Performanc-Einbußen die Daarstellung auf dem Bildschirm.
Da macht das Iterationsverfahren keinen großen Unterscheid mehr.

Kümmer dich mehr darum den Code lesbar zu halten als unrelevante Performanceoptimierungen zu machen.

_________________


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 10:58 
Zitat:
Wenn es nur 50*50 Felder sind für eine Bildschirmausgabe, sind die größeren Performanc-Einbußen die Daarstellung auf dem Bildschirm.
Da macht das Iterationsverfahren keinen großen Unterscheid mehr.

Gut, damit wirst du dann wohl recht haben.

Nehmen wir an alle Felder müssen mit jedem Rendervorgang neu gezeichnet werden: Wie geht man am optimalsten vor, oder ist es nicht möglich eine allgemeingültige Aussage zu treffen?

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Archmaester of the Citadel
Archmaester of the Citadel
Beiträge: 6468
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 17:00 
TWS, das ist Schwachsinn. Komplexitätsanalyse ist nicht "Performance-Optimierung"; wenn dein Algorithmus O(n^2) statt O(n) braucht, kriegt das dein Compiler auch nicht weg. Und seit wann schließen lesbarer Code und effiziente Algorithmen einander gegenseitig aus?
Natürlich hast du Recht, daß bei 50*50 Feldern das absolut egal ist, aber wir wissen ja nicht, wie das Problem konkret aussieht.

Askr, du fragst sehr unkonkret. Was ist der konkrete Anwendungsfall, was soll wann wie gemacht werden?
Im true/false-Fall kann es durchaus sinnvoll sein, zB alle true-Koordinaten in einer Liste zu speichern, aber man müßte halt ein bißchen mehr wissen.


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Attention-whore
Attention-whore
Benutzeravatar
Beiträge: 1583
Alter: 30
Wohnort: /var/www
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 17:31 
Askr hat geschrieben:
Nehmen wir an ich habe ein 50 * 50 großes Feld mit einem Wert bei [49, 49]. Wenn ich alle Werte in einer Liste gespeichert habe, gehe ich per foreach durch die Liste, erkenne einen Eintrag und stelle ihn an Punkt [49, 49] des Bildschirms dar. Wenn ich keine Liste habe, erkenne ich erst bei der letzten Iteration durch alle 50 Zeilen und 50 Spalten einen gesetzten Wert. Liegt auf der Hand, wieso das in diesem Fall performanter ist, oder?


Dein Punkt liegt doch in beiden Fällen an Position 2499. Wo liegt da die Optimierung?
Vor allem glaube ich das 2 for Schleifen schneller sind als eine foreach Schleife über ein Objekt.

Außer du sortierst die Liste, nach dem Setzen der Werte, entsprechend, dann ist das natürlich was anderes.


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Archmaester of the Citadel
Archmaester of the Citadel
Beiträge: 6468
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 18:39 
Ich glaube, Askr meint eher sowas wie "activeFields = [[1,15],[2,30],[5,49],...]"
Also wir speichern nur die Felder, die auch auf true gesetzt sind; was Sinn macht, wenn es nicht so viele sind. Indizieren kann man in einem Array ja mit O(1), suchen dauert länger.


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Schweizer Reiter
Schweizer Reiter
Benutzeravatar
Beiträge: 379
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Mi Sep 19, 2012 22:04 
Was findest du an meiner Aussage Schwachsinnig?
Und außerdem hab ich mit keinem Wort über Komplexität gesprochen.

Der Letzte Satz bezieht sich lediglich darauf, dass Askr sich lieber mit anderen Dingen befassen soll, als über "unnötige" Optimierungen an dieser Stellen nachzudenken.

_________________


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Do Sep 20, 2012 6:27 
Fryie hat geschrieben:
Ich glaube, Askr meint eher sowas wie "activeFields = [[1,15],[2,30],[5,49],...]"
Also wir speichern nur die Felder, die auch auf true gesetzt sind; was Sinn macht, wenn es nicht so viele sind.

Genau das war einer meiner Gedanken; ist natürlich in der Tat nur dann sinnvoll, wenn der Großteil der Felder leer ist.

Fryie hat geschrieben:
Askr, du fragst sehr unkonkret. Was ist der konkrete Anwendungsfall, was soll wann wie gemacht werden?

Der konkrete Anwendungsfall ist eine Umsetzung von Conways Game of Life. Da ich allerdings die selbe Problematik (langsame/verzögerte Ausgabe auf dem Bildschirm) auch schon vorher hatte (Roguelike, TileEngine, eben alles wo man 2D-Felder am Bildschirm darstellt), würde ich mich das grundlegende Prinzip interessieren, wie man so etwas effizient aufbaut.

Askr hat geschrieben:
Nehmen wir an alle Felder müssen mit jedem Rendervorgang neu gezeichnet werden: Wie geht man am optimalsten vor, oder ist es nicht möglich eine allgemeingültige Aussage zu treffen?

Meine Renderfunktion ist ziemlich straight-forward. Zwei For-Schleifen und auf jedes Feld wird ein Kreis gezeichnet; je nach aktueller Phase und Zustand des Felds in anderer Farbe. Zur Ausgabe auf dem Bildschirm verwende ich SFML 2.0.

Sobald das Feld größer als 30*30 Felder ist, bricht die Performance merkbar ein.

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Official Oldschool
Official Oldschool
Benutzeravatar
Beiträge: 8917
Alter: 30
Wohnort: BRD, Thüringen
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Do Sep 20, 2012 7:12 
Ich behaupte, dass eine Liste ist effizienter in den meisten Situationen. Wenn du zusätzlich noch schnellen Zugriff auf die Information brauchst, auf welchem Feld welches Objekt ist, kannst du zusätzlich zu der Liste noch einen 2D-Array mit Pointern auf die Listelemente oder ein Bitvektor, wenn dich nur die Existenz eines Objekts interessiert, abspeichern.

btw. das deine Performance einbricht, liegt NICHT an dem Iterieren der Liste (heutige Rechner können weitaus größere Listen als 30^2 iterieren ohne Performanceprobleme zu bekommen). Du zeichnest immer (in verschiedenen Farben), egal ob ein Objekt an der Position ist oder nicht. Das lässt deine Performance einbrechen. Zeichenoperationen sind nunmal enorm aufwendig. Insbesondere, wenn du noch sowas abgefahrenes wie Kreise zeichnest.
Was du probieren kannst: Die beiden verschiedenen Kreise vorher zeichnen, in einen Zwischenbuffer abspeichern und dann nur noch die Pixel jeweils auf das Feld rüberkopieren. Das sollte deutlich performanter sein.

_________________


Nach oben
 Profil ICQ  
Mit Zitat antworten  
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Do Sep 20, 2012 7:18 
Zitat:
btw. das deine Performance einbricht, liegt NICHT an dem Iterieren der Liste. Du zeichnest immer (in verschiedenen Farben), egal ob ein Objekt an der Position ist oder nicht. Das lässt deine Performance einbrechen.

Ja, das haben wir schon rausbekommen.

Zitat:
Zeichenoperationen sind nunmal enorm aufwendig. Insbesondere, wenn du noch sowas abgefahrenes wie Kreise zeichnest.

Also kann ich das Problem nur mit einer "schnelleren Library" lösen?

Zitat:
Was du probieren kannst: Die beiden verschiedenen Kreise vorher zeichnen, in einen Zwischenbuffer abspeichern und dann nur noch die Pixel jeweils auf das Feld rüberkopieren. Das sollte deutlich performanter sein.

Werd ich gleich mal ausprobieren. Ich lasse gerade die durchschnittlich benötigte Zeit zum Rendern sammeln, um Vergleichswerte zu haben.
Time to render 15*15 board (in ms): 16,90169
Time to render 20*20 board (in ms): 27,412741
Time to render 25*25 board (in ms): 41,744174
Time to render 30*30 board (in ms): 66,186618
Time to render 35*35 board (in ms): 82,818281
Time to render 40*40 board (in ms): 103,41034
Time to render 45*45 board (in ms): 128,232822
Time to render 50*50 board (in ms): 161,596158
Time to render 55*55 board (in ms): 196,699668
Time to render 60*60 board (in ms): 234,243422
Time to render 65*65 board (in ms): 272,647262
Time to render 70*70 board (in ms): 312,601257
Time to render 75*75 board (in ms): 371,297126
Time to render 80*80 board (in ms): 421,192115
Time to render 85*85 board (in ms): 475,727568
Time to render 90*90 board (in ms): 531,173112
Time to render 95*95 board (in ms): 599,989993
Time to render 100*100 board (in ms): 657,345728

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Do Sep 20, 2012 7:46 
Wow, das hat sich sehr stark bemerkbar gemacht:
Time to render 20*20 board (in ms): 9,53
Time to render 30*30 board (in ms): 9,93
Time to render 40*40 board (in ms): 11,85
Time to render 50*50 board (in ms): 17,99
Time to render 60*60 board (in ms): 26,2
Time to render 70*70 board (in ms): 35,05
Time to render 80*80 board (in ms): 45,92
Time to render 90*90 board (in ms): 55,21
Time to render 100*100 board (in ms): 67,4


Damit fühlt sich nun ein 80*80 board so flüssig, wie vorher ein 30*30 board an. Danke für den Tipp (auf den ich, bei näherer Betrachtung aber ruhig auch hätte kommen können :seek:)!

Ich werde jetzt noch das Brett auf eine Liste umstellen und nochmal prüfen; das dauert aber etwas länger. :D

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Uca purgilator
Uca purgilator
Benutzeravatar
Beiträge: 3497
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Do Sep 20, 2012 9:29 
Time to render 20*20 board (in ms): 9,540954
Time to render 30*30 board (in ms): 10,281028
Time to render 40*40 board (in ms): 16,071607
Time to render 50*50 board (in ms): 24,30243
Time to render 60*60 board (in ms): 32,133213
Time to render 70*70 board (in ms): 35,263526
Time to render 80*80 board (in ms): 44,694469
Time to render 90*90 board (in ms): 54,885488
Time to render 100*100 board (in ms): 68,496849

Und hier die Ergebnisse mit verschachtelten Listen, statt einem 2D-Array.

Nicht unbedingt besser, als der 2D-Array. Bei einer Größe von 1000*1000 ist der 2D-Array 300ms schneller, aber selbst bei 500*500 sind sie noch etwa gleichauf. Habe bei diesen Größen allerdings nur mit dem Schnitt von 10 Durchläufen gemessen; sonst hätte mir das zu lange gedauert. Ich bleibe jedenfalls nun beim 2D-Array.

_________________
Bild


Nach oben
 Profil  
Mit Zitat antworten  
Offline
Archmaester of the Citadel
Archmaester of the Citadel
Beiträge: 6468
 Betreff des Beitrags: Re: Programmier-Talk - #1
BeitragVerfasst: Fr Sep 28, 2012 7:47 
AKTIVITÄT!


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 721 Beiträge ]  Gehe zu Seite Vorherige  1 ... 41, 42, 43, 44, 45, 46, 47 ... 49  Nächste

Alle Zeiten sind UTC + 1 Stunde


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de