[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