3

I need my C program to be able to travel around a board. The board is represented by a 2D int array (where 0 and 7 are empty squares and everything else is an obstacle). The cost to move from one square to another is always the same but it should not move diagonally.

I've been looking up A* but it's confusing and every single example I could find is with C++ or Java so I'm starting to wonder if it's even possible on C.

That and if it's the best algorithm to use for it.

Edit: The board is either 24x25 or 25x24 I can't remember which

Improve this question
6
  • 1
    Is the board large? Very? How much? Commented Oct 24, 2012 at 5:59
  • Can you show us what your board looks like? Are you reading it in from a file and then storing it in a 2D array? Commented Oct 24, 2012 at 6:04
  • 1
    So are you doing pathing around the board? What kind of "travel" are you doing? Does the board ever change? Commented Oct 24, 2012 at 6:06
  • @nneonneo I'm assuming he's given a start point and an end point with a static board layout. Commented Oct 24, 2012 at 6:09
  • 1
    Oh and I'm not reading it from a file I'm making it in the program. Commented Oct 24, 2012 at 6:10

1 Answer 1

Reset to default
1

As your board is small, you can use a breadth-first search (BFS) doing a complete search for the best path. I think that the performance will be comparable if not better than A* algorithm.

The algorithm is simpler than A* and there are many implementations in C over the internet. Here is an example of a BFS transversal on a grid:

An illustration of a BFS transversal on a grid. If all squares are reachable, the distances from center are those indicated.

To get the path you can save a matrix (for example a 2d-array of char -- lets name it parent) where parent[x][y] is for example (0 - if you reach that square from left, 1 - right, 2 - up, 3 - down). For example, if you're visiting the square with coords (4,6) and will put the (5,6) on the queue, you do parent[5][6] = 2 because (5,6) came from the row above (4,6). So to retrieve the full path you can pick the destination node and save the parents coordinates until you reach the source square.

Now it is up to you think about and figure how you can implement it :)

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

How would that work for path finding? Would I look at all 4 squares around the start, and then keep going from there? Oh and how will it remember the path?
@RobertZ: yes, BFS is a graph search algorithm that can be used in your problem. It works by visiting all the neighbors from a node (square in your case). Everytime you visit a node, you put all neighbors of it on a queue. I recommend you to read the Wikipedia article that I put on my answer, you'll find out that BFS guarantee some properties useful in your problem (like the first time you reach a square, it will be the shortest path from the start point to that square).
That only leaves the problem of how I will remember the path it took to get there, or will I need to do multiple BFS's
Nope. You can save a matrix called parent for example. More details in the answer above.
@RobertZ instead of marking cells visited, you can assign them the step number when they were visited (exactly as in the picture), then to reconstruct a shortest path you simply need to step back from each n to any of n-1 until you reach 0.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.