Optimising topological sort

514 views Asked by At

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++;
    }
}
0

There are 0 answers