#35 Stendhal: MaybeFix for bug [ 1222022 ]

closed-accepted
None
2005-07-05
2005-07-01
Matthias Totz
No

This patch modifies the A* algorithm to shorten the
search path. The trick is that this solution preferes the
direct diagonal solution. The bigger the difference from
the perfect path the bigger the additional cost.

pro:
- no complicated waypoint system, so no roadways
- in big open map significant faster
- in dungeons maps as fast as the current one

cons:
- does not always find the shortest path (but the path
should not be longer than 10 per cent than the shortest
one)
- in a very unlikly situation the path will be more than 10
per cent longer (it's a big 'U'-shaped barrier with the start
point over the U and the endpoint below).
- by removing the 'distance'-fix any searches for not
existing paths take the full time (see Log "Path::
searchPathResult" when starting the deamon...)

Discussion

  • Matthias Totz
    Matthias Totz
    2005-07-01

    Logged In: YES
    user_id=1127086

    I'll add a little program to test the pathfinding. It loads a map
    and finds paths with random start and end points. No user
    interaction possible.
    The patch is needed for the program to compile.

     
  • Logged In: YES
    user_id=3949

    I will check them.
    But the problem is that the full time is unaffordable as it is
    found oftenly ( as creatures wants to move to unreachable
    areas. )

    I think the waypoint system will fix this problem because the
    search time will be a lot of smaller... and the distance-fix will
    still be valid.

     


Anonymous


Cancel   Add attachments