十字链表的AOI算法

看了云风写的AOI算法文章,自己也照着写了一下,感觉不容易理解,里面提到了十字链表的算法,在某同学提示下写了个实现.

算法的大概思想如下.每个场景维护两个链表,分别为X轴和Y轴的坐标按序排列好的链表,也就是比如在X轴链表上,越在前的对象,X坐标越小,Y轴链表同理.这样,每次需要更新状态的时候,只需要在这个链表上向前或者向后遍历结点就知道该通知谁了.

这里假设有三个API:Add(向场景中添加一个对象),Leave(某对象离开场景),Move(某对象在场景中移动).

来一个一个看.

Add:根据新增对象的X,Y坐标,依次遍历X,Y轴坐标链表,这里有两个目的,一个是获得这个新增对象的坐标在X,Y轴坐标的位置,另一方面获得该通知哪些结点.通知的范围,每个对象可以自己定制自己的通知范围.但是为了简单起见,在这里我们假设每个结点X,Y坐标相差1,而通知的范围是2.比如原有的X轴坐标为:
a->b->c->d->e->f->g->h
假设新增一个对象z,它最终所在的位置是c和d之间,根据前面的假设,它只需要通知b,c,e,f四个结点就好了.所以,新增一个结点的时候,并不需要遍历完链表的.
但是这里还需要注意的是,一个结点,必须X,Y坐标同时都在通知范围内才可以进入通知集合.

Leave:在添加了对象之后,对象身上挂了两个结点,分别存放在X,Y轴坐标链表上的位置,那么在这个对象要离开场景时,也只需要向前向后探索一定的范围,就可以得到需要通知该对象要离开的集合了.

Move:移动操作比较麻烦,但是也可以比较漂亮的解决.在更新位置之前,同样根据前面的算法得到要通知的结点集合,称为old_set;更新位置之后,再获取另一个通知集合,称为new_set;然后,old_set和new_set的交集,称为move_set,在此集合中的结点,在移动前后都在通知范围,因此要向这个集合的结点发送该对象移动的消息;而old_set-move_set的集合,在移动之后已经离开了视野,因此要向它们发送该对象离开的消息;最后,new_set-move_set是移动之后才看见该结点的结点集合,这个集合的结点,要发送该结点进入场景的消息.

我把这个算法的实现放在了.


原文