   [SOLVED] Optimisation of Tile-Based rendering system.
  Hello everyone, itsa me again!I'm currently building my tile-based engine, and ran into something that is bothering me greatly. Namely - association of tile IDs with objects in memory.Let's see what we have:Objects:- Tile ID- Stored in an object array, with arbitrary array ID, depending on filename order.Tileset:- simple x*y array of signed ints as some IDs will be negativeLet's consider the following pseudocode:// DRAWCODEfor all x in tablefor all y in tableif table(x,y) != 0{int id = FindID(table(x,y));DrawStuff(id);}}}// END DRAWCODEint FindID(int tileID){for all objects in scene{if sceneobject[iterator].tileID = tileID {return iterator;}}}What bothers me is the use of the FindID function, which needs to go through all the tiles in the scene x*y times per frame.Are there any mechanisms that would allow me to associate data so it can be fetched in one call?Our test data looks like this:3dobject Objects[4];Object[0].tileID=1;Object[1].tileID=5;Object[2].tileID=-1;Object[3].tileID=3000;What I'm aiming at here, is to make an association so the renderer knows that for ID= -1, he should draw the Object[2], without looping through all possible values.I'm pretty new(or very green) with STL, but i've seen something as std::map, would that be of any help in this case?All comments welcome.[Edited by - NestorPL on September 13, 2007 10:43:28 AM]
  Yes, std::map could help in this situation, but if each object in the array has a unique tileID (that seems to be the case), what's stopping you from just using the index into the object array directly as the identifier and storing that in the table array?  Then you don't have to worry about looking up which object in the array to use and can just do DrawStuff(table(x,y)).   ;  I don't think he can use the id as an index since he's using a signed number for the ID. An std::map should work quite well though. Though I think Kalidor does have the more efficient answer, can you just map your ID's to an unsigned int?   ;  Because DrawStuff(id) takes the array ID as a parameter, not the tile ID.The whole problem here is discrepancy (sp?) between the index of the object array, and the tileIDs the objects have.Object 0 has id of 1Object 1 has id of 4Object 2 has id of -1..Object n has id of random%For this case, calling directly via the ID would mean trying to access the index= -1, and no compilator will let that go through ;-)Imagine a large array of 3d objects, each with a random ID. You cant really order them so the array index = tile ID. This would cause major gaps in the array, or force you to redo the whole ID assignment if you want to put anything inbetween.I'll take a look at map, thank you very much.   ;Quote:Original post by Dancin_FoolI don't think he can use the id as an index since he's using a signed number for the ID.Quote:Original post by NestorPLThe whole problem here is discrepancy (sp?) between the index of the object array, and the tileIDs the objects have.Object 0 has id of 1Object 1 has id of 4Object 2 has id of -1..Object n has id of random%For this case, calling directly via the ID would mean trying to access the index= -1, and no compilator will let that go through ;-)I understand that.  What I meant is that there may not be a need for a random signed integer tile ID that needs to be mapped to an unsigned array index.  I don't know what else your code is doing, but if you don't need that signed tile ID then get rid of it and just use the array index directly.  If you do need the signed tile ID for some reason, then std::map should work for you.In the case that you do need to keep the signed tile IDs, you may be able to combine these options to speed up rendering time.  What I'm thinking is that you may be able to still store the direct array indices in the table array so you only need to do the tileID->index mapping when you populate the table array instead of every frame at render-time.  Or if the table array does still need to store the tileIDs, maybe you can have another x*y array that stores the already mapped array indices corresponding to the same (x,y) in table.   ;  In the end I went with std::map, and it's working great now.I need to keep the signed IDs and other structures, because otherwise the tile table would be a mess to manage. In current state, I can assign tileID per filename, and assign multiple tileIDs to one filename (ie, wall rotated 3 times, it's still only one object in memory).Thanks for input everyone.Until next one!   