Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

mitchw

Texture Manager and Hashing

This topic is 6470 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I have a general question on how do you usually code a texture manager? Right now mine keeps a list of textures loaded (duh in a link list. Obviously this will be extremely slow as the number of textures in use grows. I''m not *real* familiar with hash tables, but I have to believe they would work great here, hashing the filename of the texture. Thing is, how do you fit that hash value into an array? I was thinking of hashing like the following, to try to avoid name/hash collisions: DWORD dwLen = strlen(_Filename); DWORD dwHash = 0; for ( int i = 0; i < dwLen; i++ ) { dwHash += _Filename << i; } return dwHash; I''ve tested this with _filenames over 100 characters, which should suffice, as I will use relative paths. Any ideas/suggestions? Thx

Share this post


Link to post
Share on other sites
Advertisement
You could take the lower n number of bits in your hash value to determine which hash chain the texture goes in. As you noticed yourself, the DWORD hash value is just too large to use directly as a hash chain number. However, you can use it for quick tests of the individual strings.

If I remember correctly, this is how VMS used a hash table to locate logicals. (basically VMS''s version of environment variables.)

Step 1: Take a string and compute a CRC

Step 2: Take n bits from the CRC and use as index into hash chain table.

Step 3: For each string in the chain. Return no match if at end of chain.

Step 4: Compare the CRC value against CRC for test string. If no match, move to next string.

Step 5: Compare the string against the test string. If no match, move to next string.

Step 6: MATCH!!!

Tim

Share this post


Link to post
Share on other sites
That looks like a decent hash function. What you want to do is take the modulo with the size of the hash table (which should be a prime number). It should look like this:


int index_into_table=hash_function("texture_name") % table_size;
hash_table[index_into_table].insert("texture_name",pointer_to_texture);


Mike

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
what do i dont get here ???

Is it not quite a overkill to use hash tables ???

isn''t faster to initialise a manager with a max_textures and a array[max_textures] of pointers to textures, thereby returning the array index as handle for the pointer pointing to the texture ???

Sure it consumes memory if you only use 10% of the max posibile number af textures, but you dont have to hash each time you want a pointer to a texture since you already have the exact position of it. And it may also be at little slow when you load them from disk ( you have to search trough the array for a free pointer, worstcase max_texture compares - but it has only to be done once per texture at load time) ??

erhhh, or is it some sort of application for browsing thru a huge amount af textures ???

Share this post


Link to post
Share on other sites
Try frame based memory allocation. Try and guess how much physical memory the user has or let them change the amount of total ram your game has available to it and allocate it all at startup. Then just get pointers to the chunks you want and load your stuff into it. It doesn't matter if you're eating up most of the ram while your game is running, the OS or any other app doesn't really need it all while you're playing. This way as each level or chunk of associated texture data loads you can get rid of all of it by dereferencing the pointer to it.

You can read up on it in Game Programming Gems. The article there only really mentioned using the hunk of memory and allocating from the two ends moving inward, but you could split the hunk in half and have 4 data blocks to play with.

Edited by - outRider on July 30, 2001 11:07:46 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hmm...

I am undecided as to whether a hash table would have any advantages over a binary search on a sorted linked list, surely a binary search is faster and less memory is used, therefore is the better proposition for a texture manager??

Bloatware

Share this post


Link to post
Share on other sites
I''m kind of unclear on why you want to hash by the filename. Why not encode textures by an integer? this cuts down on hashing time, as well as the space requrements, especially if you''re storing the texture identifier for each surface.

Now, if you do decide to go for an integer texture identifier, may I suggest the use of a B-Tree or B-Tree variant (like red-black, b+Tree, etc.) as opposed to a hash table. Lookups would probably be faster (though, of course, only profiling will tell you for certain), because you wouldn''t need to compute the CRC or, in the case of a suboptimal hash function (and they''re all suboptimal), walk through a long linked list.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!