Fritz Heckel

Points to make

• Influence points far more efficient than influence maps
• Lookups are not much more expensive with some simple preprocessing: alpha_i * f(Distance to local influence point + Distance from local point to primary influence point) where alpha_i is a weight for influence type i, and f is decay function.
• Updates with preprocessed distance are worst case O(|R|) (number of regions)
• Updates w/out preprocessed distance are worst case O(|G|+|R|log|R|) (R: regions, G: gateways), using Dijkstra if no cached data
• Compare these values with region decomps on example worlds + grid discretization on example world

Outline:

• Introduction: strategic information, advantages of navigation meshes, how to integrate influence maps and meshes
• Background: strategic information– waypoint based SBEs, influence maps, other? Navigation mesh background, decompositions
• Method: general overview, detailed description of influence point structure. Lookup costs for calculating influence value. Insertion and update calculations.
• Evaluation: Evaluate costs of influence maps, influence points on four maps
• Conclusion