Single Array or Multi Array for Tiles?

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

Recommended Posts

I've tried both ways of drawing tiles and I didn't really notice any difference. I did read up on how single arrays are faster to draw. I've setup my Editor to draw like that but it required a ton of code because you need to draw for every row. I know that multidimensional arrays are easier to draw because you just do it once for x and y, however is there any real advantage for me drawing from single arrays instead?

Share on other sites
I am not totally sure why (or how) 1D would be "faster to draw", but would the possible slight speed increase be worth the added complexity? The answer is more than likely no, so I would just use a 2D array...

Share on other sites
I found that an array of array is easier to manage. In C# here's how I handle tiles :
	/// <summary>	/// Contain all the tile of the layer	/// </summary>	List<List<int>> Tiles;
Why is it easier ? When you need to resize your level ! Its easy to removes one row or adds a column.

Share on other sites
A 1D array is going to be much better for memory access.
1) a 2d array means accessing an element is pointer->pointer->value
a 1D array is pointer->value
over items that you are going to want access to all the time(drawing, pathing, line of sight) the one less level of indirection is paramount (this is the same reason many consoles warn against virtual functions, the pointer->pointer-> lookup can be very slow, not to mention they are bad on the instruction cache of some consoles)
2) Why can it be really slow? 1, the memory is not coherent so it means reading two very non-local blocks of memory, and that means one may be in the cache while the other isn't. and it also means that one may be in the cache and the lookup of the other evicts the first one, so you thrash the cache as you swap back and forth between the two sets of pointers.

The 1D array is going to be much nicer on your memory fragmentation as it is ONE block instead of many small blocks.

Quote:
 I've setup my Editor to draw like that but it required a ton of code because you need to draw for every row.

I have no idea what you mean here.

Assuming C++.
std::vector<Tile> mapTiles;mapTiles.resize(height * width);for ( int y = 0; y < height; ++y ){  for ( int x = 0; x < width; ++x )  {    mapTiles[ x + y*width ].Draw();  }}// ORfor ( std::vector<Tile>::iterator i = mapTiles.begin(); i != mapTiles.end(); ++i ){i->Draw();}

Quote:
 List> Tiles;

Sorry, I'm not a C# guy. But in C++ a std::list<> is a linked list.
A linked list makes no sense for a map unless you constantly stream in tiles along the edges or something. The random access is going to be terrible, the cache locality is terrible, and thus it is going to be far slower than an array.

[Edited by - KulSeran on January 14, 2009 3:26:43 AM]

Share on other sites
Quote:
 Original post by KulSeranSorry, I'm not a C# guy. But in C++ a std::list<> is a linked list.A linked list makes no sense for a map unless you constantly stream in tiles along the edges or something. The random access is going to be terrible, the cache locality is terrible, and thus it is going to be far slower than an array.
In C#, a list is a container with constant-time random access.

Share on other sites
Quote:
 Original post by KulSeranA 1D array is going to be much better for memory access.1) a 2d array means accessing an element is pointer->pointer->value a 1D array is pointer->value

It depends if your array is jagged or not. A regular old statically-allocated 2D array should perform identically to a 1D array, except the compiler will handle the pointer arithmetic for you.

But for arrays-of-arrays, yes, that might make a difference.

Share on other sites
In C++, use boost::multi_array. It provides resizable storage with all the semantics you'd expect for a multidimensional array, but also stores elements in a single contiguous block (the same as a statically sized primitive multidimensional array) and thus allows for efficient iteration.

Share on other sites
I should of made it clear in my post. I'm not using C#, I'm using C++.

How I drew for every row was easy. Just too much code to write.

KulSeran, I would make an Array for each row of my map, then draw on after another. They would all start at the same x value, I would just have to change the y value +32 for each row.

Thanks for all of the replies.

Share on other sites
Do you have any data that demonstrates that using this approach actually yields better results?

Im kinda skeptic because such task should be easy to handle for today cpu's and you will benefit from cleaner code than from minimal perf gains

Share on other sites
Quote:
 Original post by EvilNandoDo you have any data that demonstrates that using this approach actually yields better results?Im kinda skeptic because such task should be easy to handle for today cpu's and you will benefit from cleaner code than from minimal perf gains

I didn't make any claim that it runs faster. I was asking if any knew.

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 13
• 76
• 11
• 10
• 14
• Forum Statistics

• Total Topics
632968
• Total Posts
3009582
• Who's Online (See full list)

There are no registered users currently online

×