CODEWITHSUNDEEP
cshortest-path
user6431052
user6431052

Reputation: 3

shortest path in two-dimensional array using C

I want to find a shortest path from (0,0) to (6,6) but i don't know how to do it using C. -1 is the way I can go, and -2 is the way I can't go. 0 is starting point and -3 is ending point. Please help..

#include<stdio.h>

#define VERTICES 7

int maze[VERTICES][VERTICES] = {
{  0, -2, -1, -1, -1, -1, -1 },
{ -1, -2, -1, -2, -2, -2, -2 },
{ -1, -1, -1, -1, -1, -1, -1 },
{ -1, -2, -2, -2, -2, -2, -1 },
{ -1, -2, -1, -1, -1, -2, -1 },
{ -1, -2, -1, -2, -2, -2, -1 },
{ -1, -1, -1, -2, -1, -1, -3 } };

int A[VERTICES][VERTICES];

printA(int n)
{
int i, j;
printf("===============================\n");
for (i = 0; i < n; i++){
    for (j = 0; j < n; j++)
        printf("%3d", A[i][j]);
    printf("\n");
}
printf("===============================\n");
}
void solve(int n)
{
int i, j, k=0;
for (i = 0; i<n; i++)
    for (j = 0; j<n; j++)
        A[i][j] = maze[i][j];

while (1)
{
    for (i = 0; i < n; i++)
    {   
        for (j = 0; j < n; j++)
            if (A[i][j] == k)
            {
                if (0 <= i + 1 < n && 0 <= j < n && A[i + 1][j] == -1)
                    A[i + 1][j] = k + 1;
                if (0 <= i - 1 < n && 0 <= j < n && A[i - 1][j] == -1)
                    A[i - 1][j] = k + 1;
                if (0 <= i < n && 0 <= j + 1 < n && A[i][j + 1] == -1)
                    A[i][j + 1] = k + 1;
                if (0 <= i < n && 0 <= j - 1 < n && A[i][j - 1] == -1)
                    A[i][j - 1] = k + 1;
                if (A[i][j] == -3)
                    break;
            }
    }
    k++;
}
printf("%d\n", k);
printA(VERTICES);
}

main()
{
solve(VERTICES);
}

Upvotes: 0

Views: 5671

Answers (2)

deqyra
deqyra

Reputation: 764

As Jan Raufelder suggested, you could use the A* algorithm, which stands as the best compromise between quickness and accuracy and is widely used in video games. However, there are cases for which A* will deliver the shortest path after quite a long time, and these worst case scenarii mostly appear for mazes. 

███████████████████████  In this case,
██ S       1 ██ E    ██  A* will start at S,
██   █████████████   ██  explore branch 1,
██            2 ██   ██  then branch 2,
██   █████████████   ██  and then branch 3,
██            3 ██   ██  before taking branch 4
██   █████████████   ██  to finally get to E.
██            4      ██  It still gives you the shortest path,
███████████████████████  but it takes a huge time.

If you want a more robust and generally faster solution, you could try to convert your maze into a graph (vertices and edges), and apply a Dijkstra algorithm on it. But that implies you redo everything you have done so far, and take some time to think about how you are going to build your maze in memory, because it won't simply be a 2D-array of int.

Upvotes: 0

Jan Raufelder
Jan Raufelder

Reputation: 287

I know, this should be a commend but i do not have enough reputation.. Anyways:

You could also look for the a* (a-star) Algorithm to solve your problem there are heaps of implementations and descriptions available e.g.:

http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/

http://www.codeproject.com/Articles/9880/Very-simple-A-algorithm-implementation

heyes-jones.com/astar.php

Upvotes: 1

Related Questions