labaz 发表于 2013-6-20 08:51:45

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

ffdm 发表于 2013-11-8 10:38:24

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

jsleo 发表于 2013-11-8 14:31:07

private class Node
    {
      public string id;
      public string path;
      public Node(string id, string path)
      {
      this.id = id;      // this是Node类的对象
      this.path = path;
      }
    }

    static void Main(string[] args)
    {
      string idA = "849";
      string idB = "1048";
      DateTime start = DateTime.Now;

string sql = "select * from exits where roomb is not null and roomb!=''";
      DataTable exits = F.getDT(sql);

      Queue<Node> PathNode = new Queue<Node>();
      PathNode.Enqueue(new Node(idA, ""));
      foreach (DataRow row in exits.Select("roomB=" + idA))
      exits.Rows.Remove(row);

      bool notfinded = true;
      while (exits.Rows.Count > 0 && PathNode.Count>0 && notfinded)
      {
Node node = PathNode.Dequeue();//取出首部节点A
      foreach (DataRow row in exits.Select("roomA=" + node.id))
      {
          if (row["roomB"].ToString() == idB)
          {
            Console.WriteLine(node.path + row["dicAB"] + ":" + node.path.Split(';').Count());
            notfinded = false;
            break;
          }
          PathNode.Enqueue(new Node(row["roomB"].ToString(), node.path + row["dicAB"] + ";"));
          foreach (DataRow r in exits.Select("roomB=" + row["roomB"]))
            exits.Rows.Remove(r);
      }
      }
      Console.WriteLine((DateTime.Now-start).TotalMilliseconds);
      Console.ReadLine();
    }

广度优先搜索

jsleo 发表于 2013-11-8 14:35:20

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

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

hijacker 发表于 2013-11-8 15:26:55

标题

换更快的cpu
huacuoh 发表于 2013-11-8 02:47 PM http://pkuxkx.com/forum/images/common/back.gif
    正解。以前在老爷机上用这个机器人，路远一点就要卡好几秒；换了新电脑（i5）后，几乎感觉不出来明显的卡顿了

inkflower 发表于 2013-11-8 17:07:34

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


求数据库yct42

inkflower 发表于 2013-11-8 17:08:55

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

hijacker 发表于 2013-11-8 18:00:09

求数据库
inkflower 发表于 2013-11-8 05:07 PM http://pkuxkx.com/forum/images/common/back.gif


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

hasea 发表于 2013-11-12 17:27:16

本帖最后由 hasea 于 2013-11-12 05:30 PM 编辑

回复 31# jsleo

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

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

hasea 发表于 2013-11-12 20:54:10

本帖最后由 hasea 于 2013-11-12 09:02 PM 编辑

回复 38# yhzzyahoo

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

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

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

如果寻路时间以秒为单位的话，应该有很大的优化空间吧。
页: 1 2 [3] 4
查看完整版本: 寻路机器人LUA实现