Pathfinding in a grid system

Question

I'm currently building a small grid-based game in C++ using SDL. I've made a tile class, which represents each individual tile on a map. This tile class is used in a 2 dimensional vector, one dimension representing the X axis and the other one the Y axis.

I'm having an algorithm issue, I do not even know where to start with this, let's say I have this map:

0 0 1 1 0 E
0 0 0 1 0 1
0 C 0 1 0 1
0 1 0 1 0 1
0 1 1 1 1 1

C is my character, E is an exit, and 1 is a floor tile.

I would like to figure out the most optimal way to figure out if there's a way for the character to reach the exit. I know I could use a function to manually check every tile around C, and for every floor tile around C, I check again every tile around, until I find a consistent path to get to E, but that doesn't seem very optimal.

Can I have a clue or some sort of direction in which to orient myself?

Answer 1

There are so many algorithms which can find paths between two points. There are three algorithms which are easy to implement and understand.

1. Depth first search (DFS)
2. Breadth first search (BFS)
3. Dijkstra's algorithm

Depth first search

This algorithm, takes the current node, finds all the neighbors, puts them in a stack, pops by one and traverses till the end or it finds the path.

Breadth first search

This algorithm, takes the current node, finds all the neighbors, puts them in a queue, dequeues one by one and traverses till the end or it finds the path.

The difference between DFS and BFS is that, DFS cannot guarantee optimal solution. Consider this case.

S 1 1
1 1 1
1 1 E

Assuming S is (0,0) and E is (2, 2). There are many optimal solutions to this maze. Since, DFS checks the path of its neighbours till the end, it might take S -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (1,2) -> E and it will return 6 as the cost of the path. Whereas, BFS finds all the neighbours, neighbours of all neighbours and goes on. If one of neighbors is E, it returns the cost. That would be guaranteed to be optimal. So, BFS might go like this. S -> (1,0) -> (2,0) -> (2,1) -> E (It finds neighbours of neighbours, it does not go till the end with each of the neighbours).

Dijkstra's algorithm

It is similar to BFS, but it can have weights. In the example, we assumed that the cost of moving from one node to another costs us 1 unit. In Dijkstra's algorithm, it allows us to use any positive integer as the cost, and it can be different for each and every link.

Conclusion

If you want optimal result, go for BFS or Dijkstra's algorithm. For your case, BFS should work.

Answer 2

Take a look at the most used path finding algorithms.

http://qiao.github.io/PathFinding.js/visual/

This is done in JS, but you should be able to find a C++ implementation of the one that fits your needs, or write your own.