User talk:Rednaxela/kD-Tree

So this mean I can use it int close-sourced robot? » Nat | Talk » 13:24, 25 August 2009 (UTC)

Yep, so long as you don't misrepresent it's origin (i.e. claim you wrote the kd-tree in use) :) --Rednaxela 13:29, 25 August 2009 (UTC)

You used to say that it will be licensed under RWPCL and CC-BY, but I'm more happy with this though, for that I can release the code under more tricky way than usual in-jar method =) » Nat | Talk » 14:25, 25 August 2009 (UTC)

I decided I wanted to avoid as much complication as possible, and I found the zlib licence. Since I don't mind how people use it so long as they don't make false claims to have written it, and it doesn't conflict with the RWPCL (i.e. can be used in RWPCL bots), it seemed like a good match. I removed one clause that I deemed unnecessary. It seems reasonable to me :) --Rednaxela 14:46, 25 August 2009 (UTC)

I just tried this tree, and I'm getting problems where every now and again an Entry will have a null value in it. I've got workaround code for it, but I know it shouldn't be doing that, and I'm not sure why it is. Also, DrussGT is still skipping a LOT of turns with this tree, so I'll have to find a dimension or 3 to cull... I could even run 2 trees with 8 dimensions in less time than my 1 tree with 11. Oh yes, I changed the 2 distance functions to be Manhattan distance, but that shouldn't affect things too much. --Skilgannon 18:21, 26 August 2009 (UTC)

Huh... that seems odd. I don't see why null entries could ever happen, I'll look into it when I get home. As far as DrussGT skipping a lot of turns still, I assume you don't mean any turns than normal do you? And yeah, even a few dimensions will make a huge difference with any kd-tree. --Rednaxela 18:33, 26 August 2009 (UTC)

Yeah, I know it passed all the benchmarks etc. so I'm not sure what's going on. Maybe look in DrussGT 1.3.10wilo for the version I'm using if you want to test it. Lines 614 to 618 of DrussGunDC.java are where my workaround is (basically just removing all Entries with null values from the cluster). If I take that out it starts throwing errors every few rounds. (Note: just to prevent any confusion, due to me adding the first workaround - just skipping null values in the loop - it now throws the errors down on line 663 when it sorts the Indices instead of in the loop when trying to access the data inside the null value). Thanks for any light you can shed on this =) --Skilgannon 18:55, 26 August 2009 (UTC)

Aha! I haven't tested it yet, but this should fix the nulls. :) --Rednaxela 19:23, 26 August 2009 (UTC)

Oh, and also, this bug may do more than cause nulls: It may cause duplicate entries in some cases I suspect, so it may affect the results of jk.mega.DrussGT 1.3.10wilo. I don't think it wouldn't affect the results of RougeDC willow though because I'm pretty sure that bug was introduced after. --Rednaxela 19:29, 26 August 2009 (UTC)

I believe I have found the following problem, Arrays.copyOf is only supported since Java 6.0, so your code can't be compiled/run under earlier versions of Java. --Positive 22:49, 27 August 2009 (UTC)

Haha, Fnl also noticed that earlier today. Fixed and tested to have no/negligable affect on performance :) --Rednaxela 00:10, 28 August 2009 (UTC)

Hey Rednaxela, good job! One thing that you might improve the speed on (if I understand your tree correctly) is the sqrPointRegionDist function. You don't need to recalculate all distances between bounds and the point, only between the *changed* bound since last check. If that makes sense. :) Also, I think it would be nice to have another version of the tree which doesn't apply weighing while searching. In any case, it's a very nice piece of code, and I'm going to try to use it in Portia (thanks to your license!). :) --Positive 21:45, 27 August 2009 (UTC)

Hmm... you're right, that is an optimization that could be done, that is, if the overhead of caching it doesn't outweigh the benefit. I think in order to implement that I'd need to either store temporary values in the nodes, or maintain a third stack that remembers the distance of it's bounds. I'll give it a try and keep that change if it's worth it, haha. As far as a version that doesn't apply weighting, I've considered that however decided it was simpler to maintain a single version. If you want to remove the weighting capabilities, all it takes is 1) Removing the 'weights' variables where they are declared, 2) Removing the reference to them in the distance functions, and 3) Remove the couple statements that set it. Though, I suppose that if changes to the tree cease to happen for a long time I'll post the version with weighting removed as well, I just don't want to be worrying about them getting out of sync while it's in (semi-)active development. Anyways, I'm glad it's liked :) --Rednaxela 00:10, 28 August 2009 (UTC)

Okay, that makes sense. I have some other feature requests: A size() function to keep track of how many entries there are in the tree, and it'd be cool if there was something to make sure the size stays below a certain point. A possible problem might be the line with tree.weights = weights;, because it doesn't reset the weights afterwards. Also, I'd selfishly like the addPoint functions and such to be nonstatic and without the KdTree<T> tree parameter (but I suppose that is a matter of taste). :P --Positive 01:03, 28 August 2009 (UTC)

Alright, I gave that optimization of calculating the node distance as-needed from the splits a try. The result is that: 1) If replace the existing calculating of the distance to the tight boundary, the performance is worse, and 2) If I just use it to shortcut past the full distance to tight boundary calculation, the performance is about the same. This indicates to me that 1) Calculating the exact tight-boundary disance for nodes eliminates a rather significant number of node visits, and 2) The overhead of tracking the data for split-based node distance is large enough that it's not worth it to use it as a shortcut. --Rednaxela 06:23, 1 September 2009 (UTC)

Keeping the weights across calls I considered desired, but it was a bad API for it. It's now split into a setWeights() call. Haha, I don't know what I was thinking when I made the addPoint and nearestNeighbours functions static, I was in a strange mindset when I first wrote this beast. They're now non-static and tested to have no impact on performance. I'm not sure what you mean by "make sure size stays below a certain point". Do you mean removing old points? --Rednaxela 03:39, 28 August 2009 (UTC)

Great. :) Yes, that's exactly what I meant. It seems usefull and safe to have some kind of deletePoint function and perhaps a built-in linked list system to remove old entries, so that the data stays up to date & won't eventually fill up the memory. --Positive 03:48, 28 August 2009 (UTC)

Well... support for an optional limit on size is now supported. Deleting arbitrary points however, is not supported, because that would conflict with the size limit since it would be far too painfully slow to remove that point from the linked list that tracks the the order that points were added in. Also, to make sure this doesn't impact speed normally, that list is never even created if no limit was specified. Anyways, the size of the code is getting closer to 500 lines than I'd like it to, so I think this is enough non-optimization features for any sane usage of it. --Rednaxela 04:45, 28 August 2009 (UTC)

I don't know if this is standard or not, but it seems strange that the constructors isn't the very first method in the class. And the method/sub-class ordering is more like... DrussGT's =) They are now ordering by the time you added the code and where, aren't they? I know it isn't going to improve the execution speed, but... » Nat | Talk » 14:40, 28 August 2009 (UTC)

Nah, not ordered by the time added at all. At one point I had the functions for 'bounds' grouped beside the variables, but they kind of drifted apart. There wasn't any real reason for the ordering except that nearby things often had some relevance to eachother. Reformatted that a bit now as to be saner and maintain that relevance-ordering :) --Rednaxela 14:56, 28 August 2009 (UTC)

I've been testing with the pre-limit version of your tree in Portia, and it seems to be working. :) Now with your new version, I do get an error at line double[] location = this.locationStack.pop();: (The method pop() is undefined for the type LinkedList<double[]>). --Positive 15:53, 28 August 2009 (UTC)

Ugh... Any reason why you're on ancient Java 5? Anyway, that method in LinkedList only exists in 6 not 5. Making it Java 5 compatible again... --Rednaxela 16:11, 28 August 2009 (UTC)

Haha, actually I'm on Java 6. I compile everything using the Java 5 library though, so I know for sure I don't make code that's not Java 5 compatible. :) --Positive 16:14, 28 August 2009 (UTC)

I didn't exactly had time to look at this, but just out of curiosity, does this tree return the scans sorted by distance? By the way, congratulations on your optimization work.--Navajo 00:43, 1 September 2009 (UTC)

It returns the entries in max-heap array ordering, since that is the most efficent way to construct the list of nearest neighbours. Maintaining a list of "lowest n values" doesn't actually require the list to be fully ordered, it only requires enough ordering that it's easy to throw out the largest value when over the size limit, making a max-heap the perfect structure for the task. It would be fairly simple and fast to convert this to squential order for final output, but I saw no reason to bother with it since I've never seen a DC gun/movement care about the order of the outputs, only the distances associated with them. --Rednaxela 01:25, 1 September 2009 (UTC)

My DC Gun does care about the order of the output. It computes pif angles discarding the ones that end outside the battlefield, so I need to know that I end up with the closest entries possible. --ABC 10:15, 1 September 2009 (UTC)

Err... I'm not sure I understand... Any sane DC-PIF gun would be discarding result that end outside the battlefield like you say, but it's not as if the order of output affects which ones end up inside/outside the battlefield. The outputted values are ensured the closest entries possible ones, just not in sequential order. I don't see how any gun could sanely care about the output order, but if so, which order would you prefer, ascending or descending? --Rednaxela 12:39, 1 September 2009 (UTC)

I'm speculating, but maybe he builds a cluster of size M and then tries to keep the best N<M that stay inside the field. But I think that a sorted cluster should be optional as it may impact the performance for most of the tree users with no gain. --zyx 13:24, 1 September 2009 (UTC)

Yes, that's exactly what I do. If it's too much trouble I can always sort them myself. --ABC 14:09, 1 September 2009 (UTC)

Nah, it's not too much trouble, and as I explain to Nat below, it's quicker for me to get sorted output from the heap than it is for you to sort the data after. I already have this implemented on my computer at home, all I have to do is test how it impacts performance, and if it's measurable, make it optional. --Rednaxela 14:52, 1 September 2009 (UTC)

Hey ABC, unlike what you said... Simonton's tree may not always output in descending order always! Reading the code for Simonton's code indicates that it uses a PriorityQueue, and the order it outputs is the same as the iterator of PriorityQueue. If you read the java docs, it very clearly states "The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).", therefore if Simonton's tree is currently returning in descending order, then it just happens that your JVM does that. This means that the behaviour of versions of Shadow using Simonton's tree are VM-dependant. But after I make the sorting supported in my tree when I get home, Shadow using my new tree will be able to be sure it's performance is not dependant on the JVM in question. --Rednaxela 15:21, 1 September 2009 (UTC)

Thanks for that info! You are a true Java Guru. At the time I just blindly plugged Simonton's tree instead of my brute force method, noticed the entries were "backwards" and adjusted my code accordingly... --ABC 15:53, 1 September 2009 (UTC)

I don't understand, how the order affect the result of PIF algorithm? On the other hand, returning the sorted data would take O(n log n) time more due the heap, and that definitely effect the bot that doesn't care about the ordering. If we sort them ourselves, it would still take O(n log n). I see no point to add the ordering to the tree, unless, of course, it won't effect the speed. » Nat | Talk » 14:23, 1 September 2009 (UTC)

I want to find the 10 scans closest to the current one that end inside the battlefield. I ask the tree for the 20 closest scans, and then calculate the path for each of them, starting from the closest one, until I get 10 valid ones. --ABC 14:39, 1 September 2009 (UTC)

(edit conflict, crossing out redundant things) It was like Zyx said. The numbers are made up but it's like this: Shadow gets the 50 closest entries from the kD-Tree, it then runs PIF on each entry starting with the one with the last distance, and it stops processing once it has the PIF results of 10 that didn't run into walls. Again, 50 and 10 are made up numbers for sake of example. Also Nat, you're very wrong about the speed there. Firstly, the time taken by reordering the n final results, is MUCH quicker than the nearest-n-neighbours search itself, because O(n log n) only tells you how the speed is multiplied by changing the number of values sorted, it doesn't tell you the base speed, which happens to be far quicker than the base speed of the nearest-n-neighbours algorithm. Secondly, I can make the output results sorted in notably LESS than O(n log n) time. Converting max-heap ordering to sequential ordering, only requires the second part of a heapsort, rather than a full run of a sorting algorithm. --Rednaxela 14:52, 1 September 2009 (UTC)

I just checked and your made up numbers (50/10) are exactly what I currently use in Shadow's melee gun. :) --ABC 15:53, 1 September 2009 (UTC)

Is the tree really fast enough to let you query 50 neighbours for all opponents? » Nat | Talk » 16:01, 1 September 2009 (UTC)

Oh wow, my guessing skills are quite good it seems, haha. As far as speed of that goes Nat, I'm pretty sure that in most DC-PIF guns, the PIF takes considerably longer than the DC. --Rednaxela 16:08, 1 September 2009 (UTC)

Merge sort, which is default for Arrays.sort() is twice as fast as the heap sort according to my book on algorithms, which has the benchmarking time printed. And the second part of heap sort is still O(n log n), you still need to do down-heapify for n times. Unless there are faster ways to do it. » Nat | Talk » 15:13, 1 September 2009 (UTC)

True, the second part of heap sort still scales at a rate of O(n log n) but should be considerably faster than a full heapsort. I may benchmark the difference later, but I'm extremely doubtful that Arrays.sort() could be faster for data that is already in heap ordering. Plus Nat, one very important consideration that you leave out, is that in order to use Arrays.sort(), unless you're sorting a simple array of numbers, your input values need to be encapsulated in objects which implement Comparable, and comparisons of Comparable are well over 5x slower than direct numerical comparison due to function call overhead. Avoiding overhead such as that is part of why my tree is just so damn fast ;) --Rednaxela 15:31, 1 September 2009 (UTC)

Oh I see. Completely forget function overhead. Thanks. » Nat | Talk » 15:59, 1 September 2009 (UTC)

Warning! Rounding Errors!

Argh! It seems rounding errors are evil! Evil evil evil! I was toying with my tree in a very lightly segmented gun where exact-same-locations will occur frequently and it did that stupid rampent/infinite branching again. The cause? It turns out to be rounding, indicated by this excerpt from some debugging messages.

...
Split Dimension: 1, Split Value: 1.0, Range: 0.9999999999999999 to 1.0, Width: -1.1102230246251565E-16
Split Dimension: 1, Split Value: 1.0, Range: 0.9999999999999999 to 1.0, Width: -1.1102230246251565E-16
Split Dimension: 1, Split Value: 1.0, Range: 0.9999999999999999 to 1.0, Width: -1.1102230246251565E-16
Split Dimension: 1, Split Value: 1.0, Range: 0.9999999999999999 to 1.0, Width: -1.1102230246251565E-16
Split Dimension: 1, Split Value: 1.0, Range: 0.9999999999999999 to 1.0, Width: -1.1102230246251565E-16
Split Dimension: 1, Split Value: 1.0, Range: 0.9999999999999999 to 1.0, Width: -1.1102230246251565E-16
...

When the only values in the dimension were 1.0, and just BARELY below it, the splitValue would be set to the average of those two values. Due to rounding errors, the average happened to be the same as the higher value... causing the tree to lump all values into the left child node and try branching again, and again, and again :(

So as a warning to those currently using the tree, this obscure sitaution could cause the tree to lock up... I'll release a fix soon --Rednaxela 00:54, 30 August 2009 (UTC)

Simonton's fix to this was to only allow his tree a certain recursive depth (he used 500), after which it would start throwing away values. This way it was also (sort of) possible to have a tree with 'rolling averages' by setting the max recursive depth very low. However, it's more of a bandaid then a fix for the root of the actual problem. --Skilgannon 13:03, 30 August 2009 (UTC)

No, he didn't use 500. We use 500 ourselves. » Nat | Talk » 13:29, 30 August 2009 (UTC)

For this particular issue, that would indeed be a very very poor bandaid, and anyways I have a proper fix in place now. As for having a limit on tree size, I very strongly prefer the limit on the number of entries I have implemented. While it won't put a hard limit on tree depth or nodes it will generally to keep it within reasonable bounds and will always toss out old data in the exact order it was entered in. --Rednaxela 16:07, 30 August 2009 (UTC)

Well, this sucks, I thought I could fix it simply by making a > into a >= because I thought it always would round one way.... turns out it doesn't... it rounds whatever way it's in the mood for it seems.. bah. Oh and by the way ABC, curse Shadow for hitting such almost-1.0 velocitities as to cause rounding issues :P --Rednaxela 02:22, 30 August 2009 (UTC)

I'm sure there are lots of ways to deal with this, but just a comment on how my insert method handles a similar situation. Values less than the split go to the left, values greater go to the right, and values equal to the split go to alternating sides. One other implication is that when removing a node, you have to check both sides when the value is equal to the split value, but that's easy enough. --Voidious 02:33, 30 August 2009 (UTC)

I guess if you had 19 0.9999's and one 1.0 and it used 1.0 as the split, you'd still have this problem unless the first alternating side also alternated. So I suppose a different special case would probably work a lot better. Another thing that sucks about this, at least if you use the tree the way I do... Rounding every number to, say, 10 digits seems pretty reasonable, but I wouldn't want to do that either, because I count on the fact that the neighbors returned from the tree are the same exact objects I inserted. :-/ --Voidious 02:43, 30 August 2009 (UTC)

(edit conflict) I saw that alternating approach, but I really don't like that approach for several reasons. It increases the balance of the tree very slightly, but it comes at the cost of making each node wider than they need to be. Not only deletes have to search more nodes Voidious, but seraches as well. For example, presume a dimension only has values of 0.0, 0.5, and 1.0 and the first split in the tree is at 0.5. Then the full search has to be repeated completely on both sides, and thus could have a huge impact if such a split happens to be the first split in the whole tree. Anyways, I now have a fix, the solution is: If split value is equal to the maximum node value (will only occur if they're so close that no Double value between could exist), then it sets the split value to the minimum node value instead which guarantees some values will be put in each node. Extensive testing is showing this is working quite nicely :) --Rednaxela 02:48, 30 August 2009 (UTC)

Ah, cool. I agree it can unbalance the tree, but I don't think it makes searches any slower (otherwise). Mine definitely doesn't account for the equal-to-split edge case in its "findLeaf" - I recall thinking it would need to account for that, then realizing it didn't.

When coming back up the tree, you test if the other side of the tree could have a node with a distance to the search point that is lower than some threshold. Since the value could be infinitely close to the split value, you have to just assume it is the split value, right? So while you may take a wrong turn while descending the tree if you hit values equal to the split value, you'll check the other side on the way back up, which you're just as likely to have had to do anyway. In your example, you'd need to search the other side anyway - know what I mean? It's been a while since I wrote my tree, maybe I'm misunderstanding something... =) But I'm pretty sure it's just as accurate and just as fast for searches.

Deletes need to find an actual value that's already in the tree, though, which is a different scenario. (And I don't particularly care how fast deletes are.) --Voidious 03:11, 30 August 2009 (UTC)

Which reminds me, I actually wrote this case for another scenario, which might be a problem in your current solution, too: if all the nodes have the same value for the split dimension. --Voidious 03:19, 30 August 2009 (UTC)

I presume you mean all entries, not all nodes. In that case yes, I already deal with that case. I always set the split dimension to the widest dimension, and whenever "widest" is still 0 width, then it will simply double the bucket size for that particular node. My logic is that the scenario you describe could only happen with "split on widest dimension" when that all entries are in exactly the same spot, in which case there could never ever be any performance gain by putting them in seperate nodes. On a related note, one possible optimization I could also do with this, would be giving such nodes a special marking and avoiding redundent distance calculations in them. I haven't bothered with that yet though since I doubt it would occur often in practice with a well-segmented gun. --Rednaxela 04:51, 30 August 2009 (UTC)

Actually Voidious, in my tree checking the other side anyway wouldn't happen. I keep track of an extra-tight bounding box for each node and compare to that, and due to how my splitting doesn't alternate, the tight bounding box will never overlap on the split value actually. So.. you're right about some trees, but not my one :) --Rednaxela 04:51, 30 August 2009 (UTC)

Some major changes

Man, this tree keeps taking away from time to finish my melee gun, but anyways: I've done a major update now which gives the tree a bit nicer and more flexible of an API. In particular, you now construct it with things such as new KdTree.SqrElucid<T>(dimensions, sizeLimit) or new KdTree.WeightedManhattan<T>(dimensions, sizeLimit) instead of new KdTree<T>(dimensions, sizeLimit) and modifying the distance function in your copy of the code (I'm looking at you Skilgannon :)). This also makes it easy to use the unweighted version which is faster by 5-10%. One interesting note I found, is that while Manhattan distance is less complicated to calculate, it makes it harder for the tree to eliminate branches and thus is twice as slow (Looking at you again Skilgannon, considering your recent concerns with DrussGT's speed). What do people think? I'm also considering making a stripped down 'lite' version with no weighting, only sqrElucid distance, some of the more agressive and less significant optimizations removed, no size limiting, and be nearly as fast. --Rednaxela 05:52, 2 September 2009 (UTC)

Hmm, so using Manhattan approximately doubles the number of branches that must be recursed? Is this dimension-dependent, ie., would the fact that I'm using 11 dimensions make this a factor of more than 2? I'd gladly switch to using Euclidean distance to get this speed increase, but from what I've found, my gun scores significantly better using Manhattan distance. The difference between the two is about 0.5 worth of TCRM score. I'm guessing that how my dimensions are defined somehow favors the use of Manhattan over Euclidean, but I don't currently have the time to tweak my segments into a form that works well for Euclidean instead =) Another point, for bots that only use one weighting scheme throughout the match, isn't it quicker to multiply the point by the weighting before storing it, and then afterwards treat the dimensions as unweighted? This is what I've been doing in DrussGT since way back when... it also means that I can apply non-linear weightings without any performance hit at runtime. --Skilgannon 08:50, 2 September 2009 (UTC)

I didn't run an exact count of the number of branches that must be recursed, but since the time taken is doubled, I feel pretty sure the number of branches recursed is at least doubled. It being possibly dimension-dependant might indeed be the case but I don't think 11 dimensions would make it more than my test showed, since my test was with the 13-dimension data recorded from Diamond. About weighting: yes, of course it's quicker to multiply the point by weighting it before storing it. The weighted versions of the tree are only intended for bots which do dynamic weighting, like Diamond does (melee weighting vs 1v1 weighting). Static weighting is considered to be something that bots are responsible for doing when they create their dimensions in the first place. --Rednaxela 12:42, 2 September 2009 (UTC)

I haven't tested it yet, but I would like to say, fantastic job! This definitely gives "everyone what he/she wants". I only wonder, don't abstract classes make the tree that much slower (because of the overhead in having to decide which distance() function to use for example)? I'm not a java expert, so it might be that that is optimized at runtime. --Positive 14:29, 2 September 2009 (UTC)

Thanks! I was unsure about that myself at first, but I tried it, gave a it a good performance test, and it performed exactly the same it seemed, at least in Java 6 (I don't know for certain but old enough VMs I bet wouldn't perform equally with them). In fact, the slight tweak of having the distance functions read 'weights' from the class instead of passing it in as an argument seemed to cause this revision to have a very slight improvement in performance. --Rednaxela 14:44, 2 September 2009 (UTC)