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:
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:
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.
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
- List<int> Heights = new List<int>();
- int[,] IntMap;
- private void FindSea()
- {
- Heights = Heights.OrderBy(p => p).ToList();
- int MinCounter = 0;
- int MinHeight = 0;
- IntMap = new int[HeightMap.GetUpperBound(0), HeightMap.GetUpperBound(1)];
- // 1 = Border
- // 0 = Neutral
- // 2 = Flood
- int Width = IntMap.GetUpperBound(0) + 1;
- int Height = IntMap.GetUpperBound(1) + 1;
- while (MinCounter < 5)
- {
- MinHeight = Heights[MinCounter];
- for (int i = 0; i < HeightMap.GetUpperBound(0); i++)
- {
- for (int j = 0; j < HeightMap.GetUpperBound(1); j++)
- {
- bool left = false;
- bool right = false;
- bool top = false;
- bool bot = false;
- if (i - 1 >= 0)
- left = (int)HeightMap[i - 1, j] == MinHeight;
- else left = true;
- if (i + 1 < IntMap.GetUpperBound(0))
- right = (int)HeightMap[i + 1, j] == MinHeight;
- else right = true;
- if (j - 1 >= 0)
- top = (int)HeightMap[i, j - 1] == MinHeight;
- else top = true;
- if (j + 1 < IntMap.GetUpperBound(0))
- bot = (int)HeightMap[i, j + 1] == MinHeight;
- else bot = true;
- if ((int)HeightMap[i, j] == MinHeight)
- {
- if (!left || !right || !top || !bot)
- IntMap[i, j] = 1;
- }
- }
- }
- //CHECK WHETER BORDERS ARE CONNECTED.
- int Counter = 0;
- Point[] OffenseField = new Point[Width * Height + 65];
- // ADD INITIAL OFFENSE FIELDS
- for (int i = 0; i < Width; i++)
- {
- if (IntMap[i, 0] != 1)
- OffenseField[Counter++] = new Point(i, 0);
- }
- for (int i = 0; i < Width; i++)
- {
- if (IntMap[i, Height - 1] != 1)
- OffenseField[Counter++] = new Point(i, Height - 1);
- }
- for (int j = 0; j < Height; j++)
- {
- if (IntMap[0, j] != 1)
- OffenseField[Counter++] = new Point(0, j);
- }
- for (int j = 0; j < Height; j++)
- {
- if (IntMap[Width - 1, j] != 1)
- OffenseField[Counter++] = new Point(Width - 1, j);
- }
- for (int i = 0; i < Counter; i++)
- {
- Point mid = OffenseField[i];
- Point left = new Point();
- Point right = new Point();
- Point top = new Point();
- Point bot = new Point();
- if (mid.X - 1 >= 0 && IntMap[mid.X - 1, mid.Y] != 1)
- left = new Point(mid.X - 1, mid.Y);
- if (mid.X + 1 < Width && IntMap[mid.X + 1, mid.Y] != 1)
- right = new Point(mid.X + 1, mid.Y);
- if (mid.Y - 1 >= 0 && IntMap[mid.X, mid.Y - 1] != 1)
- top = new Point(mid.X, mid.Y - 1);
- if (mid.Y + 1 < Height && IntMap[mid.X, mid.Y + 1] != 1)
- bot = new Point(mid.X, mid.Y + 1);
- if (!OffenseField.Contains(left))
- OffenseField[Counter++] = left;
- if (!OffenseField.Contains(right))
- OffenseField[Counter++] = right;
- if (!OffenseField.Contains(top))
- OffenseField[Counter++] = top;
- if (!OffenseField.Contains(bot))
- OffenseField[Counter++] = bot;
- if (IntMap[mid.X, mid.Y] != 1)
- IntMap[mid.X, mid.Y] = 2;
- }
- int CounterField = 0;
- int CounterRed = 0;
- int CounterBorder = 0;
- for (int i = 0; i < HeightMap.GetUpperBound(0); i++)
- {
- for (int j = 0; j < HeightMap.GetUpperBound(1); j++)
- {
- if (IntMap[i, j] == 1)
- {
- int left = -1;
- int right = -1;
- int top = -1;
- int bot = -1;
- if (i - 1 >= 0)
- left = IntMap[i - 1, j];
- if (i + 1 < Width)
- right = IntMap[i + 1, j];
- if (j - 1 >= 0)
- top = IntMap[i, j - 1];
- if (j + 1 < Height)
- bot = IntMap[i, j + 1];
- if (bot == 0)
- CounterField++;
- if (top == 0)
- CounterField++;
- if (right == 0)
- CounterField++;
- if (left == 0)
- CounterField++;
- if (bot == 2)
- CounterRed++;
- if (top == 2)
- CounterRed++;
- if (right == 2)
- CounterRed++;
- if (left == 2)
- CounterRed++;
- if (CounterRed == 0 && CounterField > 0)
- IntMap[i, j] = 0;
- if (CounterRed > 0 && CounterField > 0)
- IntMap[i, j] = 1;
- if (CounterRed > 0 && CounterField == 0)
- IntMap[i, j] = 2;
- CounterField = 0;
- CounterRed = 0;
- }
- if (IntMap[i, j] == 0)
- CounterBorder++;
- }
- }
- if (CounterBorder > 0)
- {
- SeaHeight = Heights[MinCounter];
- break;
- }
- else
- MinCounter++;
- }
- }
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
- //CHECK WHETER BORDERS ARE CONNECTED.
- int Counter = 0;
- Point[] OffenseField = new Point[Width * Height + 65];
- // ADD INITIAL OFFENSE FIELDS
- for (int i = 0; i < Width; i++)
- {
- if (IntMap[i, 0] != 1)
- OffenseField[Counter++] = new Point(i, 0);
- }
- for (int i = 0; i < Width; i++)
- {
- if (IntMap[i, Height - 1] != 1)
- OffenseField[Counter++] = new Point(i, Height - 1);
- }
- for (int j = 0; j < Height; j++)
- {
- if (IntMap[0, j] != 1)
- OffenseField[Counter++] = new Point(0, j);
- }
- for (int j = 0; j < Height; j++)
- {
- if (IntMap[Width - 1, j] != 1)
- OffenseField[Counter++] = new Point(Width - 1, j);
- }
- for (int i = 0; i < Counter; i++)
- {
- Point mid = OffenseField[i];
- Point left = new Point();
- Point right = new Point();
- Point top = new Point();
- Point bot = new Point();
- if (mid.X - 1 >= 0 && IntMap[mid.X - 1, mid.Y] != 1)
- left = new Point(mid.X - 1, mid.Y);
- if (mid.X + 1 < Width && IntMap[mid.X + 1, mid.Y] != 1)
- right = new Point(mid.X + 1, mid.Y);
- if (mid.Y - 1 >= 0 && IntMap[mid.X, mid.Y - 1] != 1)
- top = new Point(mid.X, mid.Y - 1);
- if (mid.Y + 1 < Height && IntMap[mid.X, mid.Y + 1] != 1)
- bot = new Point(mid.X, mid.Y + 1);
- if (!OffenseField.Contains(left))
- OffenseField[Counter++] = left;
- if (!OffenseField.Contains(right))
- OffenseField[Counter++] = right;
- if (!OffenseField.Contains(top))
- OffenseField[Counter++] = top;
- if (!OffenseField.Contains(bot))
- OffenseField[Counter++] = bot;
- if (IntMap[mid.X, mid.Y] != 1)
- IntMap[mid.X, mid.Y] = 2;
- }
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.
Und Gott alleine weiß alles am allerbesten und besser.
Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „φConst“ ()