help programming!
Author
hey what is your ideas about this?
i wanna make a game with quite many instances and collisions.
whats best...
Arrays?
or
Linked List
i used arrays before but it takes much memory and is hard to delete and change
so what about linked list can a game have many collisions with some average speed??
it will be 2d.
thx
I am not sure, havent tackeled the problem myself
(the few games i completed had about 1-10 sprites on screen so I did the collision detection in the slow linked list way)
I think todays computers can handle the collision checking of many many hundreds of sprites without serious performance hit so I would go with whatever is easier to program. Try to design it right (say model-control-view pattern) so if the model is slow you can change datastructure or algorithm and it wont effect the code you have for the rest of the game.
If you have some static collision objects (that dont move around) you can maybe use some sorted data structure (sort by X coordinate for example) and then you can check collision with them much quicker: O(log(n)) instead of O(n) which would be a huge difference if you have tens/hundereds, however this is much harder to program and debug than a usual unsorted linked list.
good luck,
Iftah.
(the few games i completed had about 1-10 sprites on screen so I did the collision detection in the slow linked list way)
I think todays computers can handle the collision checking of many many hundreds of sprites without serious performance hit so I would go with whatever is easier to program. Try to design it right (say model-control-view pattern) so if the model is slow you can change datastructure or algorithm and it wont effect the code you have for the rest of the game.
If you have some static collision objects (that dont move around) you can maybe use some sorted data structure (sort by X coordinate for example) and then you can check collision with them much quicker: O(log(n)) instead of O(n) which would be a huge difference if you have tens/hundereds, however this is much harder to program and debug than a usual unsorted linked list.
good luck,
Iftah.
Author
u have some points but the sorting also takes time.
what u think about making a game with linked list's??
what u think about making a game with linked list's??
You don't have to necessarily keep deleting/creating your game objects. Instead, create an array with a fixed number of objects. (80 - 100 should be a reasonable amount for a lot of games)
Then, just give every object a bool that says if the object is used or not. If you need a new object, search for the first free object in the array, set it to "used" and then set all the other data.
This will save you a lot of ticks and the memory-penalty shouldn't be too high...
Much Luck!
Then, just give every object a bool that says if the object is used or not. If you need a new object, search for the first free object in the array, set it to "used" and then set all the other data.
This will save you a lot of ticks and the memory-penalty shouldn't be too high...
Much Luck!
I'd go for Kalasjniekof's technique. It works well for me, and is very easy to set up and use.
well, I have used linked lists at first.. they are a little hard to maintain until you get used to them.. but after that everything is fine.. but nowadays I don't use them for simplicity and ease of programming.. As Kalesnikof mentioned you can use an array.. An array of pointers that points to your objects structures would do the work.. If you make it global then every element will be also NULL so setting them will be easy.. and when initializing your object it is enough to save the adress of your object's structure in the array..
I usually used linked lists, but I've been thinking about using a tree with the branches spliting based on the object type. That way I can quickly find certain types of objects quickly, without searching the whole list.
For example, say an enemy object needed to fire a bullet at the player, he would simply call the scene manager (or where ever the tree is stored) and say "Get Player Type". This would return all the leaf nodes in the player type branch, which in this case would only have 1 object (assuming there is only one player), and he can now calculate the vector the bullet needs to be fired at. If this was done in a regular linked list or array system, the scene manager would have to travese the entire list of every object in the world.
The only problem I see is dependening on how you set up you types, there may be some ambiguties (sp?).
Hope I didn't go too far off course there [wink]
Matt Hughson
For example, say an enemy object needed to fire a bullet at the player, he would simply call the scene manager (or where ever the tree is stored) and say "Get Player Type". This would return all the leaf nodes in the player type branch, which in this case would only have 1 object (assuming there is only one player), and he can now calculate the vector the bullet needs to be fired at. If this was done in a regular linked list or array system, the scene manager would have to travese the entire list of every object in the world.
The only problem I see is dependening on how you set up you types, there may be some ambiguties (sp?).
Hope I didn't go too far off course there [wink]
Matt Hughson
Quote:Original post by Hunter_Ex
...i used arrays before but it takes much memory...
Also, an array should take up less memory than a linked list in theory.
Matt Hughson
Quote:Original post by matthughsonQuote:Original post by Hunter_Ex
...i used arrays before but it takes much memory...
Also, an array should take up less memory than a linked list in theory.
Matt Hughson
Please explain this, because it's very wrong.
Quote:Original post by BeerNuttsQuote:Original post by matthughsonQuote:Original post by Hunter_Ex
...i used arrays before but it takes much memory...
Also, an array should take up less memory than a linked list in theory.
Matt Hughson
Please explain this, because it's very wrong.
arrays do not require the next node member of the structure, hence why they should take up less room in theory
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
