Jump to content

  • Log In with Google      Sign In   
  • Create Account

help programming!


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
20 replies to this topic

#1 Kristoffer   Crossbones+   -  Reputation: 839

Like
0Likes
Like

Posted 04 October 2005 - 04:19 AM

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

Sponsor:

#2 Iftah   Members   -  Reputation: 409

Like
0Likes
Like

Posted 04 October 2005 - 04:36 AM

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.

#3 Kristoffer   Crossbones+   -  Reputation: 839

Like
0Likes
Like

Posted 04 October 2005 - 04:42 AM

u have some points but the sorting also takes time.


what u think about making a game with linked list's??

#4 Kalasjniekof   Members   -  Reputation: 246

Like
0Likes
Like

Posted 04 October 2005 - 04:58 AM

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!

#5 benryves   Members   -  Reputation: 1998

Like
0Likes
Like

Posted 04 October 2005 - 05:07 AM

I'd go for Kalasjniekof's technique. It works well for me, and is very easy to set up and use.
[Website] [+++ Divide By Cucumber Error. Please Reinstall Universe And Reboot +++]

#6 Patroclos   Members   -  Reputation: 122

Like
0Likes
Like

Posted 04 October 2005 - 05:13 AM

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..

#7 matthughson   Members   -  Reputation: 588

Like
0Likes
Like

Posted 04 October 2005 - 05:34 AM

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
__________________________________[ Website ] [ Résumé ] [ matthughson[dot]com]Contact ][ Have I been Helpful? Hook me up! ]

#8 matthughson   Members   -  Reputation: 588

Like
0Likes
Like

Posted 04 October 2005 - 05:35 AM

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
__________________________________[ Website ] [ Résumé ] [ matthughson[dot]com]Contact ][ Have I been Helpful? Hook me up! ]

#9 BeerNutts   Crossbones+   -  Reputation: 2999

Like
0Likes
Like

Posted 04 October 2005 - 07:35 AM

Quote:
Original post by matthughson
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


Please explain this, because it's very wrong.

#10 eedok   GDNet+   -  Reputation: 971

Like
0Likes
Like

Posted 04 October 2005 - 08:01 AM

Quote:
Original post by BeerNutts
Quote:
Original post by matthughson
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


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

#11 matthughson   Members   -  Reputation: 588

Like
0Likes
Like

Posted 04 October 2005 - 08:31 AM

Quote:
Original post by BeerNutts
Quote:
Original post by matthughson
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


Please explain this, because it's very wrong.


Yeah basically you have all the memory that an array would use (for storing the actual objects) plus the memory needed for the pointers in the linked list (and any other memory the linked list uses).

Matt Hughson

PS- "Please explain this, because it's very wrong." Who says stuff like this??
__________________________________[ Website ] [ Résumé ] [ matthughson[dot]com]Contact ][ Have I been Helpful? Hook me up! ]

#12 Iftah   Members   -  Reputation: 409

Like
0Likes
Like

Posted 04 October 2005 - 08:35 AM

Quote:
Original post by Hunter_Ex
u have some points but the sorting also takes time.
what u think about making a game with linked list's??


yea, sorting takes time, which is why i said keep only static collision objects in that data structure - you only sort once when the level is loading.
for example in the game of elastomania (i think thats what its called, the 2d motorcycle in a polygon world) i would try to sort the polygons somehow so i can check collision with them fairly quick, while if i had moving objects (saying boxes you can push, or moving platforms or moving enemies) i would put it in a different unsorted datastructure (either array or linked list). for collision i would then check both the sorted and the unsorted.

as for the question of array or linked list - the choice depends on how much you need to insert/remove from the structure and how much you need random access. For collision detection you dont need any random access (you loop checking for each so can do it one after the other) so linked list works fine, and the only advantage you gain from array is that its abit simpler to program. so if you dont add/remove alot you can choose array.
Linked list is my choice since in array as people suggested you might have say 500 cells and 499 empty cells but you still need to check all of them - not elegant.

but as i said first - you should start from simplest approach and fix it later if you find it too slow (i doubt you will feel slowness).

Iftah.




#13 TDragon   Members   -  Reputation: 679

Like
0Likes
Like

Posted 04 October 2005 - 08:38 AM

I believe BeerNutts, stating "Please explain this, because it's very wrong" about a linked list taking up more memory than an array, was referring to the specific scenario that Hunter_Ex brought forth -- namely, storing entities for the game in a linked list. And indeed, the linked list implementation will take up less memory on average than the array implementation, because the linked list can allocate memory on the fly and only use as much as necessary for the current number of entities, whereas the array implementation will always take up a fixed amount of memory that will on average be greater than the current number of entities.

I would advocate the linked list method over an array in this scenario not for the amount of memory it takes, but because it has
- Fast insertions and deletions, O(1)
- Equivalent searches, O(n)

An array only has the advantage in random access, which will happen much less often than any other operation in a typical game. Note that I'm not taking sorting into account for either one, because if it is for some reason necessary it can usually be done once at load time.

Cheers,
Twilight Dragon

EDIT: If you're using the standard C++ data structures such as std::vector (a better array) and std::list (a linked list), it's about as easy to program one as the other.

#14 matthughson   Members   -  Reputation: 588

Like
0Likes
Like

Posted 04 October 2005 - 08:42 AM

If only there were a data structure that was somewhere between a linked list and a static array... [wink]

Quote:
Original post by TDragon
EDIT: If you're using the standard C++ data structures such as std::vector (a better array) and std::list (a linked list), it's about as easy to program one as the other.


Bah your edit ruined my joke!

Matt Hughson
__________________________________[ Website ] [ Résumé ] [ matthughson[dot]com]Contact ][ Have I been Helpful? Hook me up! ]

#15 SiCrane   Moderators   -  Reputation: 9668

Like
0Likes
Like

Posted 04 October 2005 - 08:52 AM

Well, at least he didn't mention a std::deque too, which is more of a hybrid than std::vector.

#16 dbzprogrammer   Members   -  Reputation: 100

Like
0Likes
Like

Posted 04 October 2005 - 10:00 AM

My advice: Use the STL... It's an official part of C++ because it's good. Instead of always having to make your own, it's simply there for use. An array would be faster, but the speed difference honestly doesn't make a difference when you dealing with a few of them, but if you're dealing with a few million, it could.

#17 Kristoffer   Crossbones+   -  Reputation: 839

Like
0Likes
Like

Posted 04 October 2005 - 08:54 PM

thx for all replies and about the memory with arrays ^^

iknow but i didnt thought of making a bool and reuse old parts of the array
so i use to make some big arrays where the old just were left in memory ( very bad)

so now i have gotten lotsa new ideas thx all....

HunterEx

#18 Kizsam   Members   -  Reputation: 133

Like
0Likes
Like

Posted 04 October 2005 - 10:45 PM

Hello,

I think that a AVL tree is ideal for what you want to do. It performs as good as an array for searching and is better for inserts and deletions. Compared to a linked list it is better at searching and deleting. One neat feature of an AVL tree is that the data is ordered the same as an ordered array if you use an inorder traverse (I don't know if this has any relevence to your application).

It is basically the best of both linked lists and arrays.

regards

#19 Kristoffer   Crossbones+   -  Reputation: 839

Like
0Likes
Like

Posted 04 October 2005 - 11:40 PM

okay didnt knew of that :D

but i think ill stick to ARRAYS with use boolean, its not a gigantic game!!

/cheers

#20 ToohrVyk   Members   -  Reputation: 1591

Like
0Likes
Like

Posted 04 October 2005 - 11:47 PM

I use a (heap-based) priority queue to update, a sorted array to render, a (array-based) stack for pool allocation and a (singly) linked list for collisions.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS