Skip to content

Instantly share code, notes, and snippets.

@arms22

arms22/CMakeLists.txt

Last active September 12, 2017 08:14
Show Gist options
  • Save arms22/df8dfe0e89b521a26729f45e0547ea9b to your computer and use it in GitHub Desktop.
Save arms22/df8dfe0e89b521a26729f45e0547ea9b to your computer and use it in GitHub Desktop.
Download ZIP
マイクロマウス迷路解析プログラム
Raw
CMakeLists.txt
cmake_minimum_required(VERSION 2.8)
add_definitions("-Wall -std=c++11")
add_executable(main main.cpp)
add_executable(search search.cpp)
Raw
cola.hpp
/**
* cola.hpp: a single header only COmmand Line Argument parser.
*/
#ifndef COLA_HPP
#define COLA_HPP
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <map>
#include <stdexcept>
#include <cassert>
namespace cola {
// option argument type
typedef int integer;
typedef double real;
typedef std::string string;
typedef std::vector<integer> ivector;
typedef std::vector<real> rvector;
typedef std::vector<string> svector;
// programming error
class logic_error;
// runtime error
class runtime_error;
/**
* Command-line option parser.
* $ command [option [argument]]
*/
class parser
{
public:
/**
* Represents an option.
*/
class option;
parser();
~parser();
/**
* Define a long option.
*
* @param name option name. '--' is automatically added.
*/
option& define(const string& name, const string& description = "");
/**
* Define a short option.
*
* @param name short option name. '-' is automatically added.
*/
option& define(char name, const string& description = "");
/**
* Parse command line options.
*/
void parse(int argc, const char* const argv[]);
/**
* Returns true if the name is defined or aliased.
*/
bool is_passed(const string& name) const;
bool is_passed(char name) const;
/**
* Returns passed argument. if T is different from the type of defined one, throw exception.
* @tparam T type of argument. integer, real, string is allowed.
*/
template<typename T> T get(const string& name) const;
template<typename T> T get(char name) const;
/**
* Returns passed argument as vector. if T is different from the type of defined one, throw exception.
* @tparam T type of argument. integer, real, string is allowed.
*/
template<typename T> std::vector<T> get_vector(const string& name) const;
template<typename T> std::vector<T> get_vector(char name) const;
/**
* Returns passed arguments.
*/
svector args() const;
/**
* Returns arguments which is not defined or not an option.
*/
svector rest_args() const;
/**
* Returns command name.
*/
string command() const;
/**
* Returns command name and its description.
* @param offset offset space from beggining of line
*/
string descriptions(const string& offset = "") const;
/**
* Output template usage to ostream.
* @param overview overview of this program
* @param os output ostream
*/
void easy_usage(const string& overview, std::ostream& os = std::cerr) const;
/**
* Returns the executed command.
*/
string exec_str() const;
/**
* Reset parsed data.
* use this function after parse error.
*/
void reset();
/**
* True when there are undefined long or short options
* in parsed argv.
*/
bool exists_undefined_options() const;
private:
enum argument_type
{
FLAG,
INTEGER, REAL, STRING,
IVECTOR, RVECTOR, SVECTOR
};
enum literal_type {
SHORT, // -a
SHORTS, // -abc
LONG, // --option
LONG_ARG, // --option=<arg>
IGNORE, // -
IGNORE_AFTER, // --
ELSE // else
};
typedef std::vector<option*> option_container;
typedef std::map<string, option*> option_map;
typedef option_container::iterator option_iterator;
typedef option_container::const_iterator option_citerator;
typedef option_map::iterator lookup_iterator;
typedef option_map::const_iterator lookup_citerator;
private:
option& get_option(const string& name);
const option& get_option(const string& name) const;
option& get_option(char name);
const option& get_option(char name) const;
bool is_defined(const string& name) const;
bool is_defined(char name) const;
void parse_impl(svector::iterator begin, svector::iterator end);
literal_type judge(const string& arg) const;
void eval_short_option(svector::iterator& it, svector::iterator end);
void eval_shorts_option(svector::iterator& it, svector::iterator end);
void eval_long_option(svector::iterator& it, svector::iterator end);
void eval_long_param_option(svector::iterator& it, svector::iterator end);
static string make_arg(const string& name);
static string make_arg(char name);
void must_be_parsed(const string& func_name) const;
void must_not_be_parsed(const string& func_name) const;
template<typename T> static string to_string(const T& value);
template<typename T> static string to_string(const std::vector<T>& value);
static string to_string(argument_type type);
template<typename T> static string to_string();
template<typename T> static T from_string(const string& value);
template<typename T> static std::vector<T> from_string(const string& value, char delim);
parser(const option& other);
void operator=(const option& other);
private:
svector args_;
svector rest_args_;
option_container options_;
option_map lookup_;
bool parsed_;
bool exists_undefined_;
};
/**
* represents an option.
*/
class parser::option
{
public:
~option();
/**
* Let this option have an argument.
* @tparam T type of argument. integer, real, string are allowed.
*/
template<typename T> option& with_arg(T default_value = T());
/**
* Let this option have a vector argument.
* @tparam T type of argument. integer, real, string are allowed.
*/
template<typename T> option& with_arg_vector(const std::vector<T>& default_value = std::vector<T>());
/**
* Let this option have a vector argument.
* @param default_value string expression of default vector. ex) "1,2,3"
* @tparam T type of argument. integer, real, string are allowed.
*/
template<typename T> option& with_arg_vector(const string& default_value);
/**
* Set an alias name of this option.
* @param name long option name. '--' is automatically added.
*/
option& alias(const string& long_name);
/**
* Set an alias name of this option.
* @param name short option name. '-' is automatically added.
*/
option& alias(char short_name);
/**
* Set delimiter to parse vector value.
*/
option& delimiter(char d);
/**
* Hide this option from usage.
*/
option& hidden();
private:
typedef svector name_container;
private:
friend class parser; // parser is only class that can generate option.
option(const string& name, const string& description, parser& mother);
option(char name, const string& description, parser& mother);
template<typename T> T as() const;
template<typename T> std::vector<T> as_vector() const;
void check_multi(const string& name) const;
void passed();
bool has_arg() const;
void parse_arg(const string& arg);
void reset();
option(const option& other);
void operator=(const option& other);
private:
parser& mother_;
argument_type type_;
union {
integer value_i_;
real value_r_;
string* value_s_;
ivector* value_iv_;
rvector* value_rv_;
svector* value_sv_;
};
bool is_passed_;
string description_;
name_container names_; // contains '--', '-'
string default_value_;
char delim_; // delimiter to parse vector
bool hidden_;
};
class logic_error: public std::logic_error
{
public:
logic_error(const string& msg): std::logic_error(msg) {}
};
class runtime_error: public std::runtime_error
{
public:
runtime_error(const string& msg): std::runtime_error(msg) {}
};
// parser ------------------------------------------------------------------------------------
// ctor/dtor ---------------------------------------------------------------------------------
inline parser::parser():
parsed_(false), exists_undefined_(false)
{
}
inline parser::~parser()
{
for(option_iterator it = options_.begin(); it != options_.end(); ++it) {
delete *it;
}
}
// define ------------------------------------------------------------------------------------
inline parser::option& parser::define(const string& name, const string& description)
{
must_not_be_parsed("parser::define");
if(is_defined(name)) {
throw logic_error("the option '" + make_arg(name) + "' is already defined");
}
if(name.empty()) {
throw logic_error("don't pass empty string to parser::define");
}
const string desc = description.empty()? "option #" + to_string(options_.size() + 1)
: description;
if(name.size() == 1) {
options_.push_back(new option(name[0], desc, *this));
} else {
options_.push_back(new option(name, desc, *this));
}
return *options_.back();
}
inline parser::option& parser::define(char name, const string& description)
{
must_not_be_parsed("parser::define");
if(is_defined(name)) {
throw logic_error("the option '" + make_arg(name) + "' is already defined");
}
if(name == ' ') {
throw logic_error("don't pass white space to parser::define");
}
const string desc = description.empty()? "option #" + to_string(options_.size() + 1)
: description;
options_.push_back(new option(name, desc, *this));
return *options_.back();
}
// parse ------------------------------------------------------------------------------------
inline void parser::parse(int argc, const char* const argv[])
{
if(parsed_) {
throw logic_error("call parser::parse() only once");
}
args_.assign(argv, argv + argc);
parse_impl(args_.begin(), args_.end());
}
// passed ------------------------------------------------------------------------------------
inline bool parser::is_passed(const string& name) const
{
must_be_parsed("parser::is_passed");
return get_option(name).is_passed_;
}
inline bool parser::is_passed(char name) const
{
must_be_parsed("parser::is_passed");
return get_option(name).is_passed_;
}
// get ------------------------------------------------------------------------------------
template<typename T>
inline T parser::get(const string& name) const
{
must_be_parsed("parser::get");
return get_option(name).as<T>();
}
template<typename T>
inline T parser::get(char name) const
{
must_be_parsed("parser::get");
return get_option(name).as<T>();
}
template<typename T>
inline std::vector<T> parser::get_vector(const string& name) const
{
must_be_parsed("parser::get_vector");
return get_option(name).as_vector<T>();
}
template<typename T>
inline std::vector<T> parser::get_vector(char name) const
{
must_be_parsed("parser::get_vector");
return get_option(name).as_vector<T>();
}
// other ------------------------------------------------------------------------------------
inline svector parser::args() const
{
must_be_parsed("parser::args");
return args_;
}
inline svector parser::rest_args() const
{
must_be_parsed("parser::rest_args");
return rest_args_;
}
inline string parser::command() const
{
must_be_parsed("parser::command");
return args_[0].substr(args_[0].find_last_of('/') + 1);
}
inline string parser::descriptions(const string& offset) const
{
must_be_parsed("parser::descriptions");
svector optheads;
std::vector<std::size_t> sizes;
option_citerator it = options_.begin();
for(; it!=options_.end(); ++it) {
std::ostringstream oss;
const option& opt = **it;
const svector& names = opt.names_;
if(opt.hidden_) continue;
oss << offset << names[0];
if(names.size() >= 2) oss << " (";
for(svector::const_iterator it = names.begin()+1; it != names.end(); ++it) {
oss << *it << (it == names.end() - 1? "" : ", ");
}
if(names.size() >= 2) oss << ')';
if(opt.has_arg()) {
oss << " <" << to_string(opt.type_) << ">";
}
optheads.push_back(oss.str());
}
std::size_t max_width = 0;
svector::const_iterator it2 = optheads.begin();
for(; it2!=optheads.end(); ++it2) {
max_width = std::max(max_width, it2->size());
sizes.push_back(it2->size());
}
std::ostringstream oss;
int i = 0;
it = options_.begin();
for(; it!=options_.end(); ++it) {
const option& opt = **it;
if(opt.hidden_) continue;
oss << std::left << std::setw(max_width) << optheads[i]
<< " | " << opt.description_;
if(opt.has_arg()) {
oss << " (default = " << opt.default_value_ << ")";
}
oss << std::endl;
i++;
}
return oss.str();
}
inline void parser::easy_usage(const string& overview, std::ostream& os) const
{
must_be_parsed("parser::easy_usage");
os << "overview: " << overview << '\n'
<< "usage: $ " << command() << " [options...]\n"
<< "options:\n"
<< descriptions(" ")
<< std::endl;
}
inline string parser::exec_str() const
{
must_be_parsed("parser::exec_str");
svector optheads;
std::ostringstream os;
for(svector::const_iterator it = args_.begin(); it != args_.end(); ++it) {
os << *it << ' ';
}
return os.str();
}
inline void parser::reset()
{
args_.clear();
rest_args_.clear();
for(option_iterator it = options_.begin(); it != options_.end(); ++it) {
(**it).reset();
}
parsed_ = false;
}
inline bool parser::exists_undefined_options() const
{
return exists_undefined_;
}
// private --------------------------------------------------------------------------------------------
// get option -----------------------------------------------------------------------------------------
inline parser::option& parser::get_option(const string& name)
{
const string arg = make_arg(name);
lookup_iterator it = lookup_.find(arg);
if(it == lookup_.end()) throw logic_error("an option '" + arg + "' is undefined");
return *it->second;
}
inline const parser::option& parser::get_option(const string& name) const
{
const string arg = make_arg(name);
lookup_citerator it = lookup_.find(arg);
if(it == lookup_.end()) throw logic_error("an option '" + arg + "' is undefined");
return *it->second;
}
inline parser::option& parser::get_option(char name)
{
const string arg = make_arg(name);
lookup_iterator it = lookup_.find(arg);
if(it == lookup_.end()) throw logic_error("an option '" + arg + "' is undefined");
return *it->second;
}
inline const parser::option& parser::get_option(char name) const
{
const string arg = make_arg(name);
lookup_citerator it = lookup_.find(arg);
if(it == lookup_.end()) throw logic_error("an option '" + arg + "' is undefined");
return *it->second;
}
// defined ------------------------------------------------------------------------------------
inline bool parser::is_defined(const string& name) const
{
return lookup_.count(make_arg(name)) != 0;
}
inline bool parser::is_defined(char name) const
{
return lookup_.count(make_arg(name)) != 0;
}
// parse ---------------------------------------------------------------------------------------
inline void parser::parse_impl(svector::iterator begin, svector::iterator end)
{
svector::iterator it = begin + 1;
if(it == end) goto parse_end;
while(it != end) {
const string& arg = *it;
switch(judge(arg)) {
case SHORT: // -a
eval_short_option(it, end);
break;
case SHORTS: // -abc
eval_shorts_option(it, end);
break;
case LONG: // --option
eval_long_option(it, end);
break;
case LONG_ARG: // --option=<arg>
eval_long_param_option(it, end);
break;
case IGNORE: // -
++it;
break;
case IGNORE_AFTER: // --
++it;
for(; it != end; ++it) {
rest_args_.push_back(*it);
}
goto parse_end;
case ELSE:
rest_args_.push_back(arg);
++it;
break;
default:
assert(0);
}
}
parse_end:
parsed_ = true;
}
inline parser::literal_type parser::judge(const string& arg) const
{
const std::size_t len = arg.size();
if(arg[0] == '-') {
if(len == 1) return IGNORE; // arg == "-"
if(arg[1] == '-') { // arg == "--something"
if(len == 2) return IGNORE_AFTER; // arg == "--"
string::size_type is_optarg = arg.find_first_of('=');
if(is_optarg == string::npos) {
return LONG; // arg == "--something"
} else {
return LONG_ARG; // arg == "--something=opt_arg"
}
} else {
if(len != 2) return SHORTS; // arg == "-something"
else return SHORT; // arg == "-s"
}
} else {
return ELSE;
}
}
// eval each arguments ------------------------------------------------------------------------
inline void parser::eval_short_option(svector::iterator& it, svector::iterator end)
{
const string& arg = *it++; // it points next of arg "-a"
const char c = arg[1]; // after '-'
if(!is_defined(c)) {
exists_undefined_ = true;
rest_args_.push_back(arg);
return;
}
option& opt = get_option(c);
if(opt.has_arg()) {
if(it == end) {
throw runtime_error("the option '"+arg+"' needs argument");
} else {
opt.parse_arg(*it++);
}
}
opt.passed();
}
inline void parser::eval_shorts_option(svector::iterator& it, svector::iterator)
{
const string& arg = *it++; // it points next of arg "-abc"
// -a123
option& opt1 = get_option(arg[1]);
if(opt1.has_arg()) {
opt1.parse_arg(string(arg.begin()+2, arg.end()));
opt1.passed();
return;
}
// -abc
for(svector::size_type j=1; j<arg.size(); j++) {
const char c = arg[j]; // a b c
option& opt = get_option(c);
if(opt.has_arg()) {
throw runtime_error("the option '"+make_arg(c)+"' needs argument");
}
opt.passed();
}
}
inline void parser::eval_long_option(svector::iterator& it, svector::iterator end)
{
const string& arg = *it++; // it points next of arg "--abc"
const string name(arg.begin()+2, arg.end());
if(!is_defined(name)) {
exists_undefined_ = true;
rest_args_.push_back(arg);
return;
}
option& opt = get_option(name);
if(opt.has_arg()) {
if(it == end) {
throw runtime_error("the option '"+arg+"' needs argument");
}
opt.parse_arg(*it++);
}
opt.passed();
}
inline void parser::eval_long_param_option(svector::iterator& it, svector::iterator)
{
const string& arg = *it++; // it points next of arg "--abc=arg"
const string::size_type pos = arg.find_first_of('=');
const string name(arg.begin()+2, arg.begin()+pos);
if(!is_defined(name)) {
exists_undefined_ = true;
rest_args_.push_back(arg);
return;
}
option& opt = get_option(name);
const string arg2 = string(arg.begin()+pos+1, arg.end());
if(arg2.empty()) {
throw runtime_error("the option '"+name+"' needs argument");
}
opt.parse_arg(arg2);
opt.passed();
}
// utility ---------------------------------------------------------------------------------
inline string parser::make_arg(const string& name)
{
return (name.size() == 1)? make_arg(name[0]) : "--" + name;
}
inline string parser::make_arg(char name)
{
return string(1, '-') + name;
}
inline void parser::must_be_parsed(const string& func_name) const
{
if(!parsed_) {
throw logic_error("call '"+func_name+"' after parse arguments");
}
}
inline void parser::must_not_be_parsed(const string& func_name) const
{
if(parsed_) {
throw logic_error("call '"+func_name+"' before parse arguments");
}
}
template<typename T>
inline string parser::to_string(const T& value)
{
std::stringstream ss;
ss << value;
return ss.str();
}
template<>
inline string parser::to_string<string>(const string& value)
{
std::stringstream ss;
ss << '"' + value + '"';
return ss.str();
}
template<typename T>
inline string parser::to_string(const std::vector<T>& value)
{
std::stringstream ss;
ss << "[";
for(typename std::vector<T>::const_iterator it = value.begin(); it != value.end(); ++it) {
ss << *it << ((it == value.end()-1)? "" : ", ");
}
ss << "]";
return ss.str();
}
template<>
inline string parser::to_string<string>(const std::vector<string>& value)
{
std::stringstream ss;
ss << "[";
for(std::vector<string>::const_iterator it = value.begin(); it != value.end(); ++it) {
ss << '"' + *it + '"' << ((it == value.end()-1)? "" : ", ");
}
ss << "]";
return ss.str();
}
template<> inline string parser::to_string<integer>()
{
return "integer";
}
template<> inline string parser::to_string<real>()
{
return "real";
}
template<> inline string parser::to_string<string>()
{
return "string";
}
template<> inline string parser::to_string<ivector>()
{
return "vector<integer>";
}
template<> inline string parser::to_string<rvector>()
{
return "vector<real>";
}
template<> inline string parser::to_string<svector>()
{
return "vector<string>";
}
inline string parser::to_string(argument_type type)
{
switch(type) {
case FLAG: return "flag";
case INTEGER: return "integer";
case REAL: return "real";
case STRING: return "string";
case IVECTOR: return "vector<integer>";
case RVECTOR: return "vector<real>";
case SVECTOR: return "vector<string>";
default: assert(0);
}
}
template<typename T>
inline T parser::from_string(const string& value)
{
std::stringstream ss;
T ret;
if(!(ss << value && ss >> ret && ss.eof())) {
throw runtime_error("cast failed: '"+value+"' to "+to_string<T>());
}
return ret;
}
template<>
inline string parser::from_string<string>(const string& value)
{
return value;
}
template<typename T>
inline std::vector<T> parser::from_string(const string& value, char delim)
{
std::vector<T> ret;
std::stringstream ss(value);
string item;
while(std::getline(ss, item, delim)) {
if(!item.empty()) {
ret.push_back(from_string<T>(item));
}
}
return ret;
}
// parser::option ------------------------------------------------------------------------------
// dtor -----------------------------------------------------------------------------------
inline parser::option::~option()
{
switch(type_) {
case FLAG: break;
case INTEGER: break;
case REAL: break;
case STRING: delete value_s_; value_s_ = NULL; break;
case IVECTOR: delete value_iv_; value_iv_ = NULL; break;
case RVECTOR: delete value_rv_; value_rv_ = NULL; break;
case SVECTOR: delete value_sv_; value_sv_ = NULL; break;
default: assert(0);
}
}
// with_arg ---------------------------------------------------------------------------------
template<>
inline parser::option& parser::option::with_arg<integer>(integer default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_i_ = default_value;
default_value_ = to_string(default_value);
type_ = INTEGER;
return *this;
}
template<>
inline parser::option& parser::option::with_arg<real>(real default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_r_ = default_value;
default_value_ = to_string(default_value);
type_ = REAL;
return *this;
}
template<>
inline parser::option& parser::option::with_arg<string>(string default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_s_ = new string(default_value);
default_value_ = to_string(default_value);
type_ = STRING;
return *this;
}
// with_arg_vector(vector) -----------------------------------------------------------------------------------
template<>
inline parser::option& parser::option::with_arg_vector<integer>(const std::vector<integer>& default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg_vector");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_iv_ = new ivector(default_value);
default_value_ = to_string(default_value);
type_ = IVECTOR;
return *this;
}
template<>
inline parser::option& parser::option::with_arg_vector<real>(const std::vector<real>& default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg_vector");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_rv_ = new rvector(default_value);
default_value_ = to_string(default_value);
type_ = RVECTOR;
return *this;
}
template<>
inline parser::option& parser::option::with_arg_vector<string>(const std::vector<string>& default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg_vector");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_sv_ = new svector(default_value);
default_value_ = to_string(default_value);
type_ = SVECTOR;
return *this;
}
// with_arg_string(string) -----------------------------------------------------------------------------------
template<>
inline parser::option& parser::option::with_arg_vector<integer>(const string& default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg_vector");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_iv_ = new ivector();
*value_iv_ = from_string<integer>(default_value, delim_);
default_value_ = '[' + default_value + ']';
type_ = IVECTOR;
return *this;
}
template<>
inline parser::option& parser::option::with_arg_vector<real>(const string& default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg_vector");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_rv_ = new rvector();
*value_rv_ = from_string<real>(default_value, delim_);
default_value_ = '[' + default_value + ']';
type_ = RVECTOR;
return *this;
}
template<>
inline parser::option& parser::option::with_arg_vector<string>(const string& default_value)
{
mother_.must_not_be_parsed("parser::option::with_arg_vector");
if(type_ != FLAG) throw logic_error("parser::option::with_arg() cal be called only once");
value_sv_ = new svector();
*value_sv_ = from_string<string>(default_value, delim_);
default_value_ = '[' + default_value + ']';
type_ = SVECTOR;
return *this;
}
// alias -----------------------------------------------------------------------------------
inline parser::option& parser::option::alias(const string& long_name)
{
mother_.must_not_be_parsed("parser::option::alias");
if(long_name.size() == 1) {
alias(long_name[0]);
return *this;
}
const string name = make_arg(long_name);
check_multi(name);
names_.push_back(name);
mother_.lookup_.insert(std::make_pair(name, this));
return *this;
}
inline parser::option& parser::option::alias(char short_name)
{
mother_.must_not_be_parsed("parser::option::alias");
const string name = make_arg(short_name);
check_multi(name);
names_.push_back(name);
mother_.lookup_.insert(std::make_pair(name, this));
return *this;
}
// others -----------------------------------------------------------------------------------
inline parser::option& parser::option::delimiter(char d)
{
mother_.must_not_be_parsed("parser::option::delimiter");
delim_ = d;
return *this;
}
inline parser::option& parser::option::hidden()
{
hidden_ = true;
return *this;
}
// private -----------------------------------------------------------------------------------
// ctor -----------------------------------------------------------------------------------
inline parser::option::option(const string& name, const string& description, parser& mother):
mother_(mother),
type_(FLAG),
value_s_(NULL),
is_passed_(false),
description_(description),
delim_(','),
hidden_(false)
{
alias(name);
}
inline parser::option::option(char name, const string& description, parser& mother):
mother_(mother),
type_(FLAG),
value_s_(NULL),
is_passed_(false),
description_(description),
delim_(','),
hidden_(false)
{
alias(name);
}
// as ----------------------------------------------------------------------------------------
template<>
inline integer parser::option::as<integer>() const
{
mother_.must_be_parsed("parser::option::as");
if(type_ != INTEGER) throw logic_error("argument type of '"+names_[0]+"' is not integer");
return value_i_;
}
template<>
inline real parser::option::as<real>() const
{
mother_.must_be_parsed("parser::option::as");
if(type_ != REAL) throw logic_error("argument type of '"+names_[0]+"' is not real");
return value_r_;
}
template<>
inline string parser::option::as<string>() const
{
mother_.must_be_parsed("parser::option::as");
if(type_ != STRING) throw logic_error("argument type of '"+names_[0]+"' is not string");
return *value_s_;
}
// as_vector -----------------------------------------------------------------------------------
template<>
inline ivector parser::option::as_vector<integer>() const
{
mother_.must_be_parsed("parser::option::as_vector");
if(type_ != IVECTOR) throw logic_error("argument type of '"+names_[0]+"' is not vector<integer>");
return *value_iv_;
}
template<>
inline rvector parser::option::as_vector<real>() const
{
mother_.must_be_parsed("parser::option::as_vector");
if(type_ != RVECTOR) throw logic_error("argument type of '"+names_[0]+"' is not vector<real>");
return *value_rv_;
}
template<>
inline svector parser::option::as_vector<string>() const
{
mother_.must_be_parsed("parser::option::as_vector");
if(type_ != SVECTOR) throw logic_error("argument type of '"+names_[0]+"' is not vector<string>");
return *value_sv_;
}
template<>
inline ivector parser::option::as<ivector>() const
{
mother_.must_be_parsed("parser::option::as");
return as_vector<integer>();
}
template<>
inline rvector parser::option::as<rvector>() const
{
mother_.must_be_parsed("parser::option::as");
return as_vector<real>();
}
template<>
inline svector parser::option::as<svector>() const
{
mother_.must_be_parsed("parser::option::as");
return as_vector<string>();
}
// utility --------------------------------------------------------------------------------------------
inline bool parser::option::has_arg() const
{
return type_ != FLAG;
}
inline void parser::option::passed()
{
is_passed_ = true;
}
inline void parser::option::check_multi(const string& name) const
{
if(std::find(names_.begin(), names_.end(), name) != names_.end()) {
throw logic_error("'"+name+"' is already defined");
}
}
inline void parser::option::parse_arg(const string& arg)
{
switch(type_) {
case INTEGER:
value_i_ = from_string<integer>(arg);
break;
case REAL:
value_r_ = from_string<real>(arg);
break;
case STRING:
*value_s_ = arg;
break;
case IVECTOR:
*value_iv_ = from_string<integer>(arg, delim_);
break;
case RVECTOR:
*value_rv_ = from_string<real>(arg, delim_);
break;
case SVECTOR:
*value_sv_ = from_string<string>(arg, delim_);
break;
default:
throw logic_error("the option '"+names_[0]+"' don't take an argument.");
}
}
inline void parser::option::reset()
{
is_passed_ = false;
}
} // namespace cola
#endif // COLA_HPP
Raw
DiagonalPath.h
#ifndef __DIAGONALPATH__
#define __DIAGONALPATH__
#include "Search.h"
#include "Operation.h"
namespace Maze {
#if 0
class DiagonalSearch {
public:
uint32_t maximumPoints; // 分岐数の最大値
uint32_t numberOfSearches; // 探索回数
DiagonalGraph &g;
DiagonalSearch(DiagonalGraph &g_) : g(g_) {}
bool start(int target_, std::vector<int> &goal_)
{
bool found = false;
auto comparecost = [&](int l, int r)
{
int gl = g.node(l).cost;
int gr = g.node(r).cost;
int hl = MazeIndex(target_).manhattan(MazeIndex(l));
int hr = MazeIndex(target_).manhattan(MazeIndex(r));
if((gl + hl) == (gr + hr))
return hl > hr;
return (gl + hl) > (gr + hr);
};
std::priority_queue<int, std::vector<int>, decltype(comparecost)> search_q(comparecost);
// クリア
g.clear();
// キューに初期探索ノードを追加
for(auto it = goal_.begin(); it != goal_.end(); ++it) {
int inode = *it;
Node &n = g.node(inode);
n.cost = 0;
search_q.push(inode);
}
// 統計情報クリア
maximumPoints = numberOfSearches = 0;
// キューが空になるか target_ が見つかるまでループ
while(search_q.empty() == 0 && !found){
maximumPoints = max(uint32_t(search_q.size()), maximumPoints);
numberOfSearches++;
int inode = search_q.top();
search_q.pop();
Node &n = g.node(inode);
std::vector<Edge> edges;
g.edges(inode, edges);
for(auto e : edges){
int enode = inode + e.offset;
Node &m = g.node(enode);
Cost cur = n.cost + 1;
Cost old = m.cost;
if(cur < old){
m.from = e.reverse();
m.cost = cur;
if(old != Maze::InvalidCost){
;
} else {
if (enode == target_){
found = true;
}
}
search_q.push(enode);
}
}
}
return found;
}
string runSequence;
void makeRunSequence(int inode, int last_dir)
{
const char* command_table[12][12] = {
{ "F", "L", "_", "_", "_", "UR", "UF", "UL", "_", "_", "_", "R" },
{ "_", "_", "D", "F", "L", "_", "_", "_", "UR", "UF", "UL", "_" },
{ "F", "D", "_", "_", "_", "UR", "UF", "UL", "_", "_", "_", "R" },
{ "_", "_", "R", "F", "L", "_", "_", "_", "UR", "UF", "UL", "_" },
{ "UF", "UL", "_", "_", "_", "D", "F", "L", "_", "_", "_", "UR" },
{ "_", "_", "R", "F", "D", "_", "_", "_", "UR", "UF", "UL", "_" },
{ "UF", "UL", "_", "_", "_", "R", "F", "L", "_", "_", "_", "UR" },
{ "_", "_", "UR", "UF", "UL", "_", "_", "_", "D", "F", "L", "_" },
{ "UF", "UL", "_", "_", "_", "R", "F", "D", "_", "_", "_", "UR" },
{ "_", "_", "UR", "UF", "UL", "_", "_", "_", "R", "F", "L", "_" },
{ "F", "L", "_", "_", "_", "UR", "UF", "UL", "_", "_", "_", "D" },
{ "_", "_", "UR", "UF", "UL", "_", "_", "_", "R", "F", "D", "_" },
};
runSequence = "";
do {
Node &n = g.node(inode);
if(n.cost == 0){
runSequence += 'S';
break;
}
cout << (int)last_dir << " " << (int)n.from.direction << endl;
runSequence += command_table[last_dir][n.from.direction];
inode = n.from.offset + inode;
last_dir = n.from.direction;
} while(1);
}
void orthogonalize(void)
{
static const int dir_table[] = {
DIR_RIGHT, DIR_TOP, DIR_RIGHT, DIR_TOP, DIR_LEFT, DIR_TOP, DIR_LEFT, DIR_BOTTOM, DIR_LEFT, DIR_BOTTOM, DIR_RIGHT, DIR_BOTTOM,
};
static const int offset_table[] = {
RightNode(0), RightNode(0), TopNode(0), TopNode(0), TopNode(0), 0, 0, 0, 0, 0, 0, RightNode(0),
};
g.maze.initCosts();
g.maze.setDir(g.maze.start, DIR_TOP);
g.maze.setCost(g.maze.start, g.node(0).cost);
for(int inode=0; inode<Maze::DiagonalGraph::MaxNodes; inode++)
{
Node &n = g.node(inode);
int dir = dir_table[n.from.direction];
int cur = n.cost;
Index idx = MazeIndex(inode + offset_table[n.from.direction]);
int old = g.maze.getCost(idx);
if(cur < old){
g.maze.setDir(idx, dir);
g.maze.setCost(idx, cur);
}
}
}
string toString()
{
ostringstream oss;
#if 1
const char *dirchar[] = {"→","↗","↗","↑","↖","↖","←","↙","↙","↓","↘","↘"};
for(int y = MAZE_SIZE-1; y >= 0; y--) {
oss << " ";
for(int x = 0; x < MAZE_SIZE; x++) {
Node &n = g.node(NodeIndex(x,y));
if(n.cost == Maze::InvalidCost){
oss << "__ ";
}else{
oss << dirchar[n.from.direction] << " ";
//oss << dirchar[nodeDir[node]] << setw(2) << right << (cost % 1000);
}
}
oss << endl << " ";
for(int x = 0; x < MAZE_SIZE; x++) {
Node &n = g.node(RightNode(NodeIndex(x,y)));
if(n.cost == Maze::InvalidCost){
oss << " __";
}else{
//oss << setw(2) << right << (cost % 1000) << dirchar[nodeDir[node]];
oss << " " << dirchar[n.from.direction];
}
}
oss << endl;
}
#else
for(int x = 0; x < MAZE_SIZE; x++) {
oss << " To Ri";
}
oss << endl;
for(int y = MAZE_SIZE-1; y >= 0; y--) {
for(int x = 0; x < MAZE_SIZE; x++) {
Node &n = g.node(NodeIndex(x,y));
if(n.cost == Maze::InvalidCost){
oss << " _";
}else{
oss << setw(3) << right << (n.cost % 1000);
}
n = g.node(RightNode(NodeIndex(x,y)));
if(n.cost == Maze::InvalidCost){
oss << " _";
}else{
oss << setw(3) << right << (n.cost % 1000);
}
}
oss << endl;
}
#endif
return oss.str();
}
};
class DiagonalPathFormatter : public Formatter {
public:
Index agent;
bool colored;
bool showCost;
uint8_t *nodeDir;
DiagonalPathFormatter(bool color = false, bool cost = false)
{
agent = Maze::InvalidIndex;
colored = color;
showCost = cost;
}
DiagonalPathFormatter& setAgent(Index idx){
agent = idx;
return *this;
}
DiagonalPathFormatter& setDirection(uint8_t *direction){
nodeDir = direction;
return *this;
}
string stringFrom(Structure &maze)
{
enum {
SPACE = 0, BAR_V, BAR_H, PILLAR, PILLAR_N, PILLAR_W, PILLAR_S, PILLAR_E, PILLAR_NW, PILLAR_NE, PILLAR_SW, PILLAR_SE,
COST, DIRECTION, INVALID_DIRECTION, MARK, GOALPOS, STARTPOS, INVALID,
};
const char *attr_wall = "";
const char *attr_dir = "";
const char *attr_invalid_dir = "";
const char *attr_cost = "";
const char *attr_goal = "";
const char *attr_maker = "";
const char *attr_unknown = "";
const char *attr_reset = "";
const char *wallchar[] = {"　","┃","━","╋","┳","┣","┻","┫","┏","┓","┗","┛"};
const char *dirchar[] = {"→","↗","↑","↖","←","↙","↓","↘"};
const char *makerchar = "＠";
const char *goalchar = "Ｇ";
const char *unknownchar = "??";
if (colored) {
attr_wall = "\033[0;30m";
attr_dir = "\033[1;36m";
attr_invalid_dir = "\033[;30m";
attr_cost = "\033[m";
attr_goal = "\033[1;31m";
attr_maker = "\033[1;33m";
attr_unknown = "\033[0;30m";
attr_reset = "\033[m";
}
uint8_t printbuf[MAZE_SIZE*2+1][MAZE_SIZE*2+1];
for(int x = 0; x < MAZE_SIZE; x++) {
for(int y = 0; y < MAZE_SIZE; y++) {
int wall = maze.getWall(x,y);
printbuf[x*2+2][y*2+2] = PILLAR;
if(wall & WALL_TOP){
printbuf[x*2+1][y*2+2] = BAR_H;
}else{
if(showCost){
printbuf[x*2+1][y*2+2] = COST;
}else{
printbuf[x*2+1][y*2+2] = DIRECTION;
}
}
if(wall & WALL_RIGHT){
printbuf[x*2+2][y*2+1] = BAR_V;
}else{
if(showCost){
printbuf[x*2+2][y*2+1] = COST;
}else{
printbuf[x*2+2][y*2+1] = DIRECTION;
}
}
printbuf[x*2+1][y*2+1] = SPACE;
}
}
for(int y = 0; y < MAZE_SIZE; y++) {
printbuf[0][y*2 + 2] = PILLAR_W;
printbuf[0][y*2 + 1] = BAR_V;
printbuf[(MAZE_SIZE * 2)][y*2 + 2] = PILLAR_E;
printbuf[(MAZE_SIZE * 2)][y*2 + 1] = BAR_V;
}
for(int x = 0; x < MAZE_SIZE; x++) {
printbuf[x*2+0][(MAZE_SIZE*2)] = PILLAR_N;
printbuf[x*2+1][(MAZE_SIZE*2)] = BAR_H;
printbuf[x*2+0][0] = PILLAR_S;
printbuf[x*2+1][0] = BAR_H;
}
printbuf[0][0] = PILLAR_SW;
printbuf[MAZE_SIZE*2][0] = PILLAR_SE;
printbuf[0][MAZE_SIZE*2] = PILLAR_NW;
printbuf[MAZE_SIZE*2][MAZE_SIZE*2] = PILLAR_NE;
for(auto it = maze.classicGoal.begin(); it != maze.classicGoal.end(); ++it) {
printbuf[it->x*2+1][it->y*2+1] = GOALPOS;
}
if(agent.x >=0 && agent.x < MAZE_SIZE && agent.y >=0 && agent.y < MAZE_SIZE){
printbuf[agent.x*2+1][agent.y*2+1] = MARK;
}
ostringstream oss;
for(int y = MAZE_SIZE*2; y>=0; y--) {
for(int x = 0; x < MAZE_SIZE*2+1; x++) {
if(printbuf[x][y] == MARK){
oss << attr_maker << makerchar;
}else if(printbuf[x][y] == COST){
//int cost = nodeCost[(((y-1)/2) * MAZE_SIZE*2) + (x-1)];
//oss << attr_cost << setw(2) << right << (cost % 100);
}else if(printbuf[x][y] == DIRECTION){
int dir = nodeDir[(((y-1)/2) * MAZE_SIZE*2) + (x-1)];
oss << attr_dir << dirchar[ dir ];
}else if(printbuf[x][y] == INVALID_DIRECTION){
int dir = nodeDir[(((y-1)/2) * MAZE_SIZE*2) + (x-1)];
oss << attr_invalid_dir << dirchar[ dir ];
}else if(printbuf[x][y] == GOALPOS){
oss << attr_goal << goalchar;
}else if(printbuf[x][y] == INVALID){
oss << attr_unknown << unknownchar;
}else{
oss << attr_wall << wallchar[ printbuf[x][y] ];
}
}
oss << endl;
}
oss << attr_reset;
return oss.str();
}
};
#endif
};
#endif
Raw
Formatter.h
#ifndef __MAZEFORMATTER__
#define __MAZEFORMATTER__
#include <iostream>
#include <iomanip>
#include <sstream>
namespace Maze {
using namespace std;
class Formatter {
public:
virtual string stringFrom(Graph &g) = 0;
};
class PotentialMapFormatter : public Formatter {
public:
string stringFrom(Graph &g)
{
ostringstream oss;
for(int y = g.height()-1; y >= 0; y--) {
for(int x = 0; x < g.width(); x++) {
Node &n = g.node(x,y);
if(n.cost == Maze::InvalidCost){
oss << " *";
}else{
oss << setw(3) << right << (n.cost % 1000);
}
}
oss << endl;
}
return oss.str();
}
};
class DirectionMapFormatter : public Formatter {
public:
string stringFrom(Graph &g)
{
ostringstream oss;
for(int y = g.height()-1; y >= 0; y--) {
for(int x = 0; x < g.width(); x++) {
Node &n = g.node(x,y);
if(n.cost == Maze::InvalidCost){
oss << " *";
}else{
oss << setw(3) << right << (int)n.from.direction;
}
}
oss << endl;
}
return oss.str();
}
};
class MultiByteCharFormatter : public Formatter {
public:
Index agent;
bool colored;
bool showCost;
MultiByteCharFormatter(bool color = false, bool cost = false)
{
agent = Maze::InvalidIndex;
colored = color;
showCost = cost;
}
MultiByteCharFormatter& setAgent(Index idx){
agent = idx;
return *this;
}
string stringFrom(Graph &g)
{
enum {
SPACE = 0, BAR_V, BAR_H, PILLAR, PILLAR_N, PILLAR_W, PILLAR_S, PILLAR_E, PILLAR_NW, PILLAR_NE, PILLAR_SW, PILLAR_SE,
COST, DIRECTION, INVALID_DIRECTION, MARK, GOALPOS, STARTPOS, INVALID,
};
const char *attr_wall = "";
const char *attr_dir = "";
const char *attr_invalid_dir = "";
const char *attr_cost = "";
const char *attr_goal = "";
const char *attr_maker = "";
const char *attr_unknown = "";
const char *attr_reset = "";
const char *wallchar[] = {"　","┃","━","╋","┳","┣","┻","┫","┏","┓","┗","┛"};
const char *dirchar[] = {"→","↗","↗","↑","↖","↖","←","↙","↙","↓","↘","↘"};
const char *makerchar = "＠";
const char *goalchar = "Ｇ";
const char *unknownchar = "??";
if (colored) {
attr_wall = "\033[0;30m";
attr_dir = "\033[1;36m";
attr_invalid_dir = "\033[;30m";
attr_cost = "\033[m";
attr_goal = "\033[1;31m";
attr_maker = "\033[1;33m";
attr_unknown = "\033[0;30m";
attr_reset = "\033[m";
}
uint8_t printbuf[MAZE_SIZE*2+1][MAZE_SIZE*2+1];
for(int x = 0; x < MAZE_SIZE; x++) {
for(int y = 0; y < MAZE_SIZE; y++) {
int wall = g.maze.getWall(x,y);
printbuf[x*2+2][y*2+2] = PILLAR;
if(wall & WALL_TOP){
printbuf[x*2+1][y*2+2] = BAR_H;
}else{
printbuf[x*2+1][y*2+2] = SPACE;
}
if(wall & WALL_RIGHT){
printbuf[x*2+2][y*2+1] = BAR_V;
}else{
printbuf[x*2+2][y*2+1] = SPACE;
}
if(g.node(x,y).cost != Maze::InvalidCost){
if(showCost){
printbuf[x*2+1][y*2+1] = COST;
}else{
if(wall & WALL_VALID){
printbuf[x*2+1][y*2+1] = DIRECTION;
}else{
printbuf[x*2+1][y*2+1] = INVALID_DIRECTION;
}
}
}else{
printbuf[x*2+1][y*2+1] = INVALID;
}
}
}
for(int y = 0; y < MAZE_SIZE; y++) {
printbuf[0][y*2 + 2] = PILLAR_W;
printbuf[0][y*2 + 1] = BAR_V;
printbuf[(MAZE_SIZE * 2)][y*2 + 2] = PILLAR_E;
printbuf[(MAZE_SIZE * 2)][y*2 + 1] = BAR_V;
}
for(int x = 0; x < MAZE_SIZE; x++) {
printbuf[x*2+0][(MAZE_SIZE*2)] = PILLAR_N;
printbuf[x*2+1][(MAZE_SIZE*2)] = BAR_H;
printbuf[x*2+0][0] = PILLAR_S;
printbuf[x*2+1][0] = BAR_H;
}
printbuf[0][0] = PILLAR_SW;
printbuf[MAZE_SIZE*2][0] = PILLAR_SE;
printbuf[0][MAZE_SIZE*2] = PILLAR_NW;
printbuf[MAZE_SIZE*2][MAZE_SIZE*2] = PILLAR_NE;
for(auto it = g.maze.classicGoal.begin(); it != g.maze.classicGoal.end(); ++it) {
printbuf[it->x*2+1][it->y*2+1] = GOALPOS;
}
if(agent.x >=0 && agent.x < MAZE_SIZE && agent.y >=0 && agent.y < MAZE_SIZE){
printbuf[agent.x*2+1][agent.y*2+1] = MARK;
}
ostringstream oss;
for(int y = MAZE_SIZE*2; y>=0; y--) {
for(int x = 0; x < MAZE_SIZE*2+1; x++) {
if(printbuf[x][y] == MARK){
oss << attr_maker << makerchar;
}else if(printbuf[x][y] == COST){
oss << attr_cost << setw(2) << right << (g.node(x/2,y/2).cost % 100);
}else if(printbuf[x][y] == DIRECTION){
int dir = g.node(x/2, y/2).from.direction;
oss << attr_dir << dirchar[ dir ];
}else if(printbuf[x][y] == INVALID_DIRECTION){
int dir = g.node(x/2, y/2).from.direction;
oss << attr_invalid_dir << dirchar[ dir ];
}else if(printbuf[x][y] == GOALPOS){
oss << attr_goal << goalchar;
}else if(printbuf[x][y] == INVALID){
oss << attr_unknown << unknownchar;
}else{
oss << attr_wall << wallchar[ printbuf[x][y] ];
}
}
oss << endl;
}
oss << attr_reset;
return oss.str();
}
};
};
#endif
Raw
Graph.h
#ifndef __GRAPH__
#define __GRAPH__
#include <iostream>
#include <iomanip>
#include <sstream>
// https://dencity.jp/misc/graph/
namespace Maze {
using namespace std;
struct Edge {
enum {
Right = 0,
RightTop,
TopRight,
Top,
TopLeft,
LeftTop,
Left,
LeftBottom,
BottomLeft,
Bottom,
BottomRight,
RightBottom,
};
int8_t offset;
uint8_t direction;
Edge() : offset(0), direction(0) {}
Edge(int8_t o, uint8_t d) : offset(o), direction(d) {}
Edge reverse()
{
static const int reverse_direction[] = {
Left, BottomLeft, LeftBottom, Bottom, RightBottom, BottomRight, Right, TopRight, RightTop, Top, LeftTop, TopLeft,
};
return Edge(-offset, reverse_direction[direction]);
}
};
struct Node {
Edge from;
uint16_t cost;
Node() : cost(0) {}
Node(Edge f, int c) : from(f), cost(c) {}
};
class Graph {
public:
std::vector<Node> nodes;
Structure &maze;
int defaultStartNode;
std::vector<int> classicGoalNode;
Graph(Structure &maze_) : maze(maze_) {}
virtual ~Graph() {}
virtual void edges(int inode, std::vector<Edge> &es, bool only_use_valid_wall) = 0;
virtual int height(void) = 0;
virtual int width(void) = 0;
void clear(void)
{
nodes.assign(this->width() * this->height(), Node(Edge(),Maze::InvalidCost));
}
Node &node(int inode)
{
return nodes[inode];
}
Node &node(int x, int y)
{
return nodes[(y * this->width()) + x];
}
Node &node(Index idx)
{
return nodes[(idx.y * this->width()) + (idx.x * (this->width() / this->height()))];
}
int manhattan(int a, int b)
{
return abs(a / this->width() - b / this->width()) + abs(a % this->width() - b % this->width());
}
string makeRunSequence(int inode, int direction)
{
static const char* command_table[12][12] = {
{ "F","L","*","L","*","UR","UF","UL","*","B","*","R" },
{ "*","*","D","F","L","*","*","*","UR","UF","UL","*" },
{ "F","D","*","*","*","UR","UF","UL","*","*","*","R" },
{ "R","*","R","F","L","*","L","*","UR","UF","UL","*" },
{ "UF","UL","*","*","*","D","F","L","*","*","*","UR" },
{ "*","*","R","F","D","*","*","*","UR","UF","UL","*" },
{ "UF","UL","*","R","*","R","F","L","*","L","*","UR" },
{ "*","*","UR","UF","UL","*","*","*","D","F","L","*" },
{ "UF","UL","*","*","*","R","F","D","*","*","*","UR" },
{ "L","*","UR","UF","UL","*","R","*","R","F","L","*" },
{ "F","L","*","*","*","UR","UF","UL","*","*","*","D" },
{ "*","*","UR","UF","UL","*","*","*","R","F","D","*" },
};
string seq = "";
do {
Node &n = this->node(inode);
if(n.cost == 0){
seq += 'S';
break;
}
seq += command_table[direction][n.from.direction];
inode = n.from.offset + inode;
direction = n.from.direction;
} while(1);
return seq;
}
};
// 直交グラフ
class OrthogonalGraph : public Graph {
public:
OrthogonalGraph(Structure &m) : Graph(m)
{
defaultStartNode = 0;
classicGoalNode.push_back((MAZE_SIZE * 7) + 7);
classicGoalNode.push_back((MAZE_SIZE * 8) + 7);
classicGoalNode.push_back((MAZE_SIZE * 7) + 8);
classicGoalNode.push_back((MAZE_SIZE * 8) + 8);
}
void edges(int inode, std::vector<Edge> &es, bool only_use_valid_wall)
{
int w = maze.getWall(Index(inode%MAZE_SIZE, inode/MAZE_SIZE));
if(!only_use_valid_wall || (w & WALL_VALID)){
if(!(w & WALL_RIGHT)) es.push_back(Edge( 1, Edge::Right));
if(!(w & WALL_TOP)) es.push_back(Edge( MAZE_SIZE, Edge::Top));
if(!(w & WALL_LEFT)) es.push_back(Edge( -1, Edge::Left));
if(!(w & WALL_BOTTOM)) es.push_back(Edge(-MAZE_SIZE, Edge::Bottom));
}
}
int height(void) {
return MAZE_SIZE;
}
int width(void) {
return MAZE_SIZE;
}
};
// 斜めグラフ
class DiagonalGraph : public Graph {
public:
// XY座標をノードのインデックスに変換
// 水平ノード 0 垂直ノード 1
#define isHNode(__node__) ((__node__ & 1) == 0)
#define NodeIndex(x,y) (((y) * MAZE_SIZE * 2) + ((x) * 2))
#define MazeIndex(__node__) (Index(((__node__)>>1)%MAZE_SIZE,((__node__)>>1)/MAZE_SIZE))
// ノードの移動に使うマクロ
#define RightNode(__node__) ((__node__) + 1)
#define TopNode(__node__) ((__node__) + (MAZE_SIZE*2))
#define LeftNode(__node__) ((__node__) - 1)
#define BottomNode(__node__)((__node__) - (MAZE_SIZE*2))
DiagonalGraph(Structure &m) : Graph(m)
{
defaultStartNode = 0;
classicGoalNode.push_back(NodeIndex(7,7));
classicGoalNode.push_back(RightNode(NodeIndex(7,7)));
classicGoalNode.push_back(LeftNode(NodeIndex(8,8)));
classicGoalNode.push_back(BottomNode(NodeIndex(8,8)));
}
void edges(int inode, std::vector<Edge> &es, bool only_use_valid_wall)
{
if(isHNode(inode)){
int m = 0;
int w = maze.getWall(MazeIndex(inode));
// 未探索部分を使わない場合、有効な壁かどうかをチェックする
if(!only_use_valid_wall || (w & WALL_VALID)){
if(!(w & WALL_RIGHT)){ es.push_back(Edge(RightNode(m),Edge::BottomRight));}
if(!(w & WALL_LEFT)){ es.push_back(Edge(LeftNode(m),Edge::BottomLeft));}
if(!(w & WALL_BOTTOM)){ es.push_back(Edge(BottomNode(m),Edge::Bottom));}
}
m = TopNode(0);
w = maze.getWall(MazeIndex(inode + m));
if(!only_use_valid_wall || (w & WALL_VALID)){
if(!(w & WALL_RIGHT)){ es.push_back(Edge(RightNode(m),Edge::TopRight));}
if(!(w & WALL_TOP)){ es.push_back(Edge(m,Edge::Top));}
if(!(w & WALL_LEFT)){ es.push_back(Edge(LeftNode(m),Edge::TopLeft));}
}
}else{
int m = RightNode(0);
int w = maze.getWall(MazeIndex(inode + m));
if(!only_use_valid_wall || (w & WALL_VALID)){
if(!(w & WALL_TOP)){ es.push_back(Edge(m,Edge::RightTop));}
if(!(w & WALL_RIGHT)){ es.push_back(Edge(RightNode(m),Edge::Right));}
if(!(w & WALL_BOTTOM)){ es.push_back(Edge(BottomNode(m),Edge::RightBottom));}
}
m = LeftNode(0);
w = maze.getWall(MazeIndex(inode + m));
if(!only_use_valid_wall || (w & WALL_VALID)){
if(!(w & WALL_TOP)){ es.push_back(Edge(m,Edge::LeftTop));}
if(!(w & WALL_LEFT)){ es.push_back(Edge(LeftNode(m),Edge::Left));}
if(!(w & WALL_BOTTOM)){ es.push_back(Edge(BottomNode(m),Edge::LeftBottom));}
}
}
}
int height(void) {
return MAZE_SIZE;
}
int width(void) {
return MAZE_SIZE * 2;
}
};
};
#endif
Raw
main.cpp
#include "Maze.h"
#include "cola.hpp"
using namespace std;
int main(int argc, const char *argv[])
{
Maze::Graph *graph;
Maze::Search *search;
cola::parser parser;
parser.define("cost", "print potential map").alias("c");
parser.define("dir", "print direction map").alias("d");
parser.define("astar", "use A* algorithm");
parser.define("depth", "use depth-first algorithm");
parser.define("dia", "use Diagonal path algorithm");
parser.parse(argc,argv);
Maze::Structure maze;
maze.readFromFile(parser.rest_args()[0].c_str());
if(parser.is_passed("dia")) {
graph = new Maze::DiagonalGraph(maze);
}else{
graph = new Maze::OrthogonalGraph(maze);
}
if(parser.is_passed("astar")) {
search = new Maze::AStar(*graph);
}else if(parser.is_passed("depth")) {
search = new Maze::DepthFirstSearch(*graph);
}else{
search = new Maze::BreadthFirstSearch(*graph);
}
search->start(graph->defaultStartNode, graph->classicGoalNode);
if(parser.is_passed("cost")) {
cout << Maze::PotentialMapFormatter().stringFrom(*graph);
}else if(parser.is_passed("dir")) {
cout << Maze::DirectionMapFormatter().stringFrom(*graph);
}else{
cout << parser.rest_args()[0] << endl;
cout << "Maximum Points " << search->maximumPoints << " Number of Searches " << search->numberOfSearches << endl;
cout << Maze::MultiByteCharFormatter().stringFrom(*graph);
cout << graph->makeRunSequence(graph->defaultStartNode, Maze::Edge::Top) << endl;
cout << Maze::PotentialMapFormatter().stringFrom(*graph);
cout << Maze::DirectionMapFormatter().stringFrom(*graph);
}
delete search;
delete graph;
}
Raw
Maze.h
#ifndef __MAZE__
#define __MAZE__
#include "Structure.h"
#include "Graph.h"
#include "Search.h"
#include "Formatter.h"
#include "PathFinder.h"
#include "SmoothPath.h"
#include "DiagonalPath.h"
#endif
Raw
Operation.h
#ifndef __OPERATION__
#define __OPERATION__
namespace Maze {
using namespace std;
#define OP_STOP (0x00)
#define OP_STRAIGHT (0x10)
#define OP_DIAGONAL (0x30)
#define OP_TURN (0x50)
#define OP_END (0x70)
#define FWD0 (OP_STRAIGHT + 0)
#define FWD1 (OP_STRAIGHT + 1)
#define FWD2 (OP_STRAIGHT + 2)
#define FWD3 (OP_STRAIGHT + 3)
#define FWD4 (OP_STRAIGHT + 4)
#define FWD5 (OP_STRAIGHT + 5)
#define FWD6 (OP_STRAIGHT + 6)
#define FWD7 (OP_STRAIGHT + 7)
#define FWD8 (OP_STRAIGHT + 8)
#define FWD9 (OP_STRAIGHT + 9)
#define FWD10 (OP_STRAIGHT + 10)
#define FWD11 (OP_STRAIGHT + 11)
#define FWD12 (OP_STRAIGHT + 12)
#define FWD13 (OP_STRAIGHT + 13)
#define FWD14 (OP_STRAIGHT + 14)
#define FWD15 (OP_STRAIGHT + 15)
#define DIA0 (OP_DIAGONAL + 0)
#define DIA1 (OP_DIAGONAL + 1)
#define DIA2 (OP_DIAGONAL + 2)
#define DIA3 (OP_DIAGONAL + 3)
#define DIA4 (OP_DIAGONAL + 4)
#define DIA5 (OP_DIAGONAL + 5)
#define DIA6 (OP_DIAGONAL + 6)
#define DIA7 (OP_DIAGONAL + 7)
#define DIA8 (OP_DIAGONAL + 8)
#define DIA9 (OP_DIAGONAL + 9)
#define DIA10 (OP_DIAGONAL + 10)
#define DIA11 (OP_DIAGONAL + 11)
#define DIA12 (OP_DIAGONAL + 12)
#define DIA13 (OP_DIAGONAL + 13)
#define DIA14 (OP_DIAGONAL + 14)
#define DIA15 (OP_DIAGONAL + 15)
#define IP45R (OP_TURN + 0)
#define IP45L (OP_TURN + 1)
#define IP90R (OP_TURN + 2)
#define IP90L (OP_TURN + 3)
#define IP135R (OP_TURN + 4)
#define IP135L (OP_TURN + 5)
#define IP180R (OP_TURN + 6)
#define IP180L (OP_TURN + 7)
#define SS90SR (OP_TURN + 8)
#define SS90SL (OP_TURN + 9)
#define SS90FR (OP_TURN + 10)
#define SS90FL (OP_TURN + 11)
#define SS180R (OP_TURN + 12)
#define SS180L (OP_TURN + 13)
#define SD45R (OP_TURN + 14)
#define SD45L (OP_TURN + 15)
#define SD135R (OP_TURN + 16)
#define SD135L (OP_TURN + 17)
#define DS45R (OP_TURN + 18)
#define DS45L (OP_TURN + 19)
#define DS135R (OP_TURN + 20)
#define DS135L (OP_TURN + 21)
#define DD90R (OP_TURN + 22)
#define DD90L (OP_TURN + 23)
#define SS90ER (OP_TURN + 24)
#define SS90EL (OP_TURN + 25)
typedef uint8_t Operation;
typedef vector<Operation> OperationList;
static const char *TurnNames[] = {
"IP45R",
"IP45L",
"IP90R",
"IP90L",
"IP135R",
"IP135L",
"IP180R",
"IP180L",
"SS90SR",
"SS90SL",
"SS90FR",
"SS90FL",
"SS180R",
"SS180L",
"SD45R",
"SD45L",
"SD135R",
"SD135L",
"DS45R",
"DS45L",
"DS135R",
"DS135L",
"DD90R",
"DD90L",
"SS90ER",
"SS90EL"
};
};
#endif
Raw
PathFinder.h
#ifndef __PATHFINDER__
#define __PATHFINDER__
namespace Maze {
using namespace std;
class PathFinder {
public:
enum Status { GoToTarget, BackToHome, Finish };
Status status;
int nextDir;
uint32_t totalSearches;
uint32_t totalSteps;
Structure &maze;
Search &search;
Graph &graph;
vector<Index> targets;
string runSequence;
PathFinder(Structure &maze_, Search &search_, Graph &graph_) : maze(maze_), search(search_), graph(graph_) {
}
virtual ~PathFinder(){}
void update(Index current, int wall)
{
if(status != Finish){
bool only_use_valid_wall = false;
// 壁情報更新
if(!(maze.getWall(current) & WALL_VALID))
maze.setWall(current, wall);
// 目標に到達したかチェック
auto it = std::find(targets.begin(), targets.end(), current);
if (it != targets.end()) {
if (status == GoToTarget) {
// ゴールとスタートを入れ替える
targets.clear();
targets.push_back(maze.start);
status = BackToHome;
}else{
targets = maze.classicGoal;
only_use_valid_wall = true;
status = Finish;
}
}
// 経路情報作りなおし
if(search.start(current, targets, only_use_valid_wall)){
totalSearches += search.numberOfSearches;
}else{
status = Finish;
}
//nextDir = maze.getDir(current);
nextDir = graph.node(current).from.direction;
// 袋小路だったら封鎖
if(maze.nWall(current) >= 3){
if(current != maze.start){
maze.setWall(current, WALL_BLOCKED);
}
}
totalSteps++;
}
}
void reset(void)
{
status = GoToTarget;
targets = maze.classicGoal;
totalSearches = 0;
totalSteps = 0;
nextDir = Maze::Edge::Top;
}
};
};
#endif
Raw
Sample.h
#ifndef __MAZE_DATA__
#define __MAZE_DATA__
#include "Maze.h"
const uint8_t maze_2011_classic_expert_final[MAZE_SIZE][MAZE_SIZE]={{14,4,4,6,6,6,7,13,13,13,12,6,6,6,4,5},{12,1,10,4,5,13,12,0,0,0,0,4,6,6,3,9},{9,8,5,11,11,8,3,11,11,9,11,11,12,6,5,9},{9,11,10,5,12,2,6,6,5,9,12,6,1,12,1,9},{8,6,6,2,2,4,6,6,3,10,3,13,11,9,9,9},{8,6,7,12,6,3,12,6,4,5,14,2,6,3,11,9},{8,6,4,2,7,12,0,6,3,8,5,12,6,4,6,1},{8,5,10,6,7,9,10,4,5,9,9,8,4,2,4,1},{9,10,6,6,5,10,5,10,3,9,9,9,10,4,3,9},{8,6,7,12,3,14,2,5,14,2,1,10,5,10,5,9},{9,12,5,10,6,5,14,2,5,12,2,5,10,4,3,9},{8,3,10,4,6,2,5,14,2,0,6,2,4,1,14,1},{8,5,12,2,5,14,2,5,14,2,4,6,1,9,14,1},{9,8,3,14,1,13,12,3,13,13,10,5,10,0,6,1},{8,1,13,13,9,9,10,5,8,2,5,10,6,2,6,1},{11,10,2,2,2,2,6,2,3,15,10,6,6,6,6,3}};
const uint8_t maze_2012_classic_expert_final[MAZE_SIZE][MAZE_SIZE]={{14,6,5,12,5,12,6,4,4,6,4,6,4,6,6,5},{12,6,3,9,9,9,12,1,10,5,10,5,9,12,6,3},{10,6,4,3,9,8,3,8,5,8,5,9,9,10,6,5},{12,6,3,13,9,9,12,3,9,9,10,1,10,6,5,9},{8,6,4,2,2,2,2,6,2,2,7,10,6,4,3,9},{9,13,9,12,6,4,6,6,6,6,6,6,5,8,5,9},{9,8,3,8,6,2,6,6,6,4,6,5,9,11,10,1},{9,9,12,2,4,6,4,4,4,2,4,1,9,12,5,9},{9,9,9,12,2,6,3,10,3,14,3,9,9,9,9,9},{9,9,10,2,4,5,12,6,6,6,6,3,9,9,9,9},{9,10,6,5,9,9,10,4,6,5,12,5,9,9,9,9},{9,12,6,3,10,2,5,10,5,10,3,10,2,3,10,3},{9,10,6,6,5,13,8,5,8,4,6,5,12,6,6,5},{9,12,4,5,10,1,11,8,1,8,5,9,9,12,6,3},{9,9,9,10,6,2,5,11,10,3,10,2,3,10,6,5},{10,3,10,6,6,6,2,6,6,6,6,6,6,6,6,3}};
const uint8_t maze_2012_classic_freshman_final[MAZE_SIZE][MAZE_SIZE]={{14,6,6,5,14,7,12,6,5,12,6,4,6,6,6,5},{12,5,15,10,6,6,3,15,8,1,15,11,14,7,12,1},{9,10,6,6,6,4,4,6,3,8,4,6,6,6,3,9},{9,12,6,6,4,1,9,12,7,9,10,4,6,6,5,9},{9,10,6,4,3,9,9,11,15,9,15,10,4,6,3,9},{9,13,12,2,6,3,10,6,6,2,6,6,2,5,13,9},{9,11,9,12,5,12,4,7,14,4,5,12,5,9,11,9},{10,5,9,9,9,9,9,12,5,9,9,9,9,9,12,3},{15,9,8,3,9,9,11,8,3,11,9,9,10,1,9,15},{12,1,9,15,8,3,13,9,15,13,10,1,15,11,10,5},{9,9,9,12,3,13,9,8,5,9,13,10,4,6,4,1},{9,10,2,2,5,11,11,9,9,11,11,12,3,15,9,9},{8,7,12,5,9,12,5,9,9,13,13,9,12,5,10,1},{9,15,9,9,9,9,9,8,1,8,1,9,9,9,15,9},{8,6,1,10,3,9,9,9,9,9,9,10,3,8,6,1},{10,6,2,6,6,3,10,3,10,3,10,6,6,2,6,3}};
const uint8_t maze_2013_apec_classic[MAZE_SIZE][MAZE_SIZE]={{14,6,4,6,6,6,6,6,6,6,6,6,6,6,6,5},{12,6,2,6,6,6,6,6,6,6,6,6,6,6,5,9},{9,12,6,5,12,6,6,6,5,12,6,6,6,5,9,9},{9,9,13,9,9,12,5,12,3,9,12,4,7,9,9,9},{9,9,9,9,9,9,10,3,13,10,3,10,5,9,9,9},{9,9,9,10,3,10,4,6,2,6,6,6,3,9,9,9},{9,10,2,6,6,5,10,6,6,6,6,5,12,1,9,9},{9,12,6,6,6,3,13,12,5,13,12,3,9,9,9,9},{9,9,13,13,12,6,1,10,1,8,3,12,3,11,9,9},{9,9,9,8,3,12,3,12,3,9,12,2,7,13,9,9},{9,9,8,3,12,3,12,1,12,3,10,6,5,8,1,9},{9,10,3,12,3,12,3,11,9,12,5,13,10,1,9,9},{9,13,12,3,12,0,6,5,9,9,9,8,5,9,9,9},{9,8,3,12,3,9,14,1,10,3,9,9,9,9,9,9},{9,10,6,2,6,2,6,2,6,7,10,3,10,3,9,9},{10,6,6,6,6,6,6,6,6,6,6,6,6,6,2,3}};
const uint8_t maze_2013_classic_expert_final[MAZE_SIZE][MAZE_SIZE]={{14,6,6,6,6,6,6,6,6,6,6,6,6,4,4,5},{12,6,6,4,4,5,12,5,12,4,5,13,13,11,9,11},{8,7,12,3,9,9,9,9,9,9,8,0,0,5,10,5},{8,7,10,5,9,10,3,10,3,8,3,11,9,10,5,9},{9,14,4,3,10,5,12,6,6,3,12,5,10,6,1,9},{9,12,1,12,6,3,8,5,12,6,3,10,6,5,9,9},{9,9,11,10,5,12,3,10,3,13,13,13,13,9,9,9},{9,10,5,12,1,10,5,12,4,0,0,0,0,1,9,9},{9,12,3,9,9,12,3,10,3,9,11,11,11,9,9,9},{9,9,12,2,3,10,5,12,5,10,5,12,6,3,9,9},{9,9,8,5,12,7,10,3,10,6,3,10,5,13,9,9},{9,8,3,10,2,6,5,12,7,12,6,6,3,8,3,9},{9,10,6,6,5,13,10,2,6,3,12,6,4,3,14,1},{8,6,4,7,10,2,6,6,6,6,3,13,9,12,6,3},{9,13,10,6,6,6,6,6,6,6,6,2,3,10,6,5},{10,2,6,6,6,6,6,6,6,6,6,6,6,6,6,3}};
const uint8_t maze_2014_classic_expert_final[MAZE_SIZE][MAZE_SIZE]={{14,6,6,6,6,6,6,6,6,6,6,6,6,6,6,5},{12,6,6,6,6,6,6,6,6,6,6,6,6,6,6,3},{8,6,6,6,6,6,6,6,6,6,6,6,6,6,4,5},{8,5,14,4,6,6,6,6,5,12,5,13,13,13,11,9},{11,8,7,8,4,7,12,6,3,9,8,0,0,0,5,9},{12,3,13,11,8,5,10,5,13,9,11,11,11,11,9,9},{9,12,0,5,11,8,5,10,2,0,6,6,6,5,9,9},{9,9,11,8,5,11,8,4,5,8,7,12,5,9,9,9},{9,10,5,11,8,5,11,10,1,10,5,9,9,9,9,9},{9,14,0,5,11,8,5,14,2,5,10,3,9,9,9,9},{9,12,3,8,5,11,8,5,14,2,5,13,9,9,9,9},{9,10,4,3,10,5,11,8,5,14,2,1,9,9,9,9},{9,12,2,5,12,0,5,11,8,5,14,2,3,9,9,9},{10,2,6,2,3,11,8,7,9,8,4,7,12,3,9,9},{12,6,6,6,6,6,3,12,0,1,10,4,3,12,3,9},{10,6,6,6,6,6,6,3,11,10,6,2,7,10,6,3}};
const uint8_t maze_2015_classic_expert_final[MAZE_SIZE][MAZE_SIZE]={{14,5,12,6,6,6,6,6,6,6,6,6,6,6,6,5},{12,2,3,13,13,14,4,6,6,6,6,6,6,6,5,9},{9,12,6,0,2,5,10,6,6,6,6,6,6,5,9,9},{9,9,12,2,5,10,5,14,4,6,6,6,6,3,9,9},{9,10,0,7,10,5,10,5,10,4,4,4,6,5,9,9},{10,5,10,5,12,0,7,10,5,11,9,11,12,1,9,9},{13,8,7,8,1,11,12,5,10,5,11,12,1,9,9,9},{8,3,12,3,10,4,3,8,5,10,4,3,9,9,9,9},{8,5,10,5,12,2,5,8,3,12,2,5,9,9,9,9},{11,8,7,8,1,13,10,3,12,3,13,10,1,9,9,9},{12,3,12,3,10,0,7,12,1,12,2,5,10,1,9,9},{9,14,0,7,12,3,12,3,8,3,12,0,7,9,9,9},{10,5,10,4,3,12,3,12,3,14,1,11,12,3,9,9},{12,3,13,10,4,3,13,10,5,13,10,4,3,12,1,9},{9,12,0,5,11,12,0,5,8,0,7,11,14,3,11,9},{10,3,11,10,6,3,11,10,3,11,14,6,6,6,6,3}};
const uint8_t maze_2016_classic_expert_final[MAZE_SIZE][MAZE_SIZE]={{14,4,6,6,6,6,6,6,6,6,6,6,6,6,6,5},{12,3,12,4,6,6,6,6,6,6,4,6,6,5,12,3},{9,12,3,9,12,6,6,6,6,5,10,4,5,9,10,5},{9,9,12,1,9,12,6,6,6,3,12,3,9,10,5,9},{9,9,9,10,1,10,6,6,6,5,10,5,9,12,3,9},{9,9,8,7,10,5,14,4,5,9,12,3,9,10,6,1},{9,9,10,5,12,3,12,3,10,3,10,5,9,12,5,11},{9,10,5,9,10,5,9,12,5,12,4,3,10,3,10,5},{8,7,9,9,12,3,9,10,1,11,10,5,14,5,12,3},{9,12,1,9,10,5,9,14,0,7,12,2,4,2,2,5},{9,9,9,9,12,3,9,14,0,7,10,5,8,6,6,3},{9,8,1,9,10,5,9,14,0,7,12,3,10,6,6,5},{9,9,9,9,12,3,9,14,0,7,10,4,6,6,5,9},{9,9,10,3,10,5,9,12,0,5,12,2,7,13,9,9},{9,10,5,13,12,3,8,1,11,9,10,6,6,1,9,11},{10,6,2,3,10,6,3,10,6,2,6,6,6,3,10,7}};
struct {
const char *name;
const uint8_t *data;
} MazeDataTable[] = {
{ "2011 Classic Expert Final", &maze_2011_classic_expert_final[0][0] },
{ "2012 Classic Expert Final", &maze_2012_classic_expert_final[0][0] },
{ "2012 Classic Freshman Final",&maze_2012_classic_freshman_final[0][0] },
{ "2013 Classic Expert Final", &maze_2013_classic_expert_final[0][0] },
{ "2013 Apec Classic", &maze_2013_apec_classic[0][0] },
{ "2014 Classic Expert Final", &maze_2014_classic_expert_final[0][0] },
{ "2015 Classic Expert Final", &maze_2015_classic_expert_final[0][0] },
{ "2016 Classic Expert Final", &maze_2016_classic_expert_final[0][0] },
};
#define NUM_MAZE_DATA (sizeof(MazeDataTable)/sizeof(MazeDataTable[0]))
#endif
Raw
search.cpp
#include "Maze.h"
#include "cola.hpp"
using namespace std;
void clearscreen(void) {
cout << "\033[2J";
}
void cursor(int x,int y) {
cout << "\033[" << int(x) << ";" << int(y) << "H";
};
void clearline(void) {
cout << "\033[2K";
}
void waitMove(void)
{
getchar();
}
int main(int argc, char *argv[])
{
cola::parser parser;
parser.define("simulate", "Maze search simulation").alias("s");
parser.define("astar", "use A* algorithm");
parser.define("depth", "use depth-first algorithm");
parser.define("nocolor", "do not use attributed color");
parser.define("dia", "use Diagonal path algorithm");
parser.parse(argc,argv);
bool simulate = parser.is_passed("simulate");
Maze::Structure maze;
Maze::Structure mazedata;
Maze::MultiByteCharFormatter fmt(!parser.is_passed("nocolor"));
Maze::Graph *graph;
Maze::Search *search;
mazedata.readFromFile(parser.rest_args()[0].c_str());
if(simulate){
clearscreen();
}
if(parser.is_passed("dia")) {
graph = new Maze::DiagonalGraph(maze);
}else{
graph = new Maze::OrthogonalGraph(maze);
}
if(parser.is_passed("astar")) {
search = new Maze::AStar(*graph);
}else if(parser.is_passed("depth")) {
search = new Maze::DepthFirstSearch(*graph);
}else{
search = new Maze::BreadthFirstSearch(*graph);
}
// 経路情報作成
Maze::Index current;
Maze::PathFinder pfinder(maze, *search, *graph);
Maze::SmoothPath smpath;
int lastDir = Maze::Edge::Top;
pfinder.reset();
do {
if (pfinder.status == Maze::PathFinder::Finish) {
break;
}
// 迷路更新
pfinder.update(current, mazedata.getWall(current));
if(simulate){
// 迷路表示
cursor(1,1);
cout << fmt.setAgent(current).stringFrom(*graph);
cout << Maze::PotentialMapFormatter().stringFrom(*graph);
//cout << endl;
//cout << Maze::DirectionMapFormatter().stringFrom(*graph);
cout << "Agent x " << setw(3) << (int)current.x << " y " << setw(3) << (int)current.y << endl;
cout << "Maximum Points " << setw(3) << search->maximumPoints << " Number of Searches " << setw(3) << search->numberOfSearches << endl;
cout << "Total Searches " << setw(4) << pfinder.totalSearches << " Total Step " << setw(4) << pfinder.totalSteps << endl;
//cout << graph->makeRunSequence(graph->defaultStartNode, Maze::Edge::Top) << endl;
//smpath.makeOperationList(pfinder.runSequence);
//cout << smpath.toString() << endl;
}
current = current.neighbour(pfinder.nextDir);
//lastDir = pfinder.nextDir;
// 移動まち
if(simulate){
waitMove();
}
} while(1);
if(simulate){
cursor(1,1);
}
cout << fmt.setAgent(Maze::InvalidIndex).stringFrom(*graph);
cout << Maze::PotentialMapFormatter().stringFrom(*graph);
cout << parser.rest_args()[0] << endl;
cout << "Maximum Points " << setw(3) << search->maximumPoints << " Number of Searches " << setw(3) << search->numberOfSearches << endl;
cout << "Total Searches " << setw(4) << pfinder.totalSearches << " Total Step " << setw(4) << pfinder.totalSteps << endl;
clearline();
cout << pfinder.runSequence << endl;
clearline();
smpath.makeOperationList(pfinder.runSequence);
cout << smpath.toString() << endl;
}
Raw
Search.h
#ifndef __MAZESEARCH__
#define __MAZESEARCH__
#include <queue>
#include <stack>
#include <algorithm>
namespace Maze {
using namespace std;
class Search {
public:
uint32_t maximumPoints; // 分岐数の最大値
uint32_t numberOfSearches; // 探索回数
Search(Graph &g_) : g(g_) {}
virtual ~Search(){}
virtual bool start(Index start_, std::vector<Index> &end_, bool only_use_valid_wall = false) {
std::vector<int> end;
// クリア
g.clear();
// 初期コスト設定
for(auto it = end_.begin(); it != end_.end(); ++it) {
Index idx = *it;
int inode = idx.y * g.width() + idx.x;
g.node(inode).cost = 0;
end.push_back(inode);
}
return search_impl(start_.y * g.width() + start_.x, end, only_use_valid_wall);
}
virtual bool start(int start_, std::vector<int> &end_, bool only_use_valid_wall = false) {
// クリア
g.clear();
// 初期コスト設定
for(auto it = end_.begin(); it != end_.end(); ++it) {
g.node(*it).cost = 0;
}
return search_impl(start_, end_, only_use_valid_wall);
}
virtual bool search_impl(int start_, std::vector<int> &end_, bool only_use_valid_wall) = 0;
protected:
Graph &g;
};
class BreadthFirstSearch : public Search {
public:
BreadthFirstSearch(Graph &g_) : Search(g_) {}
bool search_impl(int start_, std::vector<int> &end_, bool only_use_valid_wall)
{
bool found = false;
std::queue<int> search_q;
// キューに探索点を追加
for(auto it = end_.begin(); it != end_.end(); ++it) {
search_q.push(*it);
}
// 統計情報クリア
maximumPoints = numberOfSearches = 0;
// キューが空になるか start_ が見つかるまでループ
std::vector<Edge> edges;
while(search_q.empty() == 0 /*&& !found*/){
maximumPoints = max(uint32_t(search_q.size()), maximumPoints);
numberOfSearches++;
int inode = search_q.front();
search_q.pop();
edges.clear();
g.edges(inode, edges, only_use_valid_wall);
Node &n = g.node(inode);
for(auto e : edges){
int enode = inode + e.offset;
Node &m = g.node(enode);
Cost cur = n.cost + 1;
Cost old = m.cost;
if(cur < old){
m.from = e.reverse();
m.cost = cur;
if(old != Maze::InvalidCost){
;
} else {
if (enode == start_){
found = true;
}
search_q.push(enode);
}
}
}
}
return found;
}
};
class DepthFirstSearch : public Search {
public:
DepthFirstSearch(Graph &g_) : Search(g_) {}
bool search_impl(int start_, std::vector<int> &end_, bool only_use_valid_wall)
{
bool found = false;
std::stack<int> search_q;
// キューに探索点を追加
for(auto it = end_.begin(); it != end_.end(); ++it) {
search_q.push(*it);
}
// 統計情報クリア
maximumPoints = numberOfSearches = 0;
// キューが空になるか start_ が見つかるまでループ
std::vector<Edge> edges;
while(search_q.empty() == 0 && !found){
maximumPoints = max(uint32_t(search_q.size()), maximumPoints);
numberOfSearches++;
int inode = search_q.top();
search_q.pop();
edges.clear();
g.edges(inode, edges, only_use_valid_wall);
Node &n = g.node(inode);
for(auto e : edges){
int enode = inode + e.offset;
Node &m = g.node(enode);
Cost cur = n.cost + 1;
Cost old = m.cost;
if(cur < old){
m.from = e.reverse();
m.cost = cur;
if(old != Maze::InvalidCost){
;
} else {
if (enode == start_){
found = true;
}
search_q.push(enode);
}
}
}
}
return found;
}
};
class AStar : public Search {
public:
AStar(Graph &g_) : Search(g_) {}
bool search_impl(int start_, std::vector<int> &end_, bool only_use_valid_wall)
{
bool found = false;
auto comparecost = [&](int l, int r)
{
int gl = g.node(l).cost;
int gr = g.node(r).cost;
int hl = g.manhattan(start_, l);
int hr = g.manhattan(start_, r);
if((gl + hl) == (gr + hr))
return hl > hr;
return (gl + hl) > (gr + hr);
};
std::priority_queue<int, std::vector<int>, decltype(comparecost)> search_q(comparecost);
// キューに探索点を追加
for(auto it = end_.begin(); it != end_.end(); ++it) {
search_q.push(*it);
}
// 統計情報クリア
maximumPoints = numberOfSearches = 0;
// キューが空になるか start_ が見つかるまでループ
std::vector<Edge> edges;
while(search_q.empty() == 0 && !found){
maximumPoints = max(uint32_t(search_q.size()), maximumPoints);
numberOfSearches++;
int inode = search_q.top();
search_q.pop();
edges.clear();
g.edges(inode, edges, only_use_valid_wall);
Node &n = g.node(inode);
//cout << inode << " " << n.cost << endl;
for(auto e : edges){
int enode = inode + e.offset;
Node &m = g.node(enode);
Cost cur = n.cost + 1;
Cost old = m.cost;
if(cur < old){
m.from = e.reverse();
m.cost = cur;
if(old != Maze::InvalidCost){
;
} else {
if (enode == start_){
found = true;
}
search_q.push(enode);
}
}
}
}
return found;
}
};
};
#endif
Raw
SmoothPath.h
#ifndef __SMOOTHPATH__
#define __SMOOTHPATH__
#include "Operation.h"
namespace Maze {
using namespace std;
class SmoothPath {
public:
enum State {
Start,
Ortho,
Ortho_L,
Ortho_R,
Ortho_LL,
Ortho_RR,
Diag_LR,
Diag_RL,
Diag_RR,
Diag_LL,
Stop,
};
OperationList operationList;
SmoothPath() {}
string toString(void) {
string str;
for(auto itr = operationList.begin(); itr != operationList.end(); ++itr) {
Operation c = *itr;
if(c < OP_STRAIGHT) {
str += "STOP,";
}
else if(c < OP_DIAGONAL) {
if(c != FWD0) {
str += "FWD";
str += std::to_string(c & 0xf);
str += ",";
}
}
else if(c < OP_TURN) {
if(c != DIA0) {
str += "DIA";
str += std::to_string(c & 0xf);
str += ",";
}
}
else if(c < OP_END) {
str += TurnNames[c - OP_TURN];
str += ",";
}
}
if(str.size() > 1)
str.pop_back();
return str;
}
void makeOperationList(const string &str) {
int x = 0;
State state = Start;
operationList.clear();
for (size_t i=0; i < str.size(); i++) {
const char c = str[i];
switch(state){
case State::Start:
if(c == 'F'){
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
operationList.push_back(IP90L);
x = 1;
state = State::Ortho;
}
else if(c == 'R'){
operationList.push_back(IP90R);
x = 1;
state = State::Ortho;
}
else if(c == 'U'){
operationList.push_back(IP180R);
x = 1;
state = State::Ortho;
}
else if(c == 'S'){
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Ortho:
if(c == 'F'){
x++;
}
else if(c == 'L'){
operationList.push_back(FWD0 + x);
x = 0;
state = State::Ortho_L;
}
else if(c == 'R'){
operationList.push_back(FWD0 + x);
x = 0;
state = State::Ortho_R;
}
else if(c == 'S'){
operationList.push_back(FWD0 + x + 1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Ortho_L:
if(c == 'F'){
operationList.push_back(SS90SL);
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
state = State::Ortho_LL;
}
else if(c == 'R'){
operationList.push_back(SD45L);
state = State::Diag_LR;
}
else if(c == 'S'){
operationList.push_back(SS90EL);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Ortho_R:
if(c == 'F'){
operationList.push_back(SS90SR);
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
operationList.push_back(SD45R);
state = State::Diag_RL;
}
else if(c == 'R'){
state = State::Ortho_RR;
}
else if(c == 'S'){
operationList.push_back(SS90ER);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Ortho_LL:
if(c == 'F'){
operationList.push_back(SS180L);
x = 1;
state = State::Ortho;
}
else if(c == 'R'){
operationList.push_back(SD135L);
state = State::Diag_LR;
}
else if(c == 'S'){
operationList.push_back(SS180L);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Ortho_RR:
if(c == 'F'){
operationList.push_back(SS180R);
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
operationList.push_back(SD135R);
state = State::Diag_RL;
}
else if(c == 'S'){
operationList.push_back(SS180R);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Diag_RL:
if(c == 'F'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS45L);
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
state = State::Diag_LL;
}
else if(c == 'R'){
x++;
state = State::Diag_LR;
}
else if(c == 'S'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS45L);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Diag_LR:
if(c == 'F'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS45R);
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
x++;
state = State::Diag_RL;
}
else if(c == 'R'){
state = State::Diag_RR;
}
else if(c == 'S'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS45R);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Diag_LL:
if(c == 'F'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS135L);
x = 1;
state = State::Ortho;
}
else if(c == 'R'){
operationList.push_back(DIA0 + x);
operationList.push_back(DD90L);
x = 0;
state = State::Diag_LR;
}
else if(c == 'S'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS135L);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Diag_RR:
if(c == 'F'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS135R);
x = 1;
state = State::Ortho;
}
else if(c == 'L'){
operationList.push_back(DIA0 + x);
operationList.push_back(DD90R);
x = 0;
state = State::Diag_RL;
}
else if(c == 'S'){
operationList.push_back(DIA0 + x);
operationList.push_back(DS135R);
operationList.push_back(FWD1);
operationList.push_back(OP_STOP);
state = State::Stop;
}
break;
case State::Stop:
break;
}
}
}
};
};
#endif
Raw
Structure.h
#ifndef __MAZESTRUCTURE__
#define __MAZESTRUCTURE__
#include <vector>
#include <fstream>
// 迷路のサイズ
#define MAZE_SIZE 16
// 壁情報
#define WALL_RIGHT 0x10 // 右
#define WALL_TOP 0x20 // 上
#define WALL_LEFT 0x40 // 左
#define WALL_BOTTOM 0x80 // 下
#define WALL_VALID 0x08 // 壁情報有効
#define WALL_MASK 0xf0
#define WALL_BLOCKED 0xf0
namespace Maze {
using namespace std;
struct Index {
int8_t x;
int8_t y;
Index() : x(0), y(0) {};
Index(int8_t x_, int8_t y_) : x(x_), y(y_) {};
Index neighbour(int direction) const
{
static const Index offset[] = {{1,0},{1,1},{1,1},{0,1},{-1,1},{-1,1},{-1,0},{-1,-1},{-1,-1},{0,-1},{1,-1},{1,-1}};
return Index(x+offset[direction].x, y+offset[direction].y);
}
int manhattan(Index idx) const
{
return abs(x - idx.x) + abs(y - idx.y);
}
bool operator==(const Index& rhs) const
{
return (rhs.x == x) && (rhs.y == y);
}
bool operator!=(const Index& rhs) const
{
return (rhs.x != x) || (rhs.y != y);
}
inline Index operator+(const Index &obj) const
{
return Index(x+obj.x, y+obj.y);
}
};
typedef uint8_t Block;
typedef uint16_t Cost;
static const Index InvalidIndex = {-1, -1};
static const Cost InvalidCost = 0x0fff;
class Structure
{
public:
Index start;
std::vector<Index> classicGoal;
Block blocks[MAZE_SIZE][MAZE_SIZE];
Structure()
{
initialize();
}
void initialize(void)
{
classicGoal.push_back(Index(7,7));
classicGoal.push_back(Index(8,7));
classicGoal.push_back(Index(7,8));
classicGoal.push_back(Index(8,8));
for(int y = 0; y < MAZE_SIZE; y++) {
for(int x = 0; x < MAZE_SIZE; x++) {
blocks[y][x] = 0;
}
}
for(int y = 0; y < MAZE_SIZE; y++) {
blocks[y][ 0] |= WALL_LEFT;
blocks[y][MAZE_SIZE - 1] |= WALL_RIGHT;
}
for(int x = 0; x < MAZE_SIZE; x++) {
blocks[MAZE_SIZE - 1][x] |= WALL_TOP;
blocks[ 0][x] |= WALL_BOTTOM;
}
blocks[0][0] = WALL_RIGHT;
}
void convert(const uint8_t *src, int mz_size = MAZE_SIZE)
{
uint8_t convert_tbl[][4] = {
// Right Top Left Bottom
{0x02, 0x01, 0x04, 0x08}, /* mice式(http://mice.deca.jp/maze/) */
{0x02, 0x01, 0x08, 0x04}, /* 森永式(http://mmk.rulez.jp/?page_id=297) */
{0x04, 0x02, 0x01, 0x08}, /* 独自1(https://www24.atwiki.jp/mm3sakusya/pages/38.html) */
};
for(int t = 0; t < 3; t++){
const uint8_t *p = src;
for(int x = 0; x < mz_size; x++) {
for(int y = 0; y < mz_size; y++) {
Block w = *p++;
Block d = 0;
for(int j = 0; j<4; j++){
if(w & convert_tbl[t][j]){
d |= WALL_RIGHT << j;
}
}
blocks[y][x] = d | WALL_VALID;
}
}
int invalid = 0;
for(int i = 0; i < mz_size; i++) {
invalid += ((blocks[0][i] & WALL_BOTTOM) == 0);
invalid += ((blocks[mz_size-1][i] & WALL_TOP) == 0);
invalid += ((blocks[i][0] & WALL_LEFT) == 0);
invalid += ((blocks[i][mz_size-1] & WALL_RIGHT) == 0);
}
if(invalid == 0)
break;
}
}
void readFromFile(const char *filename)
{
uint8_t buf[MAZE_SIZE * MAZE_SIZE];
std::ifstream ifs(filename, ios::binary);
if (ifs) {
ifs.read( (char*)buf, sizeof(buf) );
if (ifs.gcount()) {
convert(buf);
}
}
}
void setWall(Index idx, int wall)
{
if(idx.x >=0 && idx.x < MAZE_SIZE && idx.y >=0 && idx.y < MAZE_SIZE){
blocks[idx.y][idx.x] &= ~WALL_MASK;
blocks[idx.y][idx.x] |= (wall & WALL_MASK) | WALL_VALID;
if(idx.x > 0){
blocks[idx.y][idx.x - 1] &= (~WALL_RIGHT);
blocks[idx.y][idx.x - 1] |= (wall & WALL_LEFT) >> 2;
}
if(idx.x < MAZE_SIZE - 1){
blocks[idx.y][idx.x + 1] &= (~WALL_LEFT);
blocks[idx.y][idx.x + 1] |= (wall & WALL_RIGHT) << 2;
}
if(idx.y > 0){
blocks[idx.y - 1][idx.x] &= (~WALL_TOP);
blocks[idx.y - 1][idx.x] |= (wall & WALL_BOTTOM) >> 2;
}
if(idx.y < MAZE_SIZE - 1){
blocks[idx.y + 1][idx.x] &= (~WALL_BOTTOM);
blocks[idx.y + 1][idx.x] |= (wall & WALL_TOP) << 2;
}
}
}
int getWall(int8_t x, int8_t y)
{
if(x >=0 && x < MAZE_SIZE && y >=0 && y < MAZE_SIZE){
return blocks[y][x];
}
return WALL_LEFT | WALL_RIGHT | WALL_TOP | WALL_BOTTOM;
}
int getWall(Index idx)
{
if(idx.x >=0 && idx.x < MAZE_SIZE && idx.y >=0 && idx.y < MAZE_SIZE){
return blocks[idx.y][idx.x];
}
return WALL_LEFT | WALL_RIGHT | WALL_TOP | WALL_BOTTOM;
}
int nWall(Index idx)
{
if(idx.x >=0 && idx.x < MAZE_SIZE && idx.y >=0 && idx.y < MAZE_SIZE){
int wall = blocks[idx.y][idx.x] >> 4;
wall = ((wall & 0x0a)>>1) + (wall & 0x05);
wall = ((wall & 0x0c)>>2) + (wall & 0x03);
return wall;
}
return 4;
}
};
}; // namespace Maze
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment