#1669 Stendhal: optimize A* using waypoints

closed-fixed
nobody
None
8
2005-10-16
2005-06-16
No

Actually A* is giving some problems because searchs
takes too much time.
Our actual fix is to limit the distance we will search a
path, so number of nodes is limited, unfortunately this
way of working doesn't fix the problem for long path
searchs.

My proposal is to use a navigation layer:
http://stendhal.game-server.cc/navigationpoints.png
( Big image )

The blue point define the points where A* will be applied,
so to seach a path from top-left blue point to bottom right
blue point we will only need to seach in 36 nodes instead
of 4096 nodes. As you see the simplification of the map
is awesome.
The only requirement is that each navigation point has at
least a neighbour on the same row or on the same
colum.

In other to do a good path searching we will have to do:
0) Route={}
1) start=search nearest blue point to start point
2) Route=Route+search(start point, start)
3) end=search nearest blue point to end point
4) Route=Route+searchNavigationMap(start, end)
5) Route=Route+searchNavigationMap(end, end point)

return Route

The only drawback that this method has is the creation of
roadways ( pathways ) that all A* users will follow...

If someone wants to implement this system... :)
A* algo is done, you would only need to define the data
structure to host the navigation map in such a way that it
is efficient.

Discussion

  • Matthias Totz

    Matthias Totz - 2005-08-01

    Small test to 'see' what A* is doing.

     
  • Matthias Totz

    Matthias Totz - 2005-08-01

    Logged In: YES
    user_id=1127086

    Added a graphical test (PathTest.java).

    Usage:
    Put the file in src/games/stendhal/PathTest.java
    Be sure the map-files are on your classpath in the correct
    location.
    In games.stendhal.server.StendhalRPZone.java change the
    line
    private CollisionDetection collisionMap;
    to
    public CollisionDetection collisionMap;

    All interesting stuff is done in the main()-method. That's it.

     
  • Matthias Totz

    Matthias Totz - 2005-08-20

    Logged In: YES
    user_id=1127086

    Added Locs patch for reading Navigation Points

     
  • Matthias Totz

    Matthias Totz - 2005-10-16
    • status: open --> closed-fixed
     
  • Matthias Totz

    Matthias Totz - 2005-10-16

    Logged In: YES
    user_id=1127086

    done. As the path between 2 waypoints (aka streets) have a
    preference of only 10% compared to non-street tiles there is
    nearly no roadways creation

     


Anonymous

Cancel  Add attachments





Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks