Quote:
Originally posted by kedaman
that sounds relatively cool, although I think two triangles can be inseparable still
Let me show you a drawing here too...just wait a bit...:D
Quote:
Originally posted by kedaman
that sounds relatively cool, although I think two triangles can be inseparable still
Let me show you a drawing here too...just wait a bit...:D
No it is not actually the same...don't tell me that I have to draw that for you too....:D....it took me 4 og the 6 months of my ALgorith course to understand that it was not the same...I thought it was the same thing...Quote:
Originally posted by kedaman
lol.. binary search trees hehe :D I think all binary trees are search trees, why would you use trees if not for searching ;)
Heard of those....not sure what it is..never had them in our algorith class...Quote:
Originally posted by kedaman
BR means Black Red trees let me find a link
This is as long as I can go on my tree thingy....might happen that BS should have been a child node of Binary tree, and all the other child nodes of BS tree again...but I don't think that...no forget that...this is right...
http://vbforums.com/attachment.php?s=&postid=1663423
nope, it is sensible, I hope you've had your algebra done already,Quote:
Originally posted by NoteMe
BTW why did you change it too bool^2..that is even worse..
BOOL = { True, False }
BOOL^2 = BOOL X BOOL (cartesian product)
= {
(False, False),(False, True)
,
(True, False),(True, True)
}
X^2 are also called 2-tiples or 2-vectors, because they make up of 2 dimensions. A binary vector just make up a two dimensional binary spatial partitioning, True if X>Xboundary, otherwise false, for the X dimension, and True if Y>Yboundary, otherwise false for the Y dimension, and you should have all quandrants given by BOOL^2
Quote:
Originally posted by NoteMe
No it is not actually the same...don't tell me that I have to draw that for you too....:D....it took me 4 og the 6 months of my ALgorith course to understand that it was not the same...I thought it was the same thing...
hehe go ahead.. i was just guessing here i have to admit, but I can't see any other practical use without searching ;)
we had those, but they didn't bother explaining them, we had all sorts of other trees though, and if you work with C++ STL library uses a RB treeQuote:
Heard of those....not sure what it is..never had them in our algorith class...
hehe yeah, you could add, ATL trees and splay trees as well ;)Quote:
Originally posted by NoteMe
This is as long as I can go on my tree thingy....might happen that BS should have been a child node of Binary tree, and all the other child nodes of BS tree again...but I don't think that...no forget that...this is right...
http://www.vbforums.com/
btw i'm not sure if BS tree is a specific tree structure down there
But you first wrote bin (guess that means niary). Binary is 0/1Quote:
Originally posted by kedaman
nope, it is sensible, I hope you've had your algebra done already,
BOOL = { True, False }
BOOL^2 = BOOL X BOOL (cartesian product)
= {
(False, False),(False, True)
,
(True, False),(True, True)
}
X^2 are also called 2-tiples or 2-vectors, because they make up of 2 dimensions. A binary vector just make up a two dimensional binary spatial partitioning, True if X>Xboundary, otherwise false, for the X dimension, and True if Y>Yboundary, otherwise false for the Y dimension, and you should have all quandrants given by BOOL^2
1 = true
0 = false
and you have the same math as you did...
yeah sort of, i changed to boolean because binary is numeric, perhaps more in a technical sense rather than boolean which is theoreticalQuote:
Originally posted by NoteMe
But you first wrote bin (guess that means niary). Binary is 0/1
1 = true
0 = false
and you have the same math as you did...
I don't think there was any use in it...just to extract it to a theory plan, so we could understand it...I at least thing...and I don't want to open that JAVA book again...so please don't make me look for it..Quote:
Originally posted by kedaman
hehe go ahead.. i was just guessing here i have to admit, but I can't see any other practical use without searching ;)
Havn't used STl that much....but at least I know a tiny tiny bit about it...but not much...Quote:
Originally posted by kedaman
we had those, but they didn't bother explaining them, we had all sorts of other trees though, and if you work with C++ STL library uses a RB tree
It has to be it....where the bigger number goes to the right and a smaller numer goes to the left...unlike in a heap where the only thing you know is that the mother leaf is bigger then the child leaf....Quote:
Originally posted by kedaman
hehe yeah, you could add, ATL trees and splay trees as well ;)
btw i'm not sure if BS tree is a specific tree structure down there
Never learned about ATL or Splay either...:D
hehe ok, but then we have to remain sceptical on that thing ;)Quote:
I don't think there was any use in it...just to extract it to a theory plan, so we could understand it...I at least thing...and I don't want to open that JAVA book again...so please don't make me look for it..
Man.. you need to get into it, it helps your life loads :D if you are a C++ programmer that is ;)Quote:
Havn't used STl that much....but at least I know a tiny tiny bit about it...but not much...
Quote:
Originally posted by kedaman
yeah sort of, i changed to boolean because binary is numeric, perhaps more in a technical sense rather than boolean which is theoretical
OK....won't bother you with it anymore...I am never going to call it that anyway..;)
No don't do that....if you are you are forcing me to look it up....:DQuote:
Originally posted by kedaman
hehe ok, but then we have to remain sceptical on that thing ;)
Quote:
Originally posted by kedaman
Man.. you need to get into it, it helps your life loads :D if you are a C++ programmer that is ;)
Isn't it the vector classes and stuff like that in it...???? Yeah I am using C++ now days...only used the Vector class once (and not even sure if it is in STL..:D
AABB tree to the right and a drawing of it to the left....
http://vbforums.com/attachment.php?s=&postid=1663438
hehe i begin to doubt that you were listeining on that course, or maybe they didn't take up all the stuff because you had much other stuff ;)Quote:
Originally posted by NoteMe
It has to be it....where the bigger number goes to the right and a smaller numer goes to the left...unlike in a heap where the only thing you know is that the mother leaf is bigger then the child leaf....
Never learned about ATL or Splay either...:D
BTw, AVL trees, i mispelt ;) when adding a node in an AVL tree it does rotations on the nodes so that they weight about teh same on both sides, a splay tree, flattens the tree every time you pull up an element it does AVL rotations all the way until its on the top, so splay trees are especially good if you access the same things often.
PS: I wish that I had someone in my class like you....you are forcing me to read and learn all the time in a fun way...if I was just as glad to work at school I would probably have straight As...:D....
yeah doesn't make any difference anyway ;)Quote:
Originally posted by NoteMe
OK....won't bother you with it anymore...I am never going to call it that anyway..;)
Quote:
Originally posted by kedaman
hehe i begin to doubt that you were listeining on that course, or maybe they didn't take up all the stuff because you had much other stuff ;)
BTw, AVL trees, i mispelt ;) when adding a node in an AVL tree it does rotations on the nodes so that they weight about teh same on both sides, a splay tree, flattens the tree every time you pull up an element it does AVL rotations all the way until its on the top, so splay trees are especially good if you access the same things often.
We had a lot of sorting algorithms and graph representation too...and they thought us about hashing, interface and stuff like that....so there was a lot of JAva in it too..not that much theory...
Sounds nice with an AVL tree.....but if you make an quad three the right way in memory...then you can just use pointer aretmetric to reach the node you want....guess that works for most trees...
BTW we also forgot about
ABT (Adaptative Binary Tree).
B+ tree
ISAM tree
...:D
Quote:
Originally posted by NoteMe
No don't do that....if you are you are forcing me to look it up....:D
Hehehe :D look it up if you want, i'm staying sceptical here until you tell me how it is ;)
Yeah mostly containers of all sorts, some algortims, but the key concept are the iterators that connects themQuote:
Isn't it the vector classes and stuff like that in it...???? Yeah I am using C++ now days...only used the Vector class once (and not even sure if it is in STL..:D
http://www.sgi.com/tech/stl/index.html
cool, thats brilliantQuote:
Originally posted by NoteMe
AABB tree to the right and a drawing of it to the left....
http://www.vbforums.com/
hahaha :D You could always come here and talk instead so have fun and learn at the same time ;)Quote:
Originally posted by NoteMe
PS: I wish that I had someone in my class like you....you are forcing me to read and learn all the time in a fun way...if I was just as glad to work at school I would probably have straight As...:D....
Quote:
Originally posted by kedaman
Hehehe :D look it up if you want, i'm staying sceptical here until you tell me how it is ;)
Will do it when I have some time here...you are posting to fast to make that simple...;)
Quote:
Originally posted by kedaman
Yeah mostly containers of all sorts, some algortims, but the key concept are the iterators that connects them
http://www.sgi.com/tech/stl/index.html
No no no...:D...we had about iterators in 10 minutes in our C++ class....didn't understand much of the use in those 10minutes....used it in a simple loop to loop through something....
Quote:
Originally posted by kedaman
hahaha :D You could always come here and talk instead so have fun and learn at the same time ;)
Hehe...yeah maybe I should....so are you helping me with my HTML, CSS, PHP, MySQL class too...:D...J/K
BTW have seen a bit of people here that has been looking at our thread the last hour or so....wonder if there is many on this board that can keep up with us now....:D
Ah.. we have got two courses for sort/search algoritms and datastructures altogether so we might have more than you have ;) also done some java (annoying) but now recently they changed to have more programming in it, but I took this couse long ago already when it was more theoretical (thank god;))Quote:
Originally posted by NoteMe
We had a lot of sorting algorithms and graph representation too...and they thought us about hashing, interface and stuff like that....so there was a lot of JAva in it too..not that much theory...
Sounds nice with an AVL tree.....but if you make an quad three the right way in memory...then you can just use pointer aretmetric to reach the node you want....guess that works for most trees...
BTW we also forgot about
ABT (Adaptative Binary Tree).
B+ tree
ISAM tree
...:D
dunno about the pointer artimetic part, thats for heaps, other trees can't be put into arrays just that easily, at least not if you want to use them dynamically
never heard of ABT or ISAM trees, but B+ we went trough, that was when you need to do disk accesses because those are so slow that you can do it much faster with a flat tree ;)Quote:
BTW we also forgot about
ABT (Adaptative Binary Tree).
B+ tree
ISAM tree
Quote:
Originally posted by NoteMe
Will do it when I have some time here...you are posting to fast to make that simple...;)
no you are posting too fast.. I have hard to keep up with you :D
yeah well check out the site I gave you, great reference if you do anything with STL and it does explain what the iterators are ;)Quote:
No no no...:D...we had about iterators in 10 minutes in our C++ class....didn't understand much of the use in those 10minutes....used it in a simple loop to loop through something....
You don't want an oct/quad tree to be dynamicaly....you know making and destroying nodes takes time...in a game it is better to just hold the tree all the time, and use some more memory in stead. It is cheaper then using the Bus all the time....
So if you lay down the quad three as an "array" in memory, you don't get that much cash miss as you do with a normal tree. That is the biggest sinner in a quad tree. Thats what using most of the time....
ABout the JAva/Algorith stuff:
We first had 6months with Basic Java
Then 6 months of ALgorithms in Java
Then we can take Advanced algorithms 6 monts the 3rd year if we want...but remember. I am not as old as you...still on my second year here....;)
hehe noo.. i had that course too, but I wasn't listening too much on that one, can barely remember any PHP ;) and we didn't have any MySQL so if you know anything about databases it would help me if you could tell me about them too ;)Quote:
Originally posted by NoteMe
Hehe...yeah maybe I should....so are you helping me with my HTML, CSS, PHP, MySQL class too...:D...J/K
BTW have seen a bit of people here that has been looking at our thread the last hour or so....wonder if there is many on this board that can keep up with us now....:D
Quote:
Originally posted by kedaman
never heard of ABT or ISAM trees, but B+ we went trough, that was when you need to do disk accesses because those are so slow that you can do it much faster with a flat tree ;)
Never heard of ABT trees either...just saw it in the thread at beyond3d.com that I posted earlier...
They thought us about B+ and ISAM trees in our data base course....can't remember much of it...hate databases...:D (And that sucks becuase there is so many jobs out there where you need to know a whole lot abou them)
hehe yeah i wonder if they are going to post here or are they just reading our convo :D
Quote:
Originally posted by kedaman
yeah well check out the site I gave you, great reference if you do anything with STL and it does explain what the iterators are ;)
Thanks...will look at it later this week I guess....or next week...it's easter now..:D
Hehe...I got an B in databases....can't understand why...never opened the book...:D...the teacher must have been drunk....well just ask if there is something...and it might fall an answer out of my mouth..;)Quote:
Originally posted by kedaman
hehe noo.. i had that course too, but I wasn't listening too much on that one, can barely remember any PHP ;) and we didn't have any MySQL so if you know anything about databases it would help me if you could tell me about them too ;)
[Edit] Think that that BAger is pretty good at it BTW[/Edit]
Quote:
Originally posted by kedaman
hehe yeah i wonder if they are going to post here or are they just reading our convo :D
I guess they are just reading the first 2-3 posts and then give up...wonder if BobtheBuilder or what he was called is comming back to this thread...
Quote:
Originally posted by NoteMe
You don't want an oct/quad tree to be dynamicaly....you know making and destroying nodes takes time...in a game it is better to just hold the tree all the time, and use some more memory in stead. It is cheaper then using the Bus all the time....
yeah you're right there, i thought you were talking about the other trees, but the oct/quad trees are for static polygons
still though how do you know where to access the stuff? you have a tree because it saves memoryQuote:
So if you lay down the quad three as an "array" in memory, you don't get that much cash miss as you do with a normal tree. That is the biggest sinner in a quad tree. Thats what using most of the time....
hehe ok, i'm on my fourth year already but i've been doing some other stuff instead so i've had no hurry ;) I don't think we have that much algoritms and stuff, maybe its in another course.. its not always easy to compare courses..Quote:
ABout the JAva/Algorith stuff:
We first had 6months with Basic Java
Then 6 months of ALgorithms in Java
Then we can take Advanced algorithms 6 monts the 3rd year if we want...but remember. I am not as old as you...still on my second year here....;)
hehe easter next weekend yeah, and i'm going home now already so I'm probably going to miss you ;)Quote:
Originally posted by NoteMe
Thanks...will look at it later this week I guess....or next week...it's easter now..:D
hehe.. you are so lucky we have a really picky teacher in DBs and algoritms and statistics that complains about everything and is annoying as **** ;)Quote:
Originally posted by NoteMe
Hehe...I got an B in databases....can't understand why...never opened the book...:D...the teacher must have been drunk....well just ask if there is something...and it might fall an answer out of my mouth..;)
[Edit] Think that that BAger is pretty good at it BTW[/Edit]
I hate databases too.. thats for stupid people ;) real programmers make games ;)Quote:
Originally posted by NoteMe
Never heard of ABT trees either...just saw it in the thread at beyond3d.com that I posted earlier...
They thought us about B+ and ISAM trees in our data base course....can't remember much of it...hate databases...:D (And that sucks becuase there is so many jobs out there where you need to know a whole lot abou them)
Doesn't have to be. You can alter the nodes, but you don't want to make more of them or take anyone away...Quote:
Originally posted by kedaman
yeah you're right there, i thought you were talking about the other trees, but the oct/quad trees are for static polygons
This can take adges to explain...but I try it in the short way first....Quote:
Originally posted by kedaman
still though how do you know where to access the stuff? you have a tree because it saves memory
You devide the map up in a power of 2 size first...lets say 8bits. That will say that one side of the map is 0 and the other is 255.
If you have something situated in position 128.3 to 128.8 (X pos) then XOR these (int) values
10000000
10000000
-------------
00000000
there is now no "1" bit in the result, so we get 0 for the position. if you have 9 levels in the quad tree, then say 9-0 and you know it is in the 9th level.
Once the level in the tree has been determined, the only step remainin is to take the scale coordinates and extract the row and column position of the target node. If the target node is on the bottom level (stupid example by me since I got level 9 in a 9level tree), no scaling will be necessary. For each level up the tree, the target coordinates hae to be scaled down bny 2 to reflect the smaller number of nodes on that level. This scaling can be done simply by right-shifting the integer coordinates by the number of levels the target is from the bottom level. This gives the row and column positions to plug into the array lookup for nodes on that level of thequadtree
No it's not...and they change all the time...:rolleyes:Quote:
Originally posted by kedaman
hehe ok, i'm on my fourth year already but i've been doing some other stuff instead so i've had no hurry ;) I don't think we have that much algoritms and stuff, maybe its in another course.. its not always easy to compare courses..
Quote:
Originally posted by kedaman
hehe easter next weekend yeah, and i'm going home now already so I'm probably going to miss you ;)
I am not leaving before night to thursday...I have to work 12 hours on monday, 16 on tusday, and 12 on wednsday...:(
Yeah...so where are your games...:D....ore your language...;)Quote:
Originally posted by kedaman
I hate databases too.. thats for stupid people ;) real programmers make games ;)
Have looked up what a binary tree is...:D....that ugly JAVA book...:D
It is the same as saying CAR...and then BS, AVL, BR, Two-Three trees and so on are the same as saying Volvo, MAzda, Toyota and so on...
So my representation in my picture was right...;)
Eh.. i've got stuck at the "so we get 0" is the position=the result of xor?Quote:
This can take adges to explain...but I try it in the short way first....
You devide the map up in a power of 2 size first...lets say 8bits. That will say that one side of the map is 0 and the other is 255.
If you have something situated in position 128.3 to 128.8 (X pos) then XOR these (int) values
10000000
10000000
-------------
00000000
there is now no "1" bit in the result, so we get 0 for the position. if you have 9 levels in the quad tree, then say 9-0 and you know it is in the 9th level.
Once the level in the tree has been determined, the only step remainin is to take the scale coordinates and extract the row and column position of the target node. If the target node is on the bottom level (stupid example by me since I got level 9 in a 9level tree), no scaling will be necessary. For each level up the tree, the target coordinates hae to be scaled down bny 2 to reflect the smaller number of nodes on that level. This scaling can be done simply by right-shifting the integer coordinates by the number of levels the target is from the bottom level. This gives the row and column positions to plug into the array lookup for nodes on that level of thequadtree
sorry.. this is sort of too quick and heavy for me
Yeah that too.. but I meant courses between different schoolsQuote:
No it's not...and they change all the time...
ouch.. that sounds ****ed :(Quote:
Originally posted by NoteMe
I am not leaving before night to thursday...I have to work 12 hours on monday, 16 on tusday, and 12 on wednsday...:(
hehe i knew you were going to say that ;) I've all the games behind, and programming in general, I'm getting back to it if i need to do something, which i do at times if i need to do any coursework. Other than that making a game sometime in the future perhaps, but don't have time for it now ;)Quote:
Originally posted by NoteMe
Yeah...so where are your games...:D....ore your language...;)
hehe yeah I knew it ;) what about binary search tree? what does it say about that?Quote:
Originally posted by NoteMe
Have looked up what a binary tree is...:D....that ugly JAVA book...:D
It is the same as saying CAR...and then BS, AVL, BR, Two-Three trees and so on are the same as saying Volvo, MAzda, Toyota and so on...
So my representation in my picture was right...;)
Better example. An object is at this place:Quote:
Originally posted by kedaman
Eh.. i've got stuck at the "so we get 0" is the position=the result of xor?
sorry.. this is sort of too quick and heavy for me
X1: 155
X2: 166
10011011
100100110
-------------
00111101
Now the first 1 is at place 6.
If you have 9 levels then
9-6=3
So it is situated at the 3rd level.
If you didn't get it now...then Paint Shop Pro is my next tool....:D
Yeah but at our school they change what is in a course nearly every year...so it's impossible to know what people have learned...Quote:
Originally posted by kedaman
Yeah that too.. but I meant courses between different schools
Quote:
Originally posted by kedaman
hehe i knew you were going to say that ;) I've all the games behind, and programming in general, I'm getting back to it if i need to do something, which i do at times if i need to do any coursework. Other than that making a game sometime in the future perhaps, but don't have time for it now ;)
Maybe we should start a firm togheter....lets say in 10 years or so....;)...then we can make what ever we want...just have to teach it all first...:D
It's one of the Binary trees...;)...used to search fast...;)Quote:
Originally posted by kedaman
hehe yeah I knew it ;) what about binary search tree? what does it say about that?
hehe got it now.. I still have to go trough the rest of what you wroteQuote:
Originally posted by NoteMe
Better example. An object is at this place:
X1: 155
X2: 166
10011011
100100110
-------------
00111101
Now the first 1 is at place 6.
If you have 9 levels then
9-6=3
So it is situated at the 3rd level.
If you didn't get it now...then Paint Shop Pro is my next tool....:D
Yeah but at our school they change what is in a course nearly every year...so it's impossible to know what people have learned...
yeah they change quite often but not every year here
yeah sure ;) we could start programming then when functional programming is the way ;)Quote:
Originally posted by NoteMe
Maybe we should start a firm togheter....lets say in 10 years or so....;)...then we can make what ever we want...just have to teach it all first...:D
ah.. yeah but still a binary search tree has nothing that adjusts it so that it doesn't get skewed?Quote:
Originally posted by NoteMe
It's one of the Binary trees...;)...used to search fast...;)
Hehe...yeah something like that...:D...we will have to look at that later I think...;)Quote:
Originally posted by kedaman
yeah sure ;) we could start programming then when functional programming is the way ;)
Nope...thats the weeknes og the BS tree...you can easily get a left orientated, or right orientated or a zig sag (SP?) tree...Quote:
Originally posted by kedaman
ah.. yeah but still a binary search tree has nothing that adjusts it so that it doesn't get skewed?
Quote:
Originally posted by kedaman
hehe got it now.. I still have to go trough the rest of what you wrote
yeah they change quite often but not every year here
Tell me if I should use PSP again...:D...hope not..:D
hehe.. that could be something to look forward to ;)Quote:
Originally posted by NoteMe
Hehe...yeah something like that...:D...we will have to look at that later I think...;)
yeah i thought that, so the tree is just useful if you want to build it up once and then not add new nodes.. zig zag yeah ;)Quote:
Originally posted by NoteMe
Nope...thats the weeknes og the BS tree...you can easily get a left orientated, or right orientated or a zig sag (SP?) tree...
i¨'m sorry note :( its going way over my head :( really would appreciate if you made a pic though ( i love your drawings ;))Quote:
Originally posted by NoteMe
Tell me if I should use PSP again...:D...hope not..:D
Quote:
Originally posted by kedaman
yeah i thought that, so the tree is just useful if you want to build it up once and then not add new nodes.. zig zag yeah ;)
No it can be usfull for more then that....but it will be slower and slower. Untill you redo the whole thing. It's easier to implements then lots of other trees, thats why it is used that much. But if you have the time then you should use other trees for big amounts of data....
Will do...I am working on a web page, and I stumbeled in some PHP/MySQL code, so I am waithing for an answer in the PHP section anyway...so I guess I have more then enough time to draw for you...:DQuote:
Originally posted by kedaman
i¨'m sorry note :( its going way over my head :( really would appreciate if you made a pic though ( i love your drawings ;))
Bilder til forklaringen...vent litt på forklaringen...