Skip to content

C# and XNA Pathfinding with A-Star

The pathfinding in my XNA based RTS game finally works as desired. The following screenshot shows a few units and their paths (yellow lines). The blue squares are the grid cells which they would move to next.

Pathfinding in action

Base Conflict Pathfinding

For the sake of reusability I tried to keep my code relatively general. The Pathfinder class, which calculates the path relies on the following two interfaces which offer all the neccessary information describing a 2d grid map.

    /// <summary>
    /// A grid cell of a 2D grid map.
    /// </summary>
    public interface IGridCell
    {
        /// <summary>
        /// X coordinate in 2d grid space (cell index)
        /// </summary>
        int X { get; }

        /// <summary>
        /// Y coordinate in 2d grid space (cell index)
        /// </summary>
        int Y { get; }

        /// <summary>
        /// Weight of this cell. Standard value should be 0.
        /// Can be higher to account for difficult terrain or
        /// occupied cells. To make sure the cell won't be 
        /// part of a path the weight should be very high
        /// compared to the standard or usual weights used.
        /// </summary>
        int Weight { get; }

        /// <summary>
        /// Determines whether this cell can be walked and therefore
        /// should be considered for path calculations.
        /// </summary>
        bool IsWalkable { get; }

        /// <summary>
        /// Determines whether the point p corresponds to
        /// this cell, that is its X and Y coordinates are equal
        /// to the cell coordinates X and Y.
        /// </summary>
        /// <param name="p">A point of grid coordinates</param>
        /// <returns>True if the cell matches the given coordinates</returns>
        bool Matches(Point p);

        /// <summary>
        /// The 3D position of this grid cell. This should be the point
        /// right in the middle of the cell at the height of the grid.
        /// </summary>
        /// <remarks>Is not used by Pathfinder itself. This is just a convenience
        /// property for other users of the interface. If you don't need the
        /// 3D position of the cell (because your game is 2D only), you don't
        /// have to return a defined value. Just return Vector3.Zero or anything 
        /// else, it doesn't matter.</remarks>
        Vector3 Position3D { get; }
    }

    /// <summary>
    /// A 2D grid map offering key information about the grid.    
    /// </summary>
    public interface IGridMap
    {
        /// <summary>
        /// Calculates the 2D grid position (cell indices) from
        /// a 3D position.
        /// </summary>
        /// <param name="pos">position in 3D world space</param>
        /// <returns>position in 2D grid space</returns>
        Point PosToGrid(Vector3 pos);

        /// <summary>
        /// Returns the grid cell with the grid coordinates (cell indices)
        /// p.X and p.Y.
        /// </summary>
        /// <param name="p">A point of grid coordinates</param>
        /// <returns>Corresponding grid cell</returns>
        IGridCell GetCell(Point p);

        /// <summary>
        /// Returns a collection of neighbour cells. In a simple 2D grid that
        /// should be 8 cells surrounding the current cell. This method must
        /// not return invalid cells, that means it should not include non
        /// existing or invalid cells to begin with.
        /// </summary>
        /// <param name="cell">A grid cell of the strategic map</param>
        /// <returns>Collection of neighbour cells</returns>
        ICollection<IGridCell> GetNeighbourCells(IGridCell cell);
    }

This offers the advantage of not having to create a new grid representation every time the path is calculated, since you can incorporate the grid you are probably using already anyway (I have seen quite a few examples where there was created a byte array or something similar to represent the grid cells).

For my current game I just needed to implement these interfaces in my StrategicMap class to use the Pathfinder. Each cell in the StrategicMap contains a list of units that occupy it. Consequently the weight of the cells is calculated depending on whether they contain units. The property “IsWalkable” is a shortcut for discarding cells that never can be part of the path anyway. In my specific implementation it returns true in case a unit occupies the cell. The weight on the other hand can be used to account for difficult terrain or similar situations where you want to penalise certain grid cells.

My Pathfinder implementation is a simple one, I guess. It uses the manhattan distance as a heuristic which is quick and easy to calculate but not optimal. In case I needed something better I could easily swap it, however. Here is the code:

    /// <summary>
    /// Description of a path request. The path request
    /// can differ from the path itself, because the exact
    /// path might not exist. The path request stores
    /// what path was requested. The actual found path
    /// is stored in a separate Path instance.
    /// </summary>
    public struct PathRequest
    {
        public Point start;
        public Point end;

        public PathRequest(Point start, Point end)
        {
            this.start = start;
            this.end = end;
        }

        public override bool Equals(object obj)
        {
            PathRequest other = (PathRequest)obj; 	        
            return start.Equals(other.start) && end.Equals(other.end);            
        }
    }

    /// <summary>
    /// Representation of a path.
    /// Contains a implicitly linked list of PathNodes.
    /// </summary>
    public class Path
    {
        /// <summary>
        /// Current node
        /// </summary>
        PathNode current;

        /// <summary>
        /// Original start node
        /// </summary>
        PathNode start;    

        /// <summary>
        /// Creates a new path beginning at the specified start
        /// </summary>
        /// <param name="start">start path node</param>
        public Path(PathNode start)
        {
            current = start;
            this.start = start;
        }

        /// <summary>
        /// Returns true, if the path should be at its end
        /// </summary>
        public bool Finished { get { return current == null; } }

        /// <summary>
        /// Peeks at the next path node without removing it from the path
        /// </summary>
        public PathNode Next { get { return current; } }

        /// <summary>
        /// Delivers the next waypoint and moves on in the path,
        /// discarding the returned node.
        /// </summary>
        /// <returns></returns>
        public IGridCell GetNextWaypoint()
        {            
            PathNode next = current;                        
            current = current.Predecessor;            
            return next.Cell;
        }

        /// <summary>
        /// Just for debugging: Renders the complete path from beginning.
        /// </summary>
        [Conditional("DEBUG")]
        public void DrawPath()
        {
            DrawPath(start, start.Predecessor);
        }

        /// <summary>
        /// Recursive function for rendering a path segment as a yellow line.
        /// </summary>
        /// <param name="from">Start node</param>
        /// <param name="to">End node</param>
        [Conditional("DEBUG")]
        private void DrawPath(PathNode from, PathNode to)
        {            
            if (to == null) return;            
            DebugDisplay.Instance.DrawLine(from.Cell.Position3D, to.Cell.Position3D, from == start ? Color.Red : Color.Yellow);
            DrawPath(to, to.Predecessor);
        }

        /// <summary>
        /// Copies this instance of the path.
        /// </summary>
        /// <returns></returns>
        public Path Copy()
        {
            Path copy = new Path(start);
            return copy;
        }
    }

    /// <summary>
    /// A node in an A* calculated path. 
    /// </summary>
    public class PathNode : IComparable, IComparable<PathNode>, IEquatable<PathNode>
    {        
        /// <summary>
        /// The preceding node which lead to this node
        /// </summary>
        PathNode predecessor;

        /// <summary>
        /// The corresponding grid cell on the 2d map
        /// </summary>
        IGridCell cell;

        /// <summary>
        /// Destination coordinates in 2d map space
        /// </summary>
        Point goal;

        /// <summary>
        /// base cost summed up for every already visited node
        /// </summary>
        float g;

        /// <summary>
        /// cost regarding to the heuristic, estimating the left distance
        /// to the goal.
        /// </summary>
        float h;

        /// <summary>
        /// total cost of this node (g + h)
        /// </summary>
        float f;

        /// <summary>
        /// base cost summed up for every already visited node
        /// </summary>
        public float G { get { return g; } }

        /// <summary>
        /// cost regarding to the heuristic, estimating the left distance
        /// to the goal.
        /// </summary>
        public float H { get { return h; } }

        /// <summary>
        /// total cost of this node (g + h)
        /// </summary>        
        public float F { get { return f; } }

        /// <summary>
        /// The grid cell on the 2d map represented by this node
        /// </summary>
        public IGridCell Cell { get { return cell; } }

        /// <summary>
        /// The preceding node which lead to this node
        /// </summary>
        public PathNode Predecessor
        {
            get { return predecessor; }
            set { predecessor = value; }
        }

        /// <summary>
        /// Creates a new path node. The cost (or weight) of this node is automatically
        /// calculated according to the predecessor, cell and goal.
        /// </summary>
        /// <param name="predecessor">preceding node</param>
        /// <param name="cell">grid cell represented by the node</param>
        /// <param name="goal">goal coordinate in 2d map space</param>
        public PathNode(PathNode predecessor, IGridCell cell, Point goal)
        {            
            this.cell = cell;            
            this.predecessor = predecessor;
            this.goal = goal;

            Update();            
        }

        /// <summary>
        /// Recalculates the costs. This is neccessary when the predecessor has changed.
        /// </summary>
        public void Update()
        {
            if (cell.Matches(goal))
            {
                // The path ends here
                g = 1;
                h = 1;
                f = 1;
            }
            else
            {
                // cost for moving from start to this node
                g = (predecessor != null ? predecessor.G : 0) + cell.Weight;                

                // heuristic estimating the cost for moving from this node to the goal by Manhattan distance
                h = 10 * (Math.Abs(cell.X - goal.X) + Math.Abs(cell.Y - goal.Y));

                // the combined cost is later used to compare nodes
                f = g + h;
            }
        }

        #region IComparable Member

        /// <summary>
        /// Path nodes are soley compared by comparing their costs (F).
        /// </summary>
        /// <param name="obj">An other PathNode</param>
        /// <returns>Returns -1 when the the other path node is more expensive, 1 if it is less expensive and 0 otherwise</returns>
        public int CompareTo(object obj)
        {
            PathNode node = obj as PathNode;
            if (node.F < f) return 1;
            else if (node.F > f) return -1;
            else return 0;
        }

        #endregion

        #region IEquatable<PathNode> Member

        /// <summary>
        /// Two path nodes are equal when they represent the same grid cell.
        /// </summary>
        /// <param name="other">Another path node</param>
        /// <returns>True if both nodes represent the same grid cell</returns>
        public bool Equals(PathNode other)
        {
            return cell == other.cell;
        }

        #endregion

        #region IComparable<PathNode> Member

        /// <summary>
        /// Path nodes are soley compared by comparing their costs (F).
        /// </summary>
        /// <param name="other">An other PathNode</param>
        /// <returns>Returns -1 when the the other path node is more expensive, 1 if it is less expensive and 0 otherwise</returns>       
        public int CompareTo(PathNode other)
        {
            if (other.F < f) return 1;
            else if (other.F > f) return -1;
            else return 0;
        }

        #endregion
    }

    /// <summary>
    /// An A* implementation for finding paths on a 2D map.
    /// </summary>
    public class Pathfinder
    {
        /// <summary>
        /// Maximum number of steps allowed to find a path.
        /// The more steps allowed the longer the process 
        /// can take. When the step limit is reached the
        /// search is aborted.
        /// </summary>
        int stepLimit;

        /// <summary>
        /// Debug Mode settings. If true paths may be visualized.
        /// </summary>
        public static bool DebugMode { get; set; }        
        
        /// <summary>
        /// The grid map giving information about the 2D grid.
        /// </summary>
        IGridMap map;

        /// <summary>
        /// Debug Mode is enabled by default
        /// </summary>
        static Pathfinder()
        {
            DebugMode = true;
        }

        /// <summary>
        /// List containing known paths
        /// </summary>
        Dictionary<PathRequest, Path> knownPaths = new Dictionary<PathRequest, Path>();

        /// <summary>
        /// Creates a new Path finder for the specified stragic map.
        /// </summary>
        /// <param name="map">A strategic map</param>
        /// <param name="stepLimit">Maximum number of steps to find a path</param>
        public Pathfinder(IGridMap map, int stepLimit)
        {
            this.map = map;
            this.stepLimit = stepLimit;
        }

        /// <summary>
        /// Creates a new Path finder for the specified stragic map.
        /// Sets the step limit to 140 steps by default, which is only suitable for
        /// relatively short paths (depending on the grid size).
        /// </summary>
        /// <param name="map">A strategic map</param>
        public Pathfinder(IGridMap map)
            : this(map, 140)
        {
        }

        /// <summary>
        /// Calculates a path from start to end. When no path can be found in
        /// reasonable time the search is aborted and an incomplete path is returned.
        /// When refresh is not set to true a cached path is returned where possible.
        /// </summary>
        /// <param name="start">start position in 3d world space</param>
        /// <param name="end">end position in 3d world space</param>
        /// <param name="refresh">force to recalculate the path</param>
        /// <returns></returns>
        public Path CalculatePath(Vector3 start, Vector3 end, bool refresh)
        {
            return CalculatePath(map.PosToGrid(start), map.PosToGrid(end), refresh);
        }

        /// <summary>
        /// Calculates a path from start to end. When no path can be found in
        /// reasonable time the search is aborted and an incomplete path is returned. 
        /// When refresh is not set to true a cached path is returned where possible.
        /// </summary>
        /// <param name="start">start position in 2d map space</param>
        /// <param name="end">end position in 2d map space</param>
        /// <param name="refresh">force to recalculate the path</param>
        /// <returns></returns>
        public Path CalculatePath(Point start, Point end, bool refresh)
        {
            // swap points to calculate the path backwards (from end to start)
            Point temp = end;
            end = start;
            start = temp;

            // Check whether the requested path is already known
            PathRequest request = new PathRequest(start, end);
            if (!refresh && knownPaths.ContainsKey(request))
            {                
                return knownPaths[request].Copy();
            }

            // priority queue of nodes that yet have to be explored sorted in 
            // ascending order by node costs (F)
            PriorityQueue<PathNode> open = new PriorityQueue<PathNode>();

            // list of nodes that have already been explored
            LinkedList<IGridCell> closed = new LinkedList<IGridCell>();

            // start is to be explored first
            PathNode startNode = new PathNode(null, map.GetCell(start), end);
            open.Enqueue(startNode);            

            int steps = 0;            
            PathNode current;

            do 
            {
                // abort if calculation is too expensive
                if (++steps > stepLimit) return null;

                // examine the cheapest node among the yet to be explored
                current = open.Dequeue();
                
                // Finish?
                if (current.Cell.Matches(end))
                {
                    // paths which lead to the requested goal are cached for reuse
                    Path path = new Path(current);
                    
                    if (knownPaths.ContainsKey(request))
                    {
                        knownPaths[request] = path.Copy();
                    }
                    else
                    {
                        knownPaths.Add(request, path.Copy());
                    }

                    return path; 
                }                

                // Explore all neighbours of the current cell
                ICollection<IGridCell> neighbours = map.GetNeighbourCells(current.Cell);

                foreach (IGridCell cell in neighbours)
                {
                    // discard nodes that are not of interest
                    if (closed.Contains(cell) || (cell.Matches(end) == false && !cell.IsWalkable))
                    {
                        continue;
                    }

                    // successor is one of current's neighbours
                    PathNode successor = new PathNode(current, cell, end);                    
                    PathNode contained = open.Find(successor);
                    
                    if (contained != null && successor.F >= contained.F)
                    {
                        // This cell is already in the open list represented by
                        // another node that is cheaper
                        continue;
                    }                    
                    else if (contained != null && successor.F < contained.F)
                    {
                        // This cell is already in the open list but on a more expensive
                        // path -> "integrate" the node into the current path
                        contained.Predecessor = current;
                        contained.Update();
                        open.Update(contained);
                    }
                    else
                    {
                        // The cell is not in the open list and therefore still has to
                        // be explored
                        open.Enqueue(successor);
                    }
                }

                // add current to the list of the already explored nodes
                closed.AddLast(current.Cell);                

            } while (open.Peek() != null);

            return null;
        }
    }

Of course this algorithm also works for other purposes than XNA games. There is not even XNA specific code there, other than the DebugDisplay.DrawLine()-call which is one of my own classes.

The C# sourcecode can be downloaded here and contains the PriorityQueue implementation I used, as well.

Advertisements

14 replies »

  1. hi ! ziemlich coole sache mit den Interfaces !!!
    ich hab jetzt schon länger im internet nach ner simplen anleitung gesucht, wie ich einen A* Algorithmus implementieren kann und dein code is ist von allem was ich bisher so gesehen am leichtesten nachzuvollziehen (was mich trotzdem noch ne weile kosten wird^^)
    auf jeden fall hab ich den algorithmus mal in meine 2D tile engine implementiert.
    Findet auch einen Pfad, allerdings nicht den optimalsten.
    hab von einer situation nen screenshot von auf rapidshare hochgeladen (hab da die wegpunkte zwischen spieler und monster eingezeichnet, wie er sie momentan berechnet) .

    Wär super cool wenn du mir vieleicht nen tip geben könntest woran das liegt (ist ja vieleicht was ganz simples)
    ansonsten kein stress, bin nicht böse wenn du mir nicht antwortest 😉

    Auf alle fälle viel spass und erfolg bei deinem projekt ! 🙂

  2. Hallo Christopher!

    Danke für dein positives Feedback. 🙂

    Ich habe mal deine Situation in meiner Testanwendung (die ich vielleicht bei Gelegenheit auch mal als Beispiel hochladen sollte) nachgestellt: http://cid-ea731786481cbb8e.office.live.com/self.aspx/XNA/Pfadfindung.png

    Ich benutze bis auf zwei kleine Änderungen exakt dieselbe Implementierung, wie sie im Post steht. In der Version im Post wird beim Überschreiten der Schrittgrenze einfach der aktuelle Pfad zurückgegeben. Das hat sich aber als ungünstig erwiesen, weil es eigentlich keinen Sinn macht einen unfertigen (d.h. falschen) Pfad zurückzuliefern. Daher breche ich in meiner aktuellen Version in diesem Fall ab und gebe null zurück (ich werde den Blogpost dahingehend aktualisieren). Aber das dürfte ja für deinen Fall nicht von Relevanz sein, da du ja einen Pfad findest. Andererseits ist das vielleicht doch Teil des Problems, auch wenn es auf den ersten Blick unwahrscheinlich erscheint.

    Füge mal bitte an den Anfang der do-while-Schleife in Pathfinder folgende Zeile ein:
    if (++steps > stepLimit) return null;

    Wenn du dann eine Null-Pointer-Exception bekommst, sehen wir weiter.

    Die zweite Änderung, die ich gemacht habe, ist die Berechnung der Distanz. Das könnte wohlmöglich auch bei dir das Problem beheben. Die Manhatten-Distanz ist nicht ganz akkurat und kann überschätzen, ist dafür aber schneller zu berechnen. Versuche einfach mal die Distanzberechnung in PathNode.Update zur normalen euklidischen Distanz zu ändern:
    //h = 10 * (Math.Abs(cell.X - goal.X) + Math.Abs(cell.Y - goal.Y)); // <- vorher
    h = (float)Math.Sqrt((cell.X - goal.X) * (cell.X - goal.X) + (cell.Y - goal.Y) * (cell.Y - goal.Y));

    Das würde eben ganz normal c = Wurzel aus (a^2 + b^2) entsprechen und liefert die exakte Distanz.
    Versuch das bitte mal aus, vielleicht behebt diese Änderung das Problem schon.

    Ansonsten: Bist du dir sicher, dass der Pfad so aussieht, wie du ihn eingezeichnet hast? Wenn das wirklich der Fall sein sollte, dann ist vielleicht irgendwo ein Fehler bei deiner Implementierung von IGridCell oder IGridMap?

    • Ich bin gerade über diesen Beitrag gestolpert als ich mein Wissen über Pathfinding wieder auffrischen wollte und will nur zur sehr gelungenen Umsetzung des A* gratulieren, besser und praxisnäher kann man das fast nicht mehr machen.

      Ich hätte zum obigen Beitrag nur noch eine kleine Verbesserung vorzuschlagen welche häufig vergessen wird: nimmt man die euklidische Distanz (Wurzel[a^2+b^2]) kann man auf die Menge der Berechnungen noch einiges an Rechenzeit sparen wenn man die quadratische Distanz direkt vergleicht statt zuvor die Wurzel zu ziehen.

  3. Hi Mathias ! Wow sehr flotte und umfangreiche Antwort (sogar nachgemapt). Vielen Dank für deine Hilfe!
    Du hast vollkommen Recht. Ich bekomme eine NullRefernceException wenn ich in der ersten Zeile des Anweisungsblock des If Statements in der do-while Schleife “return null” einfüge 🙂
    Ich habs auch mit deiner euklidischen Formel für die Distanzberechnung versucht.
    Leider ohne Erfolg (ich bekomme genau den selben pfad).

    Meine Interface Implementierung habe ich mehrmals mit dem Debugger gecheckt und kann auch dort keine Fehler erkennen.
    Bei gegebener MapTile-Koordinaten bekommt er in der GetNeighbourCells-Funktion immer die 8 angrenzenden Tiles und giebt sie als Collection (referenziert eine LinkedList) zurück.
    Unbegehbare Tiles erkennt er auch (isWalkable == false).

    Allerdings sind mir noch ein paar Dinge aufgefallen.
    Ich habe das Gewicht der Tiles immer auf 0 gesetzt (der Konstruktor der Tiles inizialisiert jedes Tile mit 0). Das funktioniert (zumindest findet er den spieler^^).
    Jetzt habe ich die mal mit einem höheren Wert inizialisiert und siehe da ich bekomme irgendwo beim Pfadauslesen (abhängig vom gewicht) eine NullReferenceException:

    [Code]
    public IGridCell GetNextWaypoint()
    {
    PathNode next = current;
    current = current.Predecessor; // Hier: NullReferenceException
    return next.Cell;
    }
    [\Code]

    zum schluss zeig ich mal wie ich den Pfad auslese 😉

    [Code]
    Pathfinder p = new Pathfinder(map, 10000);
    Path path = p.CalculatePath(monster.MapPosition, player.MapPosition, false);

    IGridCell a = path.GetNextWaypoint(); //13 13 Monster Start
    IGridCell b = path.GetNextWaypoint(); //12 12
    IGridCell c = path.GetNextWaypoint(); //11 11
    IGridCell d = path.GetNextWaypoint(); //10 10
    IGridCell e = path.GetNextWaypoint(); //9 9
    IGridCell f = path.GetNextWaypoint(); //8 8
    IGridCell g = path.GetNextWaypoint(); //9 7
    IGridCell h = path.GetNextWaypoint(); //10 7
    IGridCell i = path.GetNextWaypoint(); //11 7
    IGridCell j = path.GetNextWaypoint(); //12 7 Player (ein Tile davor)

    [\Code]

    die boolsche Variable “Finished” (in Path) ist wenn der Debugger nicht lügt übrigens bei jedem Test bisher immer “false”.

    Das ist alles was ich bisher gefunden habe.
    Nochmals vielen Dank für deine Hife ! 🙂

  4. Hast du auch daran gedacht die andere Abfrage, in der “steps” erhöht wird zu entfernen? Also ursprünglich stand ja in der Zeile unter dem Kommentar “// Finish?” (Zeile 380 oben) auch noch in der if-Bedingung
    || steps++ > stepLimit.
    Diesen Teil musst du entfernen.

    Was die NullReferenceException angeht, die du erhalten hast: Das ist wohl schlechtes Design von mir, müsste ich wohl verbessern. Aber die Eigenschaft “Finished” ist in der aktuellen Version genau dafür da:


    while (!path.Finished)
    {
    IGridCell waypoint = path.GetNextWaypoint();
    }

    “Finished” ist genau dann wahr, wenn “current” null ist, d.h. der Pfad am Ende angelangt ist.
    Wenn man dann GetNextWaypoint() aufruft bekommt man die NullReferenceException.

    Ansonsten könntest du vielleicht ja mal versuchen die Gewichte der Tiles auf den Bildschirm zu zeichnen, also G und H bzw. deren Summe, also F in jedes Tile schreiben. A* nimmt immer die Zelle mit dem niedrigsten Gewicht (G+H). D.h. wenn er den Pfad so nimmt, wie er bei dir aussieht, dann sollten die Gewichte das wiederspiegeln. Ansonsten ist da noch irgendwo ein Bug in der Implementierung meinerseits. Aber ich habe solche Probleme noch nicht feststellen können. Hast du auch mal ein paar andere Konstellationen von Positionen etc. durchprobiert?

  5. Ich hatte tatsächlich vergessen die steps aus der “Kombi-Boolschen-Abfrage) rauszulöschen.
    (Danke für den Tip)
    Habs behoben aber leider keine Veränderungen am Pfad.
    Okay, das mit dem Finish ist mir jetzt ein wenig peinlich (hätt ich selber drauf kommen müssen^^) …das mit der schleife funktioniert natürlich (zum debuggen ist das mit den einzelnen IGridCell Variablen aber ganz angenehm) 😉
    ich werd mal wie du meinst für jedes Tile F Berechnen (brauch ich ja nur die Distanz auszulesen, denn Gewicht habe ich ja bei jedem Tile mit 0 inizialisiert.

    Ich geb dir auf alle Fälle bescheid wenns klappt ! 🙂
    (vermute langsam doch, dass ich bei der Implementierung der Interfaces irgendwo irgenwas vergessen habe. Denk nicht dass das ein Bug ist aber wenn, dann hättest du wenigstens was von meiner dummen Fragerei ^^ )

  6. Danke, ich hoffe du bekommst es noch hin. Wenn das Ganze nicht sofort funktioniert, heißt das ja in jedem Fall auch für meine Implementierung, dass sie nicht ganz einfach zu benutzen zu sein scheint, wenn man so viel “falsch” machen kann, dass nicht der optimale Pfad gefunden wird. Würde mich also sehr freuen zu hören, wenn du es hinbekommen hast und woran es gelegen hat.

  7. Hmmm meine GetNeighbourCells Funktion hat Probleme mit der Berechnung des Pfades an den äußeren Berechen der map (wenn ich z.B 4 Tiles vor dem linken Ende der map bin stürzt das Programm ab (weil path als null referenziert wird)
    Ich habe die Randbereiche außen vor gelassen und bin davon ausgegangen, dass jedes Tile auf der Map 8 umliegende Tiles hat (was aussen ja nicht gilt) ^^;

    Ich bin mir jetzt allerdings nicht sicher inwie weit sich das auf meine Beispiele Auswirkt, die sich alle relativ im Zentrum der Map abspielen.
    Meinst du das kann solche Auswirkungen auf die Pfadfindung haben ?

    Ansonsten mach ich das mal mit dem F für jedes Tile.

    PS:
    Hab jetzt noch ein paar weitere Tests (mit komplizierteren Abständen) gemacht.
    Also das Ziel findet er immer, aber manchmal springt der waypoint auch 2 Tiles
    (hab nochmal ein Bild hochgeladen..ist ganz witzig wie der die Knoten wählt ^^)

  8. Sorry hab deinen letzten Post übersehen.
    Also dein Code ist meiner Meinng nach super zu implementieren.
    (mir war vorher nie so wirklich klar wozu Interaces zu gebrauchen sind ^^)
    Mir fehlt einfach ne menge Programmierübung.
    Ich werd mir morgen nochmal die Schnittstellen anschauen…besonders die GetNeighbourCells (die ja an den Mapgrenzen noch Probleme bereitet)

    Vielen Dank für die Zeit die du dir genommen hast ! 🙂
    (Ich hoffe mal es klappt wenn ich mich das nächste mal melde)

    Mit welchen herausforderungen hast du zur Zeit an deinem Projekt zu kämpfen.
    Kommst du vorwärts ?

  9. Die Methode GetNeighbourCells ist schon wichtig, d.h. sie muss schon korrekt funktionieren. Aber dass du ungültige Zellen außerhalb des Rasters nicht beachtet hast, dürfte nicht das Problem sein, solange die Suche innerhalb des gültigen Bereiches bleibt (z.B. indem der äußere Rand durch unbegehbare Zellen gefüllt ist).

    Ist schon sehr seltsam, wie der Pfad bei dir aussieht. Ich kann es mir aber auch gerade nicht wirklich erklären, wie das zustande kommt. Ich werde bei Gelegenheit mal versuchen ein einfaches 2D-Beispielprogramm zu schreiben und gucken, ob ich da ähnliche Probleme bekomme, wenn ich die Interfaces noch mal “from scratch” beispielhaft implementiere.

    In den letzten Wochen kam das Projekt nicht viel weiter vorwärts, weil ich gerade in der Klausurphase bin (Universität). Aber morgen schreibe ich die letzte Klausur, dann habe ich an sich wieder Zeit. Allerdings beginne ich dann mit meiner Bachelorarbeit. Thema wird wohl GPU-beschleunigte Skinned-Mesh-Animation in Verbindung mit Hardware-Instancing zur performanten Darstellung vieler animierter Einheiten sein (was ich so direkt für mein Projekt verwenden können werde).

    Aber die größte Herausforderung an dem Projekt (RTS) ist eigentlich tatsächlich die Wegfindung. Denn allein mit einer funktionierenden A-Stern-Implementierung ist es noch nicht getan. Außerdem müssen die Einheiten Kollisionen vermeiden und sich einigermaßen vorausschauend bewegen. Das Hauptproblem bei der Sache ist, dass A* für viele Einheiten gleichzeitig einfach viel zu zeitaufwendig ist (bei einem großen Grid). Daher muss man Wege finden möglichst effizient die Wege zu planen. Das ist, glaube ich, aktuell die größte Herausforderung. Das Rendern und Animieren der Einheiten, Effekte usw. sind eigentlich relativ simpel, da man da nicht all zu viel nachdenken muss. ^^

    Ich glaube man kann das allgemein darauf ausweiten, dass die Künstliche Intelligenz der Einheiten das Schwierigste wird, für mich persönlich. Aber zu diesem Zweck habe ich mir nun auch eigens das Buch “Programming Game AI by Example” von Mat Buckland besorgt. Mal gucken, was ich damit erreichen kann. 🙂

  10. JUHU !!!
    Problem gelöst..das Problem muss daran gelegen, dass ich keine Gewichte inizilisiert habe
    Hab bei deinem Interface IGridCell das Property “weight” um eine set Methode erweitert.
    Dann habe ich in der GetNeighbourCells Methode die Diagonalen Tiles auf weight 14 gesetzt und die horizontalen / vertiklen auf 10 🙂
    jetzt scheints zu lufen…werd morgen trotzdem nochml ausgiebiger testen, bin jetzt endgültig zu müde..wollte das aber irgendwie noch hinbekommen ! ^^

  11. Dankeschön !
    also funktioniert soweit bis auf ein paar Macken. Bevorzugt manchmal immer noch Diagonale Tiles aber Die Strecken sind jetzt ziemlich gerade.
    Hauptproblem ist jetzt den pfad in echtzeit berechnen zu lassen (dachte es würde reichen, den jeden Frame einfach neu berechnen zu lassen und die durchwanderten Knoten einfach aus der Liste zu kicken aber das läuft wohl doch nicht soo einfach wie gedacht 😀
    Naja muss wohl bis nach den Klausuren (auch bei mir) warten.
    Wie lief eigentlich deine gestrige Klausur ?
    Freu mich auf weitere Updates zu deinem Spiel !

    • Ja, der A*-Algorithmus eignet sich nicht unbedingt dafür mehrmals pro Sekunde ausgeführt zu werden, vor allem nicht bei großen Grids. Ich persönlich mache es so, dass sich die Einheiten ein mal am Anfang einen (möglicherweise zwischengespeicherten) Pfad holen und den solange verfolgen bis sie auf ein Hinderniss stoßen. Erst dann wird ein neuer Pfad berechnet, und der möglichst auch nur zur Umgehung des Hindernisses, d.h. vom aktuellen Standpunkt bis zum nächsten unblockierten Punkt auf dem eigentlichen Pfad.

      Meine Klausur lief gut, danke. ^^ Wünsche dir auch Glück bei deinen.

      Sobald ich wieder Fortschritte zu verzeichnen habe, werde ich den Blog aktualisieren. 🙂
      Als nächstes ist erst mal die Implementierung einer eigenen Model-Klasse für XNA geplant, mit der ich dann die hardware-beschleunigte Skinned-Mesh-Animation umsetzen kann.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Bunkerbewohner1

Error: Twitter did not respond. Please wait a few minutes and refresh this page.

My Del.icio.us

%d bloggers like this: