If you want to keep the linked-list, insertion sort it and remove&re-insert when something moves.
Merge-sorting a list holds more promise than qsort does.
Why can''t you use a re-sizable array?
Anyway, I''m going to add "sorting a list" to my "damn good reason to use the stl" bag.
Rapid sorting of linked-list
Yes, it would be a good idea to try using the STL, that''s what it''s there for, but..
It appears that you are trying to do a type of "depth" drawing. Why don''t you just use a binary tree? Items will be inserted into their correct location when they are inserted, and to draw you just iterate through the tree, and everything will already be in the correct order.
-nt20
It appears that you are trying to do a type of "depth" drawing. Why don''t you just use a binary tree? Items will be inserted into their correct location when they are inserted, and to draw you just iterate through the tree, and everything will already be in the correct order.
-nt20
The radix sort is well suited to linked lists. It runs in O(n) time, and is quite fast even for a small number of items. Try to find some information on it, I can''t really explain it too well.
And Stoffel, what good is a cake if you can''t eat it?
And Stoffel, what good is a cake if you can''t eat it?
Author
After toying with the idea last night, I think I might move to a resizable array of pointers. Sure, it might use more memory than a linked list, but it sure saves me a lot of headaches. Resize only when necessary (which shouldn''t be too frequent).
The reason I''m not using the STL is because I wanna learn to do my own data structures
If it was a commercial program, sure, using the STL will be the first thing that I''ll do. But seeing as the purpose of this game is ''educational'', I''ll use my home brewed lists.
To the anon who suggested binary trees. What happens when the coordinates are updated? Will I have to recreate the entire tree?
I''d really like to thank you guys for the useful info. Its been really helpful.
The reason I''m not using the STL is because I wanna learn to do my own data structures
If it was a commercial program, sure, using the STL will be the first thing that I''ll do. But seeing as the purpose of this game is ''educational'', I''ll use my home brewed lists.To the anon who suggested binary trees. What happens when the coordinates are updated? Will I have to recreate the entire tree?
I''d really like to thank you guys for the useful info. Its been really helpful.
Hey I was the one who mentioned binary trees -
I was thinking that you probably were using objects to represent the isometerics...then you could add a pointer to the object into the tree. The coordinates being updated would not affect the tree, only the objects in the tree. From what I gather, you have to update the coordinates in some fashion right now anyway, albeit deleting a link list entry and entering a new one, etc?
However, I see your point. You''d have to resort the tree every time coordinates changed....
I think the list of pointers sounds like a good idea too.
-nt20
I was thinking that you probably were using objects to represent the isometerics...then you could add a pointer to the object into the tree. The coordinates being updated would not affect the tree, only the objects in the tree. From what I gather, you have to update the coordinates in some fashion right now anyway, albeit deleting a link list entry and entering a new one, etc?
However, I see your point. You''d have to resort the tree every time coordinates changed....
I think the list of pointers sounds like a good idea too.
-nt20
Hmm. I'm not sure if I've got the problem down right, but here's my analysis.
Considering the fact that you know each object will have a Y coordinate value, and thus need to be drawn in order, and this is the assumption part.. Why not just have n linked lists of the Y coordinates? You can just move the objects from list to list.
For example.
Array of pointers["Here's the max range of Y values"]
Array[Y=0]->Linked list of all objects with Y 0
Array[Y=1]->Linked list of all objects with Y 1
Then when the Y changes...
Just add it to Array[Y].
Maybe I've missed some of the problem?
"So much fun, so little time."
~Michael Sikora
Edited by - guardian_light on October 18, 2001 5:03:58 PM
Considering the fact that you know each object will have a Y coordinate value, and thus need to be drawn in order, and this is the assumption part.. Why not just have n linked lists of the Y coordinates? You can just move the objects from list to list.
For example.
Array of pointers["Here's the max range of Y values"]
Array[Y=0]->Linked list of all objects with Y 0
Array[Y=1]->Linked list of all objects with Y 1
Then when the Y changes...
Just add it to Array[Y].
Maybe I've missed some of the problem?
"So much fun, so little time."
~Michael Sikora
Edited by - guardian_light on October 18, 2001 5:03:58 PM
My two cents goes to Guardian_Light.
Just an array of pointers, with each index pointing to the
beginning of a linked list of sprites with the corresponding
y-coordinate.
Look up time shouldn''t be too bad, if you know where it is,
you can go to the appropriate index rather quickly.
I haven''t done an isometric game, so I''m wondering why
"because it is an isometric game, what I''m doing at the moment
is going through the list and drawing the sprites with the
highest Y coordinate value first, followed by those with lower
Y coordinate values."
Pardon my ignorance on the making of isometric games.
Just an array of pointers, with each index pointing to the
beginning of a linked list of sprites with the corresponding
y-coordinate.
Look up time shouldn''t be too bad, if you know where it is,
you can go to the appropriate index rather quickly.
I haven''t done an isometric game, so I''m wondering why
"because it is an isometric game, what I''m doing at the moment
is going through the list and drawing the sprites with the
highest Y coordinate value first, followed by those with lower
Y coordinate values."
Pardon my ignorance on the making of isometric games.
Author
In an isometric game, the object with a higher Y value, is lower down the screen, and thus "nearer" towards you. because of this, an object with a lower Y value is higher up the screen, and thus, "further" from you.
This kinda simulates 3D. So, in order for this to work, the "nearer" object must occlude(right term?) the "further" object. That''s why I''m going through the list and drawing stuff like that.
This kinda simulates 3D. So, in order for this to work, the "nearer" object must occlude(right term?) the "further" object. That''s why I''m going through the list and drawing stuff like that.
Well I've written a few iso games, (champion checkers can be seen at the GD showcase) although it's one of my first =)
I've used the pointer index list in my games, and it's a fairly quick method that can also be useful for collision detection, mouse position, etc; becuase each 'row' is a list. Anyways, I need to stop rambling, I've a party to go to =)
"So much fun, so little time."
~Michael Sikora
Edited by - guardian_light on October 19, 2001 1:38:25 PM
I've used the pointer index list in my games, and it's a fairly quick method that can also be useful for collision detection, mouse position, etc; becuase each 'row' is a list. Anyways, I need to stop rambling, I've a party to go to =)
"So much fun, so little time."
~Michael Sikora
Edited by - guardian_light on October 19, 2001 1:38:25 PM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
