Renderer/Сортировка оптимизация

Question

Хорошо вот проблема:

1. у меня есть список объектов, которые действительно должны быть обновлены времени с момента последнего кадра
2. список должны быть отсортированы по у koordinate объекта, прежде чем они получают рисовать

ток я сделать это с collection.sort и простой comperator:

figureComperator = new Comparator<Actor>() { 
    @Override 
    public int compare(Actor o1, Actor o2) { 
     return (int) o2.getY() - (int) o1.getY(); 
    } 
}; 

рендер выглядит так:

@Override 
public void render(float delta) { 
    // clearing 
    Gdx.gl.glClearColor(0, 0, 0, 1f); 
    Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT); 
    // act the character act in front 
    this.character.myAct(delta); 
    updateGameCam(); 
    if (this.status == GameStatus.GAME) { 
     // just monster act now 
     this.figureStage.act(); 
    } 
    this.figureStage.getActors().sort(figureComperator); // sort figures 
    // render background 
    this.map.drawBackground(); // draw background 
    // draw figures inclusive character 
    this.figureStage.draw(); //draw all figures 
    this.map.drawForeground(); // foreground 

    // render game HUD and act gameHud 
    this.gameHud.act(delta); 
    this.gameHud.draw(); 
} 

Так я ищу лучший способ улучшить скорость этого.

Я натолкнулся на идею позволить актерам сортировать себя внутри списка (figureStage), пока я их обновляю. Но поскольку я делаю обновление forall с this.figureStage.act();, я не мог сделать это так просто.

Итак, мой вопрос в том, есть ли какое-либо решение, не имея сложности алгоритма сортировки, чтобы всегда иметь эти объекты, отсортированные по его положению?

Answer 1

С помощью @Joni я начал использовать альтернативный алгоритм для сортировки Актеров. Это увеличивает скорость сортировки примерно на 2-3 раза, просто используя insertionsort.

public void sortList(Array<Actor> array) { 
//  double starttime = System.nanoTime(); 
     for (int i = 1; i < array.size; i++) { 
      Actor temp = array.get(i); 
      int j = i - 1; 

      while (j >= 0 && array.get(j).getY() < temp.getY()) { 
       array.set(j + 1, array.get(j)); 
       j--; 
      } 
      array.set(j + 1, temp); 
     } 
//  System.out.println("Time taken: " + (System.nanoTime() - starttime)); 
    } 

Среднее количество экземпляров Collection.sort было ~ 8700. Вставка составляет около 3300!

Answer 2

Вы можете хранить объекты в массиве (или списке) элементов HEIGHT в размере, где HEIGHT - это вертикальный размер вашего мира. Каждый элемент в этом списке представляет собой список объектов с соответствующей координатой Y. Когда объект перемещается вверх или вниз, он должен быть удален из одного списка и добавлен к другому в соответствии с его новой координатой Y. Таким образом вы можете просто перебрать массив и нарисовать все объекты во внутренних списках. Если координата Y не является целым числом, вы можете использовать ее целую часть. Надеюсь, это поможет.