Replaced manual pathfinder tests by auto

akuskis commented 6 years ago

According to ticket #378 :

Created unit tests for pathfinder. This tests replaces manual tests;
Tests are silent (no output if they pass);
When test fails, it shows "map" with actual and expected path (check marks - actual path; "X" marks - point from expected path, which was not reached).

Now there are 6 tests and 3 of them fails with the following:

Output:

/unit_tests
Walk #1
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . ✫ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✔ ##✔ . . . . 
. . . ✔ . . . . . . . . ✔ . ##. ✔ . . . 
. . . . ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ . . ##. . ✔ ✔ . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:68: Failure
Expected equality of these values:
  points
    Which is: { 8-byte object <03-00 00-00 04-00 00-00>, 8-byte object <04-00 00-00 05-00 00-00>, 8-byte object <05-00 00-00 05-00 00-00>, 8-byte object <06-00 00-00 05-00 00-00>, 8-byte object <07-00 00-00 05-00 00-00>, 8-byte object <08-00 00-00 05-00 00-00>, 8-byte object <09-00 00-00 05-00 00-00>, 8-byte object <0A-00 00-00 05-00 00-00>, 8-byte object <0B-00 00-00 05-00 00-00>, 8-byte object <0C-00 00-00 04-00 00-00>, 8-byte object <0D-00 00-00 03-00 00-00>, 8-byte object <0E-00 00-00 02-00 00-00>, 8-byte object <0F-00 00-00 03-00 00-00>, 8-byte object <10-00 00-00 04-00 00-00>, 8-byte object <11-00 00-00 05-00 00-00>, 8-byte object <12-00 00-00 05-00 00-00> }
  GetParam().expected
    Which is: { 8-byte object <03-00 00-00 03-00 00-00>, 8-byte object <04-00 00-00 03-00 00-00>, 8-byte object <05-00 00-00 03-00 00-00>, 8-byte object <06-00 00-00 03-00 00-00>, 8-byte object <07-00 00-00 03-00 00-00>, 8-byte object <08-00 00-00 03-00 00-00>, 8-byte object <09-00 00-00 03-00 00-00>, 8-byte object <0A-00 00-00 03-00 00-00>, 8-byte object <0B-00 00-00 03-00 00-00>, 8-byte object <0C-00 00-00 03-00 00-00>, 8-byte object <0D-00 00-00 03-00 00-00>, 8-byte object <0E-00 00-00 02-00 00-00>, 8-byte object <0F-00 00-00 03-00 00-00>, 8-byte object <10-00 00-00 04-00 00-00>, 8-byte object <11-00 00-00 05-00 00-00>, 8-byte object <12-00 00-00 05-00 00-00> }
Walk #2
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . ✫ ✔ ✔ . . . . ##. . . ##. . . ✔ . 
. . . . . . ✔ . . . ##. . . ##. . . ✔ . 
. . . . . . . ✔ . . ##. . . ##. . . ✔ . 
. . . . . . . . ✔ . ##. . . ##. . . ✔ . 
. . . . . . . . . ✔ ##✔ . . ##. . ✔ . . 
. . . . . . . . . . ✔ ✘ ✔ . ##. ✔ . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:68: Failure
Expected equality of these values:
  points
    Which is: { 8-byte object <04-00 00-00 0A-00 00-00>, 8-byte object <05-00 00-00 0A-00 00-00>, 8-byte object <06-00 00-00 0B-00 00-00>, 8-byte object <07-00 00-00 0C-00 00-00>, 8-byte object <08-00 00-00 0D-00 00-00>, 8-byte object <09-00 00-00 0E-00 00-00>, 8-byte object <0A-00 00-00 0F-00 00-00>, 8-byte object <0B-00 00-00 0E-00 00-00>, 8-byte object <0C-00 00-00 0F-00 00-00>, 8-byte object <0D-00 00-00 10-00 00-00>, 8-byte object <0E-00 00-00 11-00 00-00>, 8-byte object <0F-00 00-00 10-00 00-00>, 8-byte object <10-00 00-00 0F-00 00-00>, 8-byte object <11-00 00-00 0E-00 00-00>, 8-byte object <12-00 00-00 0D-00 00-00>, 8-byte object <12-00 00-00 0C-00 00-00>, 8-byte object <12-00 00-00 0B-00 00-00>, 8-byte object <12-00 00-00 0A-00 00-00> }
  GetParam().expected
    Which is: { 8-byte object <04-00 00-00 0A-00 00-00>, 8-byte object <05-00 00-00 0A-00 00-00>, 8-byte object <06-00 00-00 0B-00 00-00>, 8-byte object <07-00 00-00 0C-00 00-00>, 8-byte object <08-00 00-00 0D-00 00-00>, 8-byte object <09-00 00-00 0E-00 00-00>, 8-byte object <0A-00 00-00 0F-00 00-00>, 8-byte object <0B-00 00-00 0F-00 00-00>, 8-byte object <0C-00 00-00 0F-00 00-00>, 8-byte object <0D-00 00-00 10-00 00-00>, 8-byte object <0E-00 00-00 11-00 00-00>, 8-byte object <0F-00 00-00 10-00 00-00>, 8-byte object <10-00 00-00 0F-00 00-00>, 8-byte object <11-00 00-00 0E-00 00-00>, 8-byte object <12-00 00-00 0D-00 00-00>, 8-byte object <12-00 00-00 0C-00 00-00>, 8-byte object <12-00 00-00 0B-00 00-00>, 8-byte object <12-00 00-00 0A-00 00-00> }
Walk #3
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . ✫ ✔ ✔ . . . . ##. . . ##✔ . . . . 
. . . . . . ✔ . . . ##. . . ##✔ . . . . 
. . . . . . . ✔ . . ##. . . ##✔ . . . . 
. . . . . . . . ✔ . ##. . . ##✔ . . . . 
. . . . . . . . . ✔ ##✔ . . ##✔ . . . . 
. . . . . . . . . . ✔ ✘ ✔ . ##✔ . . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:68: Failure
Expected equality of these values:
  points
    Which is: { 8-byte object <04-00 00-00 0A-00 00-00>, 8-byte object <05-00 00-00 0A-00 00-00>, 8-byte object <06-00 00-00 0B-00 00-00>, 8-byte object <07-00 00-00 0C-00 00-00>, 8-byte object <08-00 00-00 0D-00 00-00>, 8-byte object <09-00 00-00 0E-00 00-00>, 8-byte object <0A-00 00-00 0F-00 00-00>, 8-byte object <0B-00 00-00 0E-00 00-00>, 8-byte object <0C-00 00-00 0F-00 00-00>, 8-byte object <0D-00 00-00 10-00 00-00>, 8-byte object <0E-00 00-00 11-00 00-00>, 8-byte object <0F-00 00-00 10-00 00-00>, 8-byte object <0F-00 00-00 0F-00 00-00>, 8-byte object <0F-00 00-00 0E-00 00-00>, 8-byte object <0F-00 00-00 0D-00 00-00>, 8-byte object <0F-00 00-00 0C-00 00-00>, 8-byte object <0F-00 00-00 0B-00 00-00>, 8-byte object <0F-00 00-00 0A-00 00-00> }
  GetParam().expected
    Which is: { 8-byte object <04-00 00-00 0A-00 00-00>, 8-byte object <05-00 00-00 0A-00 00-00>, 8-byte object <06-00 00-00 0B-00 00-00>, 8-byte object <07-00 00-00 0C-00 00-00>, 8-byte object <08-00 00-00 0D-00 00-00>, 8-byte object <09-00 00-00 0E-00 00-00>, 8-byte object <0A-00 00-00 0F-00 00-00>, 8-byte object <0B-00 00-00 0F-00 00-00>, 8-byte object <0C-00 00-00 0F-00 00-00>, 8-byte object <0D-00 00-00 10-00 00-00>, 8-byte object <0E-00 00-00 11-00 00-00>, 8-byte object <0F-00 00-00 10-00 00-00>, 8-byte object <0F-00 00-00 0F-00 00-00>, 8-byte object <0F-00 00-00 0E-00 00-00>, 8-byte object <0F-00 00-00 0D-00 00-00>, 8-byte object <0F-00 00-00 0C-00 00-00>, 8-byte object <0F-00 00-00 0B-00 00-00>, 8-byte object <0F-00 00-00 0A-00 00-00> }
[==========] 6 tests from 1 test case ran. (3 ms total)
[  PASSED  ] 3 tests.
[  FAILED  ] 3 tests, listed below:
[  FAILED  ] FindPathPatternsParams/FindPathPatternsTest.sample/0, where GetParam() = 96-byte object <60-8A A2-42 14-56 00-00 07-00 00-00 00-00 00-00 57-61 6C-6B 20-23 31-00 0F-00 00-00 0E-00 00-00 E0-23 A3-42 14-56 00-00 C0-25 A3-42 14-56 00-00 C0-25 A3-42 14-56 00-00 02-00 00-00 03-00 00-00 12-00 00-00 05-00 00-00 30-B2 A2-42 14-56 00-00 B0-B2 A2-42 14-56 00-00 B0-B2 A2-42 14-56 00-00>
[  FAILED  ] FindPathPatternsParams/FindPathPatternsTest.sample/2, where GetParam() = 96-byte object <60-8A A2-42 14-56 00-00 07-00 00-00 00-00 00-00 57-61 6C-6B 20-23 32-00 72-65 76-65 72-73 65-00 E0-23 A3-42 14-56 00-00 C0-25 A3-42 14-56 00-00 C0-25 A3-42 14-56 00-00 03-00 00-00 0A-00 00-00 12-00 00-00 0A-00 00-00 10-9E A2-42 14-56 00-00 A0-9E A2-42 14-56 00-00 A0-9E A2-42 14-56 00-00>
[  FAILED  ] FindPathPatternsParams/FindPathPatternsTest.sample/3, where GetParam() = 96-byte object <60-8A A2-42 14-56 00-00 07-00 00-00 00-00 00-00 57-61 6C-6B 20-23 33-00 72-65 76-65 72-73 65-00 E0-23 A3-42 14-56 00-00 C0-25 A3-42 14-56 00-00 C0-25 A3-42 14-56 00-00 03-00 00-00 0A-00 00-00 0F-00 00-00 0A-00 00-00 10-9E A2-42 14-56 00-00 A0-9E A2-42 14-56 00-00 A0-9E A2-42 14-56 00-00>

 3 FAILED TESTS

TODO (from my side of view):

fix pathfinder implementation
configure to run unit tests during each build (for TDD approach)
~pathfinder should not change "goal". Because if goal is changed, it's anyway a last point in path.~
write more tests to explain (and test) pathfinder behavior

Should it be fixed in this PR or it's a separate tickets?

akuskis commented 6 years ago

Show when position contains expected and actual (V), only actual (X) and only expected (O).

########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . ✫ ✔ ✔ . . . . ##. . . ##✔ . . . . 
. . . . . . ✔ . . . ##. . . ##✔ . . . . 
. . . . . . . ✔ . . ##. . . ##✔ . . . . 
. . . . . . . . ✔ . ##. . . ##✔ . . . . 
. . . . . . . . . ✔ ##✘ . . ##✔ . . . . 
. . . . . . . . . . ✔ ○ ✔ . ##✔ . . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################

akuskis commented 6 years ago

I agree that there can be multiple solutions for the same destination, I think that it's better to check that path contains X points and direction was changed Y times (instead of testing that it's equal to exact path, like it did int this PR). But anyway existing code would not pass this test, because direction was changed more then expected minimum (not optimal path). Why path finding can not be improved? It would affect performance? Now for me it's a bug, when hero walks like this:

Walk #1
########################################
. . . . . . . . . . . . . . . . . . . . 
. . ✘ . ✘ . ✘ . ✘ . ✘ . ✘ . ✘ . . . . . 
✫ ✘ ##✘ ##✘ ##✘ ##✘ ##✘ ##✘ ##✘ ✘ ✘ ✘ . 
. . . . . . . . . . . . . . . . . . . .

"Serial" test as I can see is "commented out" with the following "TODO: reimplement these tests for the new serial interface". It doesn't looks like this test was written first... it would be written after to skip manual testing. I'm not sure, why each test is a single application. I've done overriding "gtest", to show implementation of particular functions in one place and if it would require to change behavior, everything is already there. Empty "overriding" can be removed. But default "gtest printer" was replaced to remove useless output and show only useful information, because in general we are interested in failed tests (or if nothing is broken, then in final message that XX tests are pass).

akuskis commented 6 years ago

With checking only distance and amount of direction changes (because for one route there can be multiple acceptable solutions), output is the following:

Walk #1
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . ✫ . . . . . . . . . . ✔ ##✔ . . . . 
. . . ✔ . . . . . . . . ✔ . ##. ✔ . . . 
. . . . ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ . . ##. . ✔ ✔ . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure
Expected equality of these values:
  countDirections(points)
    Which is: 5
  GetParam().expectedDirectionsAmount
    Which is: 3
Walk #1 reverse
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ##✔ ✔ . . . 
. . . . . . . . . . . . . . ##. . ✔ . . 
. . . . . . . . . . . . . . ##. . . ✫ . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure
Expected equality of these values:
  countDirections(points)
    Which is: 5
  GetParam().expectedDirectionsAmount
    Which is: 3
Walk #2
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . ✫ ✔ ✔ . . . . ##. . . ##. . . ✔ . 
. . . . . . ✔ . . . ##. . . ##. . . ✔ . 
. . . . . . . ✔ . . ##. . . ##. . . ✔ . 
. . . . . . . . ✔ . ##. . . ##. . . ✔ . 
. . . . . . . . . ✔ ##✔ . . ##. . ✔ . . 
. . . . . . . . . . ✔ . ✔ . ##. ✔ . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure
Expected equality of these values:
  countDirections(points)
    Which is: 6
  GetParam().expectedDirectionsAmount
    Which is: 4
Walk #3
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . ✫ ✔ ✔ . . . . ##. . . ##✔ . . . . 
. . . . . . ✔ . . . ##. . . ##✔ . . . . 
. . . . . . . ✔ . . ##. . . ##✔ . . . . 
. . . . . . . . ✔ . ##. . . ##✔ . . . . 
. . . . . . . . . ✔ ##✔ . . ##✔ . . . . 
. . . . . . . . . . ✔ . ✔ . ##✔ . . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:124: Failure
Expected equality of these values:
  points.size()
    Which is: 18
  GetParam().expectedDistance
    Which is: 20
Goal point is not passable #1
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . ✔ . ##✔ . . . . 
. . . . . . . . . . . ✔ . . ##. ✔ . . . 
. . . . . . . . . . ✔ . . . ##. . ✔ . . 
. . . . . . . . . . ✔ . . . ##. . . ✫ . 
. . . . . . . . . . ✔ . . . ##. . . . . 
. . . . . . . . . . ✔ . . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure
Expected equality of these values:
  countDirections(points)
    Which is: 5
  GetParam().expectedDirectionsAmount
    Which is: 4
Goal point is not passable #2
########################################
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . . . . . ##. . . . . 
. . . . . . . . . . ##. . . ##. . . ✫ . 
. . . . . . . . . . ##✔ . . ##. . ✔ . . 
. . . . . . . . . . ##✔ . . ##. ✔ . . . 
. . . . . . . . . . ##✔ . . ##✔ . . . . 
. . . . . . . . . . ##✔ . . ##✔ . . . . 
. . . . . . . . . . . . ✔ . ##✔ . . . . 
. . . . . . . . . . . . . ✔ ##✔ . . . . 
. . . . . . . . . . . . . . ✔ . . . . . 
. . . . . . . . . . . . . . ##. . . . . 
########################################
/home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure
Expected equality of these values:
  countDirections(points)
    Which is: 5
  GetParam().expectedDirectionsAmount
    Which is: 4
[==========] 6 tests from 1 test case ran. (2 ms total)
[  PASSED  ] 0 tests.

All tests now fail. I like that now there is no need to check with exact path, but I do not like that hero should turn before hitting the wall (but if do not check that amount of direction changes is minimum, then hero would walk like a drunk). I do not commit this changes, because we are not done with expected behavior of "pathFind" (function).

wheybags commented 6 years ago

The pathfinder inetntionally does not find the optimal solution, if it did it would be too slow. Really all we can check in a test is that it made it to the destination when it should, and didn't when it shouldn't.

On Sun, Aug 12, 2018 at 9:08 PM, Artem Kuskis notifications@github.com wrote:

With checking only distance and amount of direction changes (because for one route there can be multiple acceptable solutions), output is the following:

Walk #1 ######################################## . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ✔ . . . . . . . ✫ . . . . . . . . . . ✔ ##✔ . . . . . . . ✔ . . . . . . . . ✔ . ##. ✔ . . . . . . . ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ . . ##. . ✔ ✔ . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . ######################################## /home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure Expected equality of these values: countDirections(points) Which is: 5 GetParam().expectedDirectionsAmount Which is: 3 Walk #1 reverse ######################################## . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ✔ . . . . . . . ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ##✔ ✔ . . . . . . . . . . . . . . . . . ##. . ✔ . . . . . . . . . . . . . . . . ##. . . ✫ . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . ######################################## /home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure Expected equality of these values: countDirections(points) Which is: 5 GetParam().expectedDirectionsAmount Which is: 3 Walk #2 ######################################## . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . ✫ ✔ ✔ . . . . ##. . . ##. . . ✔ . . . . . . . ✔ . . . ##. . . ##. . . ✔ . . . . . . . . ✔ . . ##. . . ##. . . ✔ . . . . . . . . . ✔ . ##. . . ##. . . ✔ . . . . . . . . . . ✔ ##✔ . . ##. . ✔ . . . . . . . . . . . . ✔ . ✔ . ##. ✔ . . . . . . . . . . . . . . . . ✔ ##✔ . . . . . . . . . . . . . . . . . . ✔ . . . . . . . . . . . . . . . . . . . ##. . . . . ######################################## /home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure Expected equality of these values: countDirections(points) Which is: 6 GetParam().expectedDirectionsAmount Which is: 4 Walk #3 ######################################## . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . ✫ ✔ ✔ . . . . ##. . . ##✔ . . . . . . . . . . ✔ . . . ##. . . ##✔ . . . . . . . . . . . ✔ . . ##. . . ##✔ . . . . . . . . . . . . ✔ . ##. . . ##✔ . . . . . . . . . . . . . ✔ ##✔ . . ##✔ . . . . . . . . . . . . . . ✔ . ✔ . ##✔ . . . . . . . . . . . . . . . . . ✔ ##✔ . . . . . . . . . . . . . . . . . . ✔ . . . . . . . . . . . . . . . . . . . ##. . . . . ######################################## /home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:124: Failure Expected equality of these values: points.size() Which is: 18 GetParam().expectedDistance Which is: 20 Goal point is not passable #1 ######################################## . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ✔ . . . . . . . . . . . . . . . . . . ✔ ##✔ . . . . . . . . . . . . . . . . ✔ . ##✔ . . . . . . . . . . . . . . . ✔ . . ##. ✔ . . . . . . . . . . . . . ✔ . . . ##. . ✔ . . . . . . . . . . . . ✔ . . . ##. . . ✫ . . . . . . . . . . . ✔ . . . ##. . . . . . . . . . . . . . . ✔ . . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . ######################################## /home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure Expected equality of these values: countDirections(points) Which is: 5 GetParam().expectedDirectionsAmount Which is: 4 Goal point is not passable #2 ######################################## . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . . . . . ##. . . ##. . . ✫ . . . . . . . . . . . ##✔ . . ##. . ✔ . . . . . . . . . . . . ##✔ . . ##. ✔ . . . . . . . . . . . . . ##✔ . . ##✔ . . . . . . . . . . . . . . ##✔ . . ##✔ . . . . . . . . . . . . . . . . ✔ . ##✔ . . . . . . . . . . . . . . . . . ✔ ##✔ . . . . . . . . . . . . . . . . . . ✔ . . . . . . . . . . . . . . . . . . . ##. . . . . ######################################## /home/artem/projects/os/freeablo/test/unit/findpath/findpath_tests.cpp:125: Failure Expected equality of these values: countDirections(points) Which is: 5 GetParam().expectedDirectionsAmount Which is: 4 [==========] 6 tests from 1 test case ran. (2 ms total) [ PASSED ] 0 tests.

All tests now fail. I like that now there is no need to check with exact path, but I do not like that hero should turn before hitting the wall (but if do not check that amount of direction changes is minimum, then hero would walk like a drunk). I do not commit this changes, because we are not done with expected behavior of "pathFind" (function).

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/wheybags/freeablo/pull/380#issuecomment-412364842, or mute the thread https://github.com/notifications/unsubscribe-auth/ABCumgVWiw-kF_-96KIUrcaKmpjLvUsoks5uQH0hgaJpZM4VlYcK .

akuskis commented 6 years ago

Tests are updated, now we are testing multiple things in parameterized test. So test was splitted (one check per test). Also added some more tests, like "walksStraightOnRectangleMap" which helps me to fix bug with "drunk walk" (sorry, but I can't accept that my character walks like that). I've added "distance" in weight. Diagonal is longer then catheus, that is the main fix. Also some code was removed (there was no need in it). I do not think that after this changes, path finding would work slower then it was. Also that test helps me to find a bug in code ("get" function).

Should I make another PR with bug fix and PR with path finder changes? It's more logical to have them here, because it's result of writing tests, but we can stuck a bit with merging PR, so I can make a separate PR.

wheybags commented 6 years ago

Mostly looks good, but I noticed a problem walking around town? pathfind_bug

When the player is standing beside Griswold like that, and clicks behind his house, pathfinding fails (and it works on master).

akuskis commented 6 years ago

I'll take a look, thanks! PS: I have some problems with original source files. That is why I have not tested in game.

wheybags commented 6 years ago

What do you mean by problems with original source files?

On Tue, Sep 11, 2018 at 9:21 AM, Artem Kuskis notifications@github.com wrote:

I'll take a look, thanks! PS: I have some problems with original source files. That is why I have not tested in game.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/wheybags/freeablo/pull/380#issuecomment-420173730, or mute the thread https://github.com/notifications/unsubscribe-auth/ABCums9oq1aFuKPQQ2Rw0EmlyOEq0tVMks5uZ2SEgaJpZM4VlYcK .

akuskis commented 6 years ago

What do you mean by problems with original source files? … On Tue, Sep 11, 2018 at 9:21 AM, Artem Kuskis @.***> wrote: I'll take a look, thanks! PS: I have some problems with original source files. That is why I have not tested in game. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#380 (comment)>, or mute the thread https://github.com/notifications/unsubscribe-auth/ABCums9oq1aFuKPQQ2Rw0EmlyOEq0tVMks5uZ2SEgaJpZM4VlYcK .

Sorry, "resources" (not "sources").

akuskis commented 6 years ago

Added heuristic from "master" version with some changes.

wheybags commented 5 years ago

Sorry for the slow response, I haven't had much time to work on freeablo lately. I still have an issue with walking around: screenshot from 2018-11-10 19-34-52

If I stand in that position and click the red x, pathfinding will fail. Also, I see you have done the unit tests in a different way to the other ones, putting them all in the same executable - that's fine (the old ones were all commented out anyway), but ti won't run in travis and appveyor, so we should update their configs to fix that. Also, thinking about it a bit, instead of having the heuristic disincentivise diagonal movement, it should probably disincentivise direction changes instead. It's fine to move in a straight diagonal line, it's the zig-zagging we want to prevent.

akuskis commented 5 years ago

As far as I remember, it fails in "master" branch too, because deep is limited. I'll take a look later to provide more details with examples (I've changed laptop and got no time right now to setup and check).

About path finding: at first I've counted direction changes, but it was not good as distance measurements. We know exactly how long this path is and can choose the shortest. Basic logic is: selection_022

I'll provide more details and update travis later.

akuskis commented 5 years ago

Happy New Year! Ok, I've checked. Your example doesn't work even in "master" branch. That is why I've increased amount of iterations. Also added a test, to check that depth is limited.

Also at first I've tried to restrict amount of direction changes, but as you see, I've finished with measuring distance. Below you can find example, why less direction changes doesn't mean the best path to go. Especially when path is much longer then in example below.

wheybags commented 5 years ago

Ok, that makes sense. I moved around some of the other tests and merged. Thanks for all the work you put into this PR!

wheybags / freeablo

Replaced manual pathfinder tests by auto #380