Predefine an array of your objects, but give them next/prev pointers. Then keep all of the unused ones linked up in one list, and all of the used ones in another list. This is similar to what Krumble said below.
Upsides:
* Constant time to allocate an object.
* Constant time to free an object.
* When traversing your object list, you only touch valid objects.
* Fixed memory footprint.
* No malloc/new/free/delete.
Downsides:
* 8 bytes extra per object for the next/prev pointers.
Should I store the enemies etc. in lists / arrays? (2D game)
Author
quote:Original post by Tazzel3D
I have tried this method, actually created an entire GUI based on this system only to relize that in D3D, (I don't know what you're using.. wait, what API, functions are you using to draw everything?
If by chance you are using D3D for 2D, you might want to recognize that you can speed up your come tremendously (which I did) by passing around 200+ verts per DIP call.... if you have one render class, you can optimize the calls based on vertex #, texture order, Vertex Buffer changing, etc... Those are very impactual(<- nice word huh?) on speed. If you are not using D3D and thus not using my 'plan', I'm sure you will prolly want to make shure you're not changing textures to offen by calling the render function of similar objects consecutively.
Just some thoughts... If you are infact using D3D just let me know and I can be a bit more specific, I would rather not write a ton and then have you tell e that you're just blitting everything, which I'm not a proficient at.
Hope I can help!
Tazzel3d ~ Dwiel
Yes I am using D3D. Feel free to write a little bit more about this, sounds like some very good ideas you've got there in store. Besides, I didn't completely understand what you said anyways.
[edited by - xjussix on December 13, 2002 8:12:55 AM]
[edited by - xjussix on December 13, 2002 8:14:09 AM]
with all those guys here maybe someone can tell me what might be bad about this:
CEnemy* enemies[256];
int numEnemies=0;
adding an enemy: enemies[numEnemies++]=new CEnemy;
deleting an enemy: enemies[index]=enemies[--numEnemies];
of course i would avoid that, if youre storing more than just pointers in the array, but basically you always have your enemies tightly packed and deleting one means copying a pointer.
one problem i could see would be for bullets. you would fill the arrays front to back and free it front to back too (meaning one copy each time a bullet 'dies'.
to expand the idea. what about always saving a pointer to another array in the last field? so if you really need more space you could allocate a new array instead of reallocating.
maybe something like: (i try to do it without recursion *g*)
though i admit this would end as a linked list of arrays *g*
[edited by - Trienco on December 13, 2002 4:05:55 AM]
[edited by - Trienco on December 13, 2002 4:06:25 AM]
[edited by - Trienco on December 13, 2002 4:07:06 AM]
CEnemy* enemies[256];
int numEnemies=0;
adding an enemy: enemies[numEnemies++]=new CEnemy;
deleting an enemy: enemies[index]=enemies[--numEnemies];
of course i would avoid that, if youre storing more than just pointers in the array, but basically you always have your enemies tightly packed and deleting one means copying a pointer.
one problem i could see would be for bullets. you would fill the arrays front to back and free it front to back too (meaning one copy each time a bullet 'dies'.
to expand the idea. what about always saving a pointer to another array in the last field? so if you really need more space you could allocate a new array instead of reallocating.
maybe something like: (i try to do it without recursion *g*)
void traverse(CEnemy* Arr, int NumEn) {
while (NumEn>0) {
for (int i=0; i //do stuff
}
NumEn-=255;
//might contain crap, but if it does we dont use it anyway
Arr=Arr[255];
}
}
though i admit this would end as a linked list of arrays *g*
[edited by - Trienco on December 13, 2002 4:05:55 AM]
[edited by - Trienco on December 13, 2002 4:06:25 AM]
[edited by - Trienco on December 13, 2002 4:07:06 AM]
Back when I had a Pentium 60, programming 640x480x16bpp in DOS using DJGPP, I made a space-ship game with a bunch of asteroids and planets flying around.
My spaceship had a VERY rapid-fire gun, and I was storing all of my object information in a resizing array of Object*s. The *only* slowdowns I noticed occurred when I drew 3000 projectiles to the screen. When I experimented by aborting the draw cycle after 100 objects, speed returned to normal (blazing fast).
Here's some stuff to keep in mind:
New/delete are NOT slow unless you have a heap manager that does cleanup EVERY time you delete. All the manager usually needs to do to NEW an object is choose the appropriate section (depending on the amount of bytes you request), find the current free block (incremented pointer), mark it as used (MOV), are return the old value of that pointer. This turns out to be VERY few instructions in assembly.
Resizing arrays or object pointers will be faster than linked lists for this type of operation (game object collections).
Walking the collection:
Array: Index pointer, ADD operator goes to the next item in the list, one dereference to the object pointer.
Linked-list: Node pointer, dereference operation required to move to next item, two dereferences to the object pointer.
New-ing items in the collection:
Array: CMP allocated size to necessary size, new and bulk-copy if required (if you resize the array in large enough segments, this will happen infrequently), object* set. Frequency of "new" is at most twice per add, and most likely only once if your array resizes by a large amount.
List: New Node created, last link pointer set to new node, object* set to object (always fast). Frequency of "new" is always 2.
Deleting items from a collection:
Array: swap last element object* with to-delete object*, then decrement the "used-item" count. No array resize necessary. Delete object.
Linked list: Set previous node's next pointer to point to next node. (if bi-directional also set next->previous = previous). Delete object, delete node.
Linked lists use 1*sizeof(pointer) more memory for one-directional traversing, and fragment memory more than an infrequently resizing array will. This may cause heap garbage collection to occur more often (if the heap manager is keeping good track of things)
Linked lists cannot be linearly accessed, so if you need to skip about in your collection without stored node* or object*s, you must follow links. You can use a splay tree to make a array operator implementation faster (of course with more memory overhead).
[edited by - Nypyren on December 13, 2002 6:16:18 AM]
My spaceship had a VERY rapid-fire gun, and I was storing all of my object information in a resizing array of Object*s. The *only* slowdowns I noticed occurred when I drew 3000 projectiles to the screen. When I experimented by aborting the draw cycle after 100 objects, speed returned to normal (blazing fast).
Here's some stuff to keep in mind:
New/delete are NOT slow unless you have a heap manager that does cleanup EVERY time you delete. All the manager usually needs to do to NEW an object is choose the appropriate section (depending on the amount of bytes you request), find the current free block (incremented pointer), mark it as used (MOV), are return the old value of that pointer. This turns out to be VERY few instructions in assembly.
Resizing arrays or object pointers will be faster than linked lists for this type of operation (game object collections).
Walking the collection:
Array: Index pointer, ADD operator goes to the next item in the list, one dereference to the object pointer.
Linked-list: Node pointer, dereference operation required to move to next item, two dereferences to the object pointer.
New-ing items in the collection:
Array: CMP allocated size to necessary size, new and bulk-copy if required (if you resize the array in large enough segments, this will happen infrequently), object* set. Frequency of "new" is at most twice per add, and most likely only once if your array resizes by a large amount.
List: New Node created, last link pointer set to new node, object* set to object (always fast). Frequency of "new" is always 2.
Deleting items from a collection:
Array: swap last element object* with to-delete object*, then decrement the "used-item" count. No array resize necessary. Delete object.
Linked list: Set previous node's next pointer to point to next node. (if bi-directional also set next->previous = previous). Delete object, delete node.
Linked lists use 1*sizeof(pointer) more memory for one-directional traversing, and fragment memory more than an infrequently resizing array will. This may cause heap garbage collection to occur more often (if the heap manager is keeping good track of things)
Linked lists cannot be linearly accessed, so if you need to skip about in your collection without stored node* or object*s, you must follow links. You can use a splay tree to make a array operator implementation faster (of course with more memory overhead).
[edited by - Nypyren on December 13, 2002 6:16:18 AM]
a simple std::vector is best.. its not more than a on the heap allocated array... after the first frames, no allocation will happen anymore (remember, vectors normally never shrink).. => the array will be big enough for you, and simply that: an array...
so technically, what goes on behind the scenes is the same as
Object* objects = new Object[simplythesizeyouneed];
game is running()
delete [] objects;
except, sometimes, there is a resize. but as i said, after the first times all objects are more or less used, resizes are really rare..
"take a look around" - limp bizkit
www.google.com
so technically, what goes on behind the scenes is the same as
Object* objects = new Object[simplythesizeyouneed];
game is running()
delete [] objects;
except, sometimes, there is a resize. but as i said, after the first times all objects are more or less used, resizes are really rare..
"take a look around" - limp bizkit
www.google.com
Quake 2 & 3 for a fact use arrays for all entities. You can have maximum of 1024 active entities in the Quake world. There''s a global definition that specifies that. I guess that would be a good way to do it, since Quake engines are one of the most efficient ones on the market.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
