## Abstract

The Weighted Region Problem is defined as the problem of finding

a cost-optimal path in a weighted planar polygonal subdivision.

Searching for paths on a grid representation of the scene is fast and

easy to implement. However, grid representations do not capture

the exact geometry of the scene. Hence, grid paths can be inaccurate

or might not even exist at all. Methods that work on an exact

representation of the scene can approximate an optimal path up to

an arbitrarily small epsilon-error. However, these methods are computationally

inefficient and thus not well-suited for real-time applications.

In this paper, we analyze the quality of optimal paths on a

8-neighbor-grid. We prove that the costs of such a path in a scene

with weighted regions can be arbitrarily high in the general case. If

all regions are aligned with the grid, we prove that the costs are at

most 4 + sqrt(4 - 2 sqrt(2)) times the costs of an optimal path. In addition,

we present a new hybrid method called Vertex-based Pruning

(VBP). VBP computes paths that are epsilon-optimal inside a pruned

subset of the scene. Experiments show that VBP paths can be computed

at interactive rates, and are thus well-suited as an input for

advanced path-following strategies in robotics, crowd simulation or

gaming applications.

a cost-optimal path in a weighted planar polygonal subdivision.

Searching for paths on a grid representation of the scene is fast and

easy to implement. However, grid representations do not capture

the exact geometry of the scene. Hence, grid paths can be inaccurate

or might not even exist at all. Methods that work on an exact

representation of the scene can approximate an optimal path up to

an arbitrarily small epsilon-error. However, these methods are computationally

inefficient and thus not well-suited for real-time applications.

In this paper, we analyze the quality of optimal paths on a

8-neighbor-grid. We prove that the costs of such a path in a scene

with weighted regions can be arbitrarily high in the general case. If

all regions are aligned with the grid, we prove that the costs are at

most 4 + sqrt(4 - 2 sqrt(2)) times the costs of an optimal path. In addition,

we present a new hybrid method called Vertex-based Pruning

(VBP). VBP computes paths that are epsilon-optimal inside a pruned

subset of the scene. Experiments show that VBP paths can be computed

at interactive rates, and are thus well-suited as an input for

advanced path-following strategies in robotics, crowd simulation or

gaming applications.

Original language | English |
---|---|

Title of host publication | 7th International ACM SIGGRAPH Conference on Motion in Games |

Pages | 77-86 |

Number of pages | 10 |

DOIs | |

Publication status | Published - 2014 |

Event | 7th International ACM SIGGRAPH Conference on Motion in Games - USC Institute for Creative Technologies, Los Angeles, United States Duration: 6 Nov 2014 → 8 Nov 2014 |

### Conference

Conference | 7th International ACM SIGGRAPH Conference on Motion in Games |
---|---|

Country/Territory | United States |

City | Los Angeles |

Period | 6/11/14 → 8/11/14 |

## Keywords

- path planning
- weighted region problem
- grid representation