Re: Storing Tilemaps/Drawing Tilemaps

In article <iPidnT7u3O63j3nfRVnytA@xxxxxxxxx>, GaRRy <spam@xxxxxxxx> wrote:
> Up until quite recently I was storing my tiles in a huge array and
> was happy with it, good speed etc. Then I realised that more than
> half of my tiles were empty - so this was a huge waste of memory.

If you're programming for a PC, this is less of a problem than
you think.

>So I made it a map point based map..
>std::map< QPOINT, unsigned int, QPOINT >

Worst. Solution. Ever. Really, this is a bad idea. std::map is not
designed for a large sparse 2D grid. There's a ton of overhead
involved, and a ton of pointer-chasing, which isn't terribly fast even
on PCs.

How about a better solution: have your large map out on disk. Read
in chunks (say 16x16 tiles) when you need them. Keep say 4x the number
of screen tiles in memory, and when you need another chunk, evict the
oldest chunk from memory and read it off disk. That will give you the
speed of arrays, and a much reduced memory hit. For bonus points, RLE
the chunks to reduce the empty ones to nearly nothing.

Nathan Mates

--
<*> Nathan Mates - personal webpage http://www.visi.com/~nathan/
# Programmer at Pandemic Studios -- http://www.pandemicstudios.com/
# NOT speaking for Pandemic Studios. "Care not what the neighbors
# think. What are the facts, and to how many decimal places?" -R.A. Heinlein
.

Relevant Pages

  • Re: VIMAGE: Freed UMA keg was not empty
    ... Freed UMA keg was not empty. ... Lost 1 pages of memory. ...
    (freebsd-current)
  • Re: [Vuln-Dev Challenge] - VulnDev1.c Summary
    ... meaning the chunk is allocated with mmap. ... turn calls munmap on an invalid memory address. ... > the Doug Lea algorithm as well has heap-based exploitation methods ... > the forward chunk, in our case buf2, is free. ...
    (Vuln-Dev)
  • [RFCv6 04/13] mm: cma: Contiguous Memory Allocator added
    ... allocating physically contiguous chunks of memory. ... per-platform and it is easy to add custom allocator algorithms if one ... The Contiguous Memory Allocator (CMA) is a framework, ... whenever it requests memory chunk. ...
    (Linux-Kernel)
  • The Malloc Maleficarum
    ... Glibc Malloc Exploitation Techniques ... the exploitation of overflowed dynamic memory chunks on Linux. ... I have the House of Prime. ... a malloc chunk. ...
    (Bugtraq)
  • [Full-disclosure] The Malloc Maleficarum
    ... Glibc Malloc Exploitation Techniques ... the exploitation of overflowed dynamic memory chunks on Linux. ... I have the House of Prime. ... a malloc chunk. ...
    (Full-Disclosure)