Subject:
|
Re: Rover Programming
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Fri, 28 Jun 2002 07:17:17 GMT
|
Original-From:
|
Steve Baker <(sjbaker1@airmail)AntiSpam(.net)>
|
Reply-To:
|
sjbaker1@airmail.netSAYNOTOSPAM
|
Viewed:
|
861 times
|
| |
|
|
PeterBalch wrote:
> Steve Baker wrote:
>
>
> > But with a little simple on-the-fly data compression, I think you could
> > solve the storage problem.
> > It wouldn't take much to decompress as much of the 'map' as it currently
> > needs
> > and place it into a small cache - recompressing that section and
> > uncompressing
> > another into the space thus free'd up.
>
>
> Run-Length-Encoding (RLE) should work well on a blobby black-and-white map.
Yes - and it's very fast to implement.
Better still, you can use one of several rectangle encoding tricks that are
out there (kind of like two-dimensional run-length encoding). Those are
typically able to compress at the square of the ratio of RLE for things like
images with very few colours.
> Or you could store line N as the difference (or XOR) between line N and
> line (N-1). The difference would be mostly zero. Then RLE it.
Yep - this is one of those problems where you can think of a dozen good
ways to do it - and any of them is sufficiently good to reduce it to a
non-issue.
> Assume one bit per map pixel. Take the detailed "image" of the map. Halve
> its resolution (so its a quarter of the area). Store this small map. Now
> double the stored map (to the original size) and note the difference with
> the original image (e.g. XOR the two images). Store the difference image
> (RLE compressed).
Yes - that's also nice because you can use the coarser resolution maps
to produce an approximate route to some destination - then check that this
route is actually feasible using the finer resolution map. This can save
a lot of time. I once wrote a computer game that used that technique to
have hundreds of computer-controlled creatures doing route planning in a
complicated environment.
----------------------------- Steve Baker -------------------------------
Mail : <sjbaker1@airmail.net> WorkMail: <sjbaker@link.com>
URLs : http://www.sjbaker.org
http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net
http://prettypoly.sf.net http://freeglut.sf.net
http://toobular.sf.net http://lodestone.sf.net
|
|
Message is in Reply To:
 | | Re: Rover Programming
|
| (...) needs (...) uncompressing (...) Run-Length-Encoding (RLE) should work well on a blobby black-and-white map. Or you could store line N as the difference (or XOR) between line N and line (N-1). The difference would be mostly zero. Then RLE it. (...) (23 years ago, 27-Jun-02, to lugnet.robotics)
|
2 Messages in This Thread:
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
