2D Array (Mit Nachbarn arbeiten)

  • VB.NET

Es gibt 13 Antworten in diesem Thema. Der letzte Beitrag () ist von Eistee.

    2D Array (Mit Nachbarn arbeiten)

    Nabend,

    Ich wollte mal fragen, wie ihr das umsetzen würdet.
    Es gibt ein 2D Array welches ihr abarbeitet, jede Zelle hat ja min. 3 Nachbarn (die Ecken).
    Wie macht ihr das, wen ihr immer mit allen vorhandenen Nachbarn irgendetwas machen wollt?



    Sagen wir es ist ein 2D Integer Array (alle Felder = 1) und jetzt geht man für jede Zelle die Nachbarn abklappern und setzt diese z. B. += 1
    Wie würdet ihr das machen? Da gibt es doch bestimmt wieder irgendein Trick, mit dem das ganze fix gemacht werden kann :D

    Also wie ich es in etwas machen würde:

    VB.NET-Quellcode

    1. For Y < Height
    2. For X < Width
    3. Array(X,Y) 'eigentliche Zelle
    4. Array(X+1,Y) 'Nachbar Rechts
    5. Array(X-1,Y) 'Nachbar Links
    6. Array(X,Y-1) 'Nachbar Oben
    7. Array(X-1,Y-1) 'Nachbar Oben-Links
    8. Next
    9. Next


    Mann muss "nur" OutOfRange abfangen.
    Aber irgendwie gefällt mir das so ganz und garnicht.
    Deswegen wollt ich hier mal nachfragen, weil ihr bis jetzt immer eine sauberere Lösung kanntet :)

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

    Wenn ich mich nicht irre, dann müsste das so funktionieren:

    C-Quellcode

    1. int[,] arr;
    2. int x, y;
    3. for (int i = Math.Max(x - 1, 0); i < Math.Min(x + 2, arr.GetUpperBound(0)); i++)
    4. {
    5. for (int j = Math.Max(y - 1, 0); j < Math.Min(y + 2, arr.GetUpperBound(1)); j++)
    6. {
    7. if (i == x && j == y)
    8. continue;
    9. //hier werden die Nachbarn durchlaufen
    10. }
    11. }

    Meinst du das nach dem if?
    Nein, solange nur ein Statement kommt, braucht man keinen Codeblock anfangen. Deshalb würde das auch so gehen:

    C-Quellcode

    1. int[,] arr;
    2. int x, y;
    3. for (int i = Math.Max(x - 1, 0); i < Math.Min(x + 2, arr.GetUpperBound(0)); i++)
    4. for (int j = Math.Max(y - 1, 0); j < Math.Min(y + 2, arr.GetUpperBound(1)); j++)
    5. if (i != x || j != y)
    6. //hier werden die Nachbarn durchlaufen

    Sieht natürlich nicht sonderlich übersichtlich aus, aber funktionieren tut es. Der Codeblock fasst mehrere Statements sozusagen zu einem Statement zusammen und vertieft den Scope.
    Von meinem iPhone gesendet

    Ich hätte noch den Vorschlag einer generischen Extension-Method für 2D-Arrays:

    VB.NET-Quellcode

    1. Imports System.Runtime.CompilerServices
    3. Module Array2DExtensions
    4. <Extension>
    5. Public Shared Function LeftOf(Of T)(sourceArray As T(,), x As Integer, y As Integer) As T
    6. Return sourceArray(Math.Max(x - 1, 0), y)
    7. End Function
    9. <Extension>
    10. Public Shared Function RightOf(Of T)(sourceArray As T(,), x As Integer, y As Integer) As T
    11. Return sourceArray(Math.Min(sourceArray.GetUpperBound(0), x + 1), y)
    12. End Function
    14. <Extension>
    15. Public Shared Function TopOf(Of T)(sourceArray As T(,), x As Integer, y As Integer) As T
    16. Return sourceArray(x, Math.Max(y - 1, 0))
    17. End Function
    19. <Extension>
    20. Public Shared Function LowerOf(Of T)(sourceArray As T(,), x As Integer, y As Integer) As T
    21. Return sourceArray(x, Math.Min(sourceArray.GetUpperBound(1), y + 1))
    22. End Function
    23. End Module

    C#:
    Spoiler anzeigen

    C-Quellcode

    1. static class Array2DExtensions
    2. {
    3. public static T LeftOf<T>(this T[,] sourceArray, int x, int y)
    4. {
    5. return sourceArray[Math.Max(x - 1, 0), y];
    6. }
    7. public static T RightOf<T>(this T[,] sourceArray, int x, int y)
    8. {
    9. return sourceArray[Math.Min(sourceArray.GetUpperBound(0), x + 1), y];
    10. }
    11. public static T TopOf<T>(this T[,] sourceArray, int x, int y)
    12. {
    13. return sourceArray[x, Math.Max(y - 1, 0)];
    14. }
    15. public static T LowerOf<T>(this T[,] sourceArray, int x, int y)
    16. {
    17. return sourceArray[x, Math.Min(sourceArray.GetUpperBound(1), y + 1)];
    18. }
    19. }


    Ob die Richtungen stimmen, weiß ich nicht. Habe es nicht getestet.
    Verwenden könntest du es so:

    VB.NET-Quellcode

    1. Dim arr As Integer(,) = New Integer(,) {{1, 2}, {3, 4}, {5, 6}, {7, 8}}
    2. Dim a As Integer = arr.LeftOf(1, 1)


    Performancemäßig nicht so toll, aber besser, wenn du nur auf die Nachbarn eines einzigen Punktes zugreifen willst.

    Edit:
    Ggf. solltest du das Verhalten ändern, falls es einen Nachbarn nicht gibt. Entweder Exception werfen oder einen Nullable(Of T) zurückgeben (und dann beim Nichtvorhandensein Nothing zurückgeben).
    Von meinem iPhone gesendet

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

    Eistee schrieb:

    Ich wollte mal fragen, wie ihr das umsetzen würdet.
    Es gibt ein 2D Array welches ihr abarbeitet, jede Zelle hat ja min. 3 Nachbarn (die Ecken).
    Wie macht ihr das, wen ihr immer mit allen vorhandenen Nachbarn irgendetwas machen wollt?
    fallen mir verschiedene Möglichkeiten ein:
    schreib dir eine Funktion, die die Indicees aller Nachbarn einer Zelle zurückgibt - als Integer-Array.

    Bastel dir eine Datenstruktur, wo jede Zelle eine Liste ihrer Nachbarn hält. Obwohl ist egal: Um die Datenstruktur zu befüllen, brauchste o.g. Funktion ja ebenso.

    Kommt aber malwieder auch drauf an, was du machen willst. Etwa in Convolution-Filter gibts eine 2D-Pattern-Matrix, die quasi über das 2D-Array gelegt und auf die darunterliegenden Zellen angewendet wird

    Hi
    andere Möglichkeit: Sofern du nicht Massen an Zellen hast, die du in einem Rutsch verarbeiten musst, kannst du Elemente verketten. Speichere hierzu einfach das linke, rechte, obere und untere Element (+ ggf. noch das davor und dahinter, wenn du 3-dimensional arbeitest). Damit ist die Verarbeitung einfacher und du kannst beliebig und insbesondere beliebig viele Elemente effizient dazuhängen, ist auch für Wegfindung und Clipping nicht schlecht, aber verbraucht viel Speicherplatz. Wenn du auf Arraybasis arbeiten möchtest, kannst du auch ein Array als Basis nehmen und die oben genannten Properties in einer Klasse verfügbar machen, das wären dann halt statt Referenzen Ausdrücke, die das gewünschte liefern. Ein effizienterer Ansatz wäre ggf. auch, mehrere Listen zu nehmen, die den Raum darstellen.

    Übrigens: Array ist mMn. bei sowas eine Art Engpass, da es erst vollständig befüllt werden muss, bevor es weitergeleitet wird. Das ist insbesondere bei asynchroner Datenverarbeitung entscheidend, da wäre IEnumerable(Of T) ggf. mit yield besser, wenn mehr, als die paar Indices zurückgegeben werden soll.

    Gruß
    ~blaze~

    Das Problem lässt sich sehr performant in unsave C# lösen, da kannst Du mit Pointern rumhantieren wie in C++.
    Mach das in C# oder mach Dir eine C#-DLL, die das Feld und die High-Speed Operationen hält.
    Dann ist das ganze so etwas wie ein Filteroperator in der Bildverarbeitung.
    -----
    In VB solltest Du das ganze jedenfalls auch parallelisieren, gugst Du Parallel.For.
    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!

    ~blaze~ schrieb:

    Speichere hierzu einfach das linke, rechte, obere und untere Element (+ ggf. noch das davor und dahinter, wenn du 3-dimensional arbeitest).
    Jo, das meinte ich mit Datenstruktur. Aber um die zu befüllen braucher genauso eine Methode, die zu einer Zelle die Nachbar-Indizees zurückgibt.

    Was das mit c# zu tun haben soll ist mir unerfindlich - Arrays sind in vb auch net anners.
    @Eistee: deutet nicht an, dass hier das letzte an Optimierung rausgeholt wern muß, sondern soll doch erstmal laufen.

    Aber muss sich @Eistee: zu äußern.

    Sucht Eistee denn eine besonders schnelle und leistungsoptimierte Methode oder eine einfach zu verwendende? Ich bin vom letzteren ausgegangen. Je nachdem kommen ja ganz unterschiedliche Ansätze in Frage.
    Von meinem iPhone gesendet

    Ganz schön viel los hier :) Ne, also im ersten Moment ging es mir nur um die einfache Umsetzung, dafür war das Schleifen-Konstrukt von Artentus wirklich hervorragend.
    Auch weil in dem Anwendungsfall, immer ein komplett gefülltes Array vorlag und immer alle Nachbarn jeder einzelnen Zelle durchlaufen werden muss.
    Die Geschwindigkeit ist dabei zu venachlässigen gewesen. (Es war hier für: [Beta] MyIsland [Alpha 0.1.0] )

    Doch da ich zur gleichen Zeit versuche, endlich mal den A* in Code zu gießen, könnte solch eine Art Funktion/Extension/Klasse wohl relativ nützlich sein.
    Nur was wiederrum für diesen Anwendungsfall die beste Methode und auch Rückgabewert ist, wüsste ich jetzt noch nicht.
    Denn ehrlich gesagt konnte ich der Ausführung nicht zu 100% folgen.. wo ich immer wieder durcheinander komme, ist die Stelle an der man vergleicht ob der Knoten mit dem niedrigsten F Wert wirklich der beste Weg ist:

    Um die Suche fortzusetzen, wählen wir aus der offenen Liste einfach das Quadrat mit dem niedrigsten F-Wert. Mit diesem (aktuellen) Quadrat machst Du Folgendes: [...]

    Falls eines der umliegenden Quadrate sich bereits in der offenen Liste befindet, prüfe, ob der Pfad vom aktuellen Quadrat zu solch einem Quadrat ein besserer ist, mit anderen Worten, ob der G-Wert für dieses Quadrat geringer wäre, wenn wir vom aktuellen Quadrat aus dorthin gehen würden. Wenn nicht, unternimm gar nichts.
    Falls jedoch die G-Kosten dieses Quadrates geringer würden, wenn wir vom aktuellen Quadrat aus dorthin gehen würden, ändere das Vorgängerquadrat dieses Quadrats auf das aktuelle Quadrat (richte dann den Zeiger im Diagramm oben auf das aktuelle Quadrat). Schließlich berechne sowohl den F- als auch den G-Wert dieses Quadrats neu. Falls dies etwas verwirrend sein sollte, findest Du eine Darstellung weiter unten.
    Quelle: policyalmanac.org/games/aStarTutorial_de.html

    Dort muss man ja auch alle Nachbarn einer Zelle/Knoten prüfen nur, wär ich mir nicht sicher was nun am besten/schnellsten wäre.
    Erst alle Nachbarn ausgeben und dann prüfen? Oder Nachbarn einzelnt Ausgeben und prüfen und das ganze abbrechen, falls der Weg über diesen Nachbarn nicht doch kürzer ist?

    Habe hier wohl mit einer starken Konzentrationsschwäche zu kämpfen, denn so schwer erscheint mir das eig. garnicht :wacko:

Facebook
Telefonspende