You are required to write your own Java program to solve the problem. The proble

Question

You are required to write your own Java program to solve the problem. The problem is described as follows. Consider an idealization of a problem where a robot has to navigate its way around obstacles. The goal is to find the shortest distance between two points on a plane that has convex polygonal obstacles. Figure 2 shows an example scene with seven polygonal obstacles where the robot has to move from the point start to the point end. Convince yourself that the shortest path from one polygon vertex to any other in the scene consists of straight-line segments joining some of the vertices of the polygon. (Note that the start and the end goal points may be considered polygons of size 0). Implement an algorithm to find the shortest path from the start node to the end node using an A* (A-star) heuristic search. Use the straight-line distance to the end node as a heuristic function. Show your pseudo code for this algorithm and present the solutions for the following problem using the A* algorithm you implemented.

Polygon 1: ((220, 616), (220, 666), (251, 670), (272, 647))

Polygon 2: ((341, 655), (359, 667), (374, 651), (366, 577))

Polygon 3: ((311, 530), (311, 559), (339, 578), (361, 560), (361, 528), (336, 516))

Polygon 4: ((105, 628), (151, 670), (180, 629), (156, 577), (113, 587))

Polygon 5: ((118, 517), (245, 517), (245, 577), (118, 557))

Polygon 6: ((280, 583), (333, 583), (333, 665), (280, 665))

Polygon 7: ((252, 594), (290, 562), (264, 538))

Polygon 8: ((198, 635), (217, 574), (182, 574))

Start: (120, 650) End: (380, 560)

Figure 2

Note: This figure is for illustration purpose only. Positions of the polygons inside the figure may not reflect their actual coordinates.

You are required to write your own Java program to solve the problem. The problem is described as follows. Consider an idealization of a problem where a robot has to navigate its way around obstacles. The goal is to find the shortest distance between two points on a plane that has convex polygonal obstacles. Figure 2 shows an example scene with seven polygonal obstacles where the robot has to move from the point start to the point end. Convince yourself that the shortest path from one polygon vertex to any other in the scene consists of straight-line segments joining some of the vertices of the polygon. (Note that the start and the end goal points may be considered polygons of size 0). Implement an algorithm to find the shortest path from the start node to the end node using an A* (A-star) heuristic search. Use the straight-line distance to the end node as a heuristic function. Show your pseudo code for this algorithm and present the solutions for the following problem using th

Explanation / Answer

import java.awt.Graphics; import java.awt.Color; import java.awt.Point; /** * Represents simple simulated robots. These robots occupy rooms with walls and * tiled floors. Robots walk around on the floors (one tile at a time), changing * and sensing the colors of tiles if they wish. But robots can't move through * walls, thus they have to stay in their room. Robots can face in any of four * directions, which are described as compass directions in analogy to a map: * north is towards the top of the robot's room as drawn on a computer screen, * east is towards the right, etc. * @see geneseo.cs.sc.RobotRoom */ public class Robot { /** * The heading a robot has when facing north. */ public static final int NORTH = 0; /** * The heading a robot has when facing east. */ public static final int EAST = 1; /** * The heading a robot has when facing south. */ public static final int SOUTH = 2; /** * The heading a robot has when facing west. */ public static final int WEST = 3; // Internally, a robot records the room it is in, its row and column // coordinates (in tiles) within that room, its heading, whether // or not it is visible, and the amount of time it should delay // after movements: private RobotRoom room; private int row; private int col; private int direction; private boolean visible; private int delayTime; private static final int initialDelay = 500; // Number of milliseconds delay for new robots // Robots also have some data that they use to draw themselves: x and y offsets // of vertices of the robot relative to its center, and a color to draw it in // (see the comments for the "draw" method below for more details): private static final int[] xOffsets = { 0, -10, -5, -5, 5, 5, 10 }; private static final int[] yOffsets = { -10, 0, 0, 10, 10, 0, 0 }; private static final Color robotColor = new Color( (float)0.25, (float)0.0, (float)0.3 ); /** * Initialize a robot and a room for it to occupy. The room will be a default room, * and this robot will be its only occupant. The robot will have the default position * and heading (center of the room, facing north). For example *

Robot r = new Robot();

*/ public Robot() { room = new RobotRoom(); // A default room for this robot. col = room.getRoomWidth() / 2; row = room.getRoomHeight() / 2; direction = NORTH; visible = true; delayTime = initialDelay; room.addRobot( this, col, row ); } /** * Initialize a robot from its position, orientation, and room. For example *

Robot r = new Robot( 1, 3, Robot.NORTH, someRoom );

* @param col The horizontal coordinate of the tile this robot is on (i.e., the * tile column the robot is in). This must be within the range of columns * for the room the robot is in, and, with the row parameter, must specify * an unobstructed tile. * @param row The vertical coordinate of the tile this robot is on (i.e., the * tile row the robot is in). This must be within the range of rows for * the room the robot is in, and, with the column parameter, must specify * an unobstructed tile. * @param heading The robot's heading. This should be one of the four headings * defined for robots. * @param room The room the robot is in. */ public Robot( int col, int row, int heading, RobotRoom room ) { this.room = room; this.col = col; this.row = row; this.direction = heading; this.visible = true; this.delayTime = initialDelay; room.addRobot( this, col, row ); } /** * Move a robot one tile forward, unless the way is blocked by a wall or * other robot. If the way is blocked, the robot will flash briefly to * indicate that it can't move. For example *

r.move();

*/ public void move() { if ( this.okToMove() ) { Point next = this.nextTile(); room.moveRobot( col, row, next.x, next.y ); col = next.x; row = next.y; this.delay(); } else { this.flash(); } } /** * Find out whether a robot can move forward. A robot can move whenever * the tile in front of it doesn't contain a wall or another robot. * For example *

if ( r.okToMove() ) {...

* @return True if the robot can move, false if moving would cause the * robot to collide with a wall or another robot. */ public boolean okToMove() { Point next = this.nextTile(); return ! room.isObstructed( next.x, next.y ); } /** * Turn a robot 90 degrees to its left (i.e., counterclockwise about * its center). For example *

r.turnLeft();

*/ // I do a 90-degree left turn as 3 90-degree right turns, 'though done // all at once so the user doesn't see distinct turns. public void turnLeft() { this.turn( 3 ); } /** * Turn a robot 90 degrees to its right (i.e., clockwise about its center). * For example *

r.turnRight();

*/ public void turnRight() { this.turn( 1 ); } /** * Change the color of the tile under a robot. For example *

r.paint( java.awt.Color.yellow );

* @param newColor The color the tile changes to. */ public void paint( Color newColor ) { room.setColor( col, row, newColor ); } /** * Find out what color the tile under a robot is. For example *

if ( r.colorOfTile() == java.awt.Color.red ) {...

* @return The color of the tile under the robot. */ public Color colorOfTile() { return room.getColor( col, row ); } /** * Find out what direction a robot is facing. For example *

if ( r.heading() == Robot.NORTH ) {...

* @return The robot's direction, encoded as one of the values * Robot.NORTH, Robot.EAST, * Robot.SOUTH, or Robot.WEST. */ public int heading() { return direction; } /** * Set the speed at which a robot moves and turns. For example *

r.setSpeed( 100 );

* @param speed An integer between 1 and 1000, which indicates approximately * how many moves or turns per second the robot should do. Values below 1 * or above 1000 are treated as if they were 1 and 1000, respectively. */ public void setSpeed( int speed ) { if ( speed < 1 ) { speed = 1; } if ( speed > 1000 ) { speed = 1000; } delayTime = 1000 / speed; } /** * Draw a robot. * @param context The graphics context in which to draw. * @param x The horizontal coordinate at which to place the robot's center. * @param y The vertical coordinate at which to place the robot's center */ // The robot is a polygon, filled with a robot color not likely to be // generated by a student -- right now, a dark purple. I define the polygon // by giving lists of X and Y offsets for its vertices from the center of // the robot, when the robot is facing north. For other orientations, I // rotate these offsets using the standard equations for 2D rotation // (x' = x cos(a) + y sin(a); y' = -x sin(a) + y cos(a)), keeping in mind // that the rotations are all multiples of 90 degrees, so the sines and cosines // are all -1, 1, or 0. To actually draw the robot, I add the rotated offsets // to the center coordinates provided as parameters, and use the results as // the vertices of a filled polygon. protected void draw( Graphics context, int x, int y ) { if ( visible ) { int sine; // Will hold the sine of the rotation angle int cosine; // Will hold the cosine of the rotation angle switch ( direction ) { case NORTH: // no rotation sine = 0; cosine = 1; break; case WEST: // 90 degrees sine = 1; cosine = 0; break; case SOUTH: // 180 degrees sine = 0; cosine = -1; break; case EAST: // -90 degrees sine = -1; cosine = 0; break; default: // Invalid rotations act like no rotation sine = 0; cosine = 1; break; } int[] xVertices = new int[ xOffsets.length ]; int[] yVertices = new int[ yOffsets.length ]; for ( int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.