A* search for Rush Hour game

[daveyb91]

Dear people..
For an assignment for school I have to make a solver for a Rush Hour game.. if you aren't familiar with Rush Hour.. check this link: http://www.puzzles.com/products/rushhour.htm

For this solver I have to use the A* search algorithm, I looked on the internet a bit, and I think I quite understood how the algorithm works.. only I don't really have an idea how to implement it in the solver.. nor how I should build up the grid for the cars.. Can someone please give me some tips/help for this? Not a complete solution..

Thanks a lot in advance, Davey

[skatamatic]

I am not too sure how you would use the A* algorithm to solve that. I mean, it could certainly be used to determine the shortest path from start to finish, but it could not be used to move the cars around in such a way that the path would be complete.

Maybe this is what your teacher meant:

Try the A* algorithm to find a path, if it cant find a path, move a car. Try every possible combination of car moving (brute force) until A* returns a successful path. If you want the shortest possible path, continue searching for paths, if you are just looking for any solution then the first path found will do.

For making the grid for the cars, a 2d array representing the 'playing field' and several objects describing cars could be used.

Eg in a 4x4 world

bool [,] bWorld = new bool [4,4];

This is what that would look like
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

And for the car objects:

struct sCar
{
Point TopLeftCornerCoordinate {get; set;}
Size  CarSize {get; set;}
bool  Direction {get; set;} //true means moves up+down, false means left+right
}

Now, with a collection of these car objects, the 'world' grid could be masked using all of the car coordinates with their sizes, then in the brute force algorithm for moving all the cars, the Direction property could be used to slide the cars around.

Here's a head start with the masking:

private void AddCarMaskToArray (bool[,] bMask, sCar car)
{
for (int i = 0; i < sCar.CarSize.Width; i++)
     for (int ii = 0; ii < sCar.CarSize.Length; ii++)
          bMask[car.TopLeftCornerCoordinate.X + i, car.TopLeftCornerCoordinate.Y + ii] = true;
}

[daveyb91]

Thanks a lot, and that's exactly what my teacher meant.. where I was a bit confused at is, how do I move the cars, is there a smart way to do it.. or just brute force? I'm gonna use some of the things you told me.
Once again, thank you :)