We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

# A star algorithm implementation for java

on
Medium Priority
13,217 Views
Does anybody has a A star Algorythm implentation example for java ?
Comment
Watch Question

## View Solution Only

CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:

Commented:
Commented:
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;
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?
}

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;

}
} else {
int estimation;
node newNode;

estimation = childState.estimate();
newNode = new node(childState, best, childCosts, estimation);
open.put(childState, newNode);
evaluated++;
}
}
open.remove(best.state);
closed.put(best.state, best);
nodes.removeElementAt(0);

}
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)

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;
//         }}
//       }
}
}

// }}}
// {{{ 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);

solution = search();
nodes.removeAllElements();
open.clear();
closed.clear();
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);
}
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();
}

// }}}
``````

Not the solution you were looking for? Getting a personalized solution is easy.

##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile