A* fuer Packman

[derDan]

Nachdem meine Idee den Packman Monstern KI zu verpassen belaechelt wurde, hab ich einem von ihnen zumindest mal den A* spendiert. Der naechste Schritt waere dann jedem der Agenten eine unterschiedliche Zelle als moegliches Spielerziel zuzuweisen (die naechsten Weggabeln halt). Vielleicht mach ich das irgendwann auch mal, hab nur grad echt keine Zeit mehr .

Na ja hier zumindest mal meine A* Implementierung,
vielleicht kann ja jemand von euch damit was anfangen.

PHP-Code:

class Astar {
    private var mcAgent:MovieClip;
    private var mcTarget:MovieClip;
    //
    //
    //
    private var arrOpen:Array;
    private var arrClose:Array;
    private var arrPath:Array;
    //
    //
    //
    private var actualCell:Cell;
    //
    //
    //
    function Astar(mcAgent, mcTarget) {
        this.mcAgent = mcAgent;
        this.mcTarget = mcTarget;
        //
        //
        //
        findNewTarget();
    }
    //
    //
    //
    function findNewTarget():Array {
        this.mcTarget = mcTarget;
        var tmpCell:Cell = new Cell(this.mcAgent._x/_root.cellWidth, this.mcAgent._y/_root.cellWidth);
        tmpCell.costG = 0;
        //
        //
        // underestimating H function
        tmpCell.costH = Math.floor(Math.sqrt(Math.pow((this.mcTarget._x/_root.cellWidth-tmpCell.coorX), 2)+Math.pow((this.mcTarget._y/_root.cellWidth-tmpCell.coorY), 2)));
        tmpCell.costT = tmpCell.costG+tmpCell.costH;
        tmpCell.parent = null;
        //
        //
        //
        this.arrOpen = new Array(tmpCell);
        this.arrClose = new Array();
        this.arrPath = new Array();
        //
        //
        //
        findPath();
        //
        //
        //
        return (this.arrPath);
    }
    //
    //
    //
    private function findPath():Void {
        var boolFound = false;
        while (this.arrOpen.length != 0) {
            if (this.arrOpen[0].coorX == this.mcTarget._x/_root.cellWidth && this.arrOpen[0].coorY == this.mcTarget._y/_root.cellWidth) {
                boolFound = true;
                break;
            } else {
                this.actualCell = this.arrOpen[0];
                this.arrClose[this.arrClose.length] = this.arrOpen.shift();
                addStar();
            }
        }
        //
        //
        //
        if (boolFound) {
            constructPath();
        }
    }
    //
    //
    //
    private function addStar() {
        checkCoor(this.actualCell.coorX, this.actualCell.coorY-1);
        checkCoor(this.actualCell.coorX+1, this.actualCell.coorY);
        checkCoor(this.actualCell.coorX, this.actualCell.coorY+1);
        checkCoor(this.actualCell.coorX-1, this.actualCell.coorY);
        sortArrays();
    }
    //
    //
    //
    function checkCoor(coorX:Number, coorY:Number) {
        //
        //
        // ueberpruefen ob die Koordinate ueberhaupt auf der Karte liegt und ob wir nicht gerade daher kommen        
        if (_root.map.hitTest(coorX*_root.cellWidth+_root.cellWidth/2, coorY*_root.cellWidth+_root.cellWidth/2, true) && !(coorX == this.actualCell.parent.coorX && coorY == this.actualCell.parent.coorY)) {
            addNewCell(coorX, coorY);
        }
    }
    //
    //
    //
    private function addNewCell(coorX:Number, coorY:Number) {
        //
        //
        // 
        var tmpCell:Cell = new Cell(coorX, coorY);
        tmpCell.costG = this.actualCell.costG+1;
        tmpCell.costH = Math.floor(Math.sqrt(Math.pow((this.mcTarget._x/_root.cellWidth-tmpCell.coorX), 2)+Math.pow((this.mcTarget._y/_root.cellWidth-tmpCell.coorY), 2)));
        tmpCell.costT = tmpCell.costG+tmpCell.costH;
        tmpCell.parent = this.actualCell;
        //
        //
        // pruefen, ob die Zelle schon einmal vorkam und wenn ja, ob wir einen schnelleren Weg zu ihr gefunden haben
        var boolFound:Boolean = false;
        for (var i = 0; i != this.arrClose.length; i++) {
            if (this.arrClose[i].coorX == tmpCell.coorX && this.arrClose[i].coorY == tmpCell.coorY) {
                if (this.arrClose[i].costG+this.arrClose[i].costH>tmpCell.costG+tmpCell.costH) {
                    this.arrOpen[this.arrOpen.length] = tmpCell;
                    this.arrClose.splice(i, 1);
                }
                boolFound = true;
            }
        }
        //
        //
        // pruefen, ob Zelle schon in der Open Liste steht und wenn ja, ob wir einen schnelleren Weg zu ihr gefunden haben
        if (!boolFound) {
            for (var i = 0; i != this.arrOpen.length; i++) {
                if (this.arrOpen[i].coorX == tmpCell.coorX && this.arrOpen[i].coorY == tmpCell.coorY) {
                    if (this.arrOpen[i].costG+this.arrOpen[i].costH>tmpCell.costG+tmpCell.costH) {
                        this.arrOpen[i] = tmpCell;
                    }
                    boolFound = true;
                }
            }
        }
        if (!boolFound) {
            this.arrOpen.unshift(tmpCell);
        }
    }
    //
    //
    //
    private function sortArrays() {
        //
        //
        // kuerzesten Weg in Open Liste an den Anfang sortieren
        this.arrOpen.sortOn("costT");
        this.arrClose.sortOn("costT", 2);
    }
    //
    //
    //
    private function constructPath() {
        var tmpCell:Cell = this.arrOpen[0];
        this.arrPath.unshift(tmpCell);
        //
        //
        // Parent Zellen in richtiger Reihenfolge sammeln
        while (tmpCell.parent != null) {
            this.arrPath.unshift(tmpCell.parent);
            tmpCell = tmpCell.parent;
        }
    }
} 


derDan

[nky]

thanx for inspiration !!!

Gruss nky

[[je]]

andre hat auch schon den a* für flash bekömmlich gemacht
deine variante gefällt mir auch ganz gut.

hier der link zu andre
http://www.andre-michelle.com/files/...n/+pathfinder/

[André Michelle]

Das sieht gut aus.
Ich fände es trotzdem besser, wenn man dem Konstruktor keine MovieClips übergibt, sondern Tilekoordinatenpaare als Objekt, oder gleich als Viererkette.
Denn die Umrechnung in Tilekoordinaten hat meiner Meinung nach in der Klasse AStar nichts zu suchen.

Trotzdem gut!

[derDan]

Macht Sinn. Frag mich warum ich das nicht schon so geloest hatte...

[André Michelle]

Beim nächstenmal. Ich finde immer wieder, dass man seine Klassen in sinnvollere kleinere Komponenten zerlegen kann, damit es sauberer wird und wiederverwendbarer.

Übrigens, ein AStar im Pacman ist wie eine Atombombe zu zünden, um eine Nuss zu öffnen, oder ? :o)

Das geht auch in Echtzeit ganz gut:
runtime pathfinder

[derDan]

Schon- aber kommt fett oder nicht?

[bokel]

Voll fett, würde ich sagen !
Ich schmeisse alle Daumen in die Luft und wer einen fängt, darf ihn behalten

mfg .r

[derDan]

Ich meinte die Atombombe kommt fett. Eigenlob stinkt!