Home > Business > Practical Application for Artificial Intelligence: AI Searches

Practical Application for Artificial Intelligence: AI Searches

/
04 Mar 2023
/
0 Comment
, , ,

Program Code

To develop an AI search algorithm to discover a path inside a maze utilizing Java, we would require seven Java packages.

  1. AbstractSearchEngine.java
  2. BreadthFirstSearchEngine.java
  3. DepthFirstSearchEngine.java
  4. Location.java
  5. Maze.java
  6. MazeBreadthFirstSearch.java
  7. MazeDepthFirstSearch.java

Since BreadthFirstSearchEngine.java and DepthFirstSearchEngine.java have some frequent code an summary class was created, AbstractSearchEngine.java, which might be inherited by each of the lessons. Maze.java is used to outline the maze and house wherein we are going to work. It accommodates numbers to inform us in regards to the beginning location and the ending location. MazeBreadthFirstSearch.java and MazeDepthFirstSearch.java inherit BreadthFirstSearchEngine.java and DepthFirstSearchEngine.java respectively. Location.java helps in finding the place within the maze.

Right here is the code for every of them:

AbstractSearchEngine.java

//For two-D Maze Search
package deal search.maze;
public class AbstractSearchEngine {
public AbstractSearchEngine(int width, int top) {
 maze = new Maze(width, top);
 initSearch();
}
public Maze getMaze() { return maze; }
protected Maze maze;
//Use Java kind Location for the search path
//Fields width and top will encode the coordinates in x and y instructions
 protected Location searchPath = null;
 protected int pathCount;
 protected int maxDepth;
 protected Location startLoc, goalLoc, currentLoc;
 protected boolean isSearching = true;
 protected void initSearch() {
 if (searchPath == null) {
  searchPath = new Location[1000];
  for (int i=0; i<1000; i++) {
   searchPath[i] = new Location();
}
}
 pathCount = 0;
 startLoc = maze.startLoc;
 currentLoc = startLoc;
 goalLoc = maze.goalLoc;
 searchPath[pathCount++] = currentLoc;
}
 protected boolean equals(Location d1, Location d2) {
 return d1.x == d2.x && d1.y == d2.y;
}
public Location getPath() {
 Location ret = new Location[maxDepth];
 for (int i=0; i  ret[i] = searchPath[i];
}
 return ret;
}
protected Location getPossibleMoves(Location loc) {
 Location tempMoves = new Location[4];
 tempMoves[0] = tempMoves[1] = tempMoves[2] = tempMoves[3] = null;
 int x = loc.x;
 int y = loc.y;
 int num = 0;
 if (maze.getValue(x – 1, y) == 0 || maze.getValue(x – 1, y) == Maze.GOAL_LOC_VALUE) {
  tempMoves[num++] = new Location(x – 1, y);
}
 if (maze.getValue(x + 1, y) == 0 || maze.getValue(x + 1, y) == Maze.GOAL_LOC_VALUE) {
  tempMoves[num++] = new Location(x + 1, y);
}
 if (maze.getValue(x, y – 1) == 0 || maze.getValue(x, y – 1) == Maze.GOAL_LOC_VALUE) {
  tempMoves[num++] = new Location(x, y – 1);
}
 if (maze.getValue(x, y + 1) == 0 || maze.getValue(x, y + 1) == Maze.GOAL_LOC_VALUE) {
  tempMoves[num++] = new Location(x, y + 1);
}
 return tempMoves;
}
}

BreadthFirstSearchEngine.java

//For two-D Maze Search
package deal search.maze;
public class BreadthFirstSearchEngine extends AbstractSearchEngine {
public BreadthFirstSearchEngine(int width, int top) {
 tremendous(width, top);
 doSearchOn2DGrid();
}
personal void doSearchOn2DGrid() {
 int width = maze.getWidth();
 int top = maze.getHeight();
 boolean alReadyVisitedFlag = new boolean[width][height];
 Location predecessor = new Location[width][height];
 LocationQueue queue = new LocationQueue();
 for (int i=0; i  for (int j=0; j   alReadyVisitedFlag[i][j] = false;
   //distanceToNode[i][j] = 10000000.0f;
   predecessor[i][j] = null;
}
}
 alReadyVisitedFlag[startLoc.x][startLoc.y] = true;
 queue.addToBackOfQueue(startLoc);
 boolean success = false;
 outer:
 whereas (queue.isEmpty() == false) {
  Location head = queue.peekAtFrontOfQueue();
  if (head == null) break; // ??
  Location linked = getPossibleMoves(head);
  for (int i=0; i<4; i++) {
   if (linked[i] == null) break;
   int w = linked[i].x;
   int h = linked[i].y;
   if (alReadyVisitedFlag[w][h] == false) {
    alReadyVisitedFlag[w][h] = true;
    predecessor[w][h] = head;
    queue.addToBackOfQueue(linked[i]);
    if (equals(linked[i], goalLoc)) {
     success = true;
     break outer; // we’re completed
}
}
}
  queue.removeFromFrontOfQueue(); // ignore return worth
}
// now calculate the shortest path from the predecessor array:
 maxDepth = 0;
 if (success) {
  searchPath[maxDepth++] = goalLoc;
  for (int i=0; i<100; i++) {
   searchPath[maxDepth] = predecessor[searchPath[maxDepth – 1].x][searchPath[maxDepth – 1].y];
   maxDepth++;
   if (equals(searchPath[maxDepth – 1], startLoc)) break; // again to beginning node
}
}
}
protected class LocationQueue {
public LocationQueue(int num) {
 queue = new Location[num];
 head = tail = 0;
 len = num;
}
public LocationQueue() {
 this(400);
}
public void addToBackOfQueue(Location n) {
 queue[tail] = n;
 if (tail >= (len – 1)) {
  tail = 0;
 } else {
  tail++;
}
}
public Location removeFromFrontOfQueue() {
 Location ret = queue[head];
 if (head >= (len – 1)) {
  head = 0;
 } else {
  head++;
}
 return ret;
}
public boolean isEmpty() {
 return head == (tail + 1);
}
public Location peekAtFrontOfQueue() {
 return queue[head];
}
personal Location queue;
 personal int tail, head, len;
}
}

DepthFirstSearchEngine.java

//For two-D Maze Search
package deal search.maze;
public class DepthFirstSearchEngine extends AbstractSearchEngine {
public DepthFirstSearchEngine(int width, int top) {
 tremendous(width, top);
 iterateSearch(startLoc, 1);
}
personal void iterateSearch(Location loc, int depth) {
 if (isSearching == false) return;
 maze.setValue(loc.x, loc.y, (quick)depth);
 Location strikes = getPossibleMoves(loc);
 for (int i=0; i<4; i++) {
  if (strikes[i] == null) break; // out of attainable strikes from this location
  searchPath[depth] = strikes[i];
  if (equals(strikes[i], goalLoc)) {
   System.out.println(‘Discovered the objective at ‘ + strikes[i].x +
‘, ‘ + strikes[i].y);
   isSearching = false;
   maxDepth = depth;
   return;
  } else {
   iterateSearch(strikes[i], depth + 1);
   if (isSearching == false) return;
}
}
  return;
}
}

Location.java

package deal search.maze;
public class Location {
 int x, y;
 public Location(int x, int y) { this.x = x; this.y = y; }
public Location() {
}
}

Maze.java

//Class Maze represents the search house as a two-dimensional maze
package deal search.maze;
public class Maze {
 public static quick OBSTACLE = -1;
 public static quick START_LOC_VALUE = -2;
 public static quick GOAL_LOC_VALUE = -3;
 personal int width = 0;
 personal int top = 0;
 public Location startLoc = new Location();
 public Location goalLoc = new Location();
//The maze (or search house) information is saved as a brief integer moderately than as a boolean
//Breadth-first type searches can use the array to retailer search depth.
//A price of -1 signifies a barrier within the maze.
 personal quick maze;
public Maze(int width, int top) {
 System.out.println(‘New maze of measurement ‘ + width + ‘ by ‘ + top);
 this.width = width;
 this.top = top;
 maze = new quick[width+2][height+2];
 for (int i=0; i  for (int j=0; j   maze[i][j] = 0;
}
}
 for (int i=0; i  maze[0][i] = maze[width+1][i] = OBSTACLE;
}
 for (int i=0; i  maze[i][0] = maze[i][height+1] = OBSTACLE;
}
//Randomize the maze by placing up arbitrary obstacles
 int max_obstacles = (width * top) / 3;
 for (int i=0; i  int x = (int)(Math.random()*width);
  int y = (int)(Math.random()*top);
  setValue(x, y, OBSTACLE);
}
//Specify the beginning location
 startLoc.x = 0;
 startLoc.y = 0;
 setValue(0, 0, (quick)0);
//Specify the objective location
 goalLoc.x = width – 1;
 goalLoc.y = top – 1;
 setValue(width – 1, top – 1, GOAL_LOC_VALUE);
}
synchronized public quick getValue(int x, int y) { return maze[x+1][y+1]; }
synchronized public void setValue(int x, int y, quick worth) { maze[x+1][y+1] = worth; }
public int getWidth() { return width; }
public int getHeight() { return top; }
}

MazeBreadthFirstSearch.java

//2D Maze Search: Performs a breadth first search in a maze.
package deal search.maze;
import javax.swing.*;
import java.awt.*;
import java.awt.picture.BufferedImage;
public class MazeBreadthFirstSearch extends javax.swing.JFrame {
 JPanel jPanel1 = new JPanel();
 BreadthFirstSearchEngine currentSearchEngine = null;
public MazeBreadthFirstSearch() {
 attempt {
  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 top = maze.getHeight();
 System.out.println(‘Measurement of present maze: ‘ + width + ‘ by ‘ + top);
 Graphics g = jPanel1.getGraphics();
 BufferedImage picture = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
 Graphics g2 = picture.getGraphics();
 g2.setColor(Shade.white);
 g2.fillRect(0, 0, 320, 320);
 g2.setColor(Shade.black);
 maze.setValue(0, 0, Maze.START_LOC_VALUE);
 for (int x=0; x  for (int y=0; y   quick val = maze.getValue(x,y);
   if ( val == Maze.OBSTACLE) {
    g2.setColor(Shade.lightGray);
    g2.fillRect(6 + x * 29, 3 + y * 29, 29, 29);
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
   } else if (val == Maze.START_LOC_VALUE) {
    g2.setColor(Shade.blue);
    g2.drawString(‘S’, 16 + x * 29, 19 + y * 29);
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
   } else if (val == Maze.GOAL_LOC_VALUE) {
    g2.setColor(Shade.pink);
    g2.drawString(‘G’, 16 + x * 29, 19 + y * 29);
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
   } else {
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
}
}
}
// redraw the trail in black:
 g2.setColor(Shade.black);
 Location path = currentSearchEngine.getPath();
 for (int i=1; i< (path.length-1); i++) {
  int x = path[i].x;
  int y = path[i].y;
  quick val = maze.getValue(x,y);
  g2.drawString(” + (path.size – i), 16 + x * 29, 19 + y * 29);
}
 g.drawImage(picture, 30, 40, 320, 320, null);
}
public static void principal(String args) {
 new MazeBreadthFirstSearch();
}
personal void jbInit() throws Exception {
 this.setContentPane(jPanel1);
 this.setCursor(null);
 this.setDefaultCloseOperation(3);
 this.setTitle(‘MazeBreadthFirstSearch’);
 this.getContentPane().setLayout(null);
 jPanel1.setBackground(Shade.white);
 jPanel1.setDebugGraphicsOptions(DebugGraphics.NONE_OPTION);
 jPanel1.setDoubleBuffered(false);
 jPanel1.setRequestFocusEnabled(false);
 jPanel1.setLayout(null);
 this.setSize(370, 420);
 this.setVisible(true);
}
}

MazeDepthFirstSearch.java

//2D Maze Search: Performs a depth first search in a maze.
package deal search.maze;
import javax.swing.*;
import java.awt.*;
import java.awt.picture.BufferedImage;
public class MazeDepthFirstSearch extends javax.swing.JFrame {
 JPanel jPanel1 = new JPanel();
 DepthFirstSearchEngine currentSearchEngine = null;
public MazeDepthFirstSearch() {
 attempt {
  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 top = maze.getHeight();
 System.out.println(‘Measurement of present maze: ‘ + width + ‘ by ‘ + top);
 Graphics g = jPanel1.getGraphics();
 BufferedImage picture = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
 Graphics g2 = picture.getGraphics();
 g2.setColor(Shade.white);
 g2.fillRect(0, 0, 320, 320);
 g2.setColor(Shade.black);
 for (int x=0; x  for (int y=0; y   quick val = maze.getValue(x,y);
   if ( val == Maze.OBSTACLE) {
    g2.setColor(Shade.lightGray);
    g2.fillRect(6 + x * 29, 3 + y * 29, 29, 29);
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
   } else if (val == Maze.START_LOC_VALUE || val == 1) {
    g2.setColor(Shade.blue);
    g2.drawString(‘S’, 16 + x * 29, 19 + y * 29);
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
   } else if (val == Maze.GOAL_LOC_VALUE) {
    g2.setColor(Shade.pink);
    g2.drawString(‘G’, 16 + x * 29, 19 + y * 29);
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
   } else {
    g2.setColor(Shade.black);
    g2.drawRect(6 + x * 29, 3 + y * 29, 29, 29);
}
}
}
// redraw the trail in black:
 g2.setColor(Shade.black);
 Location path = currentSearchEngine.getPath();
 for (int i=1; i< path.size; i++) {
  int x = path[i].x;
  int y = path[i].y;
  quick val = maze.getValue(x,y);
  g2.drawString(” + val, 16 + x * 28, 19 + y * 29);
}
 g.drawImage(picture, 30, 40, 320, 320, null);
}
public static void principal(String args) {
 new MazeDepthFirstSearch();
}
personal void jbInit() throws Exception {
 this.setContentPane(jPanel1);
 this.setCursor(null);
 this.setDefaultCloseOperation(3);
 this.setTitle(‘MazeDepthFirstSearch’);
 this.getContentPane().setLayout(null);
 jPanel1.setBackground(Shade.white);
 jPanel1.setDebugGraphicsOptions(DebugGraphics.NONE_OPTION);
 jPanel1.setDoubleBuffered(false);
 jPanel1.setRequestFocusEnabled(false);
 jPanel1.setLayout(null);
 this.setSize(370, 420);
 this.setVisible(true);
}
}

Code Software

To run and take a look at the above packages, open your command immediate and kind the next instructions:

javac AbstractSearchEngine.java

javac BreadthFirstSearchEngine.java

javac DepthFirstSearchEngine.java

javac Location.java

javac Maze.java

javac MazeBreadthFirstSearch.java

javac MazeDepthFirstSearch.java

java MazeDepthFirstSearch

java MazeBreadthFirstSearch

Observe-Up Questions

Now that you’ve compiled and run this program, you may respect the strategies of AI searches. For extra observe,

  1. Attempt forming an answer to discovering paths in a graph.
  2. Differentiate between BFS and DFS with respect to backtracking.
  3. Remedy the issue for shortest path within the maze.

Reply Key

  1. This query is similar to the one which we simply solved right here. A graph, as you understand, consists of nodes and hyperlinks or edges. The algorithms to seek out paths in graph are just like what we simply mentioned on this lesson with a minor distinction. Within the maze, we transfer from one grid house to a different provided that that house was empty. Within the graph drawback, we transfer from one node to the subsequent solely when a hyperlink is current between them.
  2. After we speak about backtracking, the primary picture that involves thoughts is the state house tree which gives all of the options for an issue. These house bushes may be created by two strategies: BFS and DFS. The key distinction between BFS and DFS lies within the formation of the house tree. Whereas BFS approach generates the house tree level-wise, DFS generates it from the basis node to the node the place the answer may lie.
  3. You may go for the branch-and-bound approach which provides you with the shortest path within the maze. Alternatively, you may view this drawback as an extension of the traveling-salesman drawback and resolve it.

Supply

About Post Author

Leave a Reply