First things first, the last <n>(?) blogs I wrote were written under the
strain of increased fatigue. Figured that out when I nearly blacked out yesterday. I've been sleeping a lot now, in order to catch up (1-2 hours of sleep per 24 hours doesn't cut it).Completely broke my sleeping pattern, trying to get as much done as I could before I have to start work. :3Secondly, let's get to what this blog is about: Decisions.Rob asked a good question in my one blog earlier; one which I failed to answer coherently. So here we go. Let me try this now that I've had at least ten hours of solid sleep.Why std::vector instead of std::list?No reason, they're interchangeable for the most part. I should have used std::list from the start, but I'm in the bad habit of automatically using vector. Linear traversal of a list is definitely faster, whereas vector is better suited to random access. Of course, in Exile, the only thing I'm really using Containers for would be the Asset manager. Before the game can start, all resources are loaded into their respective vectors, usually with a corresponding nametable. The Assets class provides the GetImage("name") and GetImageByID(9) static member functions. These use the nametable and the corresponding index in the resource table to return a pointer to the image, or throws an exception if that image was not loaded.If I was to rework the system, I would have created a pair-list class, with a basic hash table. And I probably would've done it from scratch.Of course, I wasn't expecting to get this far with Exile, nor the framework underlying it; so my all encompassing excuse for the use of vectors where lists would do better is this: Prototype evolution.Why my object vectors are insert-sortedThis only takes effect in the 2D mode of the framework, and was only in use for Exile. It's useless in 3D. The best way to describe this is as a cheap depth sort. Of course, a faster method would be to create my own doubly-linked list class, and use recursion to add new objects. Then call a recursive function to draw all elements from the tail of the list.Things I'm doing nowI created a rather extensive framework thanks to this competition, and I'm definitely going to be shelving it for further use. Already it's proven itself useful beyond a doubt, as I started creating Arbiter with it. And then I moved on to Exile, using the exact same framework. There are a lot of optimizations and general rewrites that need to be performed on the framework, granted. I have marked several locations within the code that need optimization, mathematical attention, and re-design; but the 'engine' and the games I created with it work for now. I'm planning on releasing the cleaned and optimized code to Exile within the next month or so. I still need to go back and resolve the problems I 'brute-forced' because of the time constraints.Well, back to whatever it is I was going to do today. Read a book perhaps.
Also:
Object *obj = new Object(depth or whatever); for (Node *it = objects.head; it != NULL; it = it->getNext()) { if (it->getNext() == NULL || it->getNext()->getObject()->getDepth() > obj->getDepth()) { objects.insert(it, obj); // Assuming insert after iterator break; } }Object *obj = new Object(depth or whatever); for (std::list<Object*> it = objects.begin(); ; it++) { if (it == objects.end() || (*it)->getDepth() > obj->getDepth()) { objects.insert(it, obj); break; } }Wow. The line breaks on this one were really stuffed up. I'm using NP++ next time.
@Rob: It's marginally faster. According to the algorithm, they're supposed to be equal, yes. The assembly listings show otherwise.As for the levels, I just remembered why I used vectors instead of lists. The random access speeds.Before even entering a loop, I use the current 'view' coordinate to designate a rectangle of indices into the level 'array' (Actually, I used an array later; replaced vectors). Depending on the resolution of the view, the render time remains constant. With the levels, in both Exile and Arbiter, the tile data includes a collision field. This is used for basic entity->level collision detection, and in this case, only a tiny rectangle of tiles needs to be checked by the game (Usually player.x-1, player.x+1, player.y-1,player.y+1 to get an encompassing rectangle).For entity->entity collision I first use an 'in view' test. Then I use a simple distance-squared check to see if two objects are in range. If they are, a simple AABB collision test is performed.The collision is managed by the RoomManager class in my game, which basically iterates through the Object list, remove 'dead' objects, calls the object->Step() functions, and use double-dispatch on collision between two entities. Also, in most cases with a no-argument function and recursion, stack overhead is reduced by the compiler optimizer. The difference is negligible on any piece of computer hardware better than an old P2.@Luda
I tried testing it with lots of iterations and the vectors just kept crashing after 0x3FFFF. And at 0x3FFFF it was <1 second for the list, vs 9 seconds for the vector for insertion in the middle of the container. I tried using reserve() to lower than 9 seconds, but it would just crash…Either way, even when they weren't crashing, std::vectors were slower than std::lists for insertion in the middle.Also, max_size() was returning 1,073,741,823. And 262,143(what it was crashing when I went over) is a hell of a lot smaller than 1,073,741,823. I always thought vectors used a 32bit uint though, not a 30 bit one…@MegaWhen iterating you're merely jumping to different addresses. Of course, the [] operator for vector is faster, though access times become equal (In number of operations, so be appeased, ludamad).
Of course, when using assembly operators you have to factor in the number of CPU cycles per operation (Which varies per operation).My previous statement about it being marginally faster is inaccurate. They're equal. If you want the basic figures, with a vector, chunks of memory are allocated linearly, and traversal is performed using basic pointer arithmetic (I'd say sizeof(stored object), but that's not true with classes that have virtual methods). With a list, the allocation takes place wherever it can (Sometimes in chunks, depending on the compiler implementation), and of course, pointers are used to get to the next/previous element in the list. So by what I can tell, linear access time for reading/writing.Of course, inserting is a different story. Vector can merely find an empty chunk with enough space. It gets bitten in the ass when it runs out of space, and has to allocate a new chunk, and copies the old chunk across to the new space.So list is definitely faster in that respect.Either way, guess what? I looked at Exile's code again, and guess what I was using all along? std::list. [/facePalm]@Rob:
This is more what i had in mind:Example:#include <iostream> #include <list> #include <ctime> #include <vector> using namespace std; const int testamnt = 100000; void vector_test() { std::vector<int> test; for (int i = 0; i < testamnt; i++) { std::vector<int>::iterator it = test.begin(); for (int z = 0; z < i / 2; z++) { ++it; } test.insert(it, 2); } } void list_test() { std::list<int> test; for (int i = 0; i < testamnt; i++) { std::list<int>::iterator it = test.begin(); for (int z = 0; z < i / 2; z++) { ++it; } test.insert(it, 2); } } int main() { clock_t c = clock(); list_test(); // vector_test(); cout << double(clock() - c) / CLOCKS_PER_SEC << endl; // prints !!!Hello World!!! return 0; }But wouldn't you be traversing it anyways if it's an entity list that you're updating every frame already? Traversing the entire thing every single time seems kinda unfair against the list, since I don't think it really applies here.
Fair enough, but marking all the entries for deletion with a vector and compressing it in one go will still be faster.