十字链表的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是移动之后才看见该结点的结点集合,这个集合的结点,要发送该结点进入场景的消息.

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

10 Comments

  1. 那谁 说:

    代码中做了简化的处理,默认所有对象的视野是一样的,实际上要处理你说的情况并不难.算法也是类似的.

    [回复]

  2. 那谁 说:

    @sniperHW
    我又仔细想了下,这个问题貌似不那么简单,待我想想后面再给个答复.

    [回复]

  3. sniperHW 说:

    这也是我做AOI时候想到的,不过我没用十字链法。

    [回复]

  4. 匿名 说:

    为什么要维护两个链表?把x,y值计算出一个距离dist,维护一个dist的链表,效果也是一样的

    [回复]

  5. 大厨师 说:

    插入到cd之间,通知的应该是b,c,d,e这四个节点吧

    [回复]

  6. 匿名 说:

    这个让人想起了碰撞检测里的 扫掠排序算法。

    [回复]

  7. sex 说:

    你的程序有好几个BUG

    [回复]

  8. sex 说:

    插入位置的 获取范围的 好几处都有问题 不过思路还是行,使用的时候 大伙需要注意

    [回复]

  9. ShionRyuu 说:

    十字链表的AOI看起来和划分九宫格的差不多,九宫格获取需要广播的玩家时候计算还比较少。

    [回复]

  10. lazy 说:

    搞定了吗?

    [回复]

Leave a Reply