Penalty Mazes

This is a discussion on Penalty Mazes within the C Programming forums, part of the General Programming Boards category; Hey guys, First of all I'm seriously stuck on this assignment and literally have got no idea where to start ...

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

    Penalty Mazes

    Hey guys,

    First of all I'm seriously stuck on this assignment and literally have got no idea where to start so some much needed advice would be grateful helpful. Basically I'm stuck because I'm not entirely sure where to start. I have an algorithm to base my assignment off but I cant figure out how to replicate this in C, this algorithm is as follows:

    Code:
    while (not at destination &&
           non-taboo adjacent cell exists)
      Add current cell to visited list
      Add current cell's penalty to total penalty
      Mark current cell as taboo
      Check if destination found
      Find cheapest non-taboo adjacent cell
      Check if stuck
      Move to cheapest cell
    we have a 12 x 12 maze to with sides of the mazes declared as taboo. help!

  2. #2
    Registered User
    Join Date
    Dec 2010
    Posts
    6
    I think if you gave us your assignment statement too you would have had more chances to get an answer.

  3. #3
    Registered User
    Join Date
    Dec 2010
    Posts
    3
    Don't really know what you mean but here's what the program is supposed to do, all I'm after really is a point to get me started. Basically an explanation of what the program is supposed to do as I don't have a clue.

    Code:
    data1 contains the following :
    
    1 1
    1 5
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    -1  0  1  2  3  4  5  6  7  8  9 -1
    -1 10 11 12 13 14 15 16 17 18 19 -1
    -1 20 21 22 23 24 25 26 27 28 29 -1
    -1 30 31 32 33 34 35 36 37 38 39 -1
    -1 40 41 42 43 44 45 46 47 48 49 -1
    -1 50 51 52 53 54 55 56 57 58 59 -1
    -1 60 61 62 63 64 65 66 67 68 69 -1
    -1 70 71 72 73 74 75 76 77 78 79 -1
    -1 80 81 82 83 84 85 86 87 88 89 -1
    -1 90 91 92 93 94 95 96 97 98 99 -1
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    
    $ gcc program2.c
    $ a.out data1 result1
    $ cat result1
    The destination was reached.
    Penalty accrued : 10
    1 1
    1 2
    1 3
    1 4
    $
    hope that helps

  4. #4
    Registered User
    Join Date
    Dec 2010
    Posts
    6
    What you are being asked to implement is a greedy algorithm which has a starting and an ending point. You could mantain at each step two current indexes(line number, column number) and the given matrix(if you don't care about memory usage) whose cells are updated to -1 when they become taboo. At each step you move through the matrix in a greedy fashion(to the neighbour with the lowest cost but different from -1) until you reach the destination. Sum up the cells you've travelled through and that is the "Penalty accrued".

    From (1,1) to (1,5) you travel through (1,1) - penalty 0,(1, 2) - penalty 1,(1, 3)- penalty 2,(1, 4)- penalty 3,(1, 5) - - penalty 4. 1 + 2 + 3 + 4 = 10
    Last edited by goodsamaritan; 12-08-2010 at 04:05 PM.

  5. #5
    Registered User
    Join Date
    Dec 2010
    Posts
    3
    Thanks, any ideas where i should? I still haven't got a clue how to implement this

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Think about what data types you need to represent your maze. What about your start and end coordinates and current position? What about your total penalty?

    The basic idea is to break your program down into small chunks and test as you go.

    Start with something basic, like being able to read in the data file correctly. You can take data1 and result1 as parameters and practice by just reading the data file into an appropriate structure/array/etc and then write it right back into result1 for starters.

    Once you can do that successfully, then you can work on your maze solving algorithm. Most of the statements in the pseudo code you provided sound like they'd make great functions (e.g. at_destination, find_cheapest_non_taboo_adjacent_cell). Maybe shorten the names a bit though. Write them one at a time, testing each as you go.

    Code the body of the while loop and make sure your program works for one iteration. Then, add the loop around your maze solving algorithm, writing the steps your algorithm takes to the output file as you go.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Post your games here...
    By Hammer in forum Game Programming
    Replies: 132
    Last Post: 02-28-2013, 08:29 AM
  2. using deques to solve mazes.
    By doampofo in forum C++ Programming
    Replies: 4
    Last Post: 04-19-2003, 10:44 PM
  3. need help with 10% penalty for program
    By vaio256 in forum C++ Programming
    Replies: 2
    Last Post: 04-01-2003, 04:49 AM
  4. Switch Statements
    By blackgingr in forum C Programming
    Replies: 3
    Last Post: 10-07-2002, 02:36 PM

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