[AS3] a* Wegfindung

[ING]

hab das kürzlich anhand der wiki seite nachgebaut und bin begeistert wie gut das funktioniert ist allerdings nur die halbe miete, dazu wird noch ein knoten system benötigt was sich aber jeder selbst, nach den eigenen bedürfnissen, erstellen sollte. die knoten klasse (hier PathNode) muss folgende eigenschaften und methoden besitzen:

• d : Number = der aktuelle wert des knotens (wird nur zum zwischenspeichern benötigt)
• p : PathNode = der vorige wegpunkt des knotens (wird nur zum zwischenspeichern benötigt)
• connected : Array = ein array mit den knoten die mit diesem knoten verbunden sind (ein Vector.<PathNode> macht sich natürlich auch gut)
• distance(otherNode) : Number = eine methode die die distanz zwischen dem aktuellen und dem angegebenen knoten zurück gibt.

public function aStar(_start:PathNode, _target:PathNode) : Boolean {
    var openList:Array = [], closedList:Array = [];
    var current:PathNode, successor:PathNode;
    var exist:Boolean, value:Number;
 
    openList.push(_start);
    _start.d = 0;
    
    while (openList.length) {
        openList.sortOn("d", Array.NUMERIC);
        current = PathNode(openList.shift());
        
        if (current == _target) return true;
        
        for each (successor in current.connected) {
            if (closedList.indexOf(successor) > -1) continue;
            
            value = current.d + current.distance(successor) + successor.distance(_target);
            exist = openList.indexOf(successor) > -1;
            
            if (exist && value > successor.d) continue;
            
            successor.p = current;
            successor.d = value;
            
            if (!exist) openList.push(successor);
        }
        
        closedList.push(current);
    }
    
    return false;
} 

findet die funktion einen pfad gibt sie true zurück, sonst false. der pfad kann dann rekonstruiert werden in dem man vom letzten knoten die p eigenschaften bis zum start abläuft. hier eine hilfsfunktion dazu...

// gibt ein array aus den wegpunkten zurück, beginnend bei _start
public function findPath(_start:PathNode, _target:PathNode) : Array {
    var node:PathNode, result:Array = [];
    
    if (aStar(_start, _target)) {
        node = _target;
        while (node != _start) {
            result.push(node);
            node = node.p;
        }
        result.push(_start);
        result.reverse();
    }
    
    return result;
} 

anbei noch ein screenshot und eine beispielanwendung, ihr könnt beliebig hindernisse auf die bühne zeichnen. die reine performace der wegfindung ist noch etwas schneller, in dem beispiel muss jedesmal noch die map neu berechnet werden, bei einer statischen karte fällt dieser schritt natürlich weg.
.

[DennisG]

das ist cool
könnte mir echt weiter helfen