Special Pathfinding Algorithm

Question

I need help with following pathfinding Task:

I have a grid (7x7 squares) and the starting square is always on the far left side (column 0) and its target is to reach the far right side (column 6). Between col 1-5 are some walls where the path should "walk" around.

The special thing about the task is, the path can only walk straight,diagonal up, diagonal down, so its column increases += 1 for each movement.

For Example: (row/col) Start:(1/0) Path:(1/1) straight :(2/2) daigonal down :(3/3) diagonal down :(3/4) straight :(4/5) diagonal down :(4/6) straight (reached col 6 , finish)

I'm not sure about A*, maybe its also working for my task? can anyone help me to find a good algorithm for this task? I would prefer C++ as code.

Answer 1

A* would work fine for this task, but since your map is small, Breadth First Search would work too, and it's even simpler than A*. These are “graph search” algorithms, which require you to tell them what the allowed moves are. They are not limited to grids. In your case you would tell it that the allowed moves from (x,y) are to (x+1,y-1), (x+1,y), and (x+1,y+1).

As part of my A* tutorial I have some C++ code for Breadth First Search and A* that works for any graph. Look at the SquareGrid class; you will want to write your own neighbors function that looks at the three possible steps (straight, diagonal up, diagonal down) and checks that they're in the 7x7 map area, and that they're also not blocked by a wall.

Answer 2

A* will certainly work for this.

Linked below is an excellent tutorial on how to implement it.

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square …

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           

If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

Add the target square to the closed list, in which case the path has been found (see note below), or
Fail to find the target square, and the open list is empty. In this case, there is no path.   
3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path. 

Link

Answer 3

a* will work fine. In the selection of neighbor cells consider forward, forward_up, forward_down

Answer 4

Well if you don't want to use A* for some reason, try "Dijkstra’s algorithm" or "Greedy best first search".