[SciPy-User] Dijkstra's algorithm on a lattice

Zachary Pincus zachary.pincus@yale....
Sat Nov 21 22:45:26 CST 2009


Thanks Gary!

Attached is a simplified version that addresses all of the caveats I  
had earlier, plus I added documentation and input-checking.

Boundaries are now handled properly (the bounds-checking is not too  
slow, even on huge arrays), and the code now iterates until all paths  
have been fully traced. Still BSD licensed; if it might be useful to  
scikits.image, please feel free to include it.

Here's a simple "maze" solving example / test.

 >>> import numpy
 >>> import trace_path
 >>> a = numpy.ones((8,8), dtype=numpy.float32)
 >>> a[1:-1,1] = 0
 >>> a[1,1:-1] = 0
 >>> a
array([[ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.]], dtype=float32)

 >>> trace_path.trace_path(a, (1, 6), [(7, 2)])
(array([[ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  1.],
        [ 1.,  0.,  1.,  2.,  2.,  2.,  2.,  2.],
        [ 1.,  0.,  1.,  2.,  3.,  3.,  3.,  3.],
        [ 1.,  0.,  1.,  2.,  3.,  4.,  4.,  4.],
        [ 1.,  0.,  1.,  2.,  3.,  4.,  5.,  5.],
        [ 1.,  1.,  1.,  2.,  3.,  4.,  5.,  6.]], dtype=float32),
  [[(1, 6),
    (1, 5),
    (1, 4),
    (1, 3),
    (1, 2),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 2)]])

 >>> trace_path.trace_path(a, (1, 6), [(7, 2)], diagonal_steps=False)
(array([[ 2.,  1.,  1.,  1.,  1.,  1.,  1.,  2.],
        [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  1.],
        [ 1.,  0.,  1.,  1.,  1.,  1.,  1.,  2.],
        [ 1.,  0.,  1.,  2.,  2.,  2.,  2.,  3.],
        [ 1.,  0.,  1.,  2.,  3.,  3.,  3.,  4.],
        [ 1.,  0.,  1.,  2.,  3.,  4.,  4.,  5.],
        [ 1.,  0.,  1.,  2.,  3.,  4.,  5.,  6.],
        [ 2.,  1.,  2.,  3.,  4.,  5.,  6.,  7.]], dtype=float32),
  [[(1, 6),
    (1, 5),
    (1, 4),
    (1, 3),
    (1, 2),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (6, 2),
    (7, 2)]])

Zach


On Nov 21, 2009, at 7:48 PM, Gary Ruben wrote:

> Hi Zach,
>
> I haven't looked at your code, but your description sounds like you've
> got a very nice solution. When you originally asked this, I  
> immediately
> thought of Lee's algorithm, or Jarvis's distance-transform based path
> planning, which uses a modified distance transform that fixes the  
> start
> and goal point costs. I didn't mention them because they don't cover  
> to
> your case, but I think your solution is a more general case or  
> theirs -
> i.e. you can use yours for navigation/maze solving by setting the
> obstacle/wall values to something greater than the maximum distance to
> the goal and the floor values to 0.
>
> I think would be a very nice, general routine for scikits.image,
>
> Gary R.
>
> Zachary Pincus wrote:
>> OK, here's what I have. Not Dijkstra's algorithm, but very simple and
>> not bad for many purposes.
>>
>> You pass in a 2D costs array, start- and end-points, and a maximum
>> number of iterations; the code then keeps track of the minimum
>> cumulative cost to each pixel from the starting point, as well as the
>> path thereto. It does this by keeping track of "active" pixels -- any
>> time a lower cumulative cost to a given pixel is found, that pixel is
>> made active. Each iteration, all the neighbors of the "active" pixels
>> are examined to see if their costs can be lowered too. Basically
>> breadth-first search.
>>
>> Limitations and oddities:
>> - Currently, diagonal and vertical/horizontal steps are both allowed.
>> Easy enough to make this a parameter.
>> - Paths along the boundary aren't traced out because I didn't want to
>> deal with an if-check in the inner loop to make sure that the x,y
>> position plus the current offset wasn't out of bounds. This could be
>> addressed by (a) padding the input array by one pixel on each side,  
>> (b)
>> putting the if in the inner loop, or (c) having a second pass through
>> the edge pixels.
>> - In theory, the code could find the cheapest path from top-left to
>> bottom-right in a single pass because "active" pixels are marked
>> immediately as the code iterates through the array. So the max_iters
>> parameter doesn't guarantee that paths longer than that will not be
>> found. But it does guarantee that any path found less than that  
>> length
>> is optimal...
>>
>> Let's say it's BSD licensed, in case anyone finds it of use.
>>
>> Zach
>>
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User@scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
-------------- next part --------------
A non-text attachment was scrubbed...
Name: trace_path.zip
Type: application/zip
Size: 2025 bytes
Desc: not available
Url : http://mail.scipy.org/pipermail/scipy-user/attachments/20091121/f655e995/attachment.zip 


More information about the SciPy-User mailing list