Mudlet

Crash on pathfinding using unconnected maps

Bug #1263447 reported by Vadim Peretokin on 2013-12-22

This bug affects 1 person

Affects		Status	Importance	Assigned to	Milestone
	Mudlet	Fix Released	Critical	Stephen Lyons	Mudlet 3.0.0

Bug Description

Import the sample map with rooms 1,2 which area in area 1 and are not connected. Then try to do getPath(1,2) - a crash happens.

This happens on Mudlet 2.1, Chris7/Mudlet2/mudletDev and SF master.

mudletDev backtrace:
0 astar_search<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float> >, distance_heuristic<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float> >, float, std::vector<location> >, astar_goal_visitor<unsigned long>, unsigned long*, boost::shared_array_property_map<float, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, float*, boost::adj_list_edge_property_map<boost::directed_tag, float, float const&, unsigned long, boost::property<boost::edge_weight_t, float> const, boost::edge_weight_t>, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long>, boost::shared_array_property_map<boost::default_color_type, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, std::less<float>, boost::closed_plus<float>, float, float> astar_search.hpp 294 0x5f5b4a
1 boost::astar_search<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, distance_heuristic<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, float, std::vector<location, std::allocator<location> > >, astar_goal_visitor<unsigned long>, boost::graph_visitor_t, boost::bgl_named_params<float*, boost::vertex_distance_t, boost::bgl_named_params<unsigned long*, boost::vertex_predecessor_t, boost::no_property> > > astar_search.hpp 329 0x5f5b4a
2 TMap::findPath TMap.cpp 771 0x5ef6f3
3 TLuaInterpreter::getPath TLuaInterpreter.cpp 4221 0x4de665
4 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797c23c
5 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff7986c7b
6 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797c64d
7 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797b8d7
8 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797c802
9 lua_pcall /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff7978361
10 TLuaInterpreter::call TLuaInterpreter.cpp 10178 0x4ef23d
11 TAlias::execute TAlias.cpp 426 0x529368
12 TAlias::match TAlias.cpp 275 0x52a553
13 TAlias::match TAlias.cpp 284 0x529bfe
14 AliasUnit::processDataStream AliasUnit.cpp 281 0x537754
15 Host::send Host.cpp 638 0x45ca9c
16 TCommandLine::enterCommand TCommandLine.cpp 522 0x51dd5c
17 TCommandLine::event TCommandLine.cpp 236 0x51f413
18 QApplicationPrivate::notify_helper(QObject*, QEvent*) /home/vadi/Programs/Qt5.2.0/5.2.0/gcc_64/lib/libQt5Widgets.so.5 0x7ffff644ef34
19 QApplication::notify(QObject*, QEvent*) /home/vadi/Programs/Qt5.2.0/5.2.0/gcc_64/lib/libQt5Widgets.so.5 0x7ffff6452cfe
20 QCoreApplication::notifyInternal(QObject*, QEvent*) /home/vadi/Programs/Qt5.2.0/5.2.0/gcc_64/lib/libQt5Core.so.5 0x7ffff54eb554
... <More>

master backtrace:
0 put<float, float> property_map.hpp 176 0x5f14e5
1 astar_search<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float> >, distance_heuristic<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float> >, float, std::vector<location> >, astar_goal_visitor<unsigned long>, unsigned long*, boost::shared_array_property_map<float, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, float*, boost::adj_list_edge_property_map<boost::directed_tag, float, float const&, unsigned long, boost::property<boost::edge_weight_t, float> const, boost::edge_weight_t>, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long>, boost::shared_array_property_map<boost::default_color_type, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >, std::less<float>, boost::closed_plus<float>, float, float> astar_search.hpp 294 0x5f14e5
2 boost::astar_search<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, distance_heuristic<boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, float, std::vector<location, std::allocator<location> > >, astar_goal_visitor<unsigned long>, boost::graph_visitor_t, boost::bgl_named_params<float*, boost::vertex_distance_t, boost::bgl_named_params<unsigned long*, boost::vertex_predecessor_t, boost::no_property> > > astar_search.hpp 329 0x5f14e5
3 TMap::findPath TMap.cpp 751 0x5eb0bd
4 TLuaInterpreter::getPath TLuaInterpreter.cpp 4133 0x4daee7
5 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797c23c
6 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff7986c7b
7 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797c64d
8 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797b8d7
9 ?? /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff797c802
10 lua_pcall /usr/lib/x86_64-linux-gnu/liblua5.1.so.0 0x7ffff7978361
11 TLuaInterpreter::call TLuaInterpreter.cpp 10111 0x4eae3d
12 TAlias::execute TAlias.cpp 426 0x5250b8
13 TAlias::match TAlias.cpp 275 0x5262a3
14 TAlias::match TAlias.cpp 284 0x52594e
15 AliasUnit::processDataStream AliasUnit.cpp 281 0x5334a4
16 Host::send Host.cpp 636 0x45c65c
17 TCommandLine::enterCommand TCommandLine.cpp 522 0x519aac
18 TCommandLine::event TCommandLine.cpp 236 0x51b163
19 QApplicationPrivate::notify_helper(QObject*, QEvent*) /home/vadi/Programs/Qt5.2.0/5.2.0/gcc_64/lib/libQt5Widgets.so.5 0x7ffff644ef34
20 QApplication::notify(QObject*, QEvent*) /home/vadi/Programs/Qt5.2.0/5.2.0/gcc_64/lib/libQt5Widgets.so.5 0x7ffff6452cfe
... <More>

See original description

Tags:

Revision history for this message

Vadim Peretokin (vperetokin) wrote on 2013-12-22:

simple unconnected map.dat Edit (786 bytes, application/x-ns-proxy-autoconfig)

Vadim Peretokin (vperetokin) on 2013-12-22

description:	updated
summary:	- mudletDev crashes on unconnected maps + Crash on pathfinding using unconnected maps
tags:	added: crash

Revision history for this message

Vadim Peretokin (vperetokin) wrote on 2014-01-05:

Fixed in mudlet/dev

Changed in mudlet:
status:	New → Fix Committed

Chris (chrismudlet) on 2014-01-06

Changed in mudlet:
milestone:	none → 3.0
assignee:	nobody → Chris (chrismudlet)
importance:	Undecided → Medium

Revision history for this message

Chris Leacy (cleacy1972) wrote on 2015-07-17:

I'm not sure if this just hadn't going live (I'm using win7/3.0-delta), but having an identical issue - getPath between two unconnected rooms crashes.

Revision history for this message

Stephen Lyons (slysven) wrote on 2015-07-17:

Can you make your map available for someone (me?) to look at - that crash is happening inside boost::graph library code - (or conceivably a Mudlet helper function that we've plugged into the library code) and something in the map data is not right - I'd want to do an autopsy on that data to see what is breaking things...

P.S. I've just exposed my Email address id you can post the (compressed if possible) map file!

Revision history for this message

Chris Leacy (cleacy1972) wrote on 2015-07-17:

torilmap.zip Edit (1.2 MiB, application/zip)

Thanks, i've attached a copy of my map file. With it loaded,

display(getPath(48603, 7008))

will cause an immediate crash - Both are rooms that exist, but no valid path connects them - Those rooms were arbitary choices btw, it crashes with any unconnected rooms (3.0-delta/win7)

Revision history for this message

Stephen Lyons (slysven) wrote on 2015-07-18:

Reverting status to "Confirmed" and elevating to "Critical" as this crash affects current preview code and crashes the Application. It may be a dodgy map file and if I can find a fault therein I will reduce the priority but at this time it could be a nasty regression...!

Changed in mudlet:
status:	Fix Committed → Confirmed
importance:	Medium → Critical

Revision history for this message

Stephen Lyons (slysven) wrote on 2015-07-18:

Investigating the provided file I find that ALL the rooms are in the -1 default area. The highest areaID used is 91 but all of them from 1 to 91 are empty.. This is not the problem.

It seems that the twp sample rooms and I think from some debug code that I added to test things that ALL the rooms are "Locked". Locked rooms are NOT put into the boost::graph data structure so they are not considered for speedwalks. The current code, although it checks for a usable exit from the starting room and bails out if there isn't one does NOT check that the DESTINATION room is unlocked.

The simple one line fix to prevent this crash is, in pseudo-diff form, in the TMap class file, at around line 836:

bool TMap::findPath( int from, int to )
{
      if( mMapGraphNeedsUpdate )
      {
         initGraph();
      }

TRoom * pFrom = mpRoomDB->getRoom( from );
TRoom * pTo = mpRoomDB->getRoom( to );

- if( !pFrom || !pTo )
+ if( !pFrom || !pTo || pTo->isLocked )
      {
          return false;
      }
... other stuff ...
}

We do need to revise the documentation slightly I think because I feel, in nit-picking, theoretic detail, it should be possible to start a route finding/speedwalk FROM a LOCKED room (a locked room is equivalent to an infinite room weighting but the room weighting is used as the cost TO ENTER a room, unless overridden by the weighting of the exit leading TO it) but in practice this would be quite tricky to code for because the room will not be included in the compiled BGL graph structure as stated above.

I will raise a PR and patch the above fix (and clean up a couple of other related locked room issue:)

* delete the unregistered TLuaInterpreter::isLockedRoom() function which is not available to users and is a duplicate of the TLuaInterpreter::lroomLocked() function that is made available!

* provide a mapper GUI context command "unlock" to reverse the "lock" command - so that a user can select a group of rooms and be able to unlock them for use in speedwalks as they can't do at the moment if they lock a wrong room.

Investigating the provided file I find that ALL the rooms are in the -1 default area.  The highest areaID used is 91 but all of them from 1 to 91 are empty..  This is not the problem.

It seems that the twp sample rooms and I think from some debug code that I added to test things that ALL the rooms are "Locked".  Locked rooms are NOT put into the boost::graph data structure so they are not considered for speedwalks.  The current code, although it checks for a usable exit from the starting room and bails out if there isn't one does NOT check that the DESTINATION room is unlocked.

The simple one line fix to prevent this crash is, in pseudo-diff form, in the TMap class file, at around line 836:

bool TMap::findPath( int from, int to )
 {
      if( mMapGraphNeedsUpdate )
      {
         initGraph();
      }
 
      TRoom * pFrom = mpRoomDB->getRoom( from );
      TRoom * pTo = mpRoomDB->getRoom( to );
 
-     if( !pFrom || !pTo )
+     if( !pFrom || !pTo || pTo->isLocked )
      {
          return false;
      }
... other stuff ...
 }

I will raise a PR and patch the above fix (and clean up a couple of other related locked room issue:)

* delete the unregistered TLuaInterpreter::isLockedRoom() function which is not available to users and is a duplicate of the TLuaInterpreter::lroomLocked() function that is made available!

Revision history for this message

Stephen Lyons (slysven) wrote on 2015-07-19:

Oh that is nasty!

I think I may have exposed some dodgy code with a recent commit if http://forums.mudlet.org/viewtopic.php?f=13&t=1696&p=23021#p23021 is anything to go on. However I think I have found the problem,
in (bool)TMap::findPath( int from, int to ) there is the following pair of lines:

vertex start = roomidToIndex[from];
vertex goal = roomidToIndex[to];

However if either from or to are locked rooms they will not make it into TMap::<int, int> roomidToIndex but those lines use the operator[]() WHICH AS THE QT DOCUMENTATION NOTES:
"In general, we recommend that you use contains() and value() rather than operator[]() for looking up a key in a map. The reason is that operator[]() silently inserts an item into the map if no item exists with the same key (unless the map is const)."

In this case "from" or "to" will get inserted into the graph, with a value of 0 - which corresponds to the FIRST room that was inserted into the BGL graph by TMap::initGraph(); either that will exist but IS A WRONG VALUE FOR THE AStar routine to use - or, if the graph is empty because EVERY room is locked there is not even a zero indexed value in an empty graph and the AStar routine will crash and die when it tries to look up the value in the graph - which is what Chris Leacy has found with his provided torilmap.zip test case.

Revision history for this message

Chris Leacy (cleacy1972) wrote on 2015-07-19:

Sounds like my using locked rooms is going to be why getPath crashes on me, and was also somewhat my fault.

The mapfile I posted is the starting file i'm including: It starts with all rooms held in the -1 area, and all rooms also marked locked.

I'd added in locking rooms with some of the map already visible (but not unlocked), which meant when I was trying to speedwalk to places I could see on the map, it was crashing (the room was still locked). I was aware of certain room numbers, and had aliases trying to speedwalk to those particular rooms, but it ended up being rooms held in a locked status so just never failed nicely (it crashes).

Revision history for this message

Stephen Lyons (slysven) wrote on 2015-07-20:

#10

Well you helped to uncover some rogue code - so even if the map wasn't usable it was a good test case! - there is a fixed version awaiting a PR into the "development" branch at https://github.com/SlySven/Mudlet/tree/BugFixAndEnhance_problemsWithRouteFinding (though that will go once it is incorporated into the main code repo - for anyone reading this in the future! 8-)

Stephen Lyons (slysven) on 2015-08-15

Changed in mudlet:
status:	Confirmed → In Progress
assignee:	Chris (chrismudlet) → Stephen Lyons (slysven)

Stephen Lyons (slysven) on 2015-09-15

Changed in mudlet:
status:	In Progress → Fix Committed

Vadim Peretokin (vperetokin) on 2017-03-24

Changed in mudlet:
status:	Fix Committed → Fix Released

Report a bug

This report contains Public information

Everyone can see this information.

You are

Subscribing...

Edit bug mail

Other bug subscribers

Bug attachments

Add attachment

Remote bug watches

Bug watches keep track of this bug in other bug trackers.