Zellulärer Automat - 3Dimensionales Array

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 16 Antworten in diesem Thema. Der letzte Beitrag () ist von Farliam.

    Zellulärer Automat - 3Dimensionales Array

    Hallo zusammen,

    meine Frage gilt vor allem der Performance - und der bestmöglichen Umsetzung.

    Ich würde gerne das Game Of Life in einem 3 - Dimensionalen Array darstellen. Einen ersten Entwurf habe ich bereits im SingleThread fertig.
    Nur ist die Geschwindigkeit extrem langsam. Ein 1000x1000x500 Array (Boolsche Werte) zu berechnen dauert über 5 Minuten.
    Vorteil ist das ich für die Spätere Darstellung direkt weiß, wo ich den Block zeichnen muss wenn ich mit x,y und z die Schleife laufen lasse.

    Nachteil ist das ich bei einer Dichte von ~10% die übrigen 90% tzd überprüfe - was dann sinnlose Arbeitszeit beansprucht.
    Ich könnte das Array auch in einzelne Chunks unterteilen, und parallel Berechnen lassen. Würde das Abhilfe Schaffen? Es bleiben tzd. 500mio zu überprüfen.

    Mein 2ter Ansatz wäre folgender:

    Eine List(of Vector3D) als Hilfe holen, die meine aktiven Zellen zwischenspeichert. Nun muss ich nicht mehr die 500mio überprüfen, sondern nur das was in der Liste ist.

    Das Problem dabei ist: Ich hole mir immer die Nachbarn um die Zelle.(Wie ein RubixCube, in der Mitte ist sozusagen die Zelle um die es geht, und alles drum herum sind die Nachbarn von denen der Zustand der Zentralen Zelle abhängt).
    Ich erstelle mir also einen Abstrackten Würfel, der die Zellen um die Aktive angibt:

    Spoiler anzeigen

    VB.NET-Quellcode

    1. ​ Private Function GetActive(ByVal pk As Point3D) As Integer 'Gibt den Wert zurück, wv Nachbarn leben
    3. Dim EP1, EP2, EP3, EP4, EP5, EP6, EP7, EP8, EP9 As Point3D
    4. Dim MP1, MP2, MP3, MP4, MP5, MP6, MP7, MP8 As Point3D
    5. Dim HP1, HP2, HP3, HP4, HP5, HP6, HP7, HP8, HP9 As Point3D
    7. With pk
    8. 'Die Erste Ebne
    9. EP1 = New Point3D(.X - 1, .Y - 1, .Z - 1)
    10. EP2 = New Point3D(.X, .Y - 1, .Z - 1)
    11. EP3 = New Point3D(.X + 1, .Y - 1, .Z - 1)
    12. EP4 = New Point3D(.X - 1, .Y, .Z - 1)
    13. EP5 = New Point3D(.X, .Y, .Z - 1)
    14. EP6 = New Point3D(.X + 1, .Y, .Z - 1)
    15. EP7 = New Point3D(.X - 1, .Y + 1, .Z - 1)
    16. EP8 = New Point3D(.X, .Y + 1, .Z - 1)
    17. EP9 = New Point3D(.X + 1, .Y + 1, .Z - 1)
    18. 'Die Mittlere Ebne
    19. MP1 = New Point3D(.X - 1, .Y - 1, .Z)
    20. MP2 = New Point3D(.X, .Y - 1, .Z)
    21. MP3 = New Point3D(.X + 1, .Y - 1, .Z)
    22. MP4 = New Point3D(.X - 1, .Y, .Z)
    23. MP5 = New Point3D(.X + 1, .Y, .Z)
    24. MP6 = New Point3D(.X - 1, .Y + 1, .Z)
    25. MP7 = New Point3D(.X, .Y + 1, .Z)
    26. MP8 = New Point3D(.X + 1, .Y + 1, .Z)
    27. 'Die Hintere Ebne
    28. HP1 = New Point3D(.X - 1, .Y - 1, .Z + 1)
    29. HP2 = New Point3D(.X, .Y - 1, .Z + 1)
    30. HP3 = New Point3D(.X + 1, .Y - 1, .Z + 1)
    31. HP4 = New Point3D(.X - 1, .Y, .Z + 1)
    32. HP5 = New Point3D(.X, .Y, .Z + 1)
    33. HP6 = New Point3D(.X + 1, .Y, .Z + 1)
    34. HP7 = New Point3D(.X - 1, .Y + 1, .Z + 1)
    35. HP8 = New Point3D(.X, .Y + 1, .Z + 1)
    36. HP9 = New Point3D(.X + 1, .Y + 1, .Z + 1)
    37. End With
    38. 'Nun müssen wir die Randbereiche Kontrollieren
    39. EP1.CheckCross(Breite, Höhe, Tiefe)
    40. EP2.CheckCross(Breite, Höhe, Tiefe)
    41. EP3.CheckCross(Breite, Höhe, Tiefe)
    42. EP4.CheckCross(Breite, Höhe, Tiefe)
    43. EP5.CheckCross(Breite, Höhe, Tiefe)
    44. EP6.CheckCross(Breite, Höhe, Tiefe)
    45. EP7.CheckCross(Breite, Höhe, Tiefe)
    46. EP8.CheckCross(Breite, Höhe, Tiefe)
    47. EP9.CheckCross(Breite, Höhe, Tiefe)
    48. MP1.CheckCross(Breite, Höhe, Tiefe)
    49. MP2.CheckCross(Breite, Höhe, Tiefe)
    50. MP3.CheckCross(Breite, Höhe, Tiefe)
    51. MP4.CheckCross(Breite, Höhe, Tiefe)
    52. MP5.CheckCross(Breite, Höhe, Tiefe)
    53. MP6.CheckCross(Breite, Höhe, Tiefe)
    54. MP7.CheckCross(Breite, Höhe, Tiefe)
    55. MP8.CheckCross(Breite, Höhe, Tiefe)
    56. HP1.CheckCross(Breite, Höhe, Tiefe)
    57. HP2.CheckCross(Breite, Höhe, Tiefe)
    58. HP3.CheckCross(Breite, Höhe, Tiefe)
    59. HP4.CheckCross(Breite, Höhe, Tiefe)
    60. HP5.CheckCross(Breite, Höhe, Tiefe)
    61. HP6.CheckCross(Breite, Höhe, Tiefe)
    62. HP7.CheckCross(Breite, Höhe, Tiefe)
    63. HP8.CheckCross(Breite, Höhe, Tiefe)
    64. HP9.CheckCross(Breite, Höhe, Tiefe)
    66. Dim Aktive As Integer = 0
    68. If AlleZellen(EP1.X, EP1.Y, EP1.Z) Then Aktive += 1
    69. If AlleZellen(EP2.X, EP2.Y, EP2.Z) Then Aktive += 1
    70. If AlleZellen(EP3.X, EP3.Y, EP3.Z) Then Aktive += 1
    71. If AlleZellen(EP4.X, EP4.Y, EP4.Z) Then Aktive += 1
    72. If AlleZellen(EP5.X, EP5.Y, EP5.Z) Then Aktive += 1
    73. If AlleZellen(EP6.X, EP6.Y, EP6.Z) Then Aktive += 1
    74. If AlleZellen(EP7.X, EP7.Y, EP7.Z) Then Aktive += 1
    75. If AlleZellen(EP8.X, EP8.Y, EP8.Z) Then Aktive += 1
    76. If AlleZellen(EP9.X, EP9.Y, EP9.Z) Then Aktive += 1
    78. If AlleZellen(MP1.X, MP1.Y, MP1.Z) Then Aktive += 1
    79. If AlleZellen(MP2.X, MP2.Y, MP2.Z) Then Aktive += 1
    80. If AlleZellen(MP3.X, MP3.Y, MP3.Z) Then Aktive += 1
    81. If AlleZellen(MP4.X, MP4.Y, MP4.Z) Then Aktive += 1
    82. If AlleZellen(MP5.X, MP5.Y, MP5.Z) Then Aktive += 1
    83. If AlleZellen(MP6.X, MP6.Y, MP6.Z) Then Aktive += 1
    84. If AlleZellen(MP7.X, MP7.Y, MP7.Z) Then Aktive += 1
    85. If AlleZellen(MP8.X, MP8.Y, MP8.Z) Then Aktive += 1
    87. If AlleZellen(HP1.X, HP1.Y, HP1.Z) Then Aktive += 1
    88. If AlleZellen(HP2.X, HP2.Y, HP2.Z) Then Aktive += 1
    89. If AlleZellen(HP3.X, HP3.Y, HP3.Z) Then Aktive += 1
    90. If AlleZellen(HP4.X, HP4.Y, HP4.Z) Then Aktive += 1
    91. If AlleZellen(HP5.X, HP5.Y, HP5.Z) Then Aktive += 1
    92. If AlleZellen(HP6.X, HP6.Y, HP6.Z) Then Aktive += 1
    93. If AlleZellen(HP7.X, HP7.Y, HP7.Z) Then Aktive += 1
    94. If AlleZellen(HP8.X, HP8.Y, HP8.Z) Then Aktive += 1
    95. If AlleZellen(HP9.X, HP9.Y, HP9.Z) Then Aktive += 1
    97. Return Aktive
    98. End Function


    Und diese Zellen hole ich mir aus dem Array, würde ich diese in der Liste suchen, müsste ich die Liste pro Eintrag nochmal 24 durchgehen, um zu überprüfen ob die Zelle vorhanden ist.
    Das bedeutet für mich, ich bräuchte sowohl das Array inklusive der Liste. Ich gehe aber nicht alle Bereiche im Array durch, sondern nur die in der Liste.

    Hoffe ihr versteht ungefähr wo meine Überlegung hingeht.

    LG

    @Farliam Probierma die laufende Lösung mit Parallel.For zu implementieren.
    Nimm die äußere Schleife.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich benutze Parallel.For so selten, da hab ich nichtmal dran gedacht. CPU wird jetzt zu 100% ausgelastet.

    Bei 500x500x500 dauert es aber immer noch ewig, und am Ende fliegt folgender Fehler :

    Spoiler anzeigen
    Assistent für verwaltetes Debuggen "ContextSwitchDeadlock" : "Die CLR konnte 60 Sekunden lang keinen Übergang vom COM-Kontext 0xcf8830 zum COM-Kontext 0xcf8778 durchführen. Der Thread, der Besitzer des Zielkontexts/-apartments ist, wartet entweder, ohne Meldungen zu verschieben, oder verarbeitet eine äußerst lang dauernde Operation, ohne Windows-Meldungen zu verschieben. Eine solche Situation beeinträchtigt in der Regel die Leistung und kann sogar dazu führen, dass die Anwendung nicht mehr reagiert oder die Speicherauslastung immer weiter zunimmt. Zur Vermeidung dieses Problems sollten alle STA-Threads (Singlethread-Apartment) primitive Typen verwenden, die beim Warten Meldungen verschieben (z. B. CoWaitForMultipleHandles), und bei lange dauernden Operationen generell Meldungen verschieben."


    Eventuell ist meine Schleife falsch?
    Laut Fehler ist die Operation zu lange, ohne das ich Windows-Meldungen verschiebe.

    Public Sub NextGeneration()
    Dim NeueZellen(Breite, Höhe, Tiefe) As Boolean
    ZurzeitLebend = 0

    VB.NET-Quellcode

    1. Parallel.For(0, Breite - 1, (Sub(x)
    2. For y As Integer = 0 To Höhe - 1
    3. For z As Integer = 0 To Tiefe - 1
    4. Dim Living As Integer = GetNachbar(New Point3D(x, y, z))
    5. Dim lv As Boolean = sRuleSet(Living, AlleZellen(x, y, z))
    6. NeueZellen(x, y, z) = lv
    7. If lv Then ZurzeitLebend += 1
    8. Next
    9. Next
    10. End Sub))
    11. AlleZellen = NeueZellen
    12. End Sub

    @Farliam Mach mal aus der anonymen Methode eine echte Methode.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    RodFromGermany schrieb:

    anonymen Methode


    Ich nehme mal an, du meinst das auf Bezug mit dem X in dem (Lambda?) Ausdruck?

    Mit Lambda hatte ich bisher eigentlich nie Kontakt. Sollte es so richtig sein?

    VB.NET-Quellcode

    1. Parallel.For(0, Breite - 1, New Action(Of Integer)(Sub(x)
    2. For y As Integer = 0 To Höhe - 1
    3. For z As Integer = 0 To Tiefe - 1
    4. Dim Living As Integer = GetNachbar(New Point3D(x, y, z))
    5. Dim lv As Boolean = sRuleSet(Living, AlleZellen(x, y, z))
    6. NeueZellen(x, y, z) = lv
    7. If lv Then ZurzeitLebend += 1
    8. Next
    9. Next
    10. End Sub))


    Würde das eventuell helfen? Versuch mal den ContextSwitchDeadlock MDA (Managed Debug Assistants) abschalten unter Debug --> Exceptionsund --> Managed Debugging Assistants.
    Oder eher die Finger davon lassen?^^

    @Farliam Pack den Code Sub(x) ... End Sub in eine nseparate Sub der Form und ruf die dann auf.
    Dann kannst Du sie Solo, unabhängig von Parallel.For, testen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Wie meinst du das?
    Sie hat eine eigenen Sub:

    VB.NET-Quellcode

    1. Public Sub NextGeneration()
    2. Dim NeueZellen(Breite, Höhe, Tiefe) As Boolean
    3. ZurzeitLebend = 0
    5. Parallel.For(0, Breite - 1, New Action(Of Integer)(Sub(x)
    6. For y As Integer = 0 To Höhe - 1
    7. For z As Integer = 0 To Tiefe - 1
    8. Dim Living As Integer = GetNachbar(New Point3D(x, y, z))
    9. Dim lv As Boolean = sRuleSet(Living, AlleZellen(x, y, z))
    10. NeueZellen(x, y, z) = lv
    11. If lv Then ZurzeitLebend += 1
    12. Next
    13. Next
    14. End Sub))
    15. AlleZellen = NeueZellen
    16. End Sub


    Und sie funktioniert an sich, nur das es halt langsam ist.

    @Farliam So was, ungetestet:

    VB.NET-Quellcode

    1. Public Sub NextGeneration()
    2. Dim NeueZellen(Breite, Höhe, Tiefe) As Boolean
    3. ZurzeitLebend = 0
    4. Parallel.For(0, Breite, InnereSchleife) ' der 2. Parameter ist exclusiv
    5. AlleZellen = NeueZellen
    6. End Sub
    8. Private Sub InnereSchleife(x As Integer)
    9. For y As Integer = 0 To Höhe - 1
    10. For z As Integer = 0 To Tiefe - 1
    11. Dim Living As Integer = GetNachbar(New Point3D(x, y, z))
    12. Dim lv As Boolean = sRuleSet(Living, AlleZellen(x, y, z))
    13. NeueZellen(x, y, z) = lv
    14. If lv Then ZurzeitLebend += 1
    15. Next
    16. Next
    17. End Sub
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich hab den Code etwas verändern müssen.

    VB.NET-Quellcode

    1. Private NeueZellen(Breite, Höhe, Tiefe) As Boolean
    3. Public Sub NextGenerationTest()
    4. ZurzeitLebend = 0
    5. Parallel.For(0, Breite - 1, New Action(Of Integer)(AddressOf InneR))
    6. AlleZellen = NeueZellen
    7. End Sub
    9. Public Sub InneR(ByVal x As Integer)
    10. For y As Integer = 0 To Höhe - 1
    11. GrayScale(x, y) = 0
    12. For z As Integer = 0 To Tiefe - 1
    13. Dim Living As Integer = GetNachbar(New Point3D(x, y, z))
    14. Dim lv As Boolean = sRuleSet(Living, AlleZellen(x, y, z))
    15. NeueZellen(x, y, z) = lv
    16. If lv Then
    17. ZurzeitLebend += 1
    18. GrayScale(x, y) += 1
    19. End If
    20. Next
    21. Next
    22. End Sub


    Zusätzlich habe ich noch eine Funktion gefunden die mich gedrosselt hat. Deswegen steht dort jetzt auch : GrayScale(x, y) += 1
    Somit muss ich nach der letzten Berechnung nur noch x-y durchgehen, und kann direkt zeichnen.

    Ich habe sowohl diese, als auch die andere Möglichkeit der Parallel.For mit einem Array von 200x200x200 getestet :

    5,6849886 sec. <- Alles in einem Sub

    5,695623 sec. <- Mit einer inneren Sub



    Bilder

    • Screenshot_3.png

      311,09 kB, 493×501, 110 mal angesehen

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Farliam“ ()

    Farliam schrieb:

    VB.NET-Quellcode

    1. Parallel.For(0, Breite - 1, New Action(Of Integer)(AddressOf InneR))
    machst Du

    VB.NET-Quellcode

    1. Parallel.For(0, Breite, AddressOf InneR)
    Der zweite Parameter ist exclusive!
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Irgendwas scheint da nicht zu stimmen.
    Die 2 Funktionen gleichen sich, bis auf den Unterschied das der eine im Sub läuft.
    Kann es daran liegen, das für jede Schleife X ein Thread angelegt wird, der am Ende auf die Globale Variabel "Neue Zellen" zugreifen will?

    Jedenfalls sieht das Ergebnis falsch aus. Und die Zeitersparnis ist auch = 0

    Ich glaube ich werde das ganze Konzept nochmal überdenken, und evt. wirklich auf eine List ausweichen, die nur die aktiven Speichert.
    Dann wird das überprüfen zwar schwerer, weil ich dann in einem 4x4x4 Cube auf Zellen suchen muss. Aber ich glaube die Zeitersparnis ist da höher.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Farliam“ ()

    Farliam schrieb:

    Jedenfalls sieht das Ergebnis falsch aus.
    Dann stimmt die innere Routine noch nicht.
    Du musst dafür sorgen, dass die Routinen parallel laufen können.
    Dazu dürfen sie nicht gleichzeitig in ein Element schreiben können. Das könnte ein wenig tricky werden.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Genau, doch die Frage ist lohnt sich das den Überhaupt?
    Die Parallel.For IM Sub, arbeitet ausgezeichnet.
    Die Parallel.For wo eine Innere Sub aufruft ist +/- 0 genauso schnell.
    Demnach geben sich die 2 doch nichts, und ich kann den Aufwand erstmal lassen.

    Eher würde ich das ganze Konzept einmal überdenken, mehr Speicher verwenden, aber dafür weniger CPU Last. Zusätzlich entfallen damit
    im meisten Fall nach der ersten Generation 50-60% der Aktiven Zellen, die dann umsonst abgefragt werden. Und das sind halt am Ende ein paar Millionen.

    Ich kopiere mal das aktuelle Projekt und versuche mal eine bessere Lösung zu finden.

    Farliam schrieb:

    arbeitet ausgezeichnet.
    Wenn Du sicher bist, dass der Algo stimmt, dann lass es.
    Allerdings ist mir unklar, warum sich beide Methoden so unterscheiden.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    RodFromGermany schrieb:

    Allerdings ist mir unklar, warum sich beide Methoden so unterscheiden.


    Ich gehe davon aus, das in dem einem Beispiel alles Funktioniert weil die Neuen-Zellen innerhalb des Blockes deklariert werden.
    In dem anderen Beispiel sind die Zellen Global deklariert, und wenn da mehrere Threads gleichzeitig laufen, kommt es da bestimmt zu Fehler.

    Doch weiß ich es nicht, habe Parallel.For fast nie benutzt; daher nur eine Vermutung von mir^^

    ich hatte mal ein 2d-Game of life gebastelt.
    Da ergab sich ein Performance-Durchbruch, als ich dazu überging, nicht jede Zelle zu berechnen, sondern nur die "bekannten".
    Das werden mit der Zeit immer mehr, und dadurch die Gesamt-Runden immer langsamer, aber immerhin es tat sich die ganze Zeit was.

    @ErfinderDesRades genau das war mein Ansatz im vorletzten Post.

    Ich speichere nur die Aktiven. Das 3x3x3 Raster erweitere ich auf 5x5x5. Denn Tote Zellen die als Nachbar eine Lebende haben können wiedergeboren werden. Also muss ich das schon abgrenzen.

    Bei einem 200x200x200 Würfel und 5% Aktive Zellen ist der unterschied schon ziemlich deutlich

    1,8432633 sec (5x5x5) über aktive Zellen
    5,6849886 sec Alle Zellen testen

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Farliam“ ()