Map Abstraction with Adjustable Time Bounds

Sourodeep Bhattacharjee, Scott D. Goodwin


The paper presented here addresses the problem of path planning in real time strategy games. We have proposed a new algorithm titled Map Abstraction with Adjustable Time Bounds. This algorithm uses an abstract map containing non-uniformly sized triangular sectors; the centroids of the sectors guide the path search in the game map. In a pre-processing step we calculate an upper and lower time limit to plan paths for a given two dimensional grid map that is known beforehand. Depending on the time limits, we vary the size of the sectors to save search time or to improve path quality. We have experimented using maps from commercial games such as Dragon’s Age: Origins and Warcraft III. In the worst case MAAT returns paths that are 8% less optimal. MAAT has an expensive pre-processing step which ultimately lowers the overhead CPU time consumed during game play by 1.1 milliseconds.


Pathfinding; path-planning; map abstraction; hierarchical

Full Text:


Lululemon Black Friday cheap nfl jerseys Lululemon factory Outlet ny Black Friday discount tiffany outlet wholesale soccer jerseys online oakley black friday cheap nhl jerseys china cheap nfl jerseys north face black friday sale cheap nfl jerseys online Jordans Black Friday Sale 2015 Cheap Moncler Cyber Monday moncler outlet cheap soccer jerseys moncler outlet black friday cheap authentic nfl jerseys north face cyber monday Louboutin Black Friday canada wholesale cheap nfl jerseys lululemon cyber monday 2015 cheap nfl jerseys from china 2015 Cheap Moncler Black Friday Sale Moncler Cyber Monday 2015 cheap jerseys Lululemon Cyber Monday Sale jordans cyber monday deals 2015 cheap nike nfl jerseys Black Friday deals Lululemon 2015 jordan black friday 2015 Moncler Jackets Black Friday Sale 2015 Louboutin Pas Cher Black Friday 2015 Canada Lululemon north face black friday cheap wholesale soccer jerseys