A couple of pathing related bugs

[jdoran]

I ran into these last night, and haven't tracked them down. But FYI:

1) Line of sight errors

On the 3rd floor of Crescent Reach, target an NPC near the lift. Run
into an adjacent area well out of LOS. Checklos reports no LOS as
expected. Take one step to the side, we now have LOS. There is
a solid wall between myself and the NPC. (I looked at the wall in the
map/path viewer, and didn't see any gaps or corners).

I'm not looking forward to walking through Map::LineIntersectsZone, as
I will need to understand how the geometry is represented.

2) The "Pit O' Doom"

PathManager::NoHazardsAccurate is not detecting the elevator shaft
between CR's 2nd and 3rd floors. This should be interesting.

[jdoran]

Here is an update:

Regarding the Pit O' Doom, when I went back in to get coordinates for testing, I wasn't able to reproduce the issue. I did see mobs jumping down that shaft last night, so I'm guessing there is some odd location responsible for this. I may or may not return to this, as it cannot be causing too much trouble if it is that touchy.

Regarding the line intersection... Definitely reproducible. On Crescent Reach's 3rd floor:
Point A -1187,-1441,113 (near groundspawn book on crate)
Point B -1103, -1409, 114 (in Charbone's room)

It will be useful to discuss the wall between these rooms. Using a character's #loc as a rough guide, when inside Charbone's room the wall runs from (-1121, -1330) to (-1121, -1467). The wall should have vertical faces with a constant X value around -1121.

The other wall in question has an X coordinate of -1154.

There are only two nodes to check, and neither report an intersection with that line. But the faces do not look correct...

Fortunately there are not that many faces, and it should be pretty easy to scan the list for intersection. Note that the Z locations on the ray are 113 and 114, therefore for an intersection to occur at least one face needs to cross that Z location. Ain't gonna happen.

The first node has some triangles below the floor level, and then a large number of triangles parallel to the floor. These are at about the right height to be the ceiling and floor of the room. We can quickly rule out this node.

74 faces to check
face 0:  (-1048.62,-1434.57,89.07), (-1081.72,-1434.56,89.07), (-1081.72,-1385.38,89.07)
face 1:  (-1081.72,-1385.38,89.07), (-1048.62,-1401.87,89.07), (-1048.62,-1434.57,89.07)
face 2:  (-1114.33,-1434.56,74.25), (-1114.33,-1368.89,74.25), (-1114.33,-1368.89,89.07)
face 3:  (-1114.33,-1368.89,89.07), (-1114.33,-1434.56,89.07), (-1114.33,-1434.56,74.25)
face 4:  (-1048.62,-1401.87,89.07), (-1081.72,-1385.38,89.07), (-1016.62,-1356.94,89.07)
face 5:  (-1114.33,-1434.56,52.04), (-1114.33,-1434.56,40.04), (-1114.33,-1368.89,40.04)
face 6:  (-1114.33,-1368.89,40.04), (-1114.33,-1368.89,52.04), (-1114.33,-1434.56,52.04)
face 7:  (-1040.94,-1334.42,40.04), (-1081.72,-1385.38,40.04), (-1048.62,-1401.87,40.04)
face 8:  (-1065.27,-1311.91,89.07), (-1016.62,-1356.94,89.07), (-1081.72,-1385.38,89.07)
face 9:  (-1081.72,-1385.38,89.07), (-1114.33,-1368.89,89.07), (-1065.27,-1311.91,89.07)
face 10:  (-1081.72,-1434.56,89.07), (-1114.33,-1434.56,89.07), (-1114.33,-1368.89,89.07)
face 11:  (-1114.33,-1368.89,89.07), (-1081.72,-1385.38,89.07), (-1081.72,-1434.56,89.07)
face 12:  (-1114.33,-1434.56,40.04), (-1081.72,-1434.56,40.04), (-1081.72,-1385.38,40.04)
face 13:  (-1081.72,-1385.38,40.04), (-1114.33,-1368.89,40.04), (-1114.33,-1434.56,40.04)
face 14:  (-1114.33,-1368.89,40.04), (-1081.72,-1385.38,40.04), (-1094.64,-1346.03,40.04)
face 15:  (-1081.72,-1385.38,40.04), (-1040.94,-1334.42,40.04), (-1081.92,-1331.23,40.04)
face 16:  (-1081.92,-1331.23,40.04), (-1094.64,-1346.03,40.04), (-1081.72,-1385.38,40.04)
face 17:  (-1048.62,-1407.33,40.04), (-1048.62,-1401.87,40.04), (-1081.72,-1385.38,40.04)
face 18:  (-1081.72,-1434.56,40.04), (-1048.62,-1431.44,40.04), (-1048.62,-1407.33,40.04)
face 19:  (-1081.72,-1434.56,40.04), (-1048.62,-1407.33,40.04), (-1081.72,-1385.38,40.04)
face 20:  (-1114.33,-1434.56,74.25), (-1114.33,-1434.56,52.04), (-1114.33,-1368.89,52.04)
face 21:  (-1114.33,-1368.89,52.04), (-1114.33,-1368.89,74.25), (-1114.33,-1434.56,74.25)
face 22:  (-1122.78,-1415.86,110.22), (-1089.49,-1415.86,110.23), (-1089.49,-1397.61,110.22)
face 23:  (-1089.49,-1397.61,110.22), (-1122.78,-1398.10,110.22), (-1122.78,-1415.86,110.22)
face 24:  (-1088.94,-1398.10,190.00), (-1088.94,-1415.86,190.00), (-1122.78,-1415.86,190.00)
face 25:  (-1122.78,-1415.86,190.00), (-1122.78,-1398.10,190.00), (-1088.94,-1398.10,190.00)
face 26:  (-1088.94,-1362.62,190.00), (-1088.94,-1380.30,190.00), (-1122.78,-1380.40,190.00)
face 27:  (-1122.78,-1380.40,110.22), (-1088.94,-1380.40,110.22), (-1088.94,-1362.67,110.22)
face 28:  (-1088.94,-1380.40,110.22), (-1046.53,-1380.41,110.22), (-1046.53,-1362.67,110.22)
face 29:  (-1046.53,-1362.67,110.22), (-1088.94,-1362.67,110.22), (-1088.94,-1380.40,110.22)
face 30:  (-1046.53,-1398.10,190.00), (-1046.53,-1415.86,190.00), (-1088.94,-1415.86,190.00)
face 31:  (-1088.94,-1415.86,190.00), (-1088.94,-1398.10,190.00), (-1046.53,-1398.10,190.00)
face 32:  (-1046.53,-1362.62,190.00), (-1046.53,-1380.30,190.00), (-1088.94,-1380.30,190.00)
face 33:  (-1088.94,-1380.30,190.00), (-1088.94,-1362.62,190.00), (-1046.53,-1362.62,190.00)
face 34:  (-1122.78,-1415.86,110.22), (-1122.78,-1433.53,110.22), (-1089.49,-1434.02,110.23)
face 35:  (-1089.49,-1434.02,110.23), (-1089.49,-1415.86,110.23), (-1122.78,-1415.86,110.22)
face 36:  (-1088.94,-1415.86,190.00), (-1088.94,-1433.53,190.00), (-1122.78,-1433.53,190.00)
face 37:  (-1122.78,-1433.53,190.00), (-1122.78,-1415.86,190.00), (-1088.94,-1415.86,190.00)
face 38:  (-1046.53,-1415.86,190.00), (-1046.53,-1433.53,190.00), (-1088.94,-1433.53,190.00)
face 39:  (-1088.94,-1433.53,190.00), (-1088.94,-1415.86,190.00), (-1046.53,-1415.86,190.00)
face 40:  (-1088.94,-1380.30,190.00), (-1088.94,-1398.10,190.00), (-1122.78,-1398.10,190.00)
face 41:  (-1122.78,-1398.10,190.00), (-1122.78,-1380.40,190.00), (-1088.94,-1380.30,190.00)
face 42:  (-1122.78,-1380.40,110.22), (-1122.78,-1398.10,110.22), (-1089.49,-1397.61,110.22)
face 43:  (-1089.49,-1397.61,110.22), (-1088.94,-1380.40,110.22), (-1122.78,-1380.40,110.22)
face 44:  (-1088.94,-1380.40,110.22), (-1089.49,-1397.61,110.22), (-1046.50,-1397.61,110.22)
face 45:  (-1046.50,-1397.61,110.22), (-1046.53,-1380.41,110.22), (-1088.94,-1380.40,110.22)
face 46:  (-1046.53,-1380.30,190.00), (-1046.53,-1398.10,190.00), (-1088.94,-1398.10,190.00)
face 47:  (-1088.94,-1398.10,190.00), (-1088.94,-1380.30,190.00), (-1046.53,-1380.30,190.00)
face 48:  (-1086.73,-1415.86,112.22), (-1086.73,-1431.33,112.22), (-1046.54,-1431.33,112.22)
face 49:  (-1046.54,-1431.33,112.22), (-1046.53,-1415.86,112.22), (-1086.73,-1415.86,112.22)
face 50:  (-1089.49,-1415.86,110.23), (-1089.49,-1434.02,110.23), (-1088.94,-1433.53,111.23)
face 51:  (-1088.94,-1433.53,111.23), (-1088.94,-1415.86,111.23), (-1089.49,-1415.86,110.23)
face 52:  (-1046.50,-1397.61,110.22), (-1089.49,-1397.61,110.22), (-1088.94,-1398.10,111.23)
face 53:  (-1088.94,-1398.10,111.23), (-1046.52,-1398.10,111.23), (-1046.50,-1397.61,110.22)
face 54:  (-1088.94,-1415.86,111.23), (-1088.94,-1433.53,111.23), (-1087.26,-1431.98,111.22)
face 55:  (-1087.26,-1431.98,111.22), (-1087.26,-1415.85,111.22), (-1088.94,-1415.86,111.23)
face 56:  (-1046.52,-1398.10,111.23), (-1088.94,-1398.10,111.23), (-1087.25,-1399.84,111.22)
face 57:  (-1087.25,-1399.84,111.22), (-1046.49,-1399.85,111.22), (-1046.52,-1398.10,111.23)
face 58:  (-1087.26,-1415.85,111.22), (-1087.26,-1431.98,111.22), (-1086.73,-1431.33,112.22)
face 59:  (-1086.73,-1431.33,112.22), (-1086.73,-1415.86,112.22), (-1087.26,-1415.85,111.22)
face 60:  (-1046.49,-1399.85,111.22), (-1087.25,-1399.84,111.22), (-1086.72,-1400.49,112.22)
face 61:  (-1086.72,-1400.49,112.22), (-1046.52,-1400.50,112.22), (-1046.49,-1399.85,111.22)
face 62:  (-1046.54,-1433.53,111.23), (-1046.50,-1431.98,111.22), (-1087.26,-1431.98,111.22)
face 63:  (-1087.26,-1431.98,111.22), (-1088.94,-1433.53,111.23), (-1046.54,-1433.53,111.23)
face 64:  (-1087.26,-1431.98,111.22), (-1046.50,-1431.98,111.22), (-1046.54,-1431.33,112.22)
face 65:  (-1046.54,-1431.33,112.22), (-1086.73,-1431.33,112.22), (-1087.26,-1431.98,111.22)
face 66:  (-1086.72,-1400.49,112.22), (-1086.73,-1415.86,112.22), (-1046.53,-1415.86,112.22)
face 67:  (-1046.53,-1415.86,112.22), (-1046.52,-1400.50,112.22), (-1086.72,-1400.49,112.22)
face 68:  (-1089.49,-1397.61,110.22), (-1089.49,-1415.86,110.23), (-1088.94,-1415.86,111.23)
face 69:  (-1088.94,-1415.86,111.23), (-1088.94,-1398.10,111.23), (-1089.49,-1397.61,110.22)
face 70:  (-1088.94,-1415.86,111.23), (-1087.26,-1415.85,111.22), (-1087.25,-1399.84,111.22)
face 71:  (-1087.25,-1399.84,111.22), (-1088.94,-1398.10,111.23), (-1088.94,-1415.86,111.23)
face 72:  (-1087.25,-1399.84,111.22), (-1087.26,-1415.85,111.22), (-1086.73,-1415.86,112.22)
face 73:  (-1086.73,-1415.86,112.22), (-1086.72,-1400.49,112.22), (-1087.25,-1399.84,111.22)

OK next up is the 2nd and final node checked for LOS. Fortunately it is small (30 faces).

30 faces to check
face 0:  (-1189.14,-1396.70,190.00), (-1189.14,-1434.15,190.00), (-1228.13,-1434.14,190.00)
face 1:  (-1189.14,-1469.73,167.41), (-1228.13,-1469.74,167.41), (-1228.13,-1469.74,178.00)
face 2:  (-1228.13,-1469.74,178.00), (-1189.14,-1469.73,178.00), (-1189.14,-1469.73,167.41)
face 3:  (-1189.14,-1434.15,110.22), (-1153.03,-1434.16,110.22), (-1153.03,-1396.70,110.22)
face 4:  (-1153.03,-1396.70,110.22), (-1189.14,-1396.70,110.22), (-1189.14,-1434.15,110.22)
face 5:  (-1153.03,-1434.16,190.00), (-1153.03,-1469.73,190.00), (-1189.14,-1469.73,190.00)
face 6:  (-1189.14,-1469.73,190.00), (-1189.14,-1434.15,190.00), (-1153.03,-1434.16,190.00)
face 7:  (-1153.03,-1469.73,178.00), (-1153.03,-1469.73,167.41), (-1189.14,-1469.73,167.41)
face 8:  (-1189.14,-1469.73,167.41), (-1189.14,-1469.73,178.00), (-1153.03,-1469.73,178.00)
face 9:  (-1228.13,-1469.74,110.22), (-1228.13,-1506.70,110.22), (-1189.14,-1506.70,110.22)
face 10:  (-1189.14,-1506.70,110.22), (-1189.14,-1469.74,110.22), (-1228.13,-1469.74,110.22)
face 11:  (-1189.14,-1434.15,190.00), (-1189.14,-1469.73,190.00), (-1228.13,-1469.74,190.00)
face 12:  (-1228.13,-1469.74,190.00), (-1228.13,-1434.14,190.00), (-1189.14,-1434.15,190.00)
face 13:  (-1189.14,-1469.74,110.22), (-1153.03,-1469.74,110.22), (-1153.03,-1434.16,110.22)
face 14:  (-1153.03,-1434.16,110.22), (-1189.14,-1434.15,110.22), (-1189.14,-1469.74,110.22)
face 15:  (-1189.14,-1434.15,190.00), (-1189.14,-1396.70,190.00), (-1153.03,-1396.70,190.00)
face 16:  (-1153.03,-1396.70,190.00), (-1153.03,-1434.16,190.00), (-1189.14,-1434.15,190.00)
face 17:  (-1189.14,-1434.15,110.22), (-1189.14,-1396.70,110.22), (-1228.13,-1396.70,110.22)
face 18:  (-1228.13,-1396.70,110.22), (-1228.13,-1434.14,110.22), (-1189.14,-1434.15,110.22)
face 19:  (-1189.14,-1469.74,110.22), (-1189.14,-1434.15,110.22), (-1228.13,-1434.14,110.22)
face 20:  (-1228.13,-1434.14,110.22), (-1228.13,-1469.74,110.22), (-1189.14,-1469.74,110.22)
face 21:  (-1153.03,-1469.74,110.22), (-1189.14,-1469.74,110.22), (-1189.14,-1506.70,110.22)
face 22:  (-1189.14,-1469.73,167.41), (-1189.14,-1500.21,141.82), (-1228.13,-1500.22,141.82)
face 23:  (-1228.13,-1500.22,141.82), (-1228.13,-1469.74,167.41), (-1189.14,-1469.73,167.41)
face 24:  (-1153.03,-1469.73,167.41), (-1153.03,-1500.21,141.82), (-1189.14,-1500.21,141.82)
face 25:  (-1189.14,-1500.21,141.82), (-1189.14,-1469.73,167.41), (-1153.03,-1469.73,167.41)
face 26:  (-1189.14,-1469.73,190.00), (-1189.14,-1469.73,178.00), (-1228.13,-1469.74,178.00)
face 27:  (-1228.13,-1469.74,178.00), (-1228.13,-1469.74,190.00), (-1189.14,-1469.73,190.00)
face 28:  (-1153.03,-1469.73,190.00), (-1153.03,-1469.73,178.00), (-1189.14,-1469.73,178.00)
face 29:  (-1189.14,-1469.73,178.00), (-1189.14,-1469.73,190.00), (-1153.03,-1469.73,190.00)

More ceiling/floor faces. A few angled faces, but nothing approaching vertical, nor crossing the Z=114 plane.

It looks like the wrong nodes are being checked.

[jdoran]

After more musing...

Why do Nodes have 2D bounding boxes? A node has a collection of faces, and I would expect it to have a bounding volume.

SeekNode takes an (x,y) coordinate and finds a node which intersects. At no point do I see Z being taken into account. Yet in zones with multiple levels (dungeons mainly) there would not necessarily be a unique Node for a given (x,y).

This doesn't seem a difficult problem to solve, since the same process that determines the bounding box could determine the volume. Every place where SeekNode is called has a Z value available (except recursive calls to SeekNode itself).

Which brings up another question: Why are Nodes stored in a quadtree instead of an octree?

Since my thoughts deviate significantly from what the existing code does, it would appear that I am missing something important. I hope that someone who knows this area of the code will set me straight. My motivation is to keep mobs from plowing through walls, ignoring their paths since they wrongly believe they have LOS to their destination. As this has bothered me for a bit, I figured I would take a bit of time over the holidays and see if I could get to the bottom of things.

[jdoran]

I am still holding out hope that someone will comment on these LOS issues. I don't mind fixing it, but without understanding why certain things are the way they are, I fear the chance of messing things up is great.

This issue should be occurring anywhere there are multiple overlapping areas (such as guk, blackburrow, sola...)