A-Stern funktioniert nicht...

[DGL-luke]

Hallo,

mal wieder eine C#-Frage von mir.

Ich habe mir nach Anleitung von http://www.policyalmanac.org/games/a...torial_de.html aus einer A*-Klasse, die leider nicht funktionierte, selber was zusammengeschwartet... das allerdings nix findet, sprich endlos loopt.

Code:

   FStartNode = AStartNode;
   FGoalNode = AGoalNode;
   FOpenList.Add(FStartNode);  //FOpenList ist alway-sorted

        while (FOpenList.Count > 0)
            {
                // Move best node to closed list
                AStarNode NodeCurrent = (AStarNode)FOpenList.Pop();
                FClosedList.Add(NodeCurrent);

                // investigate Successors
                ArrayList ASuccessors = new ArrayList(4);
                NodeCurrent.GetSuccessors(ASuccessors);
                foreach (AStarNode NodeSuccessor in ASuccessors)
                {
                    //If Node is Goal, write path and leave
                    if (NodeSuccessor.IsSameState(FGoalNode))
                    {
                        FSolution.Clear();
                        AStarNode Node = NodeSuccessor;
                        while (Node != null)
                        {
                            FSolution.Insert(0, Node);
                            Node = Node.Parent;
                        }
                        FOpenList.Clear(); // to exit main loop
                        break;
                    }

                    //If Node in Closed List, we skip it
                    bool SkipNode = false;
                    foreach (AStarNode NodeClosed in FClosedList)
                    {
                        if (NodeClosed.IsSameState(NodeSuccessor))  //IsSameState überprüft, ob die Nodes den gleichen Ort haben
                        {
                            SkipNode = true;
                            break;
                        }
                    }
                    if (SkipNode)
                        continue;

                    //If Node in Open List and cost higher, change it, else skip it
                    AStarNode NodeOpen = null;
                    foreach (AStarNode N in FOpenList)
                    {
                        if (N.IsSameState(NodeSuccessor))
                            NodeOpen = N;
                    }
                    if (NodeOpen != null && NodeOpen.Cost > NodeSuccessor.Cost)
                        NodeOpen = NodeSuccessor;
                    else if (NodeOpen == null)
                    {
                        FOpenList.Add(NodeSuccessor);
                    }
                }
            }
      }

Wäre vielleicht jemand so nett, das mal anzusehen und mir zu sagen, ob ich da Fehler drin hab?

EDIT: hach, das funzt ja sogar :shock:
kaum lässt mans mal 10 Minuten laufen.... :lol:

[Airblader]

Das nenn ich mal Performance pur! :mrgreen:

[Alexander]

Hast du schon Luckies A-Stern Algo gesehen? Du kannst es ja mal mit dem von der Performance her vergleichen.

[Luckie]

Wie groß ist denn das Feld? Selbst bei einer Größe von 275x200 Feldern ist der bei mir ratz fatz fertig.

[DGL-luke]

Bei mir sind 200x200....

werd mir das mal ansehen.(was für ein zufall, dass ich den schon auf dem rechner hab :mrgreen: )

EDIT: Hui, also das ist ja sowas von optimiert, da blick ich nicht durch... vielleicht find ich ja im thread was...

EDIT: hab in einem neuen Thread eine neue frage gestellt: http://www.delphipraxis.net/internal...ct.php?t=72128
;)

[DGL-luke]

Sodele... Algo geändert. Er funktioniert auch, aber nicht immer... Das Ding hat bis gerade ganz schöne Kapriolen geschlagen, aber wie soll es auch anders, wenn ich ihm für Bloodstreams negative Kosten geb ;)
Die Kosten sollten jetzt alle stimmen, aber manchmal kommt er leer zurück:

Code:

FStartNode = AStartNode;
   FGoalNode = AGoalNode;
   FOpenList.Add(FStartNode);

        while (FOpenList.Count > 0)
            {
                // Get best node and move to closed list
                AStarNode NodeCurrent = (AStarNode)FOpenList.Pop();
                FClosedMatrix[((NetNode)NodeCurrent).Coords.X, ((NetNode)NodeCurrent).Coords.Y] = true;
                //FClosedList.Add(NodeCurrent);

                // investigate Successors
                ArrayList ASuccessors = new ArrayList(4);
                NodeCurrent.GetSuccessors(ASuccessors);
                foreach (AStarNode NodeSuccessor in ASuccessors)
                {
                    //If Node is Goal, write path and leave
                    if (NodeSuccessor.IsSameState(FGoalNode))
                    {
                        FSolution.Clear();
                        AStarNode Node = NodeSuccessor;
                        while (Node != null)
                        {
                            FSolution.Insert(0, Node);
                            Node = Node.Parent;
                        }
                        FOpenList.Clear(); // to exit main loop
                        break;
                    }

                    //If Node in Closed List, we skip it
                    /*bool SkipNode = false;
                    foreach (AStarNode NodeClosed in FClosedList)
                    {
                        if (NodeClosed.IsSameState(NodeSuccessor))
                        {
                            SkipNode = true;
                            break;
                        }
                    }
                    if (SkipNode)
                        continue;
                    */
                    /*if (FClosedList.Contains(NodeSuccessor))
                        continue;*/
                    if (FClosedMatrix[((NetNode)NodeSuccessor).Coords.X, ((NetNode)NodeSuccessor).Coords.Y])
                       continue;
                                        
                    //If Node in Open List and cost higher, change it, else skip it
                    AStarNode NodeOpen = null;
                    foreach (AStarNode N in FOpenList)
                    {
                        if (N.IsSameState(NodeSuccessor))
                            NodeOpen = N;
                    }
                    if (NodeOpen != null && NodeOpen.Cost > NodeSuccessor.Cost)
                        NodeOpen = NodeSuccessor;
                    else if (NodeOpen == null)
                    {
                        FOpenList.Add(NodeSuccessor);
                    }
                }
            }

Das ganze auskommentierte Zeug liegt daran, dass ich hier meine Closed-Liste ein wenig umgebaut habe(siehe Link in vorigem Post).
Fällt jemandem ein Fehler auf?

[DGL-luke]

Kann ja nicht funktionieren, wenn ich versuche, das Ding auflaufen zu lassen ;)

Findet jetzt seinen Weg überall hin (wo kein Hindernis ist) und braucht nur noch ein wenig Feintuning.