How to implement the simplest random strategy for finding a path from Start to Goal position to move one container in a wharf (grid)?

I need to implement a code to move a strad with a container in a wharf (grid) from a start position to finish position, both set by the user.

The wharf is a grid of N x N locations. The container to be moved is in location Start. The strad is also at location Start and needs to go to location Goal to store the container. It can move horizontally or vertically one step at a time (it cannot move diagonally). Some locations are forbidden as they already contain stored containers. The free locations are represented with 0 and the forbidden with 1. The user will enter the Start and Goal locations.

I need to implement the simplest random strategy for finding a path from Start to Goal to move the container: The strad moves from one tile to another neighbouring tile randomly. It can revisit the same location, but cannot move to a forbidden location. The maximum number of steps the strad is allowed will be set for the user (e.g. 1000 steps).

Please, do you have some idea about how I can do this? In the way that I am doing the strad in crossing the forbidden positions.

[Geoff Hayes]

How are you choosing your next step? If your grid is NxN matrix

grid = zeros(N,N);

with some of the elements of grid set to one if there is a container. Each element or location in the grid has somewhere between 3 and 8 neighbours (the four corner elements have 3 neighbours only).

You could create a list of these neighbours either by assigning a unique identifier to each or just creating an mx2 matrix of indices (where m is the number of neighbours). Remove from this list all neighbours who have a container in them. That leaves at most m neighbouring locations to select. The just use rand to randomly select one of them:

r = 1 + floor(n.*rand);

where n is the number of possible locations ( n<=m).

[Cedric]

Well, it looks like this question.

Anyway, I'd use Dijkstra [ Wiki, FEX ], or a more modern variant like A* [ Wiki ].

Answer 1

[Image Analyst]

I love A* like Cedric mentioned. But look over Steve's blog on the subject of shortest paths. http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/ The Image Processing Toolbox has a function in it that can do that, bwdistgeodesic(). Though I'm not sure if it can do heuristics like A*, it might and that is what part 5 talks about. I guess it depends on what the heuristic is. But if you just want shortest path based solely on distance and not on things like adding costs for certain paths (like those with potholes or whatever) then bwdistgeodesic() would work fine. Just apply Steve's code to your layout.