Posted: 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?
Posted: 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
Posted: 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.
Posted: 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?
Posted: 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?
Posted: 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.
Posted: 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).
Posted: 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?
Posted: 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
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.
Posted: 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?
Posted: 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.
Posted: 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?
Posted: Fri Dec 07, 2012 11:03 am Post subject: RE:Rush Hour Project
Deos grade 12 programming contain Gaming
Posted: 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
Posted: 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).