Body: <p>In a 3D world, there is a Robot, boxes, and switches. The robot's job is to carry boxes (one box at a time) and put them on top of switches to solve the level. All switches must have a box on top for the level to be solved. The robot can walk through switches but cannot walk through boxes.</p>
  <p>The configuration of the robot, boxes, and switches in a level is random. However, the number of switches would always equal the number of boxes.</p>
  <p>I want to find out the order in which the robot should visit boxes and switches in a way that minimizes the total number of actions. The following is an example of a level. Obviously, this example is 2D, but the answer should be generalizable to a 3D world.</p>
  <p><a href="https://i.sstatic.net/Aj81B.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Aj81B.png" alt="enter image description here" /></a></p>
  <p>S - switch,
  B - box,
  R - Robot starting position</p>
  <p>In this particular level, if the robot goes for the box at the left cos it is the closest of the two boxes, it will have to place it on the switch at the left. Then it will have to go all the way around to pick the other box and place it on the other switch.</p>
  <p>But if the robot decides to go for the box at the right first, even though it is the farthest of the two boxes from robot's starting position, it will be able to complete the level in a much less number of total actions.</p>
  <p>So I want to figure out an algorithm that would give me the order in which the robot should visit boxes and switches so that the total number of actions will be minimal.</p>
  <p>An informed search like A* might work, but I'm having a hard time coming up with a good heuristic.</p>
  <p>I would really appreciate any help on this.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-03T21:24:02.577Z
Comments.Text: Heuristics typically don't resolve things like order of actions, but assist a search method that does. There are rules that such heuristics need to follow, but it is not clear whether that is what you want.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-04T01:57:58.047Z
Comments.Text: @NeilSlater Yes, that would help. I tried doing a state space search with A*, but I need a good heuristic that accounts for cases like in the above example. I'm having troubles coming up with one.
Comments.UserDisplayName: Arcane
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-04T10:55:34.167Z
Comments.Text: Can you please put your question in the title? "An algorithm to find shortest path in a puzzle" is not a question but an annoucement.
Comments.UserDisplayName: nbro
Tags: <algorithm><heuristics><a-star><shortest-path-problem>
Title: What is a good algorithm (and a heuristic) to find the shortest path in a puzzle game?
UserDisplayName: Arcane
ThreadText: # What is a good algorithm (and a heuristic) to find the shortest path in a puzzle game?
  
  (Asked by: username_0 on 2023-02-03)
  
  In a 3D world, there is a Robot, boxes, and switches. The robot's job is to carry boxes (one box at a time) and put them on top of switches to solve the level. All switches must have a box on top for the level to be solved. The robot can walk through switches but cannot walk through boxes.
  
  The configuration of the robot, boxes, and switches in a level is random. However, the number of switches would always equal the number of boxes.
  
  I want to find out the order in which the robot should visit boxes and switches in a way that minimizes the total number of actions. The following is an example of a level. Obviously, this example is 2D, but the answer should be generalizable to a 3D world.
  
  [![enter image description here](https://i.sstatic.net/Aj81B.png)](https://i.sstatic.net/Aj81B.png)
  
  S - switch,
  B - box,
  R - Robot starting position
  
  In this particular level, if the robot goes for the box at the left cos it is the closest of the two boxes, it will have to place it on the switch at the left. Then it will have to go all the way around to pick the other box and place it on the other switch.
  
  But if the robot decides to go for the box at the right first, even though it is the farthest of the two boxes from robot's starting position, it will be able to complete the level in a much less number of total actions.
  
  So I want to figure out an algorithm that would give me the order in which the robot should visit boxes and switches so that the total number of actions will be minimal.
  
  An informed search like A\* might work, but I'm having a hard time coming up with a good heuristic.
  
  I would really appreciate any help on this.
  
  **Tags:** algorithm, heuristics, a-star, shortest-path-problem
  > **Comments:**
  > **username_1**: Heuristics typically don't resolve things like order of actions, but assist a search method that does. There are rules that such heuristics need to follow, but it is not clear whether that is what you want.  
  > **username_0**: @NeilSlater Yes, that would help. I tried doing a state space search with A*, but I need a good heuristic that accounts for cases like in the above example. I'm having troubles coming up with one.  
  > **username_2**: Can you please put your question in the title? "An algorithm to find shortest path in a puzzle" is not a question but an annoucement.  
  
  ---
  
  ## 0 answers
  
  