Subject:
|
Re: More Speed? Re: Mindstorms 3.0 Wish List
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Thu, 6 Nov 2003 02:18:40 GMT
|
Viewed:
|
2509 times
|
| |
|
|
John Barnes wrote:
> Are you sure? How many square inches are there in a 1600 square foot house? I
> don't think the resulting map array will fit in 32k memory.
Two words...
"sparse array"
The cpu in the RCX is plenty fast enough to handle the proccessing
overhead incurred in accessing such an array. To work out how much
space in such an array your house would require, add the perimeters
measured in "distance units" of all immobile objects in the house
together, and mulitiply that by 2 to get the absolute maximum number of
cells that might need to be marked as impassable in that array (you
don't really need to mark the cells inside the perimeters of objects as
used, since the rcx would never get to be adjacent to those cells anyways).
An expansion on that solution that would scale better than the sparse
array by itself would be one which, when it has identified all the cells
in the perimeter of what appears to be an object, culls those cells from
the sparse array and uses a polygon to describe where the polygon is in
the floor space. Algorithms exist for sorting two dimensional objects
like this so that searching through such a list is approximately of time
complexity O(log n), where n is the number of polygons to search
through. If there are a lot of small perimeter objects in your house
(chair legs and so forth), you could even decide at runtime as objects
are discovered whether or not you want to use polygon representation
based on the object's size, and leave small perimeter objects in the
sparse array rather than making separate polygons for each one.
And just IMNSHO, merely making the problem easier to solve isn't really
a good reason to throw more hardware at the problem when what one has
will actually do the job with just a little more effort, unless one is
actually being paid for their time.
>> Mark
|
|
Message is in Reply To:
44 Messages in This Thread:
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
Active threads in Robotics
|
|
|
|
|
|
