change directory structure

Kei18 · Feb 13, 2021 · 0e9345f · 0e9345f
1 parent a115be6
commit 0e9345f
Show file tree

Hide file tree

Showing 19 changed files with 58 additions and 694 deletions.
diff --git a/.gitmodules b/.gitmodules
@@ -4,3 +4,6 @@
 [submodule "third_party/googletest"]
 	path = third_party/googletest
 	url = https://github.com/google/googletest.git
+[submodule "third_party/grid-pathfinding"]
+	path = third_party/grid-pathfinding
+	url = https://github.com/Kei18/grid-pathfinding.git
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -25,7 +25,7 @@ macro(add_test name target)
   list(APPEND TEST_ALL_SRC ${target})
 endmacro(add_test)
 
-add_test(test_graph ./tests/test_graph.cpp)
+# basic
 add_test(test_plan ./tests/test_plan.cpp)
 add_test(test_paths ./tests/test_paths.cpp)
 add_test(test_lib_solver ./tests/test_lib_solver.cpp)

diff --git a/mapf/CMakeLists.txt b/mapf/CMakeLists.txt
@@ -6,3 +6,6 @@ add_definitions(-D_MAPDIR_="${CMAKE_CURRENT_LIST_DIR}/../map/")
 target_compile_options(lib-mapf PUBLIC -O3 -Wall -mtune=native -march=native)
 target_compile_features(lib-mapf PUBLIC cxx_std_17)
 target_include_directories(lib-mapf INTERFACE ./include)
+
+add_subdirectory(../third_party/grid-pathfinding/graph ./graph)
+target_link_libraries(lib-mapf lib-graph)
diff --git a/mapf/include/graph.hpp b/mapf/include/graph.hpp
diff --git a/mapf/include/lib_solver.hpp b/mapf/include/lib_solver.hpp
@@ -1,5 +1,6 @@
 #pragma once
 #include <functional>
+#include <queue>
 
 #include "paths.hpp"
 #include "plan.hpp"

diff --git a/mapf/include/paths.hpp b/mapf/include/paths.hpp
@@ -1,5 +1,4 @@
 #pragma once
-#include "graph.hpp"
 #include "problem.hpp"
 
 /*

diff --git a/mapf/include/problem.hpp b/mapf/include/problem.hpp
@@ -1,10 +1,37 @@
 #pragma once
 #include <random>
+#include <graph.hpp>
 
 #include "default_params.hpp"
-#include "graph.hpp"
+// #include "graph.hpp"
 #include "util.hpp"
 
+using Config = std::vector<Node*>;  // < loc_0[t], loc_1[t], ... >
+using Configs = std::vector<Config>;
+
+// check two configurations are same or not
+[[maybe_unused]] static bool sameConfig(const Config& config_i,
+                                        const Config& config_j)
+{
+  if (config_i.size() != config_j.size()) return false;
+  const int size_i = config_i.size();
+  for (int k = 0; k < size_i; ++k) {
+    if (config_i[k] != config_j[k]) return false;
+  }
+  return true;
+}
+
+[[maybe_unused]] static int getPathCost(const Path& path)
+{
+  int cost = path.size() - 1;
+  auto itr = path.end() - 1;
+  while (itr != path.begin() && *itr == *(itr - 1)) {
+    --cost;
+    --itr;
+  }
+  return cost;
+}
+
 class Problem
 {
 private:

diff --git a/mapf/include/solver.hpp b/mapf/include/solver.hpp
@@ -8,7 +8,6 @@
 #include <unordered_map>
 
 #include "default_params.hpp"
-#include "graph.hpp"
 #include "lib_solver.hpp"
 #include "paths.hpp"
 #include "plan.hpp"

diff --git a/mapf/include/util.hpp b/mapf/include/util.hpp
@@ -62,7 +62,6 @@ static T randomChoose(std::vector<T>& arr, std::mt19937* MT)
 // get elapsed time
 [[maybe_unused]] static double getElapsedTime(const Time::time_point& t_start)
 {
-  Time::time_point t_end = Time::now();
-  return std::chrono::duration_cast<std::chrono::milliseconds>(t_end - t_start)
-      .count();
+  auto t_end = Time::now();
+  return std::chrono::duration_cast<std::chrono::milliseconds>(t_end - t_start).count();
 }