This works now.
DEFINE_string(start, "", "The starting tile positions. 0 is the hole.");
DEFINE_string(goal, "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0", "The desired tile positions. 0 is the hole.");
+DEFINE_int32(max_frontier, 100000, "The maximum frontier size. Larger values run longer and give shorter paths.");
int main(int argc, char** argv) {
gflags::ParseCommandLineFlags(&argc, &argv, false);
- std::cout << *find_path(FLAGS_start, FLAGS_goal);
+ std::cout << *find_path(FLAGS_start, FLAGS_goal, FLAGS_max_frontier);
}
return os;
}
-std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal) {
+std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier) {
std::istringstream iss_start{start}, iss_goal{goal};
Board board_start, board_goal;
iss_start >> board_start;
if (iss_goal.fail() || !iss_goal.eof()) {
throw std::runtime_error("Could not parse the goal board: " + goal);
}
- return find_path(board_start, board_goal);
+ return find_path(board_start, board_goal, max_frontier);
}
-std::shared_ptr<Step> find_path(const Board& start, const Board& goal) {
+std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier) {
InvertedBoard invgoal = goal.invert();
std::multimap<int, std::shared_ptr<Step>> todo;
std::set<Board> seen;
}
}
}
+ while (todo.size() > max_frontier) {
+ todo.erase(--todo.end());
+ }
}
throw std::runtime_error("No path from start to goal");
}
};
std::ostream& operator<<(std::ostream& os, const Step& step);
-std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal);
-std::shared_ptr<Step> find_path(const Board& start, const Board& goal);
+std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier);
+std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier);
#endif /* _SLIDING_TILE_LIB_H */