A* (A-star) Algorithmus Optimierung

Ich bin ein student und ich und mein team haben, um eine simulation des Schülers Verhalten in einem campus (wie "Freunde") gehen, etc. Für die Suche nach Pfad, der Schüler hat zu gehen, ich verwendete A* - Algorithmus (wie ich fand heraus, dass seine einer der am schnellsten Pfad zu finden-algorithmen). Leider ist unsere simulation läuft nicht flüssig (es dauert wie 1-2 Sek. zwischen aufeinander folgenden Iterationen). Ich wollte zu optimieren, den Algorithmus, aber ich habe keine Ahnung was ich mehr tun kann. Können Sie mir helfen, die Jungs und teilen Sie mit mir Informationen, wenn die Möglichkeit zur Optimierung meiner A* - Algorithmus? Hier geht code:

  public LinkedList<Field> getPath(Field start, Field exit) {


    LinkedList<Field> foundPath = new LinkedList<Field>();
    LinkedList<Field> opensList= new LinkedList<Field>();
    LinkedList<Field> closedList= new LinkedList<Field>();
    Hashtable<Field, Integer> gscore = new Hashtable<Field, Integer>();
    Hashtable<Field, Field> cameFrom = new Hashtable<Field, Field>();
    Field x = new Field();
    gscore.put(start, 0);
    opensList.add(start);
    while(!opensList.isEmpty()){

        int min = -1;
        //searching for minimal F score
        for(Field f : opensList){
            if(min==-1){
                min = gscore.get(f)+getH(f,exit);
                x = f;
            }else{
                int currf = gscore.get(f)+getH(f,exit);
                if(min > currf){
                    min = currf;
                    x = f;
                }
            }
        }
        if(x == exit){
            //path reconstruction
            Field curr = exit;
            while(curr != start){
                foundPath.addFirst(curr);
                curr = cameFrom.get(curr);
            }
            return foundPath;
        }
        opensList.remove(x);
        closedList.add(x);
        for(Field y : x.getNeighbourhood()){
            if(!(y.getType()==FieldTypes.PAVEMENT ||y.getType() == FieldTypes.GRASS) || closedList.contains(y) || !(y.getStudent()==null))
                            {
                continue;
            }
            int tentGScore = gscore.get(x) + getDist(x,y);
            boolean distIsBetter = false;
            if(!opensList.contains(y)){
                opensList.add(y);
                distIsBetter = true;
            }else if(tentGScore < gscore.get(y)){
                distIsBetter = true;
            }
            if(distIsBetter){
                cameFrom.put(y, x);
                gscore.put(y, tentGScore);
            }               
        }
    }

    return foundPath;
}

 private int getH(Field start, Field end){
    int x;
    int y;
    x = start.getX()-end.getX();
    y = start.getY() - end.getY();
    if(x<0){
        x = x* (-1);
    }
    if(y<0){
        y = y * (-1);
    }
    return x+y;
}
private int getDist(Field start, Field end){
    int ret = 0;
    if(end.getType() == FieldTypes.PAVEMENT){
        ret = 8;
    }else if(start.getX() == end.getX() || start.getY() == end.getY()){
        ret = 10;
    }else{
        ret = 14;
    }

    return ret;
}

//EDIT

Dies ist, was ich von jProfiler:

So getH ist ein bottlneck ja? Vielleicht erinnern H-score von-Feld wäre eine gute Idee?

InformationsquelleAutor Bartosz Wyględacz | 2014-01-16