carfield.com.hk

AbstractGraphSearch.java

2002-01-20T16:00:00Z

import java.util.Vector;

abstract public class AbstractGraphSearch {

public void addNode(String name, int x, int y) {
	System.out.println("Adding node: " + name + ", " + x + ", " + y);
	nodeNames[numNodes] = name;
	node_x[numNodes] = x;
	node_y[numNodes] = y;
	numNodes++;
    }

public int getNumNodes() { return numNodes; }
    public int getNumLinks() { return numLinks; }

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 int getNodeX(int index) {
	try {
	    return node_x[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodePosition: " + e);
	}
	return 0;  // error condition
    }

public int getNodeY(int index) {
	try {
	    return node_y[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodePosition: " + e);
	}
	return 0;  // error condition
    }

public int getLink1(int index) {
      return link_1[index];
    }

public int getLink2(int index) {
      return link_2[index];
    }

public void addLink(int node1, int node2) {
	link_1[numLinks] = node1;
	link_2[numLinks] = node2;
	int 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] = (int)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 start_node, int goal_node); // 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

protected int [] path = new int[AbstractGraphSearch.MAX];
    protected int num_path = 0;

// for nodes:
    protected String [] nodeNames = new String[MAX];
    protected int [] node_x = new int[MAX];
    protected int [] node_y = new int[MAX];
    // for links between nodes:
    protected int [] link_1 = new int[MAX];
    protected int [] link_2 = new int[MAX];
    protected int [] lengths = new int[MAX];

protected int numNodes = 0;
    protected int numLinks = 0;

protected int goalNodeIndex = -1, startNodeIndex = -1;

}

BreadthFirstSearch.java

2002-01-20T16:00:00Z

public class BreadthFirstSearch extends AbstractGraphSearch {

/** findPath - abstract method in super class */
    public int [] findPath(int start_node, int goal_node) { // return an array of node indices
	System.out.println("Entered BreadthFirstSearch.findPath(" +
			   start_node + ", " + goal_node + ")");
	// data structures for depth first search:
	boolean [] alreadyVisitedFlag = new boolean[numNodes];
	int [] predecessor = new int[numNodes];
	IntQueue queue = new IntQueue(numNodes + 2);

for (int i=0; i<numNodes; i++) {
	 alreadyVisitedFlag[i] = false;
	 predecessor[i] = -1;
	}

alreadyVisitedFlag[start_node] = true;
	queue.addToBackOfQueue(start_node);
outer:	while (queue.isEmpty() == false) {
	 int head = queue.peekAtFrontOfQueue();
	 int [] connected = connected_nodes(head);
	 if (connected != null) {
		for (int i=0; i<connected.length; i++) {
		 if (alreadyVisitedFlag[connected[i]] == false) {
			predecessor[connected[i]] = head;
			queue.addToBackOfQueue(connected[i]);
			if (connected[i] == goal_node) break outer; // we are done
		 }
		}
		alreadyVisitedFlag[head] = true;
		queue.removeFromQueue(); // ignore return value
	 }
	}
	// now calculate the shortest path from the predecessor array:
	int [] ret = new int[numNodes + 1];
	int count = 0;
	ret[count++] = goal_node;
	for (int i=0; i<numNodes; i++) {
	 ret[count] = predecessor[ret[count - 1]];
	 count++;
	 if (ret[count - 1] == start_node) break; // back to starting node
	}
	int [] ret2 = new int[count];
	for (int i=0; i<count; i++) {
	 ret2[i] = ret[count - 1 - i];
	}
	return ret2;
 }

protected class IntQueue {
	public IntQueue(int num) {
	    queue = new int[num];
	    head = tail = 0;
	    len = num;
	}
	public IntQueue() {
	    this(400);
	}
	private int [] queue;
	int tail, head, len;
	public void addToBackOfQueue(int n) {
	    queue[tail] = n;
	    if (tail >= (len - 1)) {
		tail = 0;
	    } else {
		tail++;
	    }
	}
	public int removeFromQueue() {
	    int ret = queue[head];
	    if (head >= (len - 1)) {
		head = 0;
	    } else {
		head++;
	    }
	    return ret;
	}
	public boolean isEmpty() {
	    return head == (tail + 1);
	}
	public int peekAtFrontOfQueue() {
	    return queue[head];
	}
    }

protected int [] connected_nodes(int node) {
	int [] ret = new int[AbstractGraphSearch.MAX];
	int num = 0;

for (int n=0; n<numNodes; n++) {
	 boolean connected = false;
	 // See if there is a link between node 'node' and 'n':
	 for (int i=0; i<numLinks; i++) {
		if (link_1[i] == node) {
		 if (link_2[i] == n) {
			connected = true;
			break;
		 }
		}
		if (link_2[i] == node) {
		 if (link_1[i] == n) {
			connected = true;
			break;
		 }
		}
	 }
	 if (connected) {
		ret[num++] = n;
	 }
	}
	if (num == 0) return null;
	int [] ret2 = new int[num];
	for (int i=0; i<num; i++) {
	 ret2[i] = ret[i];
	}
	return ret2;
 }

}

DepthFirstSearch.java

2002-01-20T16:00:00Z

public class DepthFirstSearch extends AbstractGraphSearch {

/** findPath - abstract method in super class */
    public int [] findPath(int start_node, int goal_node) { // return an array of node indices
        System.out.println("Entered DepthFirstSearch.findPath(" +
                           start_node + ", " + goal_node + ")");
        path[0] = start_node;
        return findPathHelper(path, 1, goal_node);
    }

public int [] findPathHelper(int [] path, int num_path, int goal_node) {
 System.out.println("Entered DepthFirstSearch.findPathHelper(...," +
 num_path + ", " + goal_node + ")");
 if (goal_node == path[num_path - 1]) {
 int [] ret = new int[num_path];
 for (int i=0; i<num_path; i++) ret[i] = path[i];
 return ret; // we are done!
 }
 int [] new_nodes = connected_nodes(path, num_path);
 if (new_nodes != null) {
 for (int j=0; j<new_nodes.length; j++) {
 path[num_path] = new_nodes[j];
 int [] test = findPathHelper(path, num_path + 1, goal_node);
 if (test != null) {
 if (test[test.length - 1] == goal_node) {
 return test;
 }
 }
 }
 }
 return null;
 }

protected int [] connected_nodes(int [] path, int num_path) {
 // find all nodes connected to the last node on 'path'
 // that are not already on 'path'
 int [] ret = new int[AbstractGraphSearch.MAX];
 int num = 0;
 int last_node = path[num_path - 1];
 for (int n=0; n<numNodes; n++) {
 // see if node 'n' is already on 'path':
 boolean keep = true;
 for (int i=0; i<num_path; i++) {
 if (n == path[i]) {
 keep = false;
 break;
 }
 }
 boolean connected = false;
 if (keep) {
 // now see if there is a link between node 'last_node' and 'n':
 for (int i=0; i<numLinks; i++) {
 if (link_1[i] == last_node) {
 if (link_2[i] == n) {
 connected = true;
 break;
 }
 }
 if (link_2[i] == last_node) {
 if (link_1[i] == n) {
 connected = true;
 break;
 }
 }
 }
 if (connected) {
 ret[num++] = n;
 }
 }
 }
 if (num == 0) return null;
 int [] ret2 = new int[num];
 for (int i=0; i<num; i++) {
 ret2[i] = ret[i];
 }
 return ret2;
 }

}

GraphBreadthFirstSearch.java

2002-01-20T16:00:00Z

import javax.swing.*;
import java.awt.*;

public class GraphBreadthFirstSearch extends JFrame {
  JPanel jPanel1 = new JPanel();

public GraphBreadthFirstSearch() {
    BreadthFirstSearch engine = new BreadthFirstSearch();
	  // Define a test network before calling the super class 'init':
	  engine.addNode("0", 20, 40);
	  engine.addNode("1", 60, 60);
	  engine.addNode("2", 100, 40);
	  engine.addNode("3", 50, 110);
	  engine.addNode("4", 140, 80);
	  engine.addNode("5", 160, 150);
	  engine.addNode("6", 200, 80);
	  engine.addNode("7", 160, 40);
	  engine.addNode("8", 240, 120);
	  engine.addNode("9", 260, 90);

engine.addLink(0,1);
	 engine.addLink(1,2);
	 engine.addLink(2,3);
	 engine.addLink(2,4);
	 engine.addLink(4,5);
	 engine.addLink(4,6);
	 engine.addLink(6,8);
	 engine.addLink(8,9);
	 engine.addLink(2,7);
	 engine.addLink(7,9);
 System.out.println("Before calculating path");
 path = engine.findPath(0, 9);
 System.out.println("After calculating path:");
 for (int i=0; i<path.length; i++) {
 System.out.println(" node # " + path[i]);
 }
 this.engine = engine;
 try {
 jbInit();
 }
 catch(Exception e) {
 e.printStackTrace();
 }
 }
 private int [] path = null;
 private BreadthFirstSearch engine = null;

public static void main(String[] args) {
    GraphBreadthFirstSearch graphBreadthFirstSearch1 = new GraphBreadthFirstSearch();
  }

private void jbInit() throws Exception {
    this.setDefaultCloseOperation(3);
    jPanel1.setBackground(Color.white);
    this.getContentPane().add(jPanel1, BorderLayout.CENTER);
    this.setSize(290, 180);
    this.setVisible(true);
  }
    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);
	if (engine != null && path != null) {
 int numNodes = engine.getNumNodes();
 int numLinks = engine.getNumLinks();
 for (int i=0; i<numLinks; i++) {
 int l1 = engine.getLink1(i);
 int l2 = engine.getLink2(i);
 int x1 = engine.getNodeX(l1);
 int y1 = engine.getNodeY(l1);
 int x2 = engine.getNodeX(l2);
 int y2 = engine.getNodeY(l2);
 g.setColor(Color.lightGray);
 g.drawLine(x1, y1, x2, y2);
 }
 for (int i=1; i<path.length; i++) {
 int x1 = engine.getNodeX(path[i-1]);
 int y1 = engine.getNodeY(path[i-1]);
 int x2 = engine.getNodeX(path[i]);
 int y2 = engine.getNodeY(path[i]);
 g.setColor(Color.black);
 g.drawLine(x1, y1, x2, y2);
 }
 for (int i=0; i<numNodes; i++) {
 int x1 = engine.getNodeX(i);
 int y1 = engine.getNodeY(i);
 paintNode(g, engine.getNodeName(i), x1, y1);
 }
 }
 }

}

GraphDepthFirstSearch.java

2002-01-20T16:00:00Z

import javax.swing.*;
import java.awt.*;

public class GraphDepthFirstSearch extends JFrame {
  JPanel jPanel1 = new JPanel();

public GraphDepthFirstSearch() {
    DepthFirstSearch engine = new DepthFirstSearch();
	  // Define a test network before calling the super class 'init':
	  engine.addNode("0", 20, 40);
	  engine.addNode("1", 60, 60);
	  engine.addNode("2", 100, 40);
	  engine.addNode("3", 50, 110);
	  engine.addNode("4", 140, 80);
	  engine.addNode("5", 160, 150);
	  engine.addNode("6", 200, 80);
	  engine.addNode("7", 160, 40);
	  engine.addNode("8", 240, 120);
	  engine.addNode("9", 260, 90);

public static void main(String[] args) {
    GraphDepthFirstSearch graphDepthFirstSearch1 = new GraphDepthFirstSearch();
  }

}

Maze.java

2002-01-19T16:00:00Z

import java.awt.Dimension;

/**
 * Class Maze - private class for representing search space as a two-dimensional maze
 */
public class Maze {
 public static short OBSTICLE = -1;
 public static short START_LOC_VALUE = -2;
 public static short GOAL_LOC_VALUE = -3;
 private int width = 0;
 private int height = 0;
 public Dimension startLoc = new Dimension();
 public Dimension goalLoc = new Dimension();
 /**
 * The maze (or search space) data is stored as a short integer rather than
 * as a boolean so that bread-first style searches can use the array to store
 * search depth. A value of -1 indicates a barrier in the maze.
 */
 private short [][]maze;
 public Maze(int width, int height) {
 System.out.println("New maze of size " + width + " by " + height);
 this.width = width;
 this.height = height;
 maze = new short[width+2][height+2];
 for (int i=0; i<width+2; i++) {
 for (int j=0; j<height+2; j++) {
 maze[i][j] = 0;
 }
 }
 for (int i=0; i<height+2; i++) {
 maze[0][i] = maze[width+1][i] = OBSTICLE;
 }
 for (int i=0; i<width+2; i++) {
 maze[i][0] = maze[i][height+1] = OBSTICLE;
 }
 /**
 * Randomize the maze by putting up arbitray obsticals
 */
 int max_obsticles = (width * height) / 3;
 for (int i=0; i<max_obsticles; i++) {
 int x = (int)(Math.random()*width);
 int y = (int)(Math.random()*height);
 setValue(x, y, OBSTICLE);
 }
 /**
 * Specify the starting location
 */
 startLoc.width = 0;
 startLoc.height = 0;
 setValue(0, 0, (short)0);
 /**
 * Specify the goal location
 */
 goalLoc.width = width - 1;
 goalLoc.height = height - 1;
 setValue(width - 1, height - 1, GOAL_LOC_VALUE);
 }
 synchronized public short getValue(int x, int y) { return maze[x+1][y+1]; }
 synchronized public void setValue(int x, int y, short value) { maze[x+1][y+1] = value; }
 public int getWidth() { return width; }
 public int getHeight() { return height; }
}

MazeBreadthFirstSearch.java

2002-01-19T16:00:00Z

import javax.swing.*;
import java.awt.*;
import java.awt.image.*;
import java.awt.event.*;
/**
 * Title: MazeBreadthFirstSearch
 * Description: Demo program for Java AI Programming
 * Copyright: Copyright (c) Mark Watson, Released under Open Source Artistic License
 * Company: Mark Watson Associates
 * @author Mark Watson
 * @version 1.0
 */

public class MazeBreadthFirstSearch extends javax.swing.JFrame {
    JPanel jPanel1 = new JPanel();
    BreadthFirstSearchEngine currentSearchEngine = null;

public MazeBreadthFirstSearch() {
        try {
          jbInit();
        } catch (Exception e) {
          System.out.println("GUI initilization error: " + e);
        }
        currentSearchEngine = new BreadthFirstSearchEngine(10, 10);
        repaint();
    }

public void paint(Graphics g_unused) {
 if (currentSearchEngine == null) return;
 Maze maze = currentSearchEngine.getMaze();
 int width = maze.getWidth();
 int height = maze.getHeight();
 System.out.println("Size of current maze: " + width + " by " + height);
 Graphics g = jPanel1.getGraphics();
 BufferedImage image = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
 Graphics g2 = image.getGraphics();
 g2.setColor(Color.white);
 g2.fillRect(0, 0, 320, 320);
 g2.setColor(Color.black);
 for (int x=0; x<width; x++) {
 for (int y=0; y<height; y++) {
 short val = maze.getValue(x,y);
 if ( val == Maze.OBSTICLE) {
 g2.setColor(Color.lightGray);
 g2.fillRect(6 + x * 28, 3 + y * 29, 29, 30);
 } else if (val == Maze.START_LOC_VALUE || (x==0 && y==0)) {
 g2.setColor(Color.blue);
 g2.drawString("S", 16 + x * 28, 19 + y * 29);
 } else if (val == Maze.GOAL_LOC_VALUE) {
 g2.setColor(Color.red);
 g2.drawString("G", 16 + x * 28, 19 + y * 29);
 }
 }
 }
 // redraw the path in black:
 g2.setColor(Color.black);
 Dimension [] path = currentSearchEngine.getPath();
 for (int i=1; i< (path.length-1); i++) {
 int x = path[i].width;
 int y = path[i].height;
 short val = maze.getValue(x,y);
 g2.drawString("" + (path.length - i), 16 + x * 28, 19 + y * 29);
 }
 g.drawImage(image, 30, 40, 320, 320, null);

}

public static void main(String[] args) {
        MazeBreadthFirstSearch mazeSearch1 = new MazeBreadthFirstSearch();
    }

private void jbInit() throws Exception {

this.setContentPane(jPanel1);
        this.setCursor(null);
        this.setDefaultCloseOperation(3);
        this.setTitle("MazeBreadthFirstSearch");
        this.getContentPane().setLayout(null);
        jPanel1.setBackground(Color.white);
        jPanel1.setDebugGraphicsOptions(DebugGraphics.NONE_OPTION);
        jPanel1.setDoubleBuffered(false);
        jPanel1.setRequestFocusEnabled(false);
        jPanel1.setLayout(null);
        this.setSize(370, 420);
        this.setVisible(true);
    }
}

MazeDepthFirstSearch.java

2002-01-19T16:00:00Z

import javax.swing.*;
import java.awt.*;
import java.awt.image.*;
import java.awt.event.*;
/**
 * Title: MazeDepthFirstSearch
 * Description: Demo program for Java AI Programming
 * Copyright: Copyright (c) Mark Watson, Released under Open Source Artistic License
 * Company: Mark Watson Associates
 * @author Mark Watson
 * @version 1.0
 */

public class MazeDepthFirstSearch extends javax.swing.JFrame {
    JPanel jPanel1 = new JPanel();
    DepthFirstSearchEngine currentSearchEngine = null;

public MazeDepthFirstSearch() {
        try {
          jbInit();
        } catch (Exception e) {
          System.out.println("GUI initilization error: " + e);
        }
        currentSearchEngine = new DepthFirstSearchEngine(10, 10);
        repaint();
    }

public void paint(Graphics g_unused) {
 if (currentSearchEngine == null) return;
 Maze maze = currentSearchEngine.getMaze();
 int width = maze.getWidth();
 int height = maze.getHeight();
 System.out.println("Size of current maze: " + width + " by " + height);
 Graphics g = jPanel1.getGraphics();
 BufferedImage image = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
 Graphics g2 = image.getGraphics();
 g2.setColor(Color.white);
 g2.fillRect(0, 0, 320, 320);
 g2.setColor(Color.black);
 for (int x=0; x<width; x++) {
 for (int y=0; y<height; y++) {
 short val = maze.getValue(x,y);
 if ( val == Maze.OBSTICLE) {
 g2.setColor(Color.lightGray);
 g2.fillRect(6 + x * 28, 3 + y * 29, 29, 30);
 } else if (val == Maze.START_LOC_VALUE || val == 1) {
 g2.setColor(Color.blue);
 g2.drawString("S", 16 + x * 28, 19 + y * 29);
 } else if (val == Maze.GOAL_LOC_VALUE) {
 g2.setColor(Color.red);
 g2.drawString("G", 16 + x * 28, 19 + y * 29);
 } else if (val > 0) {
 //g2.setColor(Color.green);
 //g2.drawString("" + val, 16 + x * 28, 19 + y * 29);
 }
 }
 }
 // redraw the path in black:
 g2.setColor(Color.black);
 Dimension [] path = currentSearchEngine.getPath();
 for (int i=1; i< path.length; i++) {
 int x = path[i].width;
 int y = path[i].height;
 short val = maze.getValue(x,y);
 g2.drawString("" + val, 16 + x * 28, 19 + y * 29);
 }
 g.drawImage(image, 30, 40, 320, 320, null);

}

public static void main(String[] args) {
        MazeDepthFirstSearch mazeSearch1 = new MazeDepthFirstSearch();
    }

private void jbInit() throws Exception {

this.setContentPane(jPanel1);
        this.setCursor(null);
        this.setDefaultCloseOperation(3);
        this.setTitle("MazeDepthFirstSearch");
        this.getContentPane().setLayout(null);
        jPanel1.setBackground(Color.white);
        jPanel1.setDebugGraphicsOptions(DebugGraphics.NONE_OPTION);
        jPanel1.setDoubleBuffered(false);
        jPanel1.setRequestFocusEnabled(false);
        jPanel1.setLayout(null);
        this.setSize(370, 420);
        this.setVisible(true);
    }
}