#include <robot_api.hpp>

Static Public Member Functions
static GridCell *	findNearestAlly (GridCell &origin, std::vector< std::vector< GridCell > > &grid)

static std::list< GridCell * >	findShortestPath (GridCell &origin, const GridCell &target, std::vector< std::vector< GridCell > > &grid)

Static Private Member Functions
static std::list< GridCell * >	findShortestPathInternal (GridCell &origin, const std::function< bool(const GridCell &)> &isTarget, const std::function< bool(const GridCell &)> &isPassable, std::vector< std::vector< GridCell > > &grid)

Detailed Description

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

Definition at line 146 of file robot_api.hpp.

Member Function Documentation

GridCell * robot_api::RobotUtility::findNearestAlly	(	GridCell &	origin,
		std::vector< std::vector< GridCell > > &	grid
	)

static

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

Parameters

origin	cell to find
grid	grid to analyze

Returns: nearest ally, or null if we have no allies in grid

Definition at line 19 of file robot_api.cpp.

References findShortestPathInternal().

Referenced by RoboSim::RoboAPIImplementor::sendMessage().

      {
           auto path = findShortestPathInternal(origin, RoboSim::SimGridAllyDeterminant{origin}, [](const GridCell& ignored) { return true; }, grid);
 
           if(path.size()==0)
                return NULL;
           else
                return *(--path.end());
      }

Here is the call graph for this function:

Here is the caller graph for this function:

list< GridCell * > robot_api::RobotUtility::findShortestPath	(	GridCell &	origin,
		const GridCell &	target,
		std::vector< std::vector< 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

origin	starting grid cell
target	ending grid cell
grid	grid 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 29 of file robot_api.cpp.

References robot_api::GridCell::contents, robot_api::EMPTY, and findShortestPathInternal().

Referenced by RoboSim::RoboAPIImplementor::capsuleAttack(), RoboSim::RoboAPIImplementor::rangedAttack(), and DemoBot::searchAndDestroy().

      {
           return findShortestPathInternal(origin,[&target](const GridCell& maybeTarget)
                                           {
                                                //normal == would compare by value;
                                                //this simulates Java's "same object" test
                                                //I /think/ compare-by-value would work too here, but why risk it?
                                                //This is probably faster, anyway.
                                                return &maybeTarget==&target;
                                           },
                                           [](const GridCell& maybePassable)
                                           {
                                                return maybePassable.contents==EMPTY;
                                           }, grid);
      }

Here is the call graph for this function:

Here is the caller graph for this function:

list< GridCell * > robot_api::RobotUtility::findShortestPathInternal	(	GridCell &	origin,
		const std::function< bool(const GridCell &)> &	isTarget,
		const std::function< bool(const GridCell &)> &	isPassable,
		std::vector< std::vector< GridCell > > &	grid
	)

staticprivate

Definition at line 50 of file robot_api.cpp.

References a::x, robot_api::GridCell::x_coord, and robot_api::GridCell::y_coord.

Referenced by findNearestAlly(), and findShortestPath().

      {
           //Offsets to handle incomplete world map
           int x_offset = grid[0][0].x_coord;
           int y_offset = grid[0][0].y_coord;
                     
           //Structures to efficiently handle accounting
           multimap<int,GridCell*> unvisited_nodes;
           unordered_map<GridCell*,list<GridCell*> > current_costs;
 
           //Origin's shortest path is nothing
           list<GridCell*> origin_path = {};
 
           //Initialize graph search with origin
           current_costs[&origin] = origin_path;
           unvisited_nodes.insert(make_pair(0,&origin));
 
           while(unvisited_nodes.size()!=0)
           {
                int our_cost;
                GridCell* our_cell;
                {
                     auto current_entry = unvisited_nodes.begin();
                     our_cost = current_entry->first;
                     our_cell = current_entry->second;
                     //Anonymous block because current_entry is dangling iterator after this
                     unvisited_nodes.erase(current_entry);
                }
           
                list<GridCell*>& current_path = current_costs[our_cell];
 
                //If we are a destination, algorithm has finished: return our current path
                if(isTarget(*our_cell))
                     return current_path;
 
                /*We are adjacent to up to 4 nodes, with
                  coordinates relative to ours as follows:
                  (-1,0),(1,0),(0,-1),(0,1)*/
                list<GridCell*> adjacent_nodes;
                int gridX_value = our_cell->x_coord - x_offset;
                int gridY_value = our_cell->y_coord - y_offset;
                if(gridX_value!=0)
                     adjacent_nodes.push_back(&grid[gridX_value-1][gridY_value]);
                if(gridX_value!=grid.size()-1)
                     adjacent_nodes.push_back(&grid[gridX_value+1][gridY_value]);
                if(gridY_value!=0)
                     adjacent_nodes.push_back(&grid[gridX_value][gridY_value-1]);
                if(gridY_value!=grid[0].size()-1)
                     adjacent_nodes.push_back(&grid[gridX_value][gridY_value+1]);
 
                /*Iterate over adjacent nodes, add to or update
                  entry in unvisited_nodes and current_costs if
                  necessary*/
                for(GridCell* x : adjacent_nodes)
                {
                     //If we're not passable, we can't be used as an adjacent cell, unless we're a target
                     if(!isPassable(*x) && !isTarget(*x))
                          continue;
 
                     //Generate proposed path
                     list<GridCell*> x_proposed_path = current_path;
                     x_proposed_path.push_back(x);
 
                     //current least cost path
                     if(current_costs.count(x))
                     {
                          list<GridCell*>& clcp = current_costs[x];
                          if(clcp.size()-1>our_cost+1)
                          {
                               auto old_range = unvisited_nodes.equal_range(clcp.size()-1);
                               for(auto i = old_range.first; i!=old_range.second; ++i)
                                    if(i->second==x)
                                    {
                                         unvisited_nodes.erase(i);
                                         break;
                                    }
                          }
                          else
                               continue;
                     }
 
                     unvisited_nodes.insert(make_pair(our_cost+1,x));
                     current_costs[x]=x_proposed_path;
                }
           }
 
           /*Loop is over, and we didn't find a path to the target :(
             Return empty path.*/
           return list<GridCell*>();
      }

Here is the caller graph for this function:

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

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Function Documentation