第一次用C#写游戏。在C#上写算法果然是一个挑战，时间复杂度太大的话造成的后果比C++明显好多，于是总是尽量把东西做成O(n)或者O(nlogn)。这次就在上面实现了一个寻路算法。
这个寻路算法是这样的：在16×16的方格上有一些终点，东西在格子上只能上下左右行动。每一个格子需要记录到其中一个终点的最近的路的所有方向（就像三层循环的寻路算法一样，最后给出矩阵的那个）。
于是我用了宽度优先搜索和一个队列来搞定这个事情。一开始算法写错变成O(n2)结果每一次处理都要1秒钟。后来改正了之后结果瞬间给出。
算法如下：
1：把所有的GOAL加入队列并标记。
2：记录当前队列的元素数量。
3：弹出一个元素，并将所有未标记的邻居添加一个指向自己的方向，将这些邻居不重复地放入队列（可以再用一个不同的标记来检查），标记这个元素（非邻居）。
4：如果弹出的元素数量没有第2步记录的那么多，则转3。
5：如果队列数量非空，转2。
6：结束。
执行这个算法，可以得到每一层分别是：
这个算法可以在添加障碍物的时候重新计算，仅需障碍物在一开始就被标记就行了。
C#果然是用来做大作业的不二选择啊，开发真是方便，而且不用顾及内存问题（因为
一定占用非常多）。
posted on 2008-04-30 05:29
陈梓瀚(vczh) 阅读(4406)
评论(5) 编辑 收藏 引用 所属分类:
C++