Best data structure for variable dimension arrays?
Blitz3D Forums/Blitz3D Programming/Best data structure for variable dimension arrays?
| ||
| I'm looking to create a library to allow a use to create Perlin noise maps and then apply various deformations to them to create the desired noise. I've realized that some of these variations require other Perlin noise maps, sometimes of different sizes that the user might experiment with. So, I can't just start with one global array or a fixed number of them; I want to be able to have a function essentially return the noise map as an array of floats, or something that can be interpreted as an array of floats. I've thought of a few ways of doing this, and I want your advice on which may be better: 1. Using Blitz arrays (with the []). Disadvantage; I need a separate function for each size (since they must be dimensioned at startup). Since Perlins have to be a power of two anyway (that's part of the Perlin algorithm) that might be ok. Then again, I don't think the two dimensions have to be the same power of two (x and y can be different sizes) so that would still be a slight limitation. 2. Use images to store the data. Assuming I can use all four bytes of the image ARGB, it should be possible to put the floats (also four bytes I understand?) into that data. This might be the easiest way? 3. Use memory banks of some kind? I haven't used them before. Is it possible for a function to return one and then call that function any number of times to get banks of various sizes? 4. Something I haven't thought of? Thanks for any help youse all can provide! |
| ||
| Is it possible for a function to return one and then call that function any number of times to get banks of various sizes? Yes. Banks essentially fill the same niche as dynamic arrays in other languages: they can be any size, they can be resized, they can be passed both up and down the callchain and stored wherever you like, and you're not limited to a single global instance. The price is that you have to use the peek and poke functions instead of array indexing, and that they're slower; but in practice they're usually the best option because there's simply no obvious alternative in B3D. You can think of a bank as being like an image, but without the overhead of the "renderable stuff", and with extra features like dedicated Peek and PokeFloat commands so you don't have to do any messy casting to get floats in there. It's also likely to be faster for arbitrary memory work since you don't need to do any locking of buffers and swapping to/from video memory. A bank is definitely superior to an image in all respects for this kind of task (if you want to render the final version of the map, better to develop it in a bank and then copy the pixels to an image later). Blitz arrays have two big advantages: their speed, and convenient notation. The speed is nice but unlikely to be necessary unless you're having major performance problems. Being able to use array notation instead of function calls (especially for setting data) is a really nice way to make your code clearer: bank-based code can be extremely hard to read. So you need to weigh up which factors are more important to you. Something I haven't thought of? You could use a Dim array (resizeable, and can be shrunk to zero when not in use) to generate the map, then copy the result to a bank for storage and moving around? That way you get the advantages of speed, nice (multidimensional!) array notation, and portability of result data. You only need to deal with the bank at the end of the function when you copy the data out of the array, keeping your algorithm code cleaner. Using this technique you could even go all-out silly and pass the data around as strings if you wanted, and never need to worry about freeing a bank again because strings are garbage collected (note: I am not seriously recommending strings for data storage). Last edited 2013 |
| ||
| Cool. This is so helpful. Thank you. I'll ponder these issues. I did this once before for my terrain generator, but I never liked the method. It used a Dim'd array like this: Dim CloudArray(sizeX,sizeY,4) with the last value determining how many I could play with at once. Not only was it wasteful, it limited all the arrays to the biggest size, and I realized that most of the other noisemaps I needed should be quite small by comparison. I'll try out banks. Thanks! (Hey that rhymes!) |
| ||
| 2. Use images to store the data. Assuming I can use all four bytes of the image ARGB, it should be possible to put the floats (also four bytes I understand?) into that data. This might be the easiest way? 3. Use memory banks of some kind? I haven't used them before. Is it possible for a function to return one and then call that function any number of times to get banks of various sizes? Essentially these two are equivalent, although with the IMages, you may need to work with buffer locking etc. which can be slower than directly peeking/poking the memory. So Banks are preferable, very much as Yasha suggested, although I would perhaps include a Blitzarray to act as a hash table of memory locations. This will allow much faster access to the specific bytes. |
| ||
| I'm experimenting with banks. Folks say that the peek/poke commands are slow, but I find the PeekFloat and PokeFloat are many times quicker than the corresponding commands for the other datatypes. Also, it is much faster than ReadPixelFast/WritePixelFast. I couldn't find a thread about this in my quick search (Floats being so much faster than other datatypes in banks). Is this a known thing? Arrays (both Blitz and Dimmed) are much faster than anything else, so I'll probably use a dimmed array within the perlin function, but then use a bank of floats to pass them around, combine them, etc. |
   |