3
\$\begingroup\$

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)

enter image description here

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.

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Tutorials seems to be great, but unfortunately, I can't use any of these pathfinding algorithms. Since I want the path to be random everytime, and the algorithms search the fastest path. I just random generate each direction, if it hits a wall i start alloveragain until it randomed a path to the right side. Not very efficient, but since it must be random everytime not too bad. \$\endgroup\$ – jeromintus Aug 26 '15 at 8:34
  • \$\begingroup\$ In your situation all the paths are the same length (6); that's part of why A* is overkill here. No path is shorter than any other. If you're using a graph search like Breadth First Search, to get a random path, you can either randomize the order of the neighbors function or randomly choose from the queue instead of always choosing the leftmost element of the queue. \$\endgroup\$ – amitp Aug 27 '15 at 16:58
2
\$\begingroup\$

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. 

http://www.policyalmanac.org/games/aStarTutorial.htm

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.