0

So I'm currently working on an isometric tilebased game and I'm using a topological sort to sort the order of the tiles that will be rendered. Well, the topological sort actually determines the depth of each tile and the arraylist of tiles to be rendered are sorted by a comparator comparing these depths.

The issue I'm having is basically poor performance on my topological sort. I'm not sure if there is anything I'm missing that might cause performance issues. I would be very thankful for any input that could be used to optimise the topological sort.

I'm storing some variables in fields, I'm not sure if that improves performance. I'm also using public fields for the comparisons needed.

Relevant code snippets:

private void topological(Array<IsoSprite> sprites) {
    for (int i = 0; i < sprites.size; ++i) {
        a = sprites.get(i);
        behindIndex = 0;
        for(IsoSprite sprite: sprites){
            if(sprite != a){
                if (sprite.maxX > a.minX && sprite.maxY > a.minY && sprite.minZ < a.maxZ) {
                    if (a.behind.size <= behindIndex) {
                        a.behind.add(sprite);
                        behindIndex++;
                    } else {
                        a.behind.set(behindIndex++, sprite);
                    }
                }
            }
        }
        a.visited = false;
    }
    sortDepth = 0;
    for (IsoSprite sprite : sprites) {
        visitNode(sprite);
    }
}

private void visitNode(IsoSprite sprite) {
    if (!sprite.visited) {
        sprite.visited = true;
        Iterator<IsoSprite> it = sprite.behind.iterator();
        while (it.hasNext()) {
            visitNode(it.next());
            it.remove();
        }
        sprite.isoDepth = sortDepth++;
    }
}
Deminth
  • 75
  • 7
  • What do you mean by poor performance? Takes too long? Uses too much memory? Doesn't produce the right order? – lenz Jun 13 '15 at 22:52
  • @lenz It produces the right order, but when enabling the sorting the fps drops by a lot. And it is also affected a lot when the number of tiles is increased. From what I can tell it should have a time complexity of O(n^2) so it shouldn't be too bad (though it's still not the best) – Deminth Jun 13 '15 at 22:55
  • 1
    First thing that bothers me (although unrelated to question) is why are you first using a for loop and using index only for `.get` and then the second foreach loop. Now to help with your question, you could use `Arrays.sort` on sprites and implement custom comparator, basically the if from inner loop. It would be much faster than this, which is probably even worse than O(n^2) since you're inserting the elements, which adds a lot to time complexity - array insertion is O(m) complexity, where m is current length (and from before n refers to total length). – Marko Gresak Jun 13 '15 at 23:04
  • @MarkoGrešak I see what you mean with the indexing and an enhanced for loop is probably better. The problem with creating a custom comparator for this is that you can't create a comparator for the if statement (sprite.maxX > a.minX && sprite.maxY > a.minY && sprite.minZ < a.maxZ), because it compares different variables to each other. I didn't even think about the complexity of insertion, that could be what's slowing it down, any idea of how I could avoid it? Only option I see is having an array (not arraylist) for O(1) insertion, with a predefined max length. – Deminth Jun 13 '15 at 23:11
  • @MarkoGrešak I changed it to an enhanced for loop for(IsoSprite a: sprites), but now I get the error "#iterator() cannot be used nested." from libgdx, so I'm not sure if it's possible, but it's a bit of topic – Deminth Jun 13 '15 at 23:16
  • Comparator definition is what you've just said, compare *two* elements (variables). Take a look at [docs](https://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html) or [this answer](http://stackoverflow.com/a/5245122/1276128). The ArrayList is implemented with an array so you won't improve anything. You could use a LinkedList for O(1) insertion. It's probably better since you're not doing any indexing/searching, which is O(n) for LinkedList. For more information, take a look at [Big-O Cheat Sheet](http://bigocheatsheet.com/) (or any CS algorithms 101 class). – Marko Gresak Jun 13 '15 at 23:17
  • @MarkoGrešak Of course, totally forgot about LinkedList! I'll definitely do that and try to put together a comparator that doesn't violates its general contract, thank you – Deminth Jun 13 '15 at 23:20
  • 1
    @MarkoGrešak This code inserts only to the end of the list, which is ammortized O(1) for ArrayList, so it shouldn't affect complexity. – Kolmar Jun 13 '15 at 23:26
  • I tried to implement a compareTo method in the sprite: `public int compareTo(IsoSprite b) { if (b.maxX > minX && b.maxY > minY && b.minZ < maxZ){ return -1; }else if(b.maxX < minX && b.maxY < minY && b.minZ > maxZ){ return 1; } return 0; }` But all I get is the error "Comparison method violates its general contract!", damn it would be so nice. – Deminth Jun 13 '15 at 23:29
  • @Kolmar I mistook set for insert, I thought OP was inserting at `behindIndex`, not setting. – Marko Gresak Jun 13 '15 at 23:29
  • 1
    Actually, I think you may have O(n^3) in `visitNode`: basically for each node, for each element in `behind`, you remove the first element, and that removal *is* O(n), unlike adding to the end. If you want to clear `behind`, call behind.clear() after loop or, yes, use LinkedList, or start removing from the last element (iterate in reverse). And if you are removing all elements from `behind` every time, then the part `if (a.behind.size <= behindIndex) {` in `topological` is meaningless: behind is always empty, so it will always be the "add" case, never "set". – Kolmar Jun 13 '15 at 23:38
  • @Kolmar I would agree with you, in short there is a lot in this code that could've been done simpler or even skipped altogether. I can't image a scenario for topological sort to be O(n^2), let alone O(n^3). – Marko Gresak Jun 13 '15 at 23:57
  • @Kolmar I implemented the changes you suggested and it improved performance a bit, thank you – Deminth Jun 14 '15 at 00:02
  • @MarkoGrešak I can't imagine a scenario when this topological sort isn't at least O(n^2), care to enlighten me? :) – Deminth Jun 14 '15 at 00:03
  • 1
    The O(n^2) is here because for each sprite we want to find the sprites it overlaps with (or we can simply just try every other sprite (i.e. treat this as a full graph), but then it's O(n^2) anyway). This might be sped up by using spatial indexing, look here: http://stackoverflow.com/questions/7435645/java-commercial-friendly-r-tree-implementation Maybe you'll be able to quickly plug in some R-tree library in your code, to see if it becomes faster. – Kolmar Jun 14 '15 at 00:21
  • @Kolmar I see, I will definitely look into it – Deminth Jun 14 '15 at 00:24
  • By the way, is it posible to simply sort *everything* by Z, ignoring X and Y? I don't understand what those minZ and maxZ are in your code. I mean, if you just draw everything in order of global Z, it should work as well as your current implementation, and then it'll be O(n log n). – Kolmar Jun 14 '15 at 00:27
  • @Kolmar it would probably work if everything was locked to the isometric grid, although entities for example, move freely across tiles and can jump freely as well. At least that's what I'm thinking – Deminth Jun 14 '15 at 00:30
  • Ah, sorry, didn't notice about being isometric. This idea is similar to what Marco suggested in his first comment. – Kolmar Jun 14 '15 at 00:45

0 Answers0