2 replies to this topic

[sylsau]

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+

[Ed Mack]

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

[sylsau]

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 .