There is a flash game that you can very easily find on Google called Blockage.

Rules & Goal of the game : Get all coloured blocks from their initial position to a corresponding target spot of the same color. Once a block is placed on a target spot of the same color, it cannot move anymore. You can select a specific block and move it left or right. Blocks are also subject to gravity (moving them vertically until they hit a wall or another block). There can be many blocks of the same color and more blocks than target spots. Obstacles include walls and other blocks (two blocks cannot be at the same position).

enter image description here

I would like to implement an $A^*$ algorithm that finds the sequence of steps to win this game.

I am currently thinking about a good heuristic $h(n)$ to use. The best one I could find is the following : the sum of the Manhattan distances between each colored block and its closest target.

Any idea on a better heuristic?

  • $\begingroup$ Ok! I've added the rules :) $\endgroup$ – Dory Oct 29 '17 at 19:57
  • $\begingroup$ In AIMA, there is a "heuristic" for creating heuristics; Take the rules and relax them. This often gives natural heuristics that never overestimate the cost. Have you tried this approach? $\endgroup$ – Pål GD Oct 29 '17 at 21:52
  • $\begingroup$ Yes. The heuristic I proposed in my post is in fact implicitly relaxing the gravity constraint. However, I just realized that it makes the heuristic non-admissible because gravity tends to decrease the cost from start to goal when Manhattan distance would overestimate it. For the moment the only heuristic I can think of is something like "the horizontal distance between target and block". But I feel like it's a poor heuristic. $\endgroup$ – Dory Oct 30 '17 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.