etwas komplexeres Sortieren

[Janoscharlipp]

Hallo,

ich bin grade an einem PathFinder (s. OOP-Board), und will die Laufrichtungen erstmal sortieren. Ich habe es wie folgt mit einer Funktion für array.sort(funktion); versucht:

pathFinder = new Object();
pathFinder.directions = [];
pathFinder.directions[1] = {x:0,y:-1};
pathFinder.directions[2] = {x:1,y:0};
pathFinder.directions[3] = {x:0,y:1};
pathFinder.directions[4] = {x:-1,y:0};
pathFinder.x1 = 100;
pathFinder.x2 = 100;
pathFinder.y1 = 100;
pathFinder.y2 = 300;
 
a = [1,2,3,4];
 
sortDir = function(a,b){
    trace(a+""+b);
    var pf = pathFinder;
    var pfd = pf.directions;
    var x = pf.x2-pf.x1;
    var y = pf.y2-pf.y1;
    var xd = (x>0)?(1):((x<0)?(-1):(0));
    var yd = (y>0)?(1):((y<0)?(-1):(0));
    
    var axd = Math.abs(xd - pfd[a].x);
    var ayd = Math.abs(yd - pfd[a].y);
    var bxd = Math.abs(xd - pfd[b].x);
    var byd = Math.abs(yd - pfd[b].y);
    var aw = axd*axd+ayd*ayd;
    var bw = bxd*bxd+byd*byd;
    
    if(aw > bw)return 1;
    else if(bw > aw)return -1;
    else return 0;
}
t=getTimer();
trace(a.sort(sortDir).join());
trace(getTimer()-t); 

//Ausgabe:

14
13
12
11
24
24
23
23
23
24
3,2,4,1
37

war mir sorgen macht, ist, dass das ganze 37ms braucht, wenn ich das oft machen muss, ist es viel zu langsam.

Habt ihr ne Ahnung wie ich das schneller machen kann?

[bokel]

Das Math.abs kannst du schon mal rausnehmen, das wird durch das anschliessende Quadrieren sowieso positiv.

Was für Werte können denn pfd[a].x annehmen ?

mfg r

[Janoscharlipp]

stimmt, das quadrieren habe ich erst später eingeführt, um die Unterschiede zwischen "falsche x und falsche y Richtung (falsch = 0 statt 1 oder 1 statt 0)" und "ganz falsche x oder ganz falsche y Richtung (ganz falsch = -1 statt 1 oder 1 statt -1)" herzustellen.

pfd[a].x ist oben definiert, es kann -1,0,1 sein.

[Janoscharlipp]

so, habe ich mal aufgeräumt. Der größte Fehler war, das ganze als eine Ergänzung zur sort-Funktion anzulegen, denn so wurde es sehr oft aufgerufen, tat aber immer einiges gleich. hier ne neue Version, braucht nur noch ca. 1/8 der Zeit für das gleiche Ergebnis:

sortDir = function(){
    var pf = pathFinder;
    var pfd = pf.directions;
    var x = pf.x2-pf.x1;
    var y = pf.y2-pf.y1;
    var xdir = (x>0)?(1):/**/((x<0)?(-1):/**/(0));
    var ydir = (y>0)?(1):/**/((y<0)?(-1):/**/(0));
    var dir = [],ndir = [];
    var xd,yd,w;
    
    for(var i=0; i<4; i++){
        xd = xdir - pfd[i].x;
        yd = ydir - pfd[i].y;
        w = xd*xd+yd*yd;
        dir.push({i:i,w:w});
    }
    dir.sortOn("w");
    for(i in dir){
        ndir[i] = dir[i].i;
    }
    return ndir;
}
 
t=getTimer();
bla = sortDir();
trace(getTimer()-t);
trace(bla);