0
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

0
101 Mar 26, 2005 at 14:34