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)
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)
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.
Please log in or register to post a reply.
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
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 .