/ #pathfinding

Pathfinding algorithms: Introduction

William Turner

All computer scientists should know how to find their way. But not all researchers name this task the same. Pathfinding is a good example of a problem that takes many different shapes depending on why answers the question.

A critical step in problem solving is finding how to think about the problem at hand. This means finding the correct abstraction — and naming it right. I usually start my projects by mapping all the related concepts. As one of my university teachers1 explained:

One way to succeed is to be the last to rediscover a powerful idea. The solution to your issue certainly hides in a PhD thesis somewhere.

How do we go from A to B? Many problems can be framed as pathfinding, and different frameworks of thought will be useful depending on the application:

map of topics and useful algorithms for pathfinding

In this blog posts series, our goal will be to describe the problems faced by those who study particular flavors of pathfinding, as well as insightful algorithms.

We will start by reviewing “vanilla” pathfinding, on graphs, just to recall the vocabulary. Then we’ll describe richer problems: networks and maps, states, actions….

This series is still a work in progress.

  1. Nikos, of course. ↩︎