Dan Weston wrote:
I hope the code is better than my description! :) The structure is more like
Nothing(RK 0 _) Nothing(RK 1 _) A(RK 2 4) B(RK 3 6) C(RK 2 0)
The root of the tree is the center and you can descend on the right. But with this structure, walking from A to B is O(d) = O(n) (where d is the distance from the origin, n the side length of the grid) instead of O(1).
No. The tree is [[Node]], where the outer list has one element for each radius that has an occupied node and each inner list has the number of nodes at the given radius.
You descend the spine of the outer list radially in O(deltaR) time, which for incremental moves is O(1).
Then you search for an existing inner list element in O(nk(r)), which stays fairly constant for reasonable paths (basically, the width of a path swath).
Ah, so you're using a sparse representation for grids. That's a good idea! Unfortunately, it doesn't help when the grid is a full rectangle, i.e. when nk(r) becomes proportional to r. The (most likely unattainable) goal I had in mind is to create a zipper for the full grid that supports O(1) operations.
I mean, O(d) may be fine for you, but it's not O(1) for everything as advertised. :)
d is not the distance from the origin, it is nk(r), the number of nodes at a given radius: d(2) = 2, d(3) = 1.
Oh, right.
An outward radial path will only expand the tree linearly, not quadratically, in size.
Well, that's still linear in the side length of a full grid. Directly using Data.Map (Integer,Integer) a would improve that to a logarithm. Of course, your structure can be enhanced by using a Data.Map instead of a linked list for each ring à la [Data.Map Integer a] This will give O(log nk(r)) movements, but that's still not constant time. Regards, H. Apfelmus