Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Author
Message
Sph!nx
17
Years of Service
User Offline
Joined: 3rd Dec 2008
Location: The Netherlands
Posted: 15th Oct 2013 22:00
Hey everybody,

Got a question about arrays and long data lists. I'm working on a voxel engine and need to keep track of long lists of data (blocks). For this I currently use this:

loop:

adding new elements:


Now, im really adding blocks and stuff and notice that arrays are really getting slower, the more elements get added. I can reduce the array counts, by keeping a global, but adding actual elements will slow down.

These commands...

... both appear to search through the list until it found it's place, thus making it slower, the longer it needs to search.

Any ideas on how to create such data lists without slowing down? (I hope I make sense)

Thanks!

Regards Sph!nx
www.mental-image.net
Chris Tate
DBPro Master
17
Years of Service
User Offline
Joined: 29th Aug 2008
Location: London, England
Posted: 16th Oct 2013 00:12 Edited at: 16th Oct 2013 00:19
This is quite a broad topic actually; there are so many views and solutions for this matter but I can only suggest what I am currently putting into practice; which is to not iterate 3D arrays or huge lists. Use the grid as storage, not as an iteration list.

Shortlist voxels as they fire up events; then loop through this list. Shortlist any voxels removed from the simulation and reuse IDs.

If nothing happens, do not iterate; if something happened to voxel 123,302; only update that voxel. If voxels 1,2 and 3 are out of range, do not iterate voxels 1,2 and 3. When I say iterate I am referring to for loops.

One side note and suggestion if you are taking this project really seriously. Learn how to program raw memory; RAM is really fast. Learn how to use the Peek and Poke commands supplied by the Matrix1 utility plugin; it is a free investment which pays off with lightning fast data management, much faster than array insert calls because you are dealing directly with RAM via a fast middle man. It peek/poke is also faster than memblock and bank commands; better yet you can peek and poke memblocks and banks; it is also possible to peek and poke arrays, but that is overkill.

In summary, use arrays for cache and occasional processing; use shortlists for intense processing; use raw memory for extremely intense processing. By intense I mean dealing with 1000s of voxels in one frame. By shortlist I mean making small indexes of things which need updating, and whilst updating these things you also determine whether to keep the item in the list for further updating.

I think Clonex is working on a voxel plugin or something; correct me if I am wrong?

Sph!nx
17
Years of Service
User Offline
Joined: 3rd Dec 2008
Location: The Netherlands
Posted: 16th Oct 2013 00:30
Thanks for your reply. Wow, didn't realise this was just a complex issue!

Yeah, using the grid is partially true for me. I use that for individual "Block Objects". In contrary to most voxels games, I have "Block Objects" that are controlling the chunks and they have angles and positions that can be changed... so I really need an effective data management system...

Yeah, I believe Clonex is working on that, but I wish to create my own.

I have dark data (though never worked with it)... would that be any good?

Any more suggestion (or examples) would be terrific!

Regards Sph!nx
www.mental-image.net
Chris Tate
DBPro Master
17
Years of Service
User Offline
Joined: 29th Aug 2008
Location: London, England
Posted: 16th Oct 2013 02:43 Edited at: 16th Oct 2013 02:57
Quote: "I have dark data (though never worked with it)... would that be any good?"


In most gaming situations the arrays will be much faster than Dark Data; I speed tested the plugin a few years ago. The only instance where Dark Data will be faster is if you run text based queries; say a keyword search of say 10,000 or 20,000 database entries in which case its indexing will kick in. But arguably you would use an SQL database or some .Net Linq query based database for such a thing.

So if you want to use Dark Data, you could use it to store your world; but again it is not good for iteration.

Think your database as a lorry, your array as a car, and raw memory as a motorbike; the motorbike gets to places more quickly than the lorry, the lorry can carry more things than the motorbike. You could carry lots of things on lots of motorbikes; but then it gets tedious.

The car; the array is the best of both worlds, but only when you do not need the organized nature of databases or the speed of raw memory.

I think you should stick with arrays whilst practicing raw memory manipulation. Use raw memory to store lists in arrays; where the array stores a memory address with stores a series of data; or perhaps a series of lists of data. The beauty of raw memory lists in arrays is that list items do not increase the dimension or size of the array.

Arguably a block of 100 voxels could be stored in a list, which inturn is stored in one array entry, so if you need to update these voxels, updating them is as easy as referencing the single array entry and iterating its content.

One other consideration is my coroutine class tutorial; something which allows you to allocate stacks of memory exclusive for instances of variables, arrays and functions. In a nutshell; the process of running programs in programs; sub-programs; so voxel groups can run side by side using the same functionality with different data.

Sph!nx
17
Years of Service
User Offline
Joined: 3rd Dec 2008
Location: The Netherlands
Posted: 16th Oct 2013 14:57
Wow, thanks Chris. You know how to explain stuff very well!

So basically, I'm on the right track but need put the contents of my array/type thing into memory and have the elements in my array/type point to that bit of memory, correct? (Example: keep chunks in arrays but have the blocks of that chunk in memory, that the array can find).

I have no experience with memory and stuff, so I will first try some simple exercises, like adding a string, or variable into memory and then retrieving it, etc.

I've bookmarked your tutorial and will surely dive into it when I understand memory a bit more.

Thanks again!

Regards Sph!nx
www.mental-image.net
Chris Tate
DBPro Master
17
Years of Service
User Offline
Joined: 29th Aug 2008
Location: London, England
Posted: 16th Oct 2013 16:31
That's right. Accessing arrays requires internal array ID checks, redimensioning of the array when new items are added; which is why there is a slight slow down. Raw memory access does not perform such checks but are more likely to crash your program; it is best to focus on using arrays until you get more confortable with Matrix1 raw memory commands.

Sph!nx
17
Years of Service
User Offline
Joined: 3rd Dec 2008
Location: The Netherlands
Posted: 16th Oct 2013 17:16 Edited at: 16th Oct 2013 18:05
I will, mate.

I'll keep working with my current setup to further develop the (client side) chunk mesh generation and such. I have a written a small test project in which I will practice memblocks. When I'm comfortable with that and can do with it what I wish I will replace the block data from the block array with block data memblocks in the chunk array. At least that's the plan!

Currently searching the forums to get some more beginners tutorials/information on memblocks... Found plenty stuff on image memblocks but something simple as adding a string or something is hard to find.

Thanks again Chris!

Edit:
Found this: http://forum.thegamecreators.com/?m=forum_view&t=192789&b=1

Regards Sph!nx
www.mental-image.net
Chris Tate
DBPro Master
17
Years of Service
User Offline
Joined: 29th Aug 2008
Location: London, England
Posted: 16th Oct 2013 19:17
Great; just a bit of clarification; the memblocks are different from memory functions I was talking about; which is based on Peek and Poke commands, not memblock commands. The memblocks are a little bit slower than raw memory manipulation because of memblock ID and range checks, but are OK for image manipulation amongst other things. Because you can only store 255 memblocks, they limit your potential a bit.

Matrix1 memory banks are similar to memblocks but they do not limit you to 255 instances; however the banks are slightly slower than memblocks.

Sph!nx
17
Years of Service
User Offline
Joined: 3rd Dec 2008
Location: The Netherlands
Posted: 16th Oct 2013 19:24 Edited at: 16th Oct 2013 19:35
Excellent, thanks! Will focus on that.

Edit:
I find that working with Matrix Membanks are much easier for me than native memblocks!

Regards Sph!nx
www.mental-image.net
Sph!nx
17
Years of Service
User Offline
Joined: 3rd Dec 2008
Location: The Netherlands
Posted: 17th Oct 2013 01:23 Edited at: 17th Oct 2013 02:21
Been experimenting with success. I've reduced the arrays from 3 to one ("Block Objects"), that holds a list of membanks for its chunks and each chunk membank has a list for all it's block
membanks. Works as it should but I've hit a snag...

I use "find free bank()" to get free membank nrs, but it stops at 131072... and thats not sufficient Im afraid. Every chunk count 16x16x16 blocks and I need plenty of chunks to manage!

Now, I can always combine all the block data to a string for the chunk memblock but that would create very large string. Not a problem, easy to dissect again, but is there a limit a string lengt for a membank as well?

Any more input is welcome. Thanks!!


Edit
Another solution would be to save the data in (temp) files on disc, instead of memory... though I figure that even be slower than arrays...

Regards Sph!nx
www.mental-image.net

Login to post a reply

Server time is: 2026-07-06 20:15:48
Your offset time is: 2026-07-06 20:15:48