CODEWITHSUNDEEP
javavb.netalgorithmgraph-algorithm
Green Fire
Green Fire

Reputation: 709

Finding the smallest number of steps between two points?

I have a grid, The Grid have two "Material" -

For example :

This is An Example Of a Grid In this grid we have objects that have size and location (The location of an object is the top left point).

On each object we can do some action like -

I need to make a function that returns me the Minimum amount of actions I need to do on a object to move it from one point to another point (I need only the amount of action).

I solved this problem using dijkstra's algorithm, but without the turn action.

So can anyone help me to build this function.

Example of the problem -

enter image description here

And I need to return the minimum amount of actions I need to do on a object.

Upvotes: 5

Views: 1239

Answers (4)

pwwpche
pwwpche

Reputation: 621

For your problem, I think BFS still works.

Using BFS to solve traditional Maze problem, starting from the beginning point, you have to:

1. Enqueue every point that is accessible (not a piece of wall, and not visited) and connected to the current point.
2. Dequeue current point and mark it as VISITED.

From above, you can see that BFS won't let any point to be visited twice, thus loop is avoided.

Your Problem

As for your problem, BFS still works, but we will slightly change the definition of "accessible":

First, I will introduce what the "maze" matrix looks like. Here is what the numbers mean in the following images.

(Assume that the size of the object is 1*2, and when moving, the top-left corner of the object stays at each point).

00: The point can't be accessed, neither the object is horizontal nor vertical. 
10: The point can be accessed if the object is horizontal
01: The point can be accessed if the object is vertical
11: The point can be accessed if the object is either horizontal or vertical

And your graph can be converted into a matrix like below:

img1

Fill in those inaccessible points with 00, and you'll get

enter image description here

This is more like a Maze problem, but a little bit different.

Finally, let's see how to "access" those points:

The definitions of connected is similar to the traditional Maze problem. Here are some examples:

---------
| 01| 10|
|---|---|
| 10|   |
---------    (Not Connected from top-left to either top-right or bottom-left)


---------
| 11| 10|
|---|---|
| 01|   |
---------    (Connected from top-left to both top-right and bottom-left)


---------
| 10| 10|
|---|---|
| 01|   |
---------    (Connected from top-left to top-right, but not connected to bottom-left)

So the rest may be simple. Follow the traditional BFS method, and create a 2-dimension array to store the length of the shortest path at each point. Dequeue to get the current point, add connected neighbors of current point to the queue, and mark this point as VISITED, then everything will be the same as BFS.

After you've got the shortest path, re-run your program, maintain a state of whether the object is vertical or horizontal at current point, and simulate your move on the image. Add turns only when necessary, and you will get the result with turns added.

enter image description here

Upvotes: 2

Juan Lopes
Juan Lopes

Reputation: 10565

Consider the problem as finding the shortest path in a 3D grid, with a depth of 2 (each of the possible states: horizontal and vertical). You have to code the constraints that disallows one from moving from one depth to another, e.g., cannot go vertical if it doesn't fit that way.

Now you can just use regular BFS to find the shortest path in a grid (i.e., an unweighted graph).

Upvotes: 5

Keith
Keith

Reputation: 1321

If I understand what you're asking, writing this out would take too long, but the easiest way of doing it I can think of is finding the path first, check for collision along that path, rotate, and add the actions accordingly.

  • Use basic pathing algorithm to find the path to the end.
  • Store path nodes in some sort of traversable array (should be 4 total if the pathing algorithm is good/simple).
  • Attempt to follow path notes (i to array count)
  • Check for collision on each movement.
  • (do while) If movable object intersects with the wall, rotate 90 degrees and try again.
  • (next) If success, save to move action list (move x/y, rotate z)
  • Return action count

With a more complicated grid, this would obviously get more complicated, but you only have to do 90 degree turns. It should be possible in ~9 actions.

Upvotes: 0

joseca
joseca

Reputation: 306

Use the Breadth-first search strategy, assigning weights to edges depending on must turn the object or not.

Upvotes: -2

Related Questions