<![CDATA[// SearchApplet.java
//
// This class is an abstract class for defining search
// algorithm classes.
//
// Copyright Mark Watson, 1998. Open Source and Open Content.
//
import java.awt.*;
import java.awt.event.*;
import java.util.Vector;
abstract public class SearchApplet extends java.applet.Applet {
public void init() {
String width = getParameter("pwidth");
if (width == null) {
xSizePixels = 80;
} else {
xSizePixels = Integer.valueOf(width).intValue();
}
String height = getParameter("pheight");
if (height == null) {
ySizePixels = 80;
} else {
ySizePixels = Integer.valueOf(height).intValue();
}
System.out.println("width=" + xSizePixels + ", height=" + ySizePixels);
setLayout(null);
startChoice = new Choice();
goalChoice = new Choice();
for (int i=0; i<numNodes; i++) {
startChoice.add(nodeNames[i]);
goalChoice.add(nodeNames[i]);
}
startChoice.select(0);
goalChoice.select(numNodes - 1);
Label l1 = new Label("Starting node:");
Label l2 = new Label("Goal node:");
l1.setBounds(5, 10, 90, 24);
startChoice.setBounds(100, 10, 50, 30);
l2.setBounds(5, 50, 90, 24);
goalChoice.setBounds(100, 50, 50, 30);
timeDelayChoice = new Choice();
timeDelayChoice.add("No plot time delay");
timeDelayChoice.add("Plot time delay");
timeDelayChoice.setBounds(160, 10, 90, 24);
timeDelayChoice.select(1);
add(l1); add(l2); add(startChoice); add(goalChoice); add(timeDelayChoice);
Button b = new Button("Run");
b.setBounds(160, 50, 90, 32);
add(b);
b.addMouseListener(new java.awt.event.MouseAdapter()
{
public void mouseClicked(MouseEvent me) {
int i1 = startChoice.getSelectedIndex();
int i2 = goalChoice.getSelectedIndex();
startNodeIndex = i1;
goalNodeIndex = i2;
System.out.println("mouse clicked " + i1 + " " + i2);
findPath(i1, i2);
}
}
);
canvas = new Canvas();
//Panel pp = new Panel();
add(canvas);
canvas.setBounds(5, 80, xSizePixels + 20, ySizePixels + 20);
add(canvas);
repaintPath(null, 0);
setBackground(Color.white);
}
protected Choice startChoice, goalChoice, timeDelayChoice;
private Canvas canvas;
private int goalNodeIndex = -1, startNodeIndex = -1;
public void repaintPath(int [] path, int num) {
System.out.print("repaintPath(");
boolean time_delay = timeDelayChoice.getSelectedIndex() == 1;
for (int i=0; i<num; i++) {
System.out.print(path[i]);
if (i < (num - 1)) System.out.print(", ");
}
System.out.println(")");
Graphics g = canvas.getGraphics();
g.setColor(Color.black);
float x_scale = (float)xSizePixels / (x_max - x_min);
float y_scale = (float)ySizePixels / (y_max - y_min);
// start by plotting nodes and links:
for (int i=0; i<numLinks; i++) {
int i1 = link_1[i];
int i2 = link_2[i];
int x1 = (int)(node_x[i1] * x_scale);
int x2 = (int)(node_x[i2] * x_scale);
int y1 = (int)(node_y[i1] * y_scale);
int y2 = (int)(node_y[i2] * y_scale);
g.drawLine(x1 + 10, y1 + 10, x2 + 10, y2 + 10);
g.drawLine(x1 + 10, y1 + 11, x2 + 10, y2 + 11);
}
for (int i=0; i<numNodes; i++) {
int x1 = (int)(node_x[i] * x_scale);
int y1 = (int)(node_y[i] * y_scale);
if (i == startNodeIndex) g.setColor(Color.green);
else if (i == goalNodeIndex) g.setColor(Color.blue);
else g.setColor(Color.black);
paintNode(g, nodeNames[i], x1 + 10, y1 + 10);
}
if (path == null) return;
// set line color to red:
g.setColor(Color.red);
for (int i=0; i<num - 1; i += 2) {
int x1 = (int)(node_x[path[i]] * x_scale);
int x2 = (int)(node_x[path[i+1]] * x_scale);
int y1 = (int)(node_y[path[i]] * y_scale);
int y2 = (int)(node_y[path[i+1]] * y_scale);
g.drawLine(x1 + 10, y1 + 10, x2 + 10, y2 + 10);
g.drawLine(x1 + 10, y1 + 11, x2 + 10, y2 + 11);
}
if (time_delay) {
try {
Thread.sleep(1000);
} catch (Exception e) { }
}
}
public void repaintPath(int [] path) {
repaintPath(path, path.length);
}
protected void paintNode(Graphics g, String name, int x, int y) {
int len = name.length() * 10 + 6;
int x1 = x - (len / 2);
int x2 = x + (len / 2);
int y1 = y - 10;
int y2 = y + 10;
g.setColor(Color.cyan);
g.fill3DRect(x1, y1, len, 20, true);
g.setColor(Color.black);
g.drawString(name, x1 + 4, y2 - 6);
}
public void paint(Graphics g) {
super.paint(g);
repaintPath(null, 0);
}
public void addNode(String name, float x, float y) {
System.out.println("Adding node: " + name + ", " + x + ", " + y);
nodeNames[numNodes] = name;
node_x[numNodes] = x;
node_y[numNodes] = y;
numNodes++;
if (x < x_min) x_min = x;
if (x > x_max) x_max = x;
if (y < y_min) y_min = y;
if (y > y_max) y_max = y;
}
public String getNodeName(int index) {
try {
return nodeNames[index];
} catch (Exception e) {
System.out.println("Error in getNodeName: " + e);
}
return "no name"; // error condition
}
public float getNodeX(int index) {
try {
return node_x[index];
} catch (Exception e) {
System.out.println("Error in getNodePosition: " + e);
}
return 0.0f; // error condition
}
public float getNodeY(int index) {
try {
return node_y[index];
} catch (Exception e) {
System.out.println("Error in getNodePosition: " + e);
}
return 0.0f; // error condition
}
public float getPathLength(int index) { // currently unsued - for adding heuristics
return lengths[index];
}
public void addLink(int node1, int node2) {
link_1[numLinks] = node1;
link_2[numLinks] = node2;
float dist_squared =
(node_x[node1] - node_x[node2]) * (node_x[node1] - node_x[node2]) +
(node_y[node1] - node_y[node2]) * (node_y[node1] - node_y[node2]);
lengths[numLinks] = (float)Math.sqrt(dist_squared);
numLinks++;
}
public void addLink(String name1, String name2) {
int index1 = -1, index2 = -1;
for (int i=0; i<numNodes; i++) {
if (name1.equals(nodeNames[i])) index1 = i;
if (name2.equals(nodeNames[i])) index2 = i;
}
if (index1 != -1 && index2 != -1) addLink(index1, index2);
}
/** findPath - abstract method that is defined in subclasses */
abstract public int [] findPath(int node_1, int node_2); // return an array of node indices
protected int getNodeIndex(String name) {
for (int i=0; i<numNodes; i++) {
if (name.equals(nodeNames[i])) return i;
}
return -1; // error condition
}
final public static int MAX = 50; // max number of nodes and max number of links
// for nodes:
private String [] nodeNames = new String[MAX];
private float [] node_x = new float[MAX];
private float [] node_y = new float[MAX];
// for links between nodes:
protected int [] link_1 = new int[MAX];
protected int [] link_2 = new int[MAX];
private float [] lengths = new float[MAX];
protected int numNodes = 0;
protected int numLinks = 0;
// For optional display of search progress:
private int xSizePixels = 0, ySizePixels = 0;
private float x_min = 0.0f, x_max = 0.1f;
private float y_min = 0.0f, y_max = 0.1f;
}
]]>
Back to main page