寻路机器人LUA实现

labaz

此帖说明书剑自动化进程比北侠要早得多，关键那里有pk你自动挂也连不起来。但是，北侠这里几乎没pk，反而更适合机器人的生长。

ffdm

新人表示完全看不懂！需要先学数据结构么？

jsleo

1. private class Node
   
2.     {
   
3.       public string id;
   
4.       public string path;
   
5.       public Node(string id, string path)
   
6.       {
   
7.         this.id = id;        // this是Node类的对象
   
8.         this.path = path;
   
9.       }
   
10.     }
    
11. 
    
12.     static void Main(string[] args)
    
13.     {
    
14.       string idA = "849";
    
15.       string idB = "1048";
    
16.       DateTime start = DateTime.Now;
    
17. 
    
18. string sql = "select * from exits where roomb is not null and roomb!=''";
    
19.       DataTable exits = F.getDT(sql);
    
20. 
    
21.       Queue PathNode = new Queue();
    
22.       PathNode.Enqueue(new Node(idA, ""));
    
23.       foreach (DataRow row in exits.Select("roomB=" + idA))
    
24.         exits.Rows.Remove(row);
    
25. 
    
26.       bool notfinded = true;
    
27.       while (exits.Rows.Count > 0 && PathNode.Count>0 && notfinded)
    
28.       {
    
29. Node node = PathNode.Dequeue();//取出首部节点A
    
30.         foreach (DataRow row in exits.Select("roomA=" + node.id))
    
31.         {
    
32.           if (row["roomB"].ToString() == idB)
    
33.           {
    
34.             Console.WriteLine(node.path + row["dicAB"] + ":" + node.path.Split(';').Count());
    
35.             notfinded = false;
    
36.             break;
    
37.           }
    
38.           PathNode.Enqueue(new Node(row["roomB"].ToString(), node.path + row["dicAB"] + ";"));
    
39.           foreach (DataRow r in exits.Select("roomB=" + row["roomB"]))
    
40.             exits.Rows.Remove(r);
    
41.         }
    
42.       }
    
43.       Console.WriteLine((DateTime.Now-start).TotalMilliseconds);
    
44.       Console.ReadLine();
    
45.     }

复制代码

广度优先搜索

jsleo

岳阳到牙山，37步，计算耗时2.4秒

求高手指点优化方向和思路

hijacker

换更快的cpu
huacuoh 发表于 2013-11-8 02:47 PM

    正解。以前在老爷机上用这个机器人，路远一点就要卡好几秒；换了新电脑（i5）后，几乎感觉不出来明显的卡顿了

inkflower

正解。以前在老爷机上用这个机器人，路远一点就要卡好几秒；换了新电脑（i5）后，几乎感觉不出来明显 ...
hijacker 发表于 2013-11-8 03:26 PM

  求数据库  

inkflower

求楼主以及楼上各位高手写个完整的GPS思路

hijacker

求数据库
inkflower 发表于 2013-11-8 05:07 PM

    楼主有提供数据库和录地图的alias，你可以在他的基础上自己扩展

hasea

回复 31# jsleo

不可能吧，2.4秒。你用的什么算法？？数据结构是怎么样的？在多少个数据里面搜索的？？？

你不会在所有房间数据里面用Dijkstra算法吧。！！在几千上万个数据中这样用。慢是正常的吧。如果是这样，还是要优化优化吧。
感觉也不至于54步用了2.4秒。难道你用了386。

hasea

回复 38# yyahoo

图的最短路径算法。一般复杂度是N^2。1000个房间数据的话，最长时间可能是1百万次(没算常数)。何况游戏中一般不止1000个房间。当然平均时间没有这么多。如果这样设计，又是用的脚本语言，而且还用了很多低效率的语句，路径很远的时候，10秒都会有可能。

分开城市来寻路。每个城市大约5,60个房间。最差情况下也就是计算数千或上万次。
把Dijkstra算法修改一下，就当是权值为1。。应该会减少些计算量。lua的效率不大清楚，0.1S内也许可以搞定。

事实上认真设计的话，把单个城市内寻路计算的最差计算情况控制在千次以下是有可能做到的。

如果寻路时间以秒为单位的话，应该有很大的优化空间吧。