Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.

Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


A new method to speed up path finding

By Niu Jian | Published Jan 03 2012 08:18 AM in Artificial Intelligence

grid region path regions shortest information dest source grids
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

The method is simple.
Attached Image: 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.
Attached Image: 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.
Attached Image: 3.jpg
Because there are not block grids in these convex polygon regions, so we can walk a straight line in these regions.


Brief, good

Rock on dude!!!

Interesting, how would it deal with large maps and dynamically changing environments?

Excellent idea , Seems quite hard to implement in game programming.

This technique won't guarantee finding the shortest path. The shortest path between 2 regions will in many cases depend on where in the starting region the source is, and where in the destination region the goal is.


A more accurate implementation in terms of the optimal path would be to build the table not out of the region to region table, but the list of shared edges to the list of shared edges. Then that lookup table distances can be supplemented with the knowledge of the distance to those edges within the starting and ending region to better calculate an optimal path. This is the same reason why in a navmesh, using the center of the regions is a very poor reference point for the weighting calculations for the search.

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.