No replies to this topic

[ThemePark]

I need an algorithm to find the shortest distance to move squares on a 2D grid to their destination. The A* algorithm works fine with just one square and one destination, but as in the attached example, I need to modify the algorithm to work for several destinations.

In the sketch, the two red squares need to be moved into place so that you get a 3x3 grid of squares. The top one can be moved into the empty space both to the left and to the right, and will have the same cost to both places.

The left one, however, can only be moved to the top left space as that gives a smaller cost than moving it to the top right space. And moving that would then cause the top one to only be able to move to one place.

So I need to modify A* in such a way, that it can take into account the possible destinations for each square, and find the right path, even though it may not always be the initially shortest one. But I have no idea on how to do that.

Attached Files

•  Sketch.png   339bytes   49 downloads

Edited by ThemePark, 16 February 2011 - 03:36 PM.