What pathfinding algorithm is suitable for a small grid and hard-coded points?

Question

I made an A* pathfinder to see if it works with what I'm trying to do, but I don't think it is good enough.

My grid is not too big and has some hard-coded points so what I'm trying to do is check only the hard-coded points to find paths between them; for example:

┌──────────┐
│A        B│
├───────── │
│D        C│
└──────────┘

So to get from point A to point D the pathfinder function should tell you go from A --> B --> C --> D.

What pathfinding algorithm would work for this?

Answer 1

For a single query, A* is probably about as good as you can do.

For many queries, you can convert your grid to an undirected, weighted graph consisting only of the hard-coded points where directly connected points have an edge between them and the edge weight is the distance between them.

For your example, the graph would look something like:

   9
A --- B
      | 2
D --- C
   9

To construct this graph:

For matrices where every point can only get to very few other points directly, breadth-first search from each point is probably the best option.

If any point can get to many others, an all pairs shortest path algorithm or some derivation comes to mind, although there may be better ways.

To use this graph:

You can just run A* on it.

Assuming you store the coordinates of each point, you'd still be able to use Manhattan distance as the heuristic (assuming you were using that before).