随笔-341  评论-2670  文章-0  trackbacks-0

    第一次用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) 阅读(4429) 评论(5)  编辑 收藏 引用 所属分类: C++

评论:
# re: 寻路算法:模仿Tower Defense Flash做了一个小游戏 2008-04-30 22:30 | 饭中淹
支持先,我也在用c#做造塔游戏~~
  回复  更多评论
  
# re: 寻路算法:模仿Tower Defense Flash做了一个小游戏 2008-05-02 19:36 | GouGou
这游戏干吗的???  回复  更多评论
  
# re: 寻路算法:模仿Tower Defense Flash做了一个小游戏 2009-03-10 22:00 | lyd963@live.cn
你的GOAL位置上下连在一起,如果是两个GOAL分别在两行的头尾,用你的程序跑出的结果会怎么样呢?

还有个小疑问,从步骤3执行的结果看来,中间两行指向的是到GOAL的最短路径,没有从第2行指向第3 行的情况,这个结果是因为在执行步骤3之前,就根据GOAL的分布划分了区域,所以头两行指向一个GOAL,3、4行指向另一个GOAL?  回复  更多评论
  
# re: 寻路算法:模仿Tower Defense Flash做了一个小游戏 2009-03-11 01:05 | 陈梓瀚(vczh)
算法只会找最近的那些goal。  回复  更多评论
  
# re: 寻路算法:模仿Tower Defense Flash做了一个小游戏 2009-03-12 16:49 | lyd963@live.cn
thks  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理