Gus*_*son 6 java sorting performance
我正在制作一个带有滚动视图的2D游戏(想想Red Alert或Zelda),但我正在绘制图纸.
基本上,地图上绘制了两种类型的对象.有些人有固定的位置(如树木和建筑物),有些则有移动(玩家,敌人,飞行箭头).
要使事物以正确的方式出现在彼此前面,需要按特定顺序绘制(首先是远处的物体并朝向"相机"工作).
现在我每次游戏更新(每秒100次)时都会对所有对象(两种)的列表进行排序,这感觉就像浪费了大量的CPU时间.对象的顺序很少变化,当它们发生时,它们通常只在列表中向上或向下移动一个位置.
另一个问题是只需要考虑实际在屏幕上的对象.由于地图可能变得非常大,有1000个物体,我不想每秒100次对它们进行排序.
你怎么建议我解决这个问题？
冒泡排序的最佳情况是元素已经排序.在这种情况下,你会得到O(n)比较.根据维基百科:
在计算机图形学中,它能够在几乎排序的数组中检测非常小的错误(如仅交换两个元素),并以线性复杂度(2n)修复它.
但由于链接文章中提到的各种原因,它被认为是一种"坏"算法.您可能想要分析它与插入排序(对于排序列表也是O(n))之间的差异,以查看哪个在实践中更快.
另一种选择是使用一种数据结构,该数据结构将已排序的项目保留在其中,并在项目的位置发生变化时得到通知.如果与重新绘制的对象相比,对象不会移动很多,那么这将节省大量的处理时间,因为您只需要对位置已更改的元素进行重新排序,您可以避免重新排序直到至少有一个元素移动.