?
Solved

A star algorithm implementation for java

Posted on 2009-02-08
3
Medium Priority
?
12,112 Views
Last Modified: 2013-12-26
Does anybody has a A star Algorythm implentation example for java ?
0
Comment
Question by:Tageteg
  • 2
3 Comments
 
LVL 85

Expert Comment

by:ozo
ID: 23583335
0
 

Accepted Solution

by:
kdoto earned 375 total points
ID: 23609161
http://www.geocities.com/jheyesjones/astar.html

Java A* Algorithm
=================
 
// -*- mode: java; folded-file: t -*-
/*
 * Author Geert-Jan van Opdorp
 *
 * Copyright (c) 1995 AI Engineering.
 *
 */
package aie.astar;
// {{{ import
 
import java.awt.*;
import java.awt.image.*;
import java.net.*;
import java.applet.*;
import java.lang.*;
import java.util.*;
 
// }}}
 
// {{{ final class node
 
final class node {
  State state;
  int costs;
  int distance;
  int total;
  node parent;
  node(State theState, node theParent,  int theCosts, int theDistance) {
    state = theState;
    parent = theParent;
    costs = theCosts;
    distance = theDistance;
    total = theCosts + theDistance;
  };
}
 
// }}}
// {{{ public final class AStar
 
public final class AStar {
  // {{{ Variables
 
  private final  Hashtable open = new Hashtable(500);
  private final  Hashtable closed = new Hashtable(500);
  public int evaluated = 0;
  public  int expanded = 0;
  public int bestTotal = 0;
  public boolean ready = false;
  private  boolean newBest = false;
  private final  Vector nodes = new Vector(); //sorted open node
 
  // }}}
 
  private  synchronized void setBest (int value) {
    bestTotal = value;
    newBest = true;
    notify(); // All?
    Thread.currentThread().yield();  //for getNewBest
  }
 
  public  synchronized int getNewBest() {
    while(!newBest) {
      try {
      wait();
      } catch (InterruptedException e) {
      }
    }
    newBest = false;
    return bestTotal;
  }
  
// {{{ private  node search()
 
  private  node search() {
    node best;
    Vector childStates;
    int childCosts;
    Vector children = new Vector();
    
    while (!(nodes.isEmpty())) {
      best = (node) nodes.firstElement();
       if(closed.get(best.state) != null) { //to avoid having to remove
       nodes.removeElementAt(0);          // improved nodes from nodes
       continue;
       }
      if (!(best.total == bestTotal)) {
        setBest(best.total);
      }
      if ((best.state).goalp()) return best;
 
      children.removeAllElements();
      childStates = (best.state).generateChildren();
      childCosts = 1 + best.costs;
      expanded++;
 
      for (int i = 0; i < childStates.size(); i++) {
      State childState = (State) childStates.elementAt(i);
      node closedNode = null;
      node openNode = null;
      node theNode = null;
 
      if ((closedNode = (node) closed.get(childState)) == null)
        openNode = (node) open.get(childState);
      theNode = (openNode != null) ? openNode : closedNode;
      if (theNode != null) {
        if (childCosts < theNode.costs) {
          if (closedNode != null) {        
            open.put(childState, theNode);
            closed.remove(childState);
          } else {
            int dist = theNode.distance;
            theNode = new node(childState, best, childCosts, dist);
            open.put(childState, theNode);
             //nodes.removeElement(theNode); //get rid of this
          }
          theNode.costs = childCosts;
          theNode.total = theNode.costs + theNode.distance;
          theNode.parent = best;
          children.addElement(theNode);
          
        }
      } else {
        int estimation;
        node newNode;
 
        estimation = childState.estimate();
        newNode = new node(childState, best, childCosts, estimation);
        open.put(childState, newNode);
        evaluated++;
        children.addElement(newNode);
      }
      }
      open.remove(best.state);
      closed.put(best.state, best);
      nodes.removeElementAt(0);
      addToNodes(children); // update nodes
      
    }
    return null; //no open nodes and no solution
  }
 
// }}}
 
  private int rbsearch(int l, int h, int tot, int costs){
    if(l>h) return l; //insert before l
    int cur = (l+h)/2;
    int ot = ((node) nodes.elementAt(cur)).total;
    if((tot < ot) ||
       (tot == ot && costs >= ((node) nodes.elementAt(cur)).costs))
      return rbsearch(l, cur-1, tot, costs);
    return rbsearch(cur+1, h, tot, costs);
  }
 
  private int bsearch(int l, int h, int tot, int costs){
    int lo = l;
    int hi = h;
    while(lo<=hi) {
      int cur = (lo+hi)/2;
      int ot = ((node) nodes.elementAt(cur)).total;
      if((tot < ot) ||
       (tot == ot && costs >= ((node) nodes.elementAt(cur)).costs))
      hi = cur - 1;
      else
      lo = cur + 1;
    }
    return lo; //insert before lo
  }
      
 
// {{{ private  void addToNodes(Vector children)
 
  private  void addToNodes(Vector children) {
    for (int i = 0; i < children.size(); i++) {
      node newNode = (node) children.elementAt(i);
      int newTotal = newNode.total;
      int newCosts = newNode.costs;
      boolean done = false;
      int idx = bsearch(0, nodes.size()-1, newTotal, newCosts);
      nodes.insertElementAt(newNode, idx);
    
//       for (int j = 0; j < nodes.size(); j++) {
//       int ot = ((node) nodes.elementAt(j)).total;
//       if (newTotal <  ot) {
//         nodes.insertElementAt(newNode, j);
//         done = true;
//         break;
//       }
//       if (newTotal == ot) {
//         if (newNode.costs >= ((node) nodes.elementAt(j)).costs) {
//           nodes.insertElementAt(newNode, j);
//           done = true;
//           break;
//         }}
//       }
//       if (!done) nodes.addElement(newNode);
    }
  }
 
// }}}
// {{{ public final  Vector solve (State initialState)
 
  public final  Vector solve (State initialState) {
    node solution;
    node firstNode;
    int estimation;
    
    expanded = 0;
    evaluated = 1;
    estimation = initialState.estimate();
    firstNode = new node(initialState, null, 0, estimation);
 
    open.put(initialState, firstNode);
    nodes.addElement(firstNode);
 
    solution = search();
    nodes.removeAllElements();
    open.clear();
    closed.clear();
    ready = true;
    setBest(bestTotal);
    return getSequence(solution);
  }
 
// }}}
// {{{ private  Vector getSequence(node n)
 
  private  Vector getSequence(node n) {
    Vector result;
    if (n == null) {
      result = new Vector();
    } else {
      result = getSequence (n.parent);
      result.addElement(n.state);
    }
    return result;
  }
 
// }}}
}
 
// }}}
 
State package
=============
 
// -*- mode: java; folded-file: t -*-
package aie.astar;
import java.util.Vector;
// {{{ abstract class state
 
public abstract class State {
  public abstract Vector generateChildren();
  public abstract boolean goalp();
  public abstract int estimate();
}
 
// }}}

Open in new window

0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
This video shows how to quickly and easily deploy an email signature for all users in Office 365 and prevent it from being added to replies and forwards. (the resulting signature is applied on the server level in Exchange Online) The email signat…
How can you see what you are working on when you want to see it while you to save a copy? Add a "Save As" icon to the Quick Access Toolbar, or QAT. That way, when you save a copy of a query, form, report, or other object you are modifying, you…
Suggested Courses

612 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question