5 kyu

Optimized Pathfinding Algorithm

23 of 143ByteSheep
Description
Loading description...
Games
Algorithms
Puzzles
View
AllIssues3Questions2Suggestions2Show Resolved
  • Please sign in or sign up to leave a comment.
  • AlexisGarza Avatar

    Hi, I'm trying to resolve this in Javascript, whenever I try submiting, Random test and Performance testing fail.

    If i remove all the walls from the Grid, the performance test passes.

    anyone knows why this is ?

  • monadius Avatar

    This comment has been hidden.

  • KsanfFillum Avatar

    My solution on C# passed for any tests but failed on performance and random tests. And always result different for 1 (Expected: 405 But was: 404 for example). Whats wrong with this tests?

  • Voile Avatar

    Approved

  • Blind4Basics Avatar

    Hi,

    Several things here...

    First: Python translation (Might need a moderator for approval: the original author has not been connected this month. But maybe he will come back. Who knows... ;) )

    • description has been fixed and the figures in the description are now matching the grids of the tests
    • I made the performance test a real performance test (see below)
    • added 20 random tests instead of just one
    • added 3 new fixed tests with some important edge cases

    Now, the issue part (coming from Java):

    • the performance test has good chances to NOT be demanding: the starting point is chosen randomly on the full height of the grid, so if it begins "high" (talking about the index value), that's not demanding at all. So, need limitation of the value of the starting row.
    • needs real random tests, not just one (2 actually, with the performance test. But that's not enough...)
    • needs REAL random tests: the block frequency you choose is too high! On a bunch of 20 random grids, I found none where it cas possible to reach the last line so answer is always 0 for this test, currently. => I used 20% for the block frequency threshold, as for the performance test.

    I strongly suggest to update the test cases in each languages so that they match the tests I implemented in the python translation.

    Cheers,

    B4B

    Note: if the author doesn't show up and a moderator approve the python version, I'll update the Java version myself. But someone will have to do the JS and C# versions.

  • myjinxin2015 Avatar

    Have it, But some suggestions about description to you.

    In array, the goal line is the last row(r-1), but in the descripton, your example is put the line at top

    rows
3 |__|__|__|__|
2 |__|__|__|__|
1 |__|__|PL|__|              PL = Player position
0 |__|__|__|__|
    0  1  2  3  columns

    Why not show it like this:

    rows
    0  1  2  3  columns
0 |__|__|__|__|
1 |__|__|PL|__|
2 |__|__|__|__|              PL = Player position
3 |__|__|__|__|

    and most of these "picture" are confused, like this:

    RE = Reachable field

4 |RE|RE|RE|                           4 |RE|RE|□□|RE|
3 |__|__|__|                           3 |□□|__|__|__|
2 |__|□□|□□|      2 |__|__|□□|□□|      2 |__|__|□□|□□|        2 |RE|
1 |__|__|__|      1 |□□|□□|__|__|      1 |□□|PL|__|__|        1 |__|
0 |__|PL|__|      0 |__|□□|__|PL|      0 |□□|□□|__|□□|        0 |PL|
    0  1  2           0  1  2  3           0  1  2  3             0
  Output: 3           Output: 0            Output: 3         Output: 1

    They are all mixed up together. May need to re-layout ;-)

  • myjinxin2015 Avatar
     
    Test.it("Single path should return 1", function() {
    var inputGrid = [[true],[true]];
    Test.assertEquals(getNumberOfReachableFields(inputGrid, 1, 1, 0, 0), 1);
  });

    JS version, The arguments of this example testcase perhaps should be inputGrid, 2, 1, 0, 0

  • myjinxin2015 Avatar

    This comment has been hidden.

  • dinglemouse Avatar

    This comment has been hidden.

  • Kaiyou Avatar

    My algorithm works for small sizes, but fails on bigger ones. (Finds less paths than expected and is off by less then around 12.) Is there a way to inspect the larger grids to figure out what went wrong? I tried to solve this by walking every possible path, setting flags when a goal was found (to account for multiple paths leading to the same goal) and returning the sum of all flags.

    Are you perhaps allowed to move down under certain conditions?

    Also, I regularly get this error from "PerformanceTest" (but not always) and can't figure out why. If someone got any ideas that would be great.

    SetUp : System.NullReferenceException : Object reference not set to an instance of an object at NUnit.Core.NUnitFramework.GetResultState (System.Exception ex) <0x40914c20 + 0x0004c> in :0 at NUnit.Core.TestMethod.RunTest () <0x4090ac40 + 0x00168> in :0

  • dinglemouse Avatar

    FYI the test case called singlePath has an input grid with different size to what the passed rows/columns parameters say.

  • ByteSheep Avatar

    If you get stuck and aren't sure how to approach this problem then you can read through the following discussion: http://answers.unity3d.com/questions/1229414/very-basic-pathfinding-for-infinite-runner.html#answer-1229436