Minedetector, shortest path

This is a discussion on Minedetector, shortest path within the C Programming forums, part of the General Programming Boards category; Solved, thanks :)...

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    14

    shortest path (SOLVED)

    Solved, thanks :)
    Last edited by Kurdo; 05-19-2011 at 01:57 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,512
    What is the correct answer for the map you provided? Knowing your incorrect results doesn't help much, and I don't feel like running Djikstra's algorithm by hand to figure this out. How does the robot know where a mine is? I don't see any on your map. Also, you should work on providing a neater map.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    261
    There's a lot code there to swallow. Before you ask others to invest their time to help you might consider:

    1) Indentation and whitespace matter (yours could use some work)
    2) Give your variables decent names (most of yours have horrible names)
    3) Don't use globals unless you MUST. (Your code uses way more than I think it should)
    4) Comments matter (it's hard to tell what the intentions are for most of your code. This problem, believe it or not, is made worse by #1, #2 and #3).

  4. #4
    Registered User
    Join Date
    Dec 2010
    Posts
    14
    There is no correct answer. You just choose a starting point and an ending point. Dijkstra's algorithm will then give you the shortest path. From that path, I have to give the directions between each point.
    so for example: If the robot has to go from point 1 to point 16
    my code gives the output: 1 5 12 19 18 17 16
    Next thing is to give the direction it goes between each step, so it goes straight forward, straight forward, straight forward, left, straight forward, straight forward.

    I just found out that my code gives result=3 at the direction fuction, i just dont know why.

    Also sorry about the map, i had to make it quickly. I'm going to put some comments in the code so it gets a little bit clearer, thanks!

  5. #5
    Registered User
    Join Date
    Dec 2010
    Posts
    14
    Quote Originally Posted by mike65535 View Post
    There's a lot code there to swallow. Before you ask others to invest their time to help you might consider:

    1) Indentation and whitespace matter (yours could use some work)
    2) Give your variables decent names (most of yours have horrible names)
    3) Don't use globals unless you MUST. (Your code uses way more than I think it should)
    4) Comments matter (it's hard to tell what the intentions are for most of your code. This problem, believe it or not, is made worse by #1, #2 and #3).
    Ok sorry about that, I'm going to edit it now.

    Thanks a lot!

  6. #6
    Registered User
    Join Date
    Mar 2011
    Posts
    261
    Quote Originally Posted by Kurdo View Post
    I just found out that my code gives result=3 at the direction fuction, i just dont know why.

    Code:
    int direction(int a, int b, int c)
    {
        int diff[5];
        int result;
       
        diff[0] = points[a].x - points[b].x;
        diff[1] = points[b].x - points[c].x;
        diff[2] = points[c].x - points[a].x;
    
        diff[3] = points[a].y - points[b].y;
        diff[4] = points[b].y - points[c].y;
        diff[5] = points[c].y - points[a].y;
    One cannot access the 6th element in an array that has only 5

  7. #7
    Registered User
    Join Date
    Dec 2010
    Posts
    14
    Quote Originally Posted by anduril462 View Post
    How does the robot know where a mine is? I don't see any on your map.
    the robot is programmed in VHDL, if it finds a mine, it wil send a signal to the computer. That signal is "0" in my code. The mines are put in the map randomly.
    Last edited by Kurdo; 05-19-2011 at 12:43 PM.

  8. #8
    Registered User
    Join Date
    Mar 2011
    Posts
    261
    Quote Originally Posted by Kurdo View Post
    The mines are put in the map randomly.
    Yeah but where in your code is a mine looked for? Shouldn't each potential leg along the path be checked with some function you wrote called something like IsMineFound() ?

    edit: ok, I see more now...

  9. #9
    Registered User
    Join Date
    Dec 2010
    Posts
    14
    Quote Originally Posted by mike65535 View Post
    One cannot access the 6th element in an array that has only 5
    Ah yes, your right. But that still didn't solve it

  10. #10
    Registered User
    Join Date
    Dec 2010
    Posts
    14
    oh yeah i forgot to mention, the mines can only be placed at the dots in the map, not in the cross sections. But that isnt really the problem. The problem is that when i put 1 as source and 16 as destination, the directions that are given to me are wrong.
    I'm getting the output: 1 5 4 11 17 16

    straight forward - left - straight forward - destination reached

    it should be: straight forward - left - straight forward - straight forward - left - destination reached

  11. #11
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Also, if d and prev and visited are all [3000], then you can't do for (i = 1; i <= n; ++i) . ARrays are indexed 0 to size-1.

  12. #12
    Registered User
    Join Date
    Dec 2010
    Posts
    14
    Ah i found it!

    Code:
    if(route[i+2]==destination)
                {
                    printf("\nDestination Reached\n");
                    exit(EXIT_SUCCESS);
                }
    route[i+2] should be route[i]. That solved my problem, THANKS A LOT GUYS!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. breath first search shortest path
    By iamnew in forum C Programming
    Replies: 3
    Last Post: 06-10-2010, 11:10 AM
  2. Shortest path
    By anirban in forum Tech Board
    Replies: 3
    Last Post: 06-10-2008, 11:42 PM
  3. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 05:32 PM
  4. shortest path problems
    By talz13 in forum C++ Programming
    Replies: 7
    Last Post: 05-08-2004, 06:13 AM
  5. Help!!! Shortest path graph
    By hansy32 in forum C Programming
    Replies: 5
    Last Post: 03-01-2002, 05:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21