北大侠客行MUD论坛

 找回密码
 注册
搜索
热搜: 新手 wiki 升级
楼主: ptouch

寻路机器人LUA实现

[复制链接]
发表于 2013-6-20 08:51:45 | 显示全部楼层
此帖说明书剑自动化进程比北侠要早得多,关键那里有pk你自动挂也连不起来。但是,北侠这里几乎没pk,反而更适合机器人的生长。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 10:38:24 | 显示全部楼层
新人表示完全看不懂!需要先学数据结构么?
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 14:31:07 | 显示全部楼层
  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.     static void Main(string[] args)
  12.     {
  13.       string idA = "849";
  14.       string idB = "1048";
  15.       DateTime start = DateTime.Now;

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

  18.       Queue PathNode = new Queue();
  19.       PathNode.Enqueue(new Node(idA, ""));
  20.       foreach (DataRow row in exits.Select("roomB=" + idA))
  21.         exits.Rows.Remove(row);

  22.       bool notfinded = true;
  23.       while (exits.Rows.Count > 0 && PathNode.Count>0 && notfinded)
  24.       {
  25. Node node = PathNode.Dequeue();//取出首部节点A
  26.         foreach (DataRow row in exits.Select("roomA=" + node.id))
  27.         {
  28.           if (row["roomB"].ToString() == idB)
  29.           {
  30.             Console.WriteLine(node.path + row["dicAB"] + ":" + node.path.Split(';').Count());
  31.             notfinded = false;
  32.             break;
  33.           }
  34.           PathNode.Enqueue(new Node(row["roomB"].ToString(), node.path + row["dicAB"] + ";"));
  35.           foreach (DataRow r in exits.Select("roomB=" + row["roomB"]))
  36.             exits.Rows.Remove(r);
  37.         }
  38.       }
  39.       Console.WriteLine((DateTime.Now-start).TotalMilliseconds);
  40.       Console.ReadLine();
  41.     }
复制代码


广度优先搜索
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 14:35:20 | 显示全部楼层
岳阳到牙山,37步,计算耗时2.4秒

求高手指点优化方向和思路
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 15:26:55 | 显示全部楼层

标题

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

    正解。以前在老爷机上用这个机器人,路远一点就要卡好几秒;换了新电脑(i5)后,几乎感觉不出来明显的卡顿了
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 17:07:34 | 显示全部楼层
正解。以前在老爷机上用这个机器人,路远一点就要卡好几秒;换了新电脑(i5)后,几乎感觉不出来明显 ...
hijacker 发表于 2013-11-8 03:26 PM



  求数据库  
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 17:08:55 | 显示全部楼层
求楼主以及楼上各位高手写个完整的GPS思路
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-8 18:00:09 | 显示全部楼层
求数据库
inkflower 发表于 2013-11-8 05:07 PM



    楼主有提供数据库和录地图的alias,你可以在他的基础上自己扩展
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-12 17:27:16 | 显示全部楼层
本帖最后由 hasea 于 2013-11-12 05:30 PM 编辑

回复 31# jsleo

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

你不会在所有房间数据里面用Dijkstra算法吧。!!在几千上万个数据中这样用。慢是正常的吧。如果是这样,还是要优化优化吧。
感觉也不至于54步用了2.4秒。难道你用了386。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2013-11-12 20:54:10 | 显示全部楼层
本帖最后由 hasea 于 2013-11-12 09:02 PM 编辑

回复 38# yyahoo

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

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

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

如果寻路时间以秒为单位的话,应该有很大的优化空间吧。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|北大侠客行MUD ( 京ICP备16065414号-1 )

GMT+8, 2024-11-1 03:26 PM , Processed in 0.013303 second(s), 12 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表