Finally, testing complete
I'm pretty satisfied with the results. I'm ready to move forward now that my sparse tile storage class is complete. I even took a few days to have some fun programming OpenGL on SDL. Attached is a picture of the pixel dump into a texture then displayed via a call to glTexSubImage2d.
As you can see there is no visual loss of data from the original picture. This is a visual representation of the data stored in HashNodes class. A pixel represents either a root node, branch node or uncompressed tile.
Both of the below test applications used an abstract function (GetMapTile) to call an underlying data structure. I made sure both were using stack assigned variables.
Maybe I should make a lib out of it and post it on github or something. gprof results std::map name: GetMapTile(unsigned int, unsigned int) [rank]time% self children called [2] 79.2 0.12 10.08 20,160,000 Core search lookup implementation name: std::map<unsigned int,tilemap::Tile>(...)::find() [rank]time% self children called [4] 77.2 0.03 9.92 20,160,000 VS. Will's hash algorithm (WHA). name: GetMapTile(unsigned int, unsigned int) [rank]time% self children called [4] 42.0 0.33 6.14 20,160,000 Core search lookup implementation name: BinarySearch(std::vector<unsigned int, std::allocator<unsigned int> > const&, int, int, unsigned int) [rank]time% self children called(+ recursive) [9] 18.2 2.52 0.58 11390744 (+75491000) Total Speed: std::map (10.20 seconds) / WHA ( 6.47 seconds ) = WHA 40% faster. Memory storage: *** Compression Test Results *** Control struture: (std::map) Size dimension: x=8400 y=2400 Total tile count:20160000 Size (MB):230 Map overhead (MB):400 (had to observe in process explorer) Total memory (MB): 630
Branches structure: (WHA) Size dimension (both x&y):20 Branches count:40470 Total tile count:6676135 Branches overhead (KB):2529 Size (MB):76 Total Size (MB):79 Total Compression/Memory efficiency = WHA has 87% smaller memory use
.