Contents

Title - Abstract

Preface

Contents

1 Introduction

1.1 Digital maps

1.1.1 Raster data

1.1.2 Geometric data

1.2 Problem definition

1.3 Objective

1.4 Outline

2 Overview of path finding methods

2.1 Line intersection methods

2.2 Weighted graph methods

2.3 Other methods

3 Graph construction

3.1 Problem reduction

3.1.1 Limiting space

3.1.2 Introducing the cost function

3.2 Efficient representation

3.2.1 Implicit graph representation

3.2.2 Computing the cost function

3.2.3 Memory space

3.2.4 Sample implementation

4 Search algorithms

4.1 Overview of methods

4.1.1 Exhaustive search

4.1.2 Relaxation methods

4.1.3 Linear programming

4.1.4 Simulated annealing

4.2 Algorithm

4.2.1 Dijkstra’s algorithm

4.2.2 The A* heuristic improvement

4.2.3 Reconstructing the path

4.2.4 Avoiding directional biasing

4.2.5 Memory space and time complexity

4.2.6 Sample implementation

4.3 Progressive approximation

5 Examples

5.1 Avoiding obstacles

5.2 Avoiding enemies

5.3 Following roads

5.4 A* search area

5.5 Progressive approximation

5.6 Miscellaneous

6 Conclusions

6.1 General conclusions

6.2 Fields for future work

6.2.1 Dynamic scenes

6.2.2 Extending the number of edges

6.2.3 Faster ways of determining visibility

6.2.4 Approximate paths using non-optimal A* heuristics

6.2.5 Other graph search methods

7 Bibliography


Previous section... - Next section...