Rush Hour Project

[Panphobia]

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?

[Raknarg]

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

[Insectoid]

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.

[Panphobia]

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?

[Panphobia]

It seems that recursion would be kind of inefficient. Would it not?

[Insectoid]

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.

[mirhagk]

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

[Panphobia]

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?

[mirhagk]

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.

[Panphobia]

What I mean by using ArrayList is like when you dequeue you just (arraylist).remove(0), which gives the same effect right?

[mirhagk]

oh yeah sorry, so long as you're using a queue interface that works.

[Panphobia]

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?

[AntoxicatedDevil78]

Deos grade 12 programming contain Gaming

[Panphobia]

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

[Insectoid]

@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).