#16 - lordmetroid - Wed Jan 01, 2003 1:28 am
I have this array for use as a char cashe of what's in the VRAM... And make heavy use of it in my dynamic tile uploading engine...
so I wonder I have just recently read a whole book about optimization but didn't find any real help, but I have a feeling there is no optimization for this!
I wonder is there any sort of optimization for a:
for(search throught the whole array) routine?
#31 - AnthC - Wed Jan 01, 2003 11:56 am
Hi
Yes there's many things you can do for this kind of search.
I would suggest reading up on hashing algorithms, and that should get you started.
Anth
#33 - dovoto2 - Wed Jan 01, 2003 1:29 pm
I believe the fastest approach to this is to use a reverse LUT. You will need a table big enough to have an entry for every actual tile in your tile set. Then any time you write that tile to the screen you store its location in video memory in the reverse lut. You also keep a counter that tracks how many of each tile are currently on-screen. This can be memory intensive but you can usualy spare the 2-10K of eram that it will eat . Basicaly to use it you would place the new tile into video memory incemement that tiles counter and add the video memory tile location to the reverse LUT. Before actualy writting the tile check the LUT. If there is an entry you just write that entry to your map, increment your counter, and you are done. This does require you to track when tiles go out of scope and decrement the tile counters when they are off-screen so you can free the tile memory. It also requires the use of some sort of memory management preferably a stack to control vram character usage.
I do this in c++ and use all four layers with unlimited tile set...full sprite animation and full music support from krawal libs and I have no problems with speed. A tile set with 3000 unique tiles uses about 8k of ewram memory for the reverse LUT and the counters. Drop in the bucket.
I will even be covering this technique in a tutorial soon.
Thanks goes to boofly ( www.2headed.com ) for this algorithem.
Hope this was in some way usefull or even relavant :)
-dovoto
#39 - I.C.E - Wed Jan 01, 2003 7:41 pm
I also think that the fastest approach is the one explained by dovoto2. I know this technique from the Gameboy Advanced Resource Management document by Rafael Baptista. I have rewritten his code a lilttle bit :)
The only disatvantage is the huge amount ram it is used (at least in my case were i need a lot of tiles). But it can easily be minimzed with costs of CPU usage.
#43 - Nessie - Wed Jan 01, 2003 9:47 pm
I'm not quite sure why you need to search the array...is it to find unused slots for when you want to add a new tile to your array? If so, why can't you just have a linked list structure?
You'd need a "free" list and an "active" list....All you do is put each array element into the free list on program initialization. Any time you need a free array element, just grab one off the list ( if there is one )...then append that to the active list. Whenever an active array element is no longer used, push it back onto the free list.
Of course, I might be completely misunderstanding what you even asking. :)
#49 - lordmetroid - Wed Jan 01, 2003 11:15 pm
yes indeed I'm searching for unused slots...
But wouldn't handleing the linked list take alot of power... more so then handling an array of [1024][3], (the second dimension is for properties of the tile)
and if I use a linked list and remove a object so the whole list get's smaller I would need to reupdate my whole vram instead of just the part I have changed...
if anyone are intrested in my not finished dynamic tile engine you can find it on our page...
and one more thing I have been wondering about... what if I make:
u8 *pcx point to REG_BG0HOFS, and the REG_BG0HOFS has a value of 255 and I make pcx++; will REG_BG0HOFS be set to 0 or 256?
_________________
*Spam*
Open Solutions for an open mind, www.areta.org
Areta is an organization of coders codeing mostly open source project, but there is alot of sections like GBA dev, Language learning communities, RPG communities, etc...
#56 - Splam - Thu Jan 02, 2003 1:21 am
0 because you've defined it as a pointer to a u8 so it'll access the ram as bytes and when u do ++ it'll wrap round to 0. You really don't want to access it as a u8 because it's not, there are 9 bits accessible not just 8 so it should be a u16 instead. I'm presuming you've made your define for BG0HOFS like *(u16 *)0x4000010 else the code you've given would actually incremement the pointer pcx to 0x4000011 and not the memory it points to (I know you probably already know this but I thought I'd mention in in case you haven't done it like that and get weird errors)..
#60 - adavie - Thu Jan 02, 2003 1:29 am
Full source code to a dynamic tile-based scrolling engine is freely available at www.2headed.com/bg.zip - sample binary using this code, showing a scrolling map using 17,500 characters is viewable at www.2headed.com/earth3.bin
Enjoy.
Cheers
A
#61 - Costis - Thu Jan 02, 2003 1:45 am
Hi,
You can't assign the address of those variables to point to the BG0 scrolling registers and then use "++" to increase them because they are read-only registers. Using "++" reads the previous value located in that register, increases it by 1, and then writes it back into the register. Instead you should use a method like this:
void AGBMain (void)
{
unsigned short scrollx, scrolly;
....
BG0XOFS = scrollx = xscroll_init_value;
BG0YOFS = scrolly = yscroll_init_value;
...
BG0XOFS = ++scrollx; \\ Use this method for updating the scroll
BG0YOFS = ++scrolly; \\ registers without reading them.
...
}
In this method, variables in RAM (that can be read and written) are used to hold the current horizontal and vertical scroll positions. Because of this, the actual GBA scroll registers just have to be written to instead of read as well. Also, if you want it to overflow to 0 at 8 bits then you would have to change the variable types from "unsigned short" to "unsigned char".
Costis
#63 - Splam - Thu Jan 02, 2003 2:01 am
hehe forgot about that register being write only, too busy explaining about u8 being wrong (and the fact that I don't think I've ever directly ++ed a hardware register on any machine I've ever coded for, always have variables and update those) :)
#85 - Eloist - Thu Jan 02, 2003 3:20 pm
A linked list is very handy for this. Just let every unused entry of your array point to the next unused entry. This takes some time to set up during initilaization, but you're only going to do that once anyway. Then you need to keep track of the first unused index (0 at first). And whenever you allocate an entry you just let that first unused be you entry and replace the first unused index with the index stored in the entry you just allocated. Upon freeing an entry, you just link it back in by letting it point to the previous first unused and replace the first unused index with the free'd index.
Almost no cpu overhead.
#103 - tubooboo - Thu Jan 02, 2003 8:52 pm
a very good, albeit very general coverage of dealing with memory management issues effectively is found at http://www.memorymanagement.org
It helped me write the BG and OBJ allocation systems in HAM
Emanuel
_________________
HAM author
http://www.ngine.de
#36854 - Bojangles - Wed Mar 02, 2005 3:03 pm
| adavie wrote: |
Full source code to a dynamic tile-based scrolling engine is freely available at www.2headed.com/bg.zip - sample binary using this code, showing a scrolling map using 17,500 characters is viewable at www.2headed.com/earth3.bin
Enjoy.
Cheers
A |
Hi there, I realize I'm almost 2 years behind now ;-) But the link to the Earth3.bin Demo is broken, anyone have it still?
#36863 - Miked0801 - Wed Mar 02, 2005 5:22 pm
We use a stack to hold all the possible free tiles - push them all to start in order, pop them as you need to add/remove chars. For our search of tiles in use, we use a hash table with a very simple hash function. I'm sure there are other ways, but this runs plenty fast for us as normal C code in ROM.
#36905 - lordmetroid - Thu Mar 03, 2005 7:28 am
whoa, spoky I get an e-mail noticing me that there has been a reply in a topic I have been watching... This is really old, too old to even remeber I posted it!
I thought this was some new stuff I posted rescently but it didn't make sense I have no such problems which I describe and people replies to. Then I noticed the dates. Talk about digging up dead topics!
_________________
*Spam*
Open Solutions for an open mind, www.areta.org
Areta is an organization of coders codeing mostly open source project, but there is alot of sections like GBA dev, Language learning communities, RPG communities, etc...