Classes | Static Public Member Functions | Static Private Member Functions | List of all members
Robot.RobotUtility Class Reference

Classes

class  FSPPredicate
 

Static Public Member Functions

static GridCell findNearestAlly (GridCell origin, GridCell[][] grid)
 
static GridCell[] findShortestPath (GridCell origin, final GridCell target, GridCell[][] grid)
 

Static Private Member Functions

static GridCell[] findShortestPathInternal (GridCell origin, FSPPredicate isTarget, FSPPredicate isPassable, GridCell[][] grid)
 

Detailed Description

RobotUtility class
Provides utilities for students to use in Robot implementations.

Definition at line 125 of file Robot.java.

Member Function Documentation

static GridCell Robot.RobotUtility.findNearestAlly ( GridCell  origin,
GridCell  grid[][] 
)
static

Find nearest neighbor:
Finds the nearest ally to cell, approximately as the crow flies.

Parameters
origincell to find
gridgrid to analyze
Returns
nearest ally, or null if we have no allies in grid

Definition at line 139 of file Robot.java.

References Robot.RobotUtility.findShortestPathInternal().

140  {
141  GridCell[] path = findShortestPathInternal(origin, new RoboSim.SimGridAllyDeterminant(origin), new FSPPredicate() {
142  public boolean validCell(GridCell cell) { return true; }}, grid);
143 
144  if(path==null)
145  return null;
146  else
147  return path[path.length-1];
148  }
Robot.RobotUtility.findShortestPathInternal
static GridCell[] findShortestPathInternal(GridCell origin, FSPPredicate isTarget, FSPPredicate isPassable, GridCell[][] grid)
Definition: Robot.java:180

Here is the call graph for this function:

static GridCell [] Robot.RobotUtility.findShortestPath ( GridCell  origin,
final GridCell  target,
GridCell  grid[][] 
)
static

Shortest path calculator:
Finds the shortest path from one grid cell to another.

This uses Dijkstra's algorithm to attempt to find the shortest path from one grid cell to another. Cells are adjacent if they are up, down, left, or right of each other. Cells are not adjacent if they are diagonal to one another.

Parameters
originstarting grid cell
targetending grid cell
gridgrid to analyze
Returns
a path guaranteed to be the shortest path from the origin to the target. Will return null if no path could be found in the given grid.

Definition at line 163 of file Robot.java.

References Robot.GridObject.EMPTY, and Robot.RobotUtility.findShortestPathInternal().

164  {
165  return findShortestPathInternal(origin,new FSPPredicate () {
166  public boolean validCell(GridCell maybeTarget)
167  {
168  return maybeTarget==target;
169  }
170  },
171  new FSPPredicate() {
172  public boolean validCell(GridCell maybePassable)
173  {
174  return maybePassable.contents==GridObject.EMPTY;
175  }
176  },
177  grid);
178  }
Robot.RobotUtility.findShortestPathInternal
static GridCell[] findShortestPathInternal(GridCell origin, FSPPredicate isTarget, FSPPredicate isPassable, GridCell[][] grid)
Definition: Robot.java:180

Here is the call graph for this function:

static GridCell [] Robot.RobotUtility.findShortestPathInternal ( GridCell  origin,
FSPPredicate  isTarget,
FSPPredicate  isPassable,
GridCell  grid[][] 
)
staticprivate

Definition at line 180 of file Robot.java.

References Robot.RobotUtility.FSPPredicate.validCell().

Referenced by Robot.RobotUtility.findNearestAlly(), and Robot.RobotUtility.findShortestPath().

181  {
182  //Offsets to handle incomplete world map
183  int x_offset = grid[0][0].x_coord;
184  int y_offset = grid[0][0].y_coord;
185 
186  //Structures to efficiently handle accounting
187  TreeMap<Integer,LinkedList<GridCell>> unvisited_nodes = new TreeMap<Integer,LinkedList<GridCell>>(); //this is really a multimap
188  Map<GridCell,LinkedList<GridCell>> current_costs = new HashMap<GridCell,LinkedList<GridCell>>();
189 
190  //Origin's shortest path is simply itself
191  LinkedList<GridCell> origin_path = new LinkedList<GridCell>();
192  origin_path.add(origin);
193 
194  //Initialize graph search with origin
195  current_costs.put(origin,origin_path);
196  unvisited_nodes.put(0,origin_path);
197 
198  while(unvisited_nodes.size()!=0)
199  {
200  Map.Entry<Integer,LinkedList<GridCell>> current_entry = unvisited_nodes.firstEntry();
201  int our_cost = current_entry.getKey();
202  GridCell our_cell = current_entry.getValue().pop();
203  LinkedList<GridCell> current_path = current_costs.get(our_cell);
204 
205  //If we are a destination, algorithm has finished: return our current path
206  if(isTarget.validCell(our_cell))
207  return current_path.toArray(new GridCell[0]);
208 
209  //Erase our cost mapping from unvisited_nodes if necessary
210  if(current_entry.getValue().size()==0)
211  unvisited_nodes.remove(our_cost);
212 
213  /*We are adjacent to up to 4 nodes, with
214  coordinates relative to ours as follows:
215  (-1,0),(1,0),(0,-1),(0,1)*/
216  LinkedList<GridCell> adjacent_nodes = new LinkedList<GridCell>();
217  int gridX_value = our_cell.x_coord - x_offset;
218  int gridY_value = our_cell.y_coord - y_offset;
219  if(gridX_value!=0)
220  adjacent_nodes.add(grid[gridX_value-1][gridY_value]);
221  if(gridX_value!=grid.length-1)
222  adjacent_nodes.add(grid[gridX_value+1][gridY_value]);
223  if(gridY_value!=0)
224  adjacent_nodes.add(grid[gridX_value][gridY_value-1]);
225  if(gridY_value!=grid[0].length-1)
226  adjacent_nodes.add(grid[gridX_value][gridY_value+1]);
227 
228  /*Iterate over adjacent nodes, add to or update
229  entry in unvisited_nodes and current_costs if
230  necessary*/
231  for(GridCell x : adjacent_nodes)
232  {
233  //If we're not passable, we can't be used as an adjacent cell, unless we're a target
234  if(!isPassable.validCell(x) && !isTarget.validCell(x))
235  continue;
236 
237  //Generate proposed path
238  LinkedList<GridCell> x_proposed_path = (LinkedList<GridCell>)(current_path.clone());
239  x_proposed_path.add(x);
240 
241  //current least cost path
242  List<GridCell> clcp = current_costs.get(x);
243 
244  if(clcp!=null && clcp.size()-1>our_cost+1)
245  {
246  LinkedList<GridCell> old_unvisited = unvisited_nodes.get(clcp.size()-1);
247  old_unvisited.removeFirstOccurrence(x);
248  if(old_unvisited.size()==0)
249  unvisited_nodes.remove(clcp.size()-1);
250  }
251  else if(clcp!=null && clcp.size()-1<=our_cost+1)
252  continue;
253 
254  LinkedList<GridCell> new_unvisited = unvisited_nodes.get(our_cost+1);
255  if(new_unvisited==null)
256  {
257  new_unvisited = new LinkedList<GridCell>();
258  unvisited_nodes.put(our_cost+1,new_unvisited);
259  }
260  new_unvisited.add(x);
261  current_costs.put(x,x_proposed_path);
262  }
263  }
264 
265  /*Loop is over, and we didn't find a path to the target :(
266  Return null.*/
267  return null;
268  }

Here is the call graph for this function:

Here is the caller graph for this function:

The documentation for this class was generated from the following file: