search

implicit-invocation / jwalkable

Easy 2D polygonal pathfinding for Java.
Other
26 stars 8 forks source link

Endless loop #10

Open BambooBandit opened 3 years ago

BambooBandit commented 3 years ago

pathHelper.addPolygon(polygon.getTransformedVertices()); can get stuck in an endless loop. I can reproduce it every time with the shapes that I have. I believe it has to do with the shapes being tiny and or their position. Profiler says all the time is being spent in hxDaedalus.data.Mesh.insertConstraintSegment(), and I took a look. There are some while(true) in there that could be the culprit

reproduce the issue:

map size: 186 x 170

polygons added in order:

[181.08981, 132.90536, 161.60878, 133.1051, 156.85825, 129.07321, 160.73047, 124.40253, 175.50087, 116.53815] [160.49069, 90.19095, 146.99763, 84.402626, 141.86778, 68.803856, 143.81387, 66.50844] [145.29729, 17.313477, 130.04779, 17.712791, 120.91937, 16.595093, 118.6306, 13.933769, 119.58864, 7.706215] [175.62056, 106.79762, 166.51875, 106.43841, 158.25523, 98.85364, 160.53061, 89.67198] [125.87005, 104.63898, 129.99182, 106.38545, 128.1755, 112.88247, 114.34326, 126.086174] [20.536934, 32.191338, 23.121758, 31.259846, 27.406532, 32.58716, 27.220276, 37.849968, 15.739914, 38.94453] [14.3892975, 40.877342, 20.746582, 40.807434, 21.095901, 43.299114, 19.612228, 45.75421, 12.609581, 48.701706, 9.555687, 48.49215] [106.32214, 51.02301, 105.9063, 49.94184, 110.01473, 47.43017, 119.29617, 48.44474, 119.97815, 49.675606, 115.720024, 52.569847, 110.09794, 53.01899] [135.6809, 165.41736, 135.67087, 160.9463, 145.18185, 160.93625, 145.01556, 167.43658] [91.28903, 69.91202, 103.953674, 65.84007, 110.12134, 66.768166, 108.444725, 70.48076] [158.73479, 167.08386, 158.69482, 160.85631, 168.23573, 161.05585, 168.4154, 165.0279] [139.84175, 47.436607, 137.37999, 45.207756, 142.33665, 33.098602, 146.26213, 32.932236] [119.233696, 154.58913, 128.66486, 157.45334, 131.38943, 161.57507, 129.9224, 165.9064] [145.53046, 57.38334, 133.8205, 49.6988, 140.44055, 46.57167] [44.432365, 18.215755, 47.06378, 19.356789, 40.822952, 22.756702, 26.268723, 21.988346] [139.9417, 66.132545, 133.88713, 65.30093, 133.3881, 61.907715, 135.41736, 59.246357, 140.64026, 59.346115] [21.275597, 51.878616, 21.48516, 50.714275, 30.194412, 50.57449, 35.22439, 55.138657, 33.89705, 56.27972] [179.63284, 147.3964, 180.53093, 132.54608, 185.00204, 137.7756] [78.337845, 11.974651, 77.08037, 12.766411, 66.135574, 10.856976, 63.737003, 5.8736267] [173.29225, 147.39642, 167.49382, 143.6706, 168.14583, 140.03784, 172.82646, 140.13095, 174.31682, 141.52815] [112.8763, 140.40753, 121.05007, 156.40547, 117.83652, 158.22186] [110.88607, 11.3257065, 109.02316, 16.169369, 104.39909, 17.623165, 98.68052, 16.036385] [53.211403, 7.270916, 55.377075, 8.342091, 56.937313, 11.229637, 55.609978, 12.8131485, 48.158234, 15.630901] [114.622696, 125.38756, 113.435196, 142.57321, 109.87232, 142.22394] [175.22144, 117.176865, 175.34113, 106.23875, 179.97186, 106.877426] [121.67172, 96.06615, 123.90725, 96.298996, 126.98114, 100.49059, 126.51544, 105.42739] [172.40735, 156.53816, 174.13718, 149.6985, 180.04535, 147.09033] [162.80322, 146.89084, 159.19708, 143.63072, 165.46454, 143.12503, 167.3807, 144.78835] [82.93576, 72.84621, 83.744125, 70.42105, 90.24112, 69.16352, 93.0555, 70.271286] [113.09549, 80.17133, 116.82139, 81.80138, 121.24591, 86.92443, 120.31445, 88.75411] [42.985588, 63.984238, 43.08538, 62.966274, 47.09736, 62.84648, 48.97361, 64.18379, 47.795998, 67.537094] [120.69362, 87.58978, 122.09088, 96.25244, 118.78418, 97.74282] [90.75997, 55.62726, 92.889046, 55.228043, 99.5291, 55.733646, 100.68679, 56.691723, 98.57103, 57.29054, 91.89105, 56.891388] [145.01463, 33.32147, 144.32263, 25.796524, 147.69586, 23.201687] [47.795998, 67.537094, 51.249084, 67.13786, 55.360878, 68.97416, 53.364883, 70.850426] [58.25514, 76.28286, 73.48468, 75.70058, 73.83399, 77.26079] [58.683773, 5.012062, 52.745667, 7.5969353, 50.836136, 4.8723984] [73.08548, 76.07982, 73.53456, 73.17563, 80.1214, 74.19354] [91.30557, 58.36844, 100.114624, 59.51275, 100.51384, 60.497444, 92.07737, 59.605957] [26.894142, 21.945114, 14.8083725, 29.21067, 12.456406, 29.140827] [14.695251, 28.927887, 20.676651, 32.098186, 17.928825, 33.239258] [93.3016, 61.162827, 100.4473, 61.09624, 101.44532, 62.29384, 95.33753, 62.214043] [112.16399, 74.349655, 114.32633, 75.181305, 113.12877, 81.43547] [172.56711, 164.94801, 172.32751, 156.45833, 174.03078, 156.45831] [98.76036, 16.049683, 96.967285, 16.37571, 77.75568, 11.974655] [54.34294, 73.04603, 59.20988, 74.047325, 58.394867, 76.7253] [47.759377, 62.177803, 54.56243, 61.662117, 56.026176, 62.876343, 50.620323, 62.992817] [143.76398, 67.65614, 139.62225, 66.10927, 141.46854, 63.514446] [14.569023, 53.974472, 14.63887, 52.41426, 16.105934, 51.878654, 21.508461, 51.855324] [37.832565, 63.731453, 44.050133, 63.754692, 43.491264, 65.82722] [109.04351, 68.53464, 112.72619, 74.67233, 111.31901, 75.331024] [147.47963, 23.461163, 145.2707, 21.890987, 145.03114, 17.07396] [9.119934, 55.092278, 11.844467, 53.99778, 14.91832, 53.648453, 13.381409, 55.3484] [119.6951, 9.51593, 110.91268, 11.67168, 110.08766, 10.740219] [111.92757, 46.348984, 114.888306, 45.73353, 117.616196, 47.03091, 114.17308, 47.380238] [33.827187, 56.070137, 36.43531, 56.90844, 36.15589, 60.35488] [33.035385, 48.50193, 36.019424, 49.709496, 32.55635, 49.949043, 30.370712, 49.080795] [144.8825, 166.93759, 159.42674, 166.88425, 159.3336, 167.41652] [15.739914, 38.94453, 14.6221695, 41.482796, 11.757896, 41.22666] [139.4759, 59.545723, 144.93164, 56.78454, 146.096, 57.549667] [48.25138, 15.584324, 44.08306, 16.352821, 43.640594, 14.769325] [160.12198, 158.13504, 162.58371, 157.50961, 165.57108, 158.68723, 162.40408, 158.73383] [168.15593, 164.56882, 173.30563, 164.58875, 173.00624, 165.88614] [129.52652, 165.13461, 135.94037, 165.16118, 136.12666, 166.17249] [78.59445, 74.37319, 84.22318, 72.30728, 84.22319, 73.32525] [53.384834, 70.47119, 55.58046, 71.52906, 54.303024, 73.48515] [64.20274, 6.8050995, 59.80154, 6.0599556, 57.496136, 4.406616] [116.00774, 52.217224, 116.501755, 53.21622, 114.76723, 53.589485, 113.18638, 52.491695] [9.818512, 52.08828, 8.467903, 55.068996, 6.8843994, 54.882713] [36.15589, 60.35489, 38.99688, 61.07676, 37.669548, 62.404114] [9.655487, 50.085625, 11.891029, 51.249947, 9.818512, 52.27458] [9.655472, 48.38569, 10.097939, 50.27191, 7.722687, 50.388363] [44.781662, 15.95694, 44.595383, 18.378765, 43.29132, 18.215767] [162.98291, 157.0106, 165.21179, 156.77106, 166.28964, 157.59607, 164.81924, 157.63602] [150.27173, 167.00407, 150.27173, 166.61818, 153.3988, 166.57825, 153.34558, 166.97745] [37.669548, 62.147957, 38.368164, 64.383484, 37.576416, 64.68622] [8.421326, 54.78955, 9.79525, 55.23199, 9.8185425, 56.37304] [167.19443, 144.85489, 168.40533, 143.85687, 168.81786, 144.7085] [147.73074, 161.32043, 148.5308, 161.09555, 149.41737, 161.41989, 148.50055, 161.73128] [154.27399, 161.37662, 155.09135, 161.09119, 155.78763, 161.35931, 155.1, 161.72691] [131.17218, 21.415379, 131.4117, 21.425358, 131.19217, 25.387432] [118.47758, 22.8027, 120.64322, 18.94041, 120.8528, 18.990307] [119.95465, 26.026237, 119.71513, 26.08612, 118.477585, 22.8027] [120.72305, 19.020248, 120.71307, 18.90049, 125.613266, 18.72081] [102.20697, 48.70102, 103.803795, 51.229282, 103.93686, 51.18936] [62.84239, 47.969448, 65.74327, 49.80575, 65.76988, 49.659378] [75.47048, 51.335953, 79.85506, 53.711166, 79.84175, 53.584755] [65.78319, 49.699295, 70.274216, 50.657345, 70.274216, 50.537582] [79.81514, 53.63798, 84.20636, 54.69583, 84.20636, 54.556114] [88.378006, 54.150223, 89.382675, 56.432316, 89.66878, 56.458927] [58.138454, 46.851723, 62.862347, 48.04264, 62.868996, 47.90957]

last polygon causes the eternal loop.

nanjizal commented 3 years ago

map size: 186 x 170 is small suggest muliplying all your dimensions by 1000 and then in the draw code dividing by 1000 and possibly rounding. Reducing Epsilon as you say may help but ideally you don't want calculation numbers getting too small so better to scale model up for calculations.