Computer Science Canada

Rush Hour Project
Author:  Panphobia [ Wed Dec 05, 2012 10:52 am ]
Post subject:  Rush Hour Project
For my final project in grade 12 programming, we have to have a group project, and my group wanted to do the Rush Hour game, which is basically, where you are a car, and you have to move other cars so you can get to your destination. We have to create the shortest number of moves for the differentiation between easy,medium,and hard. Which algorithm should I use, would a BFS be ok?
Author:  Raknarg [ Wed Dec 05, 2012 5:31 pm ]
Post subject:  RE:Rush Hour Project
In this situation, I would venture to say no... It seems like something that would take way too much recursion. Any disagreements? I'm just judging on first glance here
Author:  Insectoid [ Wed Dec 05, 2012 6:57 pm ]
Post subject:  RE:Rush Hour Project
I don't think there's so many moves on a Rush Hour board that you couldn't use recursion. It's only a 6x6 grid. There are only 16 vehicles. Vehicle data shouldn't be more than a few bytes each in a basic implementation (type, location, orientation) so it's not like you're going to run out of RAM.
Author:  Panphobia [ Wed Dec 05, 2012 7:24 pm ]
Post subject:  RE:Rush Hour Project
Basically for this project we are supposed to use everything we learned in grade 12, so recursion, object orientation, arraylists etc, so with recursion, should I check for the shortest path between the car and the end, and if there is a car in the way, to move the car, and recurse my way until i get the minimum amount of moves?
Author:  Panphobia [ Thu Dec 06, 2012 12:39 am ]
Post subject:  RE:Rush Hour Project
It seems that recursion would be kind of inefficient. Would it not?
Author:  Insectoid [ Thu Dec 06, 2012 8:50 am ]
Post subject:  RE:Rush Hour Project
It's probably less efficient than a more intelligent algorithm, but a more intelligent algorithm would be harder to write and would require you to study the game itself for a bit. The number of moves really is very small. Trucks have six valid moves each (three backward/three forward) and cars have eight. There are only 120 valid moves total, but that's without any obstructions. Of course, you can't fit all vehicles on the table simultaneously because they would take up all 36 squares, for 0 moves each. Considering that a vehicle is likely blocked by another and may have all, some, or no valid moves, the tree becomes much smaller. The program shouldn't take more than a few seconds to run at worst, and should be apparently instant at best.
Author:  mirhagk [ Thu Dec 06, 2012 3:32 pm ]
Post subject:  RE:Rush Hour Project
BFS traditionally uses a queue, not a stack, and therefore is usually only implemented recursively if the language is extremely high level and nearly forces recursion (like haskell).

You could make the while loop recursive, but it'd just increase memory consumption and time (unless the language has tail recursion and you optimize for that).

Essentially the point is BFS should not be done recursively (but requires the same sort of knowledge, and therefore should be easy to convince the teacher that the knowledge is transferable).

See here for more info:
http://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively
Author:  Panphobia [ Thu Dec 06, 2012 3:59 pm ]
Post subject:  RE:Rush Hour Project
So I can use an arraylist for the BFS, and I can say that it can be done recursively but is less efficient? But the arraylist will work as a queue so that will knock two of the criteria down?
Author:  mirhagk [ Thu Dec 06, 2012 6:07 pm ]
Post subject:  RE:Rush Hour Project
the arraylist solution actually only works with a binary tree (which you won't have).

Just do a regular BFS, and then convert the while loop to a recursive loop
code:

BFS()
{
while(true)
{
  doWork
  if(done)
    return
}
}

Becomes
code:

BFS(localVars)
{
  doWork
  if (done)
    return
  BFS(localVars)
}

You need to pass in all the local variables as parameters (pass the queue as a reference so you don't need to copy it). Any loop can trivially be turned into a recursive function like that. Then spend the rest of your time making sure you fully comprehend BFS and the queue it uses.
Author:  Panphobia [ Thu Dec 06, 2012 6:26 pm ]
Post subject:  RE:Rush Hour Project
What I mean by using ArrayList is like when you dequeue you just (arraylist).remove(0), which gives the same effect right?
Author:  mirhagk [ Thu Dec 06, 2012 11:49 pm ]
Post subject:  RE:Rush Hour Project
oh yeah sorry, so long as you're using a queue interface that works.
Author:  Panphobia [ Thu Dec 06, 2012 11:57 pm ]
Post subject:  RE:Rush Hour Project
yea, now if a bfs is a good way to go, would i use the bfs to move the cars or to check if you can make it to the exit without obstruction, or both?
Author:  AntoxicatedDevil78 [ Fri Dec 07, 2012 11:03 am ]
Post subject:  RE:Rush Hour Project
Deos grade 12 programming contain Gaming
Author:  Panphobia [ Fri Dec 07, 2012 11:24 am ]
Post subject:  RE:Rush Hour Project
Well for the final project, you can make a game, but it has to do with project management, so a group with 3 people, and make a program that uses everything in the curriculum
Author:  Insectoid [ Fri Dec 07, 2012 3:48 pm ]
Post subject:  RE:Rush Hour Project
@AntoxicatedDevil78- don't spam threads with unrelated comments. If you'd like to know what 12th grade compsci involves, ask in the appropriate forum (Student Life).
Author:  Panphobia [ Sat Dec 15, 2012 6:12 pm ]
Post subject:  Re: Rush Hour Project
Currently, I have a grid/graph that i could read from in a text file,
code:
* * * * * * * *
* 2 2 . . . 7 *
* 1 . . 5 . 7 *
* 1 0 0 5 . 7 A
* 1 . . 5 . . *
* 3 . . . 4 4 *
* 3 . 6 6 6 . *
* * * * * * * *
If the number modulo 2 not 1 than it moves vertically, else moves horizontally, and 0 is start car, now what I am thinking to do is to go through all the possible ways to solve the game, and then keep getting the minimum amount of moves, this algorithm should not be too hard BUT, it might run infinitely, any suggestions?
Author:  Insectoid [ Sat Dec 15, 2012 6:47 pm ]
Post subject:  RE:Rush Hour Project
There's a finite number of moves and states. If it reaches a state you've been to before, don't go any further down that branch. Alternatively, you can set a limit on depth. If you're a hundred moves deep, don't go further down that branch.
Author:  Panphobia [ Sat Dec 15, 2012 6:51 pm ]
Post subject:  RE:Rush Hour Project
So how would I map something that has already happened, is there a function for that?
Author:  Insectoid [ Sat Dec 15, 2012 7:20 pm ]
Post subject:  RE:Rush Hour Project
There is no such function. However, you can save the map states as you progress. It's probably easier to just add a depth limitation though. Saving each map can take up a lot of RAM, and Rush Hour hasn't doesn't take up that many moves to win. a 100-move limit is very reasonable.
Author:  Panphobia [ Sat Dec 15, 2012 7:45 pm ]
Post subject:  RE:Rush Hour Project
ahhh yeaa considering the most advanced rush hour game only has 93 moves, i should make a limit to 93, thanks Very Happy
Author:  Panphobia [ Sat Dec 15, 2012 9:01 pm ]
Post subject:  RE:Rush Hour Project
by the way, how can you keep a certain car from not moving backwards and forwards until the limit and then restarting over and over again infinitely, is there a way to stop this? also is there a good way to save an incorrect solution in a type of variable to not repeat it again
Author:  Panphobia [ Sun Dec 16, 2012 4:54 pm ]
Post subject:  RE:Rush Hour Project
is there any function that saves previous moves that are proved to not help a solution, so the program does not loop over these moves infinitely?
Author:  Insectoid [ Sun Dec 16, 2012 5:18 pm ]
Post subject:  RE:Rush Hour Project
No. You'll have to write that function yourself.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy