Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Rush Hour Project
Author Message
Panphobia

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?
Sponsor
Sponsor

Raknarg

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
Insectoid

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.
Panphobia

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?
Panphobia

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?
Insectoid

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.
mirhagk

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

See here for more info:
http://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively
Panphobia

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?
Sponsor
Sponsor

mirhagk

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
 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

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?
mirhagk

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.
Panphobia

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?
AntoxicatedDevil78

Posted: Fri Dec 07, 2012 11:03 am   Post subject: RE:Rush Hour Project

Deos grade 12 programming contain Gaming
Panphobia

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
Insectoid

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).
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: