学步园

/**<br /> * 寻径<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>框架<br /> * by lxslove<br /> * e-mail:moodlxs@163.com<br /> * 用法：<br /> * 注意：编译本框架需要加上-ldl选项<br /> * g++ -ldl src.cpp<br /> *<br /> * 地图文件格式为不同符号的矩阵，具体什么符号代表可通行，什么符号代表不可通行，由自己决定。举个例子：<br /> * ###################<br /> * # ###### ########<br /> * # ###### ##########<br /> * # ##########<br /> * ######## # ####<br /> * ## #### ## ######<br /> * ### # ######### ##<br /> * ###### ##### # # ##<br /> * #### # ##### ######<br /> * ###### #######<br /> * ###################<br /> * 以上的例子，假设空格是可通行的，#是不可通行的。<br /> *<br /> * 具体的算法采用插件的形式，插件（so文件）需要提供find_path函数接口，该函数的形式为：<br /> * extern "C"<br /> * int find_path(size_t start_pos, size_t end_pos, vector<char>* map_data, vector<char>* path_list)<br /> * {<br /> * return 0; //成功则返回0<br /> * }<br /> * 编译so文件的方式例子如下：<br /> * g++ -fPIC -shared -o 1.so 1.cpp 1.h<br /> *<br /> * start_pos/end_pos为地图数据在map_data中的位置，path_list暂时没用到<br /> * 在得到路径时，需要在find_path接口方法中修改map_data的符号，标志其为路径，具体修改为什么符号由自己决定，举个例子：<br /> * ###################<br /> * #@######@ ########<br /> * #@######@##########<br /> * #@@@@@@@@##########<br /> * ######## # ####<br /> * ## #### ## ######<br /> * ### # ######### ##<br /> * ###### ##### # # ##<br /> * #### # ##### ######<br /> * ###### #######<br /> * ###################<br /> * 以上例子中，将相应位置的符号修改为@<br /> * 框架会直接显示地图数据，是什么符号就显示什么符号。<br /> * */</p> <p>#define DL cout<br /> #include <stdio.h><br /> #include <string.h><br /> #include <libgen.h><br /> #include <dlfcn.h><br /> #include <sys/time.h><br /> #include <string><br /> #include <fstream><br /> #include <iostream><br /> #include <vector></p> <p>using namespace std;</p> <p>/// 插件接口<br /> // 参数为：<br /> // 开始位置，结束位置，地图数据列表， 路径列表,暂时不用,固定为NULL<br /> typedef int (*pfunc)(size_t, size_t, vector<char>*, vector<char>*);</p> <p>const char* const FUNC_NAME = "find_path";</p> <p>class XJFrame<br /> {<br /> private:<br /> string m_map_path; /// 地图位置<br /> pfunc p_func; /// 插件的接口函数<br /> vector<char> m_map_data; /// 地图数据指针<br /> vector<size_t>* m_p_path_data; /// 路径数据指针<br /> size_t m_map_width; /// 地图宽度<br /> size_t m_map_heigh; /// 地图高度<br /> void * m_p_module; /// 模块指针<br /> struct timeval m_use_time; /// 算法耗时</p> <p> public:<br /> size_t get_map_width()<br /> {<br /> return m_map_width;<br /> }</p> <p> size_t get_map_heigh()<br /> {<br /> return m_map_heigh;<br /> }</p> <p> const struct timeval* get_use_time()<br /> {<br /> return &m_use_time;<br /> }</p> <p> private:<br /> XJFrame(const XJFrame& rv);<br /> XJFrame& operator=(const XJFrame& rv);</p> <p> public:<br /> XJFrame()<br /> :m_map_width(0), m_map_heigh(0), m_p_module(NULL), m_p_path_data(NULL)<br /> {<br /> }</p> <p> XJFrame(const string& map_path)<br /> :m_map_path(map_path), m_map_width(0), m_map_heigh(0), m_p_module(NULL), m_p_path_data(NULL)</p> <p> {<br /> }</p> <p> ~XJFrame()<br /> {<br /> if (m_p_module)<br /> {<br /> dlclose(m_p_module);<br /> m_p_module = NULL;<br /> }<br /> if (m_p_path_data)<br /> {<br /> delete m_p_path_data;<br /> m_p_path_data = NULL;<br /> }<br /> }</p> <p> void set_map_path(const string & map_path)<br /> {<br /> m_map_path = map_path;<br /> }</p> <p> int open_module(const string & module_path)<br /> {<br /> if (module_path.empty())<br /> {<br /> DL << "module_path not setting!\n";<br /> return -1;<br /> }</p> <p> if (m_p_module)<br /> {<br /> dlclose(m_p_module);<br /> m_p_module = NULL;<br /> }</p> <p> void* m_p_module = dlopen(module_path.c_str(), RTLD_LAZY );<br /> if( !m_p_module )<br /> {<br /> DL << "can't open module: " << module_path <<", error:" << dlerror() << "\n";<br /> return -1;<br /> }<br /> p_func = (pfunc)dlsym(m_p_module, FUNC_NAME);<br /> const char *dlsym_error = dlerror();<br /> if (dlsym_error)<br /> {<br /> DL << "load symbol: " << FUNC_NAME << "! err: " << dlsym_error << "\n";<br /> return -1;<br /> }</p> <p> return 0;<br /> }</p> <p> int init_map()<br /> {<br /> if (m_map_path.empty())<br /> {<br /> DL << "map_path not setting!\n";<br /> return -1;<br /> }</p> <p> m_map_data.clear();</p> <p> ifstream in_file(m_map_path.c_str());<br /> if (!in_file)<br /> {<br /> DL << "open file error:" << m_map_path << "\n";<br /> return -1;<br /> }</p> <p> size_t len;<br /> char buffer[1024];<br /> while (!in_file.eof())<br /> {<br /> in_file.getline(buffer, sizeof(buffer));<br /> len = strlen(buffer);<br /> if (len == 0)<br /> {<br /> break;<br /> }</p> <p> //根据第一次的宽度计算地图宽度<br /> if (!m_map_width)<br /> {<br /> m_map_width = len;<br /> }<br /> else if (m_map_width != len)<br /> {<br /> DL << "map format error！0\n";<br /> return -1;<br /> }</p> <p> //计算地图高度<br /> ++m_map_heigh;</p> <p> //读取地图信息<br /> for (size_t i = 0; i < len; ++i)<br /> {<br /> if ((*(buffer + i)) != ' ' && (*(buffer + i)) != '#')<br /> {<br /> DL << "map format error！2\n";<br /> return -1;<br /> }<br /> else<br /> {<br /> m_map_data.push_back(*(buffer + i));<br /> }<br /> }<br /> }</p> <p> in_file.close();</p> <p> return 0;<br /> }</p> <p> void display_map()<br /> {<br /> if (m_map_data.empty())<br /> {<br /> DL << "Please load map before!" << endl;<br /> return ;<br /> }</p> <p> DL << "Map Info: width:" << m_map_width << ", heigh:" << m_map_heigh << endl;<br /> for (int i = 0; i < m_map_data.size(); ++i)<br /> {<br /> DL << m_map_data[i];<br /> if ((i + 1) % m_map_width == 0)<br /> {<br /> DL << "\n";<br /> }<br /> }<br /> }</p> <p> int find_path(size_t start_pos, size_t end_pos)<br /> {<br /> if (m_map_data.empty())<br /> {<br /> DL << "Please load map before!" << endl;<br /> return -1;<br /> }<br /> struct timeval tvs, tve;<br /> gettimeofday(&tvs, NULL);<br /> int ret = p_func(start_pos, end_pos, &m_map_data, NULL);<br /> gettimeofday(&tve, NULL);<br /> if (tve.tv_usec < tvs.tv_usec)<br /> {<br /> --tve.tv_sec;<br /> tve.tv_usec+=1000;<br /> }<br /> m_use_time.tv_sec = tve.tv_sec - tvs.tv_sec;<br /> m_use_time.tv_usec = tve.tv_usec - tvs.tv_usec;<br /> }<br /> };</p> <p>int main(int argc, char** argv)<br /> {<br /> XJFrame xjframe;<br /> int user_select;<br /> bool is_exit = false;</p> <p> if (argc == 3)<br /> {<br /> xjframe.set_map_path(argv[1]);<br /> xjframe.init_map();<br /> xjframe.open_module(argv[2]);<br /> xjframe.display_map();<br /> }<br /> do<br /> {<br /> cout << "MENU:\nSetMap(1)\tSetModule(2)\tDisplayMap(3)\tFindPath(4)\tExit(0)" << endl;<br /> cout << "Input:" << flush;<br /> while (!(cin >> user_select))<br /> {<br /> cout <<"Input error, retry:"<< flush;<br /> cin.clear();<br /> cin.ignore(10000,'\n');<br /> }</p> <p> string str;<br /> int ret;<br /> switch (user_select)<br /> {<br /> case 1:<br /> cout << "Your Map Path:";<br /> cin >> str;<br /> xjframe.set_map_path(str);<br /> ret = xjframe.init_map();<br /> if (ret != 0)<br /> {<br /> cout << "Set Map Error" << endl;<br /> }<br /> else<br /> {<br /> cout << "Set Map Success" << endl;<br /> }</p> <p> break;</p> <p> case 2:<br /> cout << "Your Module Path:";<br /> cin >> str;<br /> ret = xjframe.open_module(str);<br /> if (ret != 0)<br /> {<br /> cout << "Set Module Error" << endl;<br /> }<br /> else<br /> {<br /> cout << "Set Module Success" << endl;<br /> }</p> <p> break;</p> <p> case 3:<br /> xjframe.display_map();<br /> break;</p> <p> case 4:<br /> cout << "Enter the start position and end position,format:x y x y";<br /> {<br /> int sx,sy,ex,ey;<br /> if (!(cin >> sx >> sy >> ex >> ey))<br /> {<br /> cout << "Input Error!" << endl;<br /> break;<br /> }<br /> else<br /> {<br /> int start_pos = sy * xjframe.get_map_width() + sx;<br /> int end_pos = ey * xjframe.get_map_width() + ex;</p> <p> ret = xjframe.find_path(start_pos, end_pos);<br /> if (ret != 0)<br /> {<br /> cout << "can not find any path!" << endl;<br /> }<br /> else<br /> {<br /> cout << "path find!" << endl;<br /> xjframe.display_map();<br /> }<br /> cout << "Use Time:" << xjframe.get_use_time()->tv_sec << " second " << xjframe.get_use_time()->tv_usec << " microsecond" << endl;<br /> }<br /> }</p> <p> break;</p> <p> case 0:<br /> is_exit = true;<br /> break;<br /> default:<br /> break;<br /> }<br /> cin.clear();<br /> cin.ignore(10000,'\n');<br /> }while (!is_exit);<br /> cout << "byebye" << endl;</p> <p> return 0;<br /> }</p> <p>