🔒 Locked

Heuristic for a labyrinth problem

Started by sylsau Mar 26, 2005 at 8:00 AM 2 replies 2.5k views

Original Post

Mar 26, 2005 at 8:00 AM

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=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+

xEricx

Mar 26, 2005 at 8:53 AM

Hi,

First, for non French readers, a "personnage" is a character, "largeur" is width and "hauteur" is height.

I don't get how your blocks should affect pathfinding. I mean, characters can push them if the node on the other side of the block is empty? What are these criterions you're talking about?

What's your goal here? Faster search with some "sub optimal" paths? or "perfect" paths?

Eric

sylsau

Mar 26, 2005 at 9:45 AM

First, thanks to answer me.

I specify that the character can only move on 4 directions (up,down,left,right).

Example of a grid to solve :

C**B*
*BB**
****G

Here, C means character, B means Block and G means Goal.

In the game, there are two possibilities (the user of the program choose one of both possibilities when he runs the program) for the blocks' movements :

1/ the character can push block if the other side of block is empty.

2/ the character can push block if the other side of block is empty and in more when he pushs a block, there is a sort of Cinetic Energy that block transmit to other block in this direction of movement.

Example (C means Character and B means Block and Star means empty) :

CB**B**B*

Here, the character can push the first block at his right. The result of the movement for the possibility 1 :

*CB*B**B*

The result for the possibility 2 :

*C*B**B*B

In the other part, there are two levels in the game (that user can choose). These levels concern the character's movement.

Level 1 : the character can only move on one case in the direction choosen.

Level 2 : in more of the level 1, the character can move on several cases while he haven't got others possibilities of movement.

Example :

*BBBBB**
C*******
*BBBBB**

If C choose the right direction, in the level 1, we will have this configuration of the grid :

*BBBBB**
*C******
*BBBBB**

Where as in the level 2, we will have this configuration :

*BBBBB**
******C*
*BBBBB**

So, the presence of blocks must take part in the heuristic.
For the moment, I search an heuristic for the problem in general but certainely, certains heuristics will be better according to level and blocks' movements.

Here, My goal is to have a perfect path. But, I would like understand how it can find a sub optimal path and to be sure that it isn't so far of the perfect path.

sylsau

Mar 27, 2005 at 6:56 AM

up :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.