• 01/03/12 02:18 PM
    Sign in to follow this  
    Followers 0

    A simple method to speed up path finding

    Artificial Intelligence

    NiuJian
    • Posted By NiuJian
    The method is simple. 1.jpg Red grid is block grid,Green grid can walk. first,Pre process on map to get datas that we need: 1) The map is divided into many regions, each region consist of a number of grids, these regions must be convex polygon(int most cases,they are rectangulars), there are not block grids in these regions. 2.jpg 2) then generate the shortest path information between regions, such as: the shortest path information between region r1 to region r4 is: r1 -> r2 -> r3 -> r4, save these information in a table. 3) get shared adjacent grid between regions,for the sake of brevity,I shall select middle grid in share adiacents. 4) Save the above information to map data file. Second, path finding process: 1)Determine region where the source grid at and region where dest grid at, for example the source grid in the region r1, the dest grid in the region r4. 2) find the shortest path between the two regions by searching the region path table, the shortest path between the region r1 and region r4 is: r1 -> r2 -> r3 -> r4, this is rough path. 3) the result path will is: source grid -> g2(regions r1 and r2 share grid g2) -> g3(region r2 and region r3 shared grid g3)-> dest grid. 3.jpg Because there are not block grids in these convex polygon regions, so we can walk a straight line in these regions.
    0


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!


    Register a new account

    Sign in

    Already have an account? Sign in here.


    Sign In Now

    cireNeikual

    • 5
      
    0

    Share this review


    Link to review
    Ectara

    • 5
      
    0

    Share this review


    Link to review