Opened 5 years ago

Last modified 20 months ago

#3785 reopened defect

[PATCH]shortPathfinder may return paths in non passable region.

Reported by: mimo Owned by: mimo
Priority: Should Have Milestone: Backlog
Component: Simulation Keywords:
Cc: Patch:

Description

There is a defect in the short pathfinder when dealing with obstructions. It can enter inside the obstruction and then continue its path in non passable regions. This is easily reproducile with a dock. Putting a unit along the dock, at the limit of the water and asking it to go just a few meters (smaller than the short/long separation) inside the water. The short pathfinder will make it go round the dock. Same thing with a ship and ask it to go a few meters in the land. This is one of the reasons for bugs as #3472 because as soon as there is a dock around, ship movements become completely crazy due to this problem. The patch attached is a (hacky) fix.

Attachments (4)

shortPathfinder.patch (1.2 KB ) - added by mimo 5 years ago.
real_fix.patch (1.4 KB ) - added by wraitii 4 years ago.
betterfix.patch (4.1 KB ) - added by wraitii 4 years ago.
finalgif.gif (846.7 KB ) - added by fatherbushido 4 years ago.

Download all attachments as: .zip

Change History (26)

by mimo, 5 years ago

Attachment: shortPathfinder.patch added

comment:1 by mimo, 5 years ago

Owner: set to mimo
Resolution: fixed
Status: newclosed

In 17765:

prevent short pathfinder to go into impassable region, fixes #3785

comment:2 by mimo, 5 years ago

Keywords: review removed

Although i've not noticed problems with r17765, it could be too restrictive is some cases to forbid paths with an impassable vertex. The new patch in r17768 allows back such vertices, but consider all paths between two impassable vertices as non visible.

comment:3 by wraitii, 4 years ago

Component: Core engineUI & Simulation
Keywords: patch review added
Milestone: Alpha 20Alpha 22

Reopening, Mimo's fix is most likely not entirely accurate. A building may have all its vertexes inside it's impassable raster, so it would be illegally discarded by the above fix, which may lead to weird paths now and then. I don't believe this is very likely, but it could cause trouble. In general, it also lead to some over computation of passability.

The below patch check only whether the target vertex is on impassable terrain, and discards it if so.

by wraitii, 4 years ago

Attachment: real_fix.patch added

comment:4 by Palaxin, 4 years ago

Resolution: fixed
Status: closedreopened

comment:5 by gameboy, 4 years ago

This patch can completely solve the problem?

comment:6 by gameboy, 4 years ago

My friend, if you have forgotten this problem?

by wraitii, 4 years ago

Attachment: betterfix.patch added

comment:7 by wraitii, 4 years ago

Simply expand the area we'll compute the terrain obstructions in. Fixes the issue more neatly, as used in #4327.

comment:8 by elexis, 4 years ago

Milestone: Alpha 22Work In Progress

Moving to the new WIP milestone.

comment:9 by wraitii, 4 years ago

Resolution: fixed
Status: reopenedclosed

In 19024:

Better fix to #3785. Fixes #3785

comment:10 by wraitii, 4 years ago

Keywords: patch review removed
Milestone: Work In ProgressAlpha 22

comment:11 by stanislas69, 4 years ago

This looks like a little duplicated code, why can't a for : be used here ?

comment:12 by elexis, 4 years ago

Resolution: fixed
Status: closedreopened

With gcc 5.4.1:

../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp: In member function ‘virtual void CCmpPathfinder::ComputeShortPath(const IObstructionTestFilter&, entity_pos_t, entity_pos_t, entity_pos_t, entity_pos_t, const PathGoal&, pass_class_t, WaypointPath&)’:
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:618:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:618:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:619:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:619:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:621:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:621:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:622:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:622:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:624:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:624:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:625:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:625:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:627:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:627:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X < rangeXMin) rangeXMin = vert.p.X; if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
                                                   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:628:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:628:51: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (vert.p.X > rangeXMax) rangeXMax = vert.p.X; if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
                                                   ^~

Agreeing with the compiler that every statement should be on an individual line. I subjectively prefer the x = std::max(x, y) pattern, but be careful in case you rearrange (it also supports the initializer list std::max({x, y, z}) though you can't use that here by the looks of things).


Re Stan: Removing code duplication in that hunk doesn't seem effective due to the slight differences in those lines and cpp being less flexible than JS.

Last edited 4 years ago by elexis (previous) (diff)

comment:13 by wraitii, 4 years ago

Grmbl, compilers can be really annoying now and then. might use the std::max trick, will see what's more readable.

For stan's comment, what you said + this part of the code is kind of never looked at and already repetitive and also doomed to be replaced one day so who cares.

comment:14 by stanislas69, 4 years ago

Okay makes sense. Just asking cause sometimes cleanup is good to have.

comment:15 by wraitii, 4 years ago

Resolution: fixed
Status: reopenedclosed

In 19041:

Fix misleading indentation warning on gcc, introduced by [19024]. Reported by elexis. Fixes #3785

comment:16 by elexis, 4 years ago

In r19043 by wraitii:

Fix a bug introduced by a fix of a bug introduced by a fix of a bug (x100) in the vertex pathfinder. Revealed by automated tests on another branch of mine. Revert back to pre-new pathfinder behavior of not returning paths in some cases, since that is most likely less broken than now - but probably still a little broken.

comment:17 by elexis, 4 years ago

Resolution: fixed
Status: closedreopened

With gcc 5.4.1:

../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp: In member function ‘virtual void CCmpPathfinder::ComputeShortPath(const IObstructionTestFilter&, entity_pos_t, entity_pos_t, entity_pos_t, entity_pos_t, const PathGoal&, pass_class_t, WaypointPath&)’:
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:619:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (aa) vert.quadInward = QUADRANT_BR; vertexes.push_back(vert);
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:619:42: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (aa) vert.quadInward = QUADRANT_BR; vertexes.push_back(vert);
                                          ^~~~~~~~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:625:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (aa) vert.quadInward = QUADRANT_TR; vertexes.push_back(vert);
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:625:42: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (aa) vert.quadInward = QUADRANT_TR; vertexes.push_back(vert);
                                          ^~~~~~~~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:631:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (aa) vert.quadInward = QUADRANT_TL; vertexes.push_back(vert);
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:631:42: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (aa) vert.quadInward = QUADRANT_TL; vertexes.push_back(vert);
                                          ^~~~~~~~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:637:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   if (aa) vert.quadInward = QUADRANT_BL; vertexes.push_back(vert);
   ^~
../../../source/simulation2/components/CCmpPathfinder_Vertex.cpp:637:42: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘if’
   if (aa) vert.quadInward = QUADRANT_BL; vertexes.push_back(vert);
                                          ^~~~~~~~

comment:18 by mimo, 4 years ago

I'm even not sure r19043 was ever tested on game as 0ad is now unplayable with lots of units being blocked. I don't even know why it was needed to modify r17768, but this succession of untested and unreviewed patches is not what we should expect.

Edit: I've not tried to understand what is done in the commit, but having the vert and edges arrays contents depending on the order with which we loop on the quadrants is highly suspicious.

Last edited 4 years ago by mimo (previous) (diff)

by fatherbushido, 4 years ago

Attachment: finalgif.gif added

comment:19 by fatherbushido, 4 years ago

I have indeed stuff like stucked units, some finally find a path, some doesn't.

http://trac.wildfiregames.com/raw-attachment/ticket/3785/finalgif.gif

comment:20 by elexis, 4 years ago

In r19054 by wraitii:

Revert [19043]

comment:21 by elexis, 4 years ago

Milestone: Alpha 22Backlog

Backlogging due to lack of progress

comment:22 by Imarok, 20 months ago

Component: UI & SimulationSimulation

Move tickets to Simulation as UI & Simulation got some sub components.

Note: See TracTickets for help on using tickets.