Heuristic for a labyrinth problem

6ca918857342bc3d90b6452cfc69f4e1
0
sylsau 101 Mar 26, 2005 at 12:54

Hello,

I’m a french student, so excuse me for my english :)
I use the A* algorithm to solve a labyrinth problem. In this labyrinth, there are a personnage and blocs (that personnage can move according to certains criterions). The personnage start on the left top corner and must go on the right down corner. The dimensions of the labyrinth and the number of blocs are parameters of the program.

For the A* algorithm, I search heuristics to improve the number of nodes of the search tree. For the moment, I thought a two heuristics :

1/ the classical Manhattan distance.
2/ the classical Manhattan distance + a valuation of the blocs which are close to the personnage.
For example, if the personnage is in the case (x,y).

I do this :

if( (x+2<largeur) && (y+2<hauteur) && tab[x+1][y]==bloc && tab[x+2][y]==bloc && tab[x][y+1]==bloc && tab[x][y+2]==bloc)
{
heuristic+=2;

if( (y-1>=0) && (x-1)>=0 && tab[x+1][y-1]==bloc && tab[x+2][y-1]==bloc && tab[x-1][y+1]==bloc && tab[x-1][y+2]==bloc)
heuristic+=2;

}

where tab is the matrice who represents the grid.

The second heuristic is a little bit better than the first but the difference is not very important. So, I would like find others heuristics with the constraint that this heuristic be undervaluing.

Someone would have an idea to improve my heuristic ?

Thanks to you to help me.

A+

2 Replies

Please log in or register to post a reply.

065f0635a4c94d685583c20132a4559d
0
Ed_Mack 101 Mar 26, 2005 at 14:34

Your french-english is lovely :)

For labyrinth problems, it can be very difficult to find any other good heuristics, since a well made labyrinth can take you on the most absurd routes to get to the goal - and A* may very well end up investigating most of the map as it has no other choice.

You could try things like also tracing back paths from the goal, and aiming at those, but in a Labyrinth you could end up with the heuristic costing as much as the algoritm :P

6ca918857342bc3d90b6452cfc69f4e1
0
sylsau 101 Mar 27, 2005 at 12:08

I’m going to try this solution. According to the configuration of the grid, it can be better.

But I think, I can find a solution to improve my heuristic with a better consideration of the blocks but I don’t arrive for the moment to find this better consideration .