Effiziente Fill Operation durchführen

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 8 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    Effiziente Fill Operation durchführen

    Guten Abend,
    ich entwickle für das Community-Projekt ( Minecraft-Klon Monogame) ein See Biom.

    Dafür schrieb ich ein Algorithmus um die maximale See-Höhe eines Chunks zu bestimmen:

    C#-Quellcode

    1. List<int> Heights = new List<int>();
    2. int[,] IntMap;
    4. private void FindSea()
    5. {
    6. Heights = Heights.OrderBy(p => p).ToList();
    8. int MinCounter = 0;
    9. int MinHeight = 0;
    11. IntMap = new int[HeightMap.GetUpperBound(0), HeightMap.GetUpperBound(1)];
    13. // 1 = Border
    14. // 0 = Neutral
    15. // 2 = Flood
    17. int Width = IntMap.GetUpperBound(0) + 1;
    18. int Height = IntMap.GetUpperBound(1) + 1;
    20. while (MinCounter < 5)
    21. {
    22. MinHeight = Heights[MinCounter];
    24. for (int i = 0; i < HeightMap.GetUpperBound(0); i++)
    25. {
    26. for (int j = 0; j < HeightMap.GetUpperBound(1); j++)
    27. {
    28. bool left = false;
    29. bool right = false;
    31. bool top = false;
    32. bool bot = false;
    34. if (i - 1 >= 0)
    35. left = (int)HeightMap[i - 1, j] == MinHeight;
    36. else left = true;
    37. if (i + 1 < IntMap.GetUpperBound(0))
    38. right = (int)HeightMap[i + 1, j] == MinHeight;
    39. else right = true;
    40. if (j - 1 >= 0)
    41. top = (int)HeightMap[i, j - 1] == MinHeight;
    42. else top = true;
    43. if (j + 1 < IntMap.GetUpperBound(0))
    44. bot = (int)HeightMap[i, j + 1] == MinHeight;
    45. else bot = true;
    46. if ((int)HeightMap[i, j] == MinHeight)
    47. {
    48. if (!left || !right || !top || !bot)
    49. IntMap[i, j] = 1;
    51. }
    52. }
    53. }
    55. //CHECK WHETER BORDERS ARE CONNECTED.
    57. int Counter = 0;
    58. Point[] OffenseField = new Point[Width * Height + 65];
    60. // ADD INITIAL OFFENSE FIELDS
    62. for (int i = 0; i < Width; i++)
    63. {
    64. if (IntMap[i, 0] != 1)
    65. OffenseField[Counter++] = new Point(i, 0);
    66. }
    68. for (int i = 0; i < Width; i++)
    69. {
    70. if (IntMap[i, Height - 1] != 1)
    71. OffenseField[Counter++] = new Point(i, Height - 1);
    72. }
    74. for (int j = 0; j < Height; j++)
    75. {
    76. if (IntMap[0, j] != 1)
    77. OffenseField[Counter++] = new Point(0, j);
    78. }
    80. for (int j = 0; j < Height; j++)
    81. {
    82. if (IntMap[Width - 1, j] != 1)
    83. OffenseField[Counter++] = new Point(Width - 1, j);
    84. }
    86. for (int i = 0; i < Counter; i++)
    87. {
    88. Point mid = OffenseField[i];
    90. Point left = new Point();
    91. Point right = new Point();
    92. Point top = new Point();
    93. Point bot = new Point();
    95. if (mid.X - 1 >= 0 && IntMap[mid.X - 1, mid.Y] != 1)
    96. left = new Point(mid.X - 1, mid.Y);
    97. if (mid.X + 1 < Width && IntMap[mid.X + 1, mid.Y] != 1)
    98. right = new Point(mid.X + 1, mid.Y);
    100. if (mid.Y - 1 >= 0 && IntMap[mid.X, mid.Y - 1] != 1)
    101. top = new Point(mid.X, mid.Y - 1);
    102. if (mid.Y + 1 < Height && IntMap[mid.X, mid.Y + 1] != 1)
    103. bot = new Point(mid.X, mid.Y + 1);
    105. if (!OffenseField.Contains(left))
    106. OffenseField[Counter++] = left;
    107. if (!OffenseField.Contains(right))
    108. OffenseField[Counter++] = right;
    109. if (!OffenseField.Contains(top))
    110. OffenseField[Counter++] = top;
    111. if (!OffenseField.Contains(bot))
    112. OffenseField[Counter++] = bot;
    114. if (IntMap[mid.X, mid.Y] != 1)
    115. IntMap[mid.X, mid.Y] = 2;
    116. }
    118. int CounterField = 0;
    119. int CounterRed = 0;
    120. int CounterBorder = 0;
    122. for (int i = 0; i < HeightMap.GetUpperBound(0); i++)
    123. {
    124. for (int j = 0; j < HeightMap.GetUpperBound(1); j++)
    125. {
    126. if (IntMap[i, j] == 1)
    127. {
    128. int left = -1;
    129. int right = -1;
    130. int top = -1;
    131. int bot = -1;
    133. if (i - 1 >= 0)
    134. left = IntMap[i - 1, j];
    135. if (i + 1 < Width)
    136. right = IntMap[i + 1, j];
    138. if (j - 1 >= 0)
    139. top = IntMap[i, j - 1];
    140. if (j + 1 < Height)
    141. bot = IntMap[i, j + 1];
    143. if (bot == 0)
    144. CounterField++;
    145. if (top == 0)
    146. CounterField++;
    147. if (right == 0)
    148. CounterField++;
    149. if (left == 0)
    150. CounterField++;
    152. if (bot == 2)
    153. CounterRed++;
    154. if (top == 2)
    155. CounterRed++;
    156. if (right == 2)
    157. CounterRed++;
    158. if (left == 2)
    159. CounterRed++;
    161. if (CounterRed == 0 && CounterField > 0)
    162. IntMap[i, j] = 0;
    165. if (CounterRed > 0 && CounterField > 0)
    166. IntMap[i, j] = 1;
    169. if (CounterRed > 0 && CounterField == 0)
    170. IntMap[i, j] = 2;
    172. CounterField = 0;
    173. CounterRed = 0;
    174. }
    175. if (IntMap[i, j] == 0)
    176. CounterBorder++;
    177. }
    178. }
    182. if (CounterBorder > 0)
    183. {
    184. SeaHeight = Heights[MinCounter];
    185. break;
    186. }
    187. else
    188. MinCounter++;
    190. }
    192. }


    Sieht imho widerlich aus.

    Es versucht ein geschlossenes System festzustellen... das erreicht es dadurch, dass er ein ganzes Array füllt .
    Dabei werden natürlich die Koordinaten bewahrt, die von Obstakel umkreist werden.

    Das Füllen geschieht so:

    C#-Quellcode

    1. //CHECK WHETER BORDERS ARE CONNECTED.
    3. int Counter = 0;
    4. Point[] OffenseField = new Point[Width * Height + 65];
    6. // ADD INITIAL OFFENSE FIELDS
    8. for (int i = 0; i < Width; i++)
    9. {
    10. if (IntMap[i, 0] != 1)
    11. OffenseField[Counter++] = new Point(i, 0);
    12. }
    14. for (int i = 0; i < Width; i++)
    15. {
    16. if (IntMap[i, Height - 1] != 1)
    17. OffenseField[Counter++] = new Point(i, Height - 1);
    18. }
    20. for (int j = 0; j < Height; j++)
    21. {
    22. if (IntMap[0, j] != 1)
    23. OffenseField[Counter++] = new Point(0, j);
    24. }
    26. for (int j = 0; j < Height; j++)
    27. {
    28. if (IntMap[Width - 1, j] != 1)
    29. OffenseField[Counter++] = new Point(Width - 1, j);
    30. }
    32. for (int i = 0; i < Counter; i++)
    33. {
    34. Point mid = OffenseField[i];
    36. Point left = new Point();
    37. Point right = new Point();
    38. Point top = new Point();
    39. Point bot = new Point();
    41. if (mid.X - 1 >= 0 && IntMap[mid.X - 1, mid.Y] != 1)
    42. left = new Point(mid.X - 1, mid.Y);
    43. if (mid.X + 1 < Width && IntMap[mid.X + 1, mid.Y] != 1)
    44. right = new Point(mid.X + 1, mid.Y);
    46. if (mid.Y - 1 >= 0 && IntMap[mid.X, mid.Y - 1] != 1)
    47. top = new Point(mid.X, mid.Y - 1);
    48. if (mid.Y + 1 < Height && IntMap[mid.X, mid.Y + 1] != 1)
    49. bot = new Point(mid.X, mid.Y + 1);
    51. if (!OffenseField.Contains(left))
    52. OffenseField[Counter++] = left;
    53. if (!OffenseField.Contains(right))
    54. OffenseField[Counter++] = right;
    55. if (!OffenseField.Contains(top))
    56. OffenseField[Counter++] = top;
    57. if (!OffenseField.Contains(bot))
    58. OffenseField[Counter++] = bot;
    60. if (IntMap[mid.X, mid.Y] != 1)
    61. IntMap[mid.X, mid.Y] = 2;
    62. }


    Ich generiere ein Array willkürlicher Größe( Width * Height + 65 ) und erzeuge ein 3x3 Pattern mit "Top", "Bot", "Left", "Right"... wenn diese nicht Obstakel sind, werden sie gefüllt... dauert nur lange.

    Gibt es einen effizienteren Füll Algorithmus?
    Lieben Dank!


    Post scriptum: Es funktioniert schon so ...(siehe Anhang) soll jedoch auch in 500x500 großen Arrays in unter 1 Sekunde einen See finden.
    Bilder

    • mc_sea.png

      1,34 MB, 1.920×1.080, 104 mal angesehen

    • seafinder.png

      6,32 kB, 756×538, 103 mal angesehen
    Und Gott alleine weiß alles am allerbesten und besser.

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „φConst“ ()

    Nevermid, habe ein HashSet benutzt, jetzt funktioniert es perfekt!

    In einem 582x475 großem Array wird in unter 2 Sekunden ein See gefunden!

    Pff, lol, falscher Alarm, doch nicht.
    Und Gott alleine weiß alles am allerbesten und besser.

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

    φConst schrieb:

    Gibt es einen effizienteren Füll Algorithmus?
    Höchstwahrscheinlich.

    Aber ich hab noch keinen Plan, wie dein bisheriger Algo funktioniert, nicht mal, was der eiglich machen soll.

    Kannst du nicht einen brauchbaren Methoden-Rumpf angeben, mit Parametern und Return-Value?
    Sowas definiert in klarer Weise (anhand der Datentypen), was hineingeht, und was bei rauskommen soll.

    C#-Quellcode

    1. HashSet<Point> OffenseField = new HashSet<Point>();
    2. for (int i = 0; i < OffenseField.Count; i++)
    3. {
    4. Point mid = OffenseField.ElementAt(i);
    6. Point left = new Point();
    7. Point right = new Point();
    8. Point top = new Point();
    9. Point bot = new Point();
    11. if (mid.X - 1 >= 0 && IntMap[mid.X - 1, mid.Y] != 1)
    12. left = new Point(mid.X - 1, mid.Y);
    14. if (mid.X + 1 < Width && IntMap[mid.X + 1, mid.Y] != 1)
    15. right = new Point(mid.X + 1, mid.Y);
    17. if (mid.Y - 1 >= 0 && IntMap[mid.X, mid.Y - 1] != 1)
    18. top = new Point(mid.X, mid.Y - 1);
    20. if (mid.Y + 1 < Height && IntMap[mid.X, mid.Y + 1] != 1)
    21. bot = new Point(mid.X, mid.Y + 1);
    23. if (!OffenseField.Contains(left))
    24. OffenseField.Add(left);
    25. if (!OffenseField.Contains(right))
    26. OffenseField.Add(right);
    27. if (!OffenseField.Contains(top))
    28. OffenseField.Add(top);
    29. if (!OffenseField.Contains(bot))
    30. OffenseField.Add(bot);
    32. IntMap[mid.X, mid.Y] = 2;
    33. }


    Diese Sektion der Methode füllt das Array.

    Felder die von Obstakel umkreist werden können nicht gefüllt werden.
    Wenn nun ein Feld nach der Füllung noch "klar" ist, also "leer", so ist die Höhe die dem Obstakel X zugewiesen ist, eine ideale Höhe für einen See...

    Das ist auch egal, ich suche nur nach einer effizienteren Variante eines Füll-Algorithmus'

    Zurzeit funktioniert es folgendergestalt:

    Gegeben sei eine Liste mit dem Typen Point.
    Der Liste werden Initial-Werte ( Initial-Angriffs-Punkte) hinzugefügt.

    Nun wird in einer For-Schleife Top, Bot, Left, Right - sofern eines dieser nicht Obstakel ist - in die Liste abgebildet... dies geschieht solange bis eben das ganze Array gefüllt ist.
    Problem: Anzahl der Elemente einer Liste steigt exponentiell, die Methode Contains ist für solche Größen nicht optimiert..

    Ich suche nach einer effizienteren Variante.
    Und Gott alleine weiß alles am allerbesten und besser.

    Ups - sorry - ich war etwas ungenau. Ich meinte nicht Methoden-Rumpf, sondern Methoden-Signatur.
    Also nicht den Inhalt der Methode, sondern nur ihre Deklaration.
    Dort wird ja bestimmt, was reingeht, und was zurückkommt.

    Aus diesem Code-Abschnitt ohne Anfang und Ende kann man nix weiter-entwickeln.
    Ausserdem ist dein wirklicher Code mit Sicherheit anders, denn hier zeigst du nichts von der Initial-Befüllung.
    Also der Code wie hier gezeigt würde die Schleife ühaupt nicht betreten.

    Ich sehe auch kein Array, was befüllt wird, und die gezeigte Contains-Methode - nämlich Hashset.Contains() ist sehr wohl für beliebig grosse Größen optimiert.
    Was hier suboptimal ist, ist die Hashset.ElementAt(i) - Extension.

    Und eine Liste kommt im Code auch nicht vor, deren Elemente exponentiell ansteigen würden.

    Und wie gesagt das Ziel der Veranstaltung ist mir unklar. Soll in ausgewählte IntMap-Felder 2 eingetragen werden - ist das das Ziel?

    (ich weiß auch nicht, was ein Obstakel ist, und wie man mit obigem Code rausfindet, um welches Feld - damit sind die IntMap-Felder gemeint? - son Obstakel herumkreist)

    hast du eine Füllhöhe, mit welcher gefüllt werden soll, oder ein Volumen? Volumen ist natürlich komplizierter.

    Mir fällt spontan ein Ansatz über OctTrees ein:
    Am jeweiligen Node werden nur die Ränder überprüft um somit ganze Nodes auszuschließen, oder eben nicht. Dann natürlich immer in niedrigeren Ebenen weiter suchen.

    Ist nur eine Grundsätzliche Idee, nie probiert und keine Ahnung wie effizient das nachher wäre.
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Eigentlich eine gute Idee.... oh man!
    Du hast recht( falls du das meinst)!
    Ich versuche einfach das Innere eines Umkreises zu füllen... wenn Feld X ein Obstakel ist, dann ist der Initial-Angriffspunkt bei Feld X.
    Wenn es nun ein Umkreis ist, dann hat jedes Feld Y das gefüllt ist, einen Feld X .

    Mit anderen Worten: Statt das ganze Array zu füllen, fülle ich nur die Bereiche im Obstakel.
    Und Gott alleine weiß alles am allerbesten und besser.

    Hat echt geklappt!!!!!

    C#-Quellcode

    1. List<int> Heights = new List<int>();
    2. int[,] IntMap;
    4. private void FindSea()
    5. {
    6. Heights = Heights.OrderBy(p => p).ToList();
    8. int MinCounter = 0 ;
    9. int MinHeight = 0;
    11. IntMap = new int[HeightMap.GetUpperBound(0) + 1, HeightMap.GetUpperBound(1) + 1];
    14. // 1 = Border
    15. // 0 = Neutral
    16. // 2 = Flood
    18. int Width = IntMap.GetUpperBound(0) + 1;
    19. int Height = IntMap.GetUpperBound(1) + 1;
    21. List<Point> Obstacles = new List<Point>();
    23. while (true)
    24. {
    25. MinHeight = Heights[MinCounter];
    27. for (int i = 0; i < HeightMap.GetUpperBound(0) + 1; i++)
    28. {
    29. for (int j = 0; j < HeightMap.GetUpperBound(1) + 1; j++)
    30. {
    31. bool left = true;
    32. bool right = true;
    34. bool top = true;
    35. bool bot = true;
    37. if (i - 1 >= 0)
    38. left = (int)HeightMap[i - 1, j] <= MinHeight;
    39. if (i + 1 < IntMap.GetUpperBound(0))
    40. right = (int)HeightMap[i + 1, j] <= MinHeight;
    41. if (j - 1 >= 0)
    42. top = (int)HeightMap[i, j - 1] <= MinHeight;
    43. if (j + 1 < IntMap.GetUpperBound(0))
    44. bot = (int)HeightMap[i, j + 1] <= MinHeight;
    45. if ((int)HeightMap[i, j] == MinHeight)
    46. {
    47. if (!left || !right || !top || !bot)
    48. {
    49. IntMap[i, j] = 1;
    50. Obstacles.Add(new Point(i, j));
    51. }
    53. }
    54. }
    55. }
    58. // CHECK WHETER BORDERS ARE CONNECTED.
    60. for (int i = 0; i < IntMap.GetUpperBound(0) + 1; i++)
    61. {
    62. for (int j = 0; j < IntMap.GetUpperBound(1) + 1; j++)
    63. {
    64. if (IntMap[i, j] != 1)
    65. {
    66. // COUNT
    67. if (Obstacles.Count(p => p.X == i) > 1 && Obstacles.Count(p => p.Y == j) > 1)
    68. IntMap[i, j] = 2;
    69. }
    70. }
    71. }
    73. // CLEAR
    74. int Counter = 0;
    76. int MinY = Obstacles.OrderBy(p => p.Y).ToList()[0].Y;
    77. int MaxY = Obstacles.OrderBy(p => p.Y).ToList()[Obstacles.Count - 1].Y;
    79. for (int k = 0; k < MaxY - MinY - 2; k++)
    80. {
    81. for (int i = 0; i < IntMap.GetUpperBound(0) + 1; i++)
    82. {
    83. for (int j = 0; j < IntMap.GetUpperBound(1) + 1; j++)
    84. {
    86. if (IntMap[i, j] == 2)
    87. {
    88. int left = -1;
    89. int right = -1;
    90. int top = -1;
    91. int bot = -1;
    93. if (i - 1 >= 0)
    94. left = IntMap[i - 1, j];
    95. if (i + 1 < Width)
    96. right = IntMap[i + 1, j];
    98. if (j - 1 >= 0)
    99. top = IntMap[i, j - 1];
    100. if (j + 1 < Height)
    101. bot = IntMap[i, j + 1];
    103. if (bot == 0)
    104. Counter++;
    105. if (top == 0)
    106. Counter++;
    107. if (right == 0)
    108. Counter++;
    109. if (left == 0)
    110. Counter++;
    112. if (Counter > 0)
    113. IntMap[i, j] = 0;
    114. }
    115. Counter = 0;
    117. }
    118. }
    119. }
    121. break;
    122. }
    123. }


    Der Algorithmus ist verdammt schnell!

    Noch eine Frage: Gibt es eine effizientere Methode zum Zählen spezifischer Elemente einer Liste statt .Count(a => a == b)?
    Bilder

    • seafinder_improved.png

      11,77 kB, 1.508×537, 92 mal angesehen
    Und Gott alleine weiß alles am allerbesten und besser.

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

    φConst schrieb:

    Gibt es eine effizientere Methode zum Zählen spezifischer Elemente einer Liste statt .Count(a => a == b)?
    Das ist eiglich schon ziemlich effizient - oder hast du wirklich Probleme damit?
    Ansonsten, wenn die Liste sortiert ist, kann man evtl. was mit BinärSuche machen - ist auch schon für Array und List(Of T) im Framework enthalten.

Facebook
Telefonspende