#177 Pathfinding problem

closed-fixed
None
7
2005-12-05
2005-11-24
No

I have spotted something very weird in pathfinding
algorithm. If you explored a part of galaxy and then
you go back to the explored system and send it to the
unexplored planet that have only one visible starlane
to it (however there can be other, but you haven't
explored that part from the other side of this system)
the path is shown properly, but the scout doesn't
follow it. To illustrate what I mean I will try to show
it by rough ascii art.
S---S
S / \ / \ / B
/ S
C S S
|\ ---S----S | S---D S
/ \ |
/ S---S S
A

Let's suppose the scout is ordered to go from A to B.
It's path is A-C-B. However when it moves to C it
doesn't follow it's path! It's going towards D. The
lines drawn are visible starlanes, S means system.

Discussion

  • Karol Tomala

    Karol Tomala - 2005-11-24

    Logged In: YES
    user_id=926790

    I see that my drawn graph got broken. Here is the correct
    version:
    ...................S....|
    ................../.\...S
    .................S...\./.\ ................/.....S...B
    .............../
    ..............C.........S
    ..............|\ ---S----S.....|.S---D.....S
    ../......\....|
    ./........S---S........S
    A

    Just substitute . as a space and you'll get the idea. Also.
    You have to look at this graph in fixed font.

     
  • Dennis Brakhane

    Dennis Brakhane - 2005-11-24

    Logged In: YES
    user_id=26932

    Do you have a savegame available?

     
  • Karol Tomala

    Karol Tomala - 2005-11-24

    Logged In: YES
    user_id=926790

    How am I supposed to have it when saving crashes FO?

     
  • Zach Laine

    Zach Laine - 2005-11-28

    Logged In: YES
    user_id=729903

    The save game crash is now fixed in CVS. Can you supply a
    savegame that demonstrates this bug now?

     
  • Karol Tomala

    Karol Tomala - 2005-11-29

    Saves

     
  • Karol Tomala

    Karol Tomala - 2005-11-29

    Logged In: YES
    user_id=926790

    I have reproduced this bug. Sending savegames now.

     
  • Zach Laine

    Zach Laine - 2005-12-03
    • priority: 5 --> 7
     
  • Zach Laine

    Zach Laine - 2005-12-03
    • assigned_to: nobody --> tzlaine
     
  • Geoff Topping

    Geoff Topping - 2005-12-04
     
  • Geoff Topping

    Geoff Topping - 2005-12-04

    Logged In: YES
    user_id=913462

    This bug happens when there exists a path from the location
    of a ship to a system, which is shorter than the shortest
    path your empires knows about. If a ship is located at the
    system where the two paths diverge when it is given the
    order to move, then it will take the path you know about for
    the next turn. If during a turn processing phase, the ship
    passes through a system where the paths diverge, the ship
    will take the "undiscovered" shorter path.

    In the attached, the ship will take the marked-in-green
    pathes when ordered to move to the indicated system in the
    two cases. In the left case, the ship decides during the
    turn which way to turn when reaching Situla, so takes the
    shorter hidden path to the right. In the right case, the
    ship's initial move follows the path shown, though on the
    turn after next, it reaches Shapley, has to make a decision
    about which path to follow, and actually turns around and
    heads back towards Situla to take the still-shorter hidden path.

     
  • Zach Laine

    Zach Laine - 2005-12-05
    • status: open --> closed-fixed
     

Log in to post a comment.