Du bist nicht angemeldet.

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 690

Wohnort: Gießen

  • Private Nachricht senden

1

20.01.2018, 19:51

simpelstes Pathfinding auf einem Grid

Hallo,
ich habe eine Bewegungsrichtung, die ich über ein Enum setzen kann

C#-Quelltext

1
2
3
4
5
6
7
public enum MovementDirections
{
    Up,
    Down,
    Left,
    Right
}


und ein Grid, bestehend aus Zellen

C#-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Cell
{
    public Cell(int posX, int posY, bool isObstacle)
    {
        PosX = posX;
        PosY = posY;
        IsObstacle = isObstacle;
    }

    public int PosX { get; set; }

    public int PosY { get; set; }

    public bool IsObstacle { get; set; }
}


Beim Erzeugen der Karte speichere ich mir alle Zellen in einer Liste. Für das Verständnis,

C#-Quelltext

1
mapCells


ist die Liste mit sämtlichen Zellen der Karte.

C#-Quelltext

1
playerInfo.CurrentCell


speichert einfach nur die Zelle, auf der sich der Spieler momentan befindet.

Bei einer Bewegung möchte ich also alle Zellen einer Reihe haben. Dabei kann aber eine Zelle auch ein Hindernis sein, dann soll der Spieler beim "ersten" Hindernis stoppen. Die folgende Methode soll mir die finale Zelle zurückliefern, dabei gibt es viele Ähnlichkeiten im Code und die fast identischen Schleifen springen mir ins Auge. Ebenso die fast immer gleichen If-Abfragen. Dennoch fällt mir momentan keine saubere Lösung ein, da ich in dem zweiten Switch die Anzahl der Zellen in der Reihe brauche und diese Anzahl lege ich erst im ersten Switch fest. :S

Vielleicht hat ja jemand eine Idee, ob man den Code noch kürzer / sauberer / optimaler aufbauen kann.



Vielleicht geht es auch nicht besser, aber wie gesagt, ich sehe da schon einige Ähnlichkeiten im Code ?(

David Scherfgen

Administrator

Beiträge: 10 198

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

20.01.2018, 21:20

Noch umständlicher konntest du es nicht machen? ;)
Für ein Grid benutzt man ein 2D-Array*, der Index [x][y] liefert dir die Zelle an Position x, y. Du musst in der Zelle keine Position speichern.

* Alternativ ein 1D-Array, wo du den Index über y*Breite+x berechnest.

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 690

Wohnort: Gießen

  • Private Nachricht senden

3

21.01.2018, 00:01

@David da gebe ich dir Recht. Dennoch trägt die Zelle auch andere Informationen, beispielsweise, ob sie ein Hindernis ist. Da ich mir jede erzeugte Zelle sowieso in einer Liste speichern muss, kann ich dann ja auch die Position dazu nehmen.

Sonst hätte ich ja eine Liste mit Zellen und ein 2D Array mit Positionen. Oder denke ich da falsch?

Außerdem würde sich dann doch der Code bei der oben genannten Methode noch nicht kürzen oder?

4

21.01.2018, 01:25

Da es sich hierbei um ein Grid Handelt ist es effizenter einfach ein 2D Array mit dem Datentyp "Cell" zu nehmen. Wenn dann z.B der Player/Cursor sich in dem Grid bewegt musst du lediglich die umliegenden Felder abfragen, viel einfacher als in einer reinen Liste nach Positionenwerten zu suchen.

David Scherfgen

Administrator

Beiträge: 10 198

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

5

21.01.2018, 06:21

Exakt. Einfacher und schneller, da man nicht umständlich suchen muss, um die Zelle an einer bestimmten Position zu finden. Man weiß direkt, wo man gucken muss, nämlich bei [x, y]. Deine Variante mit Suchen ist O(n), d.h. je größer die Welt wird, desto langsamer wird es (stell dir vor, du hast eine Milliarde Zellen und musst im Schnitt eine halbe Milliarde davon testen, bis du die richtige gefunden hast). Die vorgeschlagene Variante ist O(1), braucht also immer gleich lange.

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 690

Wohnort: Gießen

  • Private Nachricht senden

6

21.01.2018, 10:22

Es leuchtet ein :P

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 690

Wohnort: Gießen

  • Private Nachricht senden

7

21.01.2018, 21:26

so @David, ich hoffe so hattest du es dir gewünscht

C#-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public Cell GetTargetCell(Vector2 movementDirection)
    {
        Vector2 currentCellIndex = GetPlayerCellIndex(); // aktuellen Zellindex holen
        Vector2 targetCellIndex = GetTargetCellIndex(currentCellIndex, movementDirection); // rekursiv die Felder durchsuchen
        return mapCells[(int)targetCellIndex.x, (int)targetCellIndex.y];
    }

private Vector2 GetTargetCellIndex(Vector2 currentCellIndex, Vector2 movementDirection)
    {
        Vector2 nextCellIndex = currentCellIndex + movementDirection;

        int maxLengthHorizontal = mapCells.GetLength(0); // Länge einer Reihe
        int maxLengthVertical = mapCells.GetLength(1); // Länge einer Spalte

        bool fitsMinIndexHorizontal = nextCellIndex.x >= 0;
        bool fitsMinIndexVertical = nextCellIndex.y >= 0;
        bool fitsMaxIndexHorizontal = nextCellIndex.x < maxLengthHorizontal;
        bool fitsMaxIndexVertical = nextCellIndex.y < maxLengthVertical;

        if (fitsMinIndexHorizontal && fitsMinIndexVertical && fitsMaxIndexHorizontal && fitsMaxIndexVertical) // Innerhalb des Spielfeldes?
        {
            bool nextCellIsObstacle = mapCells[(int)nextCellIndex.x, (int)nextCellIndex.y].IsObstacle;

            if (!nextCellIsObstacle)
            {
                return GetTargetCellIndex(nextCellIndex, movementDirection);
            }
        }

        return currentCellIndex;
    }


Er durchläuft rekursiv eine Reihe / Spalte immer ein Feld weiter und prüft dabei, ob das nächste Feld ein Hindernis ist oder der Spielfeldrand erreicht wurde.

Zumindest jetzt ohne Switch oder sonst was, 100% Mathe ;)

David Scherfgen

Administrator

Beiträge: 10 198

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

8

21.01.2018, 21:30

Schon besser, aber sowas löst man normalerweise nicht rekursiv, sondern iterativ. Ist effizienter, du bekommst keinen Stack Overflow wegen zu tiefer Rekursion, und meiner Meinung nach ist es in diesem Fall auch besser lesbar.
Außerdem muss ich bemängeln, dass du ständig zwischen int und float hin und her konvertierst, obwohl hier doch alles mit Integern geht. Gibt's bei dir keine Klasse für 2D-Vektoren mit Integer-Koordinaten?
Und eigentlich musst du nicht immer in alle 4 Richtungen prüfen, ob du das Spielfeld verlässt. Wenn du nach rechts gehst, kannst du das Spielfeld nur nach rechts verlassen, nicht nach links, oben oder unten.
Du kannst das Ganze wahrscheinlich sehr kompakt und effizient in unter 10 Zeilen machen. Du hast da noch extrem viel Overhead drin.

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 690

Wohnort: Gießen

  • Private Nachricht senden

9

21.01.2018, 22:14

Ja, eine while-Schleife würde ich nehmen.

Die Konvertierungen mache ich deshalb, weil Vector2 eine Klasse von Unity ist und die Werte nur floats sein können. Also müsste ich mir entweder eine eigene Koordinaten Klasse schreiben (würde wohl Sinn machen) oder ich muss es zu Beginn umwandeln.

Wegen den Prüfungen gucke ich mal gleich, ich weiß, das geht besser :P

Tobiking

1x Rätselkönig

  • Private Nachricht senden

10

21.01.2018, 22:18


Die Konvertierungen mache ich deshalb, weil Vector2 eine Klasse von Unity ist und die Werte nur floats sein können. Also müsste ich mir entweder eine eigene Koordinaten Klasse schreiben (würde wohl Sinn machen) oder ich muss es zu Beginn umwandeln.

Laut Doku gibt es auch eine Klasse Vector2Int.

Werbeanzeige