simpelstes Pathfinding auf einem Grid

Werbeanzeige

Garzec

Alter Hase

Beiträge: 693

Wohnort: Gießen

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

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.

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

Suche

C#-Quelltext

public Cell GetTargetCell(MovementDirections movementDirection)
    {
        List<Cell> cellsOnPath = new List<Cell>(); // Alle Zellen in der Reihe

        for (int i = 0; i < mapCells.Count; i++)
        {
            Cell currentCell = mapCells[i];

            switch (movementDirection)
            {
                case MovementDirections.Up:
                    if (currentCell.PosX == playerInfo.CurrentCell.PosX && currentCell.PosY > playerInfo.CurrentCell.PosY) // (0,1)
                    {
                        cellsOnPath.Add(currentCell);
                    }
                    break;

                case MovementDirections.Down:
                    if (currentCell.PosX == playerInfo.CurrentCell.PosX && currentCell.PosY < playerInfo.CurrentCell.PosY) // (0,-1)
                    {
                        cellsOnPath.Add(currentCell);
                    }
                    break;

                case MovementDirections.Left:
                    if (currentCell.PosX < playerInfo.CurrentCell.PosX && currentCell.PosY == playerInfo.CurrentCell.PosY) // (-1,0)
                    {
                        cellsOnPath.Add(currentCell);
                    }
                    break;

                case MovementDirections.Right:
                    if (currentCell.PosX > playerInfo.CurrentCell.PosX && currentCell.PosY == playerInfo.CurrentCell.PosY) // (1,0)
                    {
                        cellsOnPath.Add(currentCell);
                    }
                    break;
            }
        }

        int closestObstacleIndex = cellsOnPath.Count; // der Index für das "erste" Hindernis

        for (int i = 0; i < cellsOnPath.Count; i++)
        {
            Cell currentCell = cellsOnPath[i];

            switch (movementDirection)
            {
                case MovementDirections.Up:
                    if (currentCell.PosY < closestObstacleIndex)
                    {
                        closestObstacleIndex = currentCell.PosY;
                    }
                    break;

                case MovementDirections.Down:
                    if (currentCell.PosY > closestObstacleIndex)
                    {
                        closestObstacleIndex = currentCell.PosY;
                    }
                    break;

                case MovementDirections.Left:
                    if (currentCell.PosX > closestObstacleIndex)
                    {
                        closestObstacleIndex = currentCell.PosX;
                    }
                    break;

                case MovementDirections.Right:
                    if (currentCell.PosX < closestObstacleIndex)
                    {
                        closestObstacleIndex = currentCell.PosX;
                    }
                    break;
            }
        }

        return cellsOnPath[closestObstacleIndex];
    }

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

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

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.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Garzec

Alter Hase

Beiträge: 693

Wohnort: Gießen

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?

Zum Seitenanfang

Pidi64

Frischling

Beiträge: 1

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.

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

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.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Garzec

Alter Hase

Beiträge: 693

Wohnort: Gießen

21.01.2018, 10:22

Es leuchtet ein

Zum Seitenanfang

Garzec

Alter Hase

Beiträge: 693

Wohnort: Gießen

21.01.2018, 21:26

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

C#-Quelltext

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

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

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.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Garzec

Alter Hase

Beiträge: 693

Wohnort: Gießen

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

Zum Seitenanfang

Tobiking

1x Rätselkönig

Beiträge: 1 231

21.01.2018, 22:18

Zitat von »Garzec«

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.

Zum Seitenanfang

Werbeanzeige

spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

simpelstes Pathfinding auf einem Grid

simpelstes Pathfinding auf einem Grid

C#-Quelltext

C#-Quelltext

C#-Quelltext

C#-Quelltext

Suche

C#-Quelltext

C#-Quelltext

Zitat von »Garzec«

Ähnliche Themen