search

silmerusse / fudge_pathfinding

A C++ implmentation of A* and Jump Point Search algorithm
MIT License
75 stars 20 forks source link

Error while compiling GUI #1

Closed kxhit closed 6 years ago

kxhit commented 6 years ago

Hi! I run cmake and make, but got an error below. It seems like executable fudge_gui did not compile successfully. Something with error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Item; _Dp = std::default_delete<Item>]’ and /usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here unique_ptr(const unique_ptr&) = delete;` Could anyone help me? Thanks in advance! I am building in Ubuntu14.04 & gcc 4.8.5 & boost1.54.

kx@kx-Lenovo-IdeaPad-Y410P:~/project/fudge_pathfinding-master$ cmake CMakeLists.txt 
-- The C compiler identification is GNU 4.8.5
-- The CXX compiler identification is GNU 4.8.5
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: /home/kx/project/fudge_pathfinding-master

kx@kx-Lenovo-IdeaPad-Y410P:~/project/fudge_pathfinding-master$ make
Scanning dependencies of target astar_torches_puzzle
[  3%] Building CXX object sample/CMakeFiles/astar_torches_puzzle.dir/astar_torches_puzzle.cc.o
[  6%] Linking CXX executable astar_torches_puzzle
[  6%] Built target astar_torches_puzzle
Scanning dependencies of target astar_multi_agent_map
[ 10%] Building CXX object sample/CMakeFiles/astar_multi_agent_map.dir/astar_multi_agent_map.cc.o
[ 13%] Linking CXX executable astar_multi_agent_map
[ 13%] Built target astar_multi_agent_map
Scanning dependencies of target dijkstra_water_jug
[ 16%] Building CXX object sample/CMakeFiles/dijkstra_water_jug.dir/dijkstra_water_jug.cc.o
[ 20%] Linking CXX executable dijkstra_water_jug
[ 20%] Built target dijkstra_water_jug
Scanning dependencies of target astar_sliding_puzzle
[ 23%] Building CXX object sample/CMakeFiles/astar_sliding_puzzle.dir/astar_sliding_puzzle.cc.o
[ 26%] Linking CXX executable astar_sliding_puzzle
[ 26%] Built target astar_sliding_puzzle
Scanning dependencies of target astar_jump_point
[ 30%] Building CXX object sample/CMakeFiles/astar_jump_point.dir/astar_jump_point.cc.o
[ 33%] Linking CXX executable astar_jump_point
[ 33%] Built target astar_jump_point
Scanning dependencies of target astar_grid_map
[ 36%] Building CXX object sample/CMakeFiles/astar_grid_map.dir/astar_grid_map.cc.o
[ 40%] Linking CXX executable astar_grid_map
[ 40%] Built target astar_grid_map
Scanning dependencies of target fudge_test
[ 43%] Building CXX object test/CMakeFiles/fudge_test.dir/binary_heap_test.cc.o
[ 46%] Building CXX object test/CMakeFiles/fudge_test.dir/grid_map_test.cc.o
[ 50%] Building CXX object test/CMakeFiles/fudge_test.dir/hot_queue_test.cc.o
[ 53%] Building CXX object test/CMakeFiles/fudge_test.dir/jump_point_map_test.cc.o
[ 56%] Building CXX object test/CMakeFiles/fudge_test.dir/multi_agent_map_test.cc.o
[ 60%] Building CXX object test/CMakeFiles/fudge_test.dir/priority_queue_stl_test.cc.o
[ 63%] Building CXX object test/CMakeFiles/fudge_test.dir/rra_test.cc.o
[ 66%] Building CXX object test/CMakeFiles/fudge_test.dir/sliding_puzzle_map_test.cc.o
[ 70%] Building CXX object test/CMakeFiles/fudge_test.dir/torches_puzzle_test.cc.o
[ 73%] Building CXX object test/CMakeFiles/fudge_test.dir/water_jug_map_test.cc.o
[ 76%] Linking CXX executable fudge_test
[ 76%] Built target fudge_test
Scanning dependencies of target fudge_gui
[ 80%] Building CXX object gui/CMakeFiles/fudge_gui.dir/fudge_event_handler.cc.o
[ 83%] Building CXX object gui/CMakeFiles/fudge_gui.dir/game.cc.o
In file included from /usr/include/boost/multi_index_container.hpp:20:0,
                 from /home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/../core/repository.h:5,
                 from /home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/json_item_loader.h:6,
                 from /home/kx/project/fudge_pathfinding-master/gui/game.cc:1:
/usr/include/boost/detail/allocator_utilities.hpp: In instantiation of ‘void boost::detail::allocator::construct(void*, const Type&) [with Type = std::unique_ptr<Item>]’:
/usr/include/boost/multi_index/detail/index_base.hpp:88:54:   required from ‘boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::node_type* boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::insert_(boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::value_param_type, boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::node_type*) [with Value = std::unique_ptr<Item>; IndexSpecifierList = boost::multi_index::indexed_by<boost::multi_index::ordered_unique<boost::multi_index::tag<ID>, boost::multi_index::member<Item, int, &Item::id_> >, boost::multi_index::hashed_non_unique<boost::multi_index::tag<TAG>, boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_> > >; Allocator = std::allocator<std::unique_ptr<Item> >; boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::node_type = boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > >; boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::value_param_type = const std::unique_ptr<Item>&]’
/usr/include/boost/multi_index/hashed_index.hpp:701:62:   required from ‘boost::multi_index::detail::hashed_index<KeyFromValue, Hash, Pred, SuperMeta, TagList, Category>::node_type* boost::multi_index::detail::hashed_index<KeyFromValue, Hash, Pred, SuperMeta, TagList, Category>::insert_(boost::multi_index::detail::hashed_index<KeyFromValue, Hash, Pred, SuperMeta, TagList, Category>::value_param_type, boost::multi_index::detail::hashed_index<KeyFromValue, Hash, Pred, SuperMeta, TagList, Category>::node_type*) [with KeyFromValue = boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_>; Hash = boost::hash<std::basic_string<char> >; Pred = std::equal_to<std::basic_string<char> >; SuperMeta = boost::multi_index::detail::nth_layer<2, std::unique_ptr<Item>, boost::multi_index::indexed_by<boost::multi_index::ordered_unique<boost::multi_index::tag<ID>, boost::multi_index::member<Item, int, &Item::id_> >, boost::multi_index::hashed_non_unique<boost::multi_index::tag<TAG>, boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_> > >, std::allocator<std::unique_ptr<Item> > >; TagList = boost::mpl::v_item<TAG, boost::mpl::vector0<mpl_::na>, 0>; Category = boost::multi_index::detail::hashed_non_unique_tag; boost::multi_index::detail::hashed_index<KeyFromValue, Hash, Pred, SuperMeta, TagList, Category>::node_type = boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > > >; typename SuperMeta::type::node_type = boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > >; boost::multi_index::detail::hashed_index<KeyFromValue, Hash, Pred, SuperMeta, TagList, Category>::value_param_type = const std::unique_ptr<Item>&]’
/usr/include/boost/multi_index/ordered_index.hpp:633:62:   required from ‘boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::node_type* boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::insert_(boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::value_param_type, boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::node_type*) [with KeyFromValue = boost::multi_index::member<Item, int, &Item::id_>; Compare = std::less<int>; SuperMeta = boost::multi_index::detail::nth_layer<1, std::unique_ptr<Item>, boost::multi_index::indexed_by<boost::multi_index::ordered_unique<boost::multi_index::tag<ID>, boost::multi_index::member<Item, int, &Item::id_> >, boost::multi_index::hashed_non_unique<boost::multi_index::tag<TAG>, boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_> > >, std::allocator<std::unique_ptr<Item> > >; TagList = boost::mpl::v_item<ID, boost::mpl::vector0<mpl_::na>, 0>; Category = boost::multi_index::detail::ordered_unique_tag; boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::node_type = boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > > > >; typename SuperMeta::type::node_type = boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > > >; boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::value_param_type = const std::unique_ptr<Item>&]’
/usr/include/boost/multi_index_container.hpp:488:40:   required from ‘std::pair<typename boost::multi_index::detail::multi_index_base_type<Value, IndexSpecifierList, Allocator>::type::node_type*, bool> boost::multi_index::multi_index_container<Value, IndexSpecifierList, Allocator>::insert_(const Value&) [with Value = std::unique_ptr<Item>; IndexSpecifierList = boost::multi_index::indexed_by<boost::multi_index::ordered_unique<boost::multi_index::tag<ID>, boost::multi_index::member<Item, int, &Item::id_> >, boost::multi_index::hashed_non_unique<boost::multi_index::tag<TAG>, boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_> > >; Allocator = std::allocator<std::unique_ptr<Item> >; typename boost::multi_index::detail::multi_index_base_type<Value, IndexSpecifierList, Allocator>::type::node_type = boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > > > >]’
/usr/include/boost/multi_index/detail/index_base.hpp:150:30:   required from ‘std::pair<typename boost::multi_index::detail::multi_index_node_type<Value, IndexSpecifierList, Allocator>::type*, bool> boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::final_insert_(boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::value_param_type) [with Value = std::unique_ptr<Item>; IndexSpecifierList = boost::multi_index::indexed_by<boost::multi_index::ordered_unique<boost::multi_index::tag<ID>, boost::multi_index::member<Item, int, &Item::id_> >, boost::multi_index::hashed_non_unique<boost::multi_index::tag<TAG>, boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_> > >; Allocator = std::allocator<std::unique_ptr<Item> >; typename boost::multi_index::detail::multi_index_node_type<Value, IndexSpecifierList, Allocator>::type = boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > > > >; boost::multi_index::detail::index_base<Value, IndexSpecifierList, Allocator>::value_param_type = const std::unique_ptr<Item>&]’
/usr/include/boost/multi_index/ordered_index.hpp:275:61:   required from ‘std::pair<boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<typename SuperMeta::type::node_type> >, bool> boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::insert(boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::value_param_type) [with KeyFromValue = boost::multi_index::member<Item, int, &Item::id_>; Compare = std::less<int>; SuperMeta = boost::multi_index::detail::nth_layer<1, std::unique_ptr<Item>, boost::multi_index::indexed_by<boost::multi_index::ordered_unique<boost::multi_index::tag<ID>, boost::multi_index::member<Item, int, &Item::id_> >, boost::multi_index::hashed_non_unique<boost::multi_index::tag<TAG>, boost::multi_index::member<Item, std::basic_string<char>, &Item::tag_> > >, std::allocator<std::unique_ptr<Item> > >; TagList = boost::mpl::v_item<ID, boost::mpl::vector0<mpl_::na>, 0>; Category = boost::multi_index::detail::ordered_unique_tag; typename SuperMeta::type::node_type = boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<std::unique_ptr<Item>, std::allocator<std::unique_ptr<Item> > > >; boost::multi_index::detail::ordered_index<KeyFromValue, Compare, SuperMeta, TagList, Category>::value_param_type = const std::unique_ptr<Item>&]’
/home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/../core/repository.h:63:5:   required from ‘T* Repository::add_item(int, const string&, std::unique_ptr<T>) [with T = Tile; std::string = std::basic_string<char>]’
/home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/../core/repository.h:47:44:   required from ‘T* Repository::create_item(int, const string&) [with T = Tile; std::string = std::basic_string<char>]’
/home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/../core/repository.h:41:34:   required from ‘T* Repository::create_item(const string&) [with T = Tile; std::string = std::basic_string<char>]’
/home/kx/project/fudge_pathfinding-master/gui/game.cc:45:52:   required from here
/usr/include/boost/detail/allocator_utilities.hpp:178:3: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Item; _Dp = std::default_delete<Item>]’
   new (p) Type(t);
   ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from /usr/include/boost/detail/allocator_utilities.hpp:18,
                 from /usr/include/boost/multi_index_container.hpp:20,
                 from /home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/../core/repository.h:5,
                 from /home/kx/project/fudge_pathfinding-master/gui/include/fruitcandy/json/json_item_loader.h:6,
                 from /home/kx/project/fudge_pathfinding-master/gui/game.cc:1:
/usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^
make[2]: *** [gui/CMakeFiles/fudge_gui.dir/game.cc.o] Error 1
make[1]: *** [gui/CMakeFiles/fudge_gui.dir/all] Error 2
make: *** [all] Error 2
silmerusse commented 6 years ago

Hello @kxhit ,

This is because multi_index in boost 1.54 does not support std::unique_ptr as element yet (no copy constructor). Please upgrade boost to at least 1.55.

This is addressed in 1.55 release notes:

Non-copyable elements (such as std::unique_ptr) supported. This includes insertion of a range [first,last) where the iterators point to a type that is convertible to that of the element: no copy construction happens in the process.

kxhit commented 6 years ago

Many thanks @silmerusse ! Now I can run the program successfully! It seems like multi-agent path finding algorithm in astar_multi_agent_map will not avoid conflicts when one agent's target point is just right in another agent's only way (which must be passed) .When one agent arrives at it's target point, it will not make ways for other agents (seems will never move again). They will avoid conflicts in other situations. Is there any misunderstanding? Looking forward to your reply!

silmerusse commented 6 years ago

@kxhit ,

Well, actually to simplify the problem, if an agent reaches it's destination I just remove it from the searching node so that it no longer be an obstacle to other agents, especially to those having the same destination. Of course you can change this behavior to satisfy your needs. In fact, I think there are a lot more to enhance for multi-agent path finding in a more realistic scenario. This is just a sample to showcase A* algorithm.

kxhit commented 6 years ago

Thanks! @silmerusse , Is there any simple solution to make multi-agent path finding (astar_multi_agent_map) to get diagonal path? I make enable_diagonal_=true, but still get straight path. Could you help me? It seems result.push_back(fudge::Edge<NodeType, double>(from, to, 1)); in multi_agent_map.h make every edge's cost to be 1 (not like in grid_map.h, the cost will be 1 or 1.4143 depends on the coordinate ).

silmerusse commented 6 years ago

Right now multi_agent_map does not support grid_map's diagonal path feature yet. I haven't made it inherit from grid_map because an edge in multi_agent_map has a different meaning. (The edge cost here is "turn" instead of grid distance. Therefore it's always 1.) Also it's for simplifying problem because if cost of any move is integer it is easier to know agent state and position at any given turn and it's simple to resolve conflicts.

To support diagonal path, you may need to change possible_moves(const Agent &agent) to make it generate diagonal moves for an agent. Also you should consider how to handle agent moving in diagonal, which has a non-integer cost, while the turns are integers. It could be implemented but I think it would be a little complicated. Please feel free to enhance it if you are interested. : )

silmerusse commented 6 years ago

By the way, if you are developing a game, I would not recommend to use the algorithm in multi_agent_map sample. The sample demonstrated how to use one time search for multiple agents to find paths that have no conflicts. But this is in an ideal scene and its performance is quite low. It's common in a game, where obstacles are often dynamic, to calculate individual path for each agent. When a conflict happens or after a regular interval, a new path would be regenerated. Also there are other techniques to gain better performance besides A* searching.