ITeye博客

Algorithm

共 8 篇文章

卡马克地图缓冲图大小计算方法

背景缓冲的大小 背景缓冲图像的大小要大于屏幕最多可涉及的Tile的区域。 例如: 屏幕大小是128 X 128,Tile是 8 X 8,缓冲图像至少是 136 X 136 = (128 + 8) X (128 + 8) 屏幕大小是120 X 130,Tile是 8 X 8,缓冲图像至少是 128 X 144 = (120 + 8) X ((130+7)/8*8 + 8) 屏幕大小是 screenW X screenH,Tile是 tileW X tileH, 缓冲图宽高的计算公式为: (screenW + (tileW - 1)) / tileW * tileW + tileW (scree…

2012-02-21 16:58 · Algorithm

概率不等的随机数生成的一点思路

题目:产生0-9中的随机数,要求0到9出现的概率依次递减, 一般思路,把10个0,9个1,8个2.....2个8,1个9放到数组中,然后随机生成数组下标,按下标取出数字. 二般思路:生成两个0-9的随机数,取小的那个,这个思路(手链魔咒提出)说实际的不知道是什么原理,但是实验证明,确实能达到效果. 验证方法: 程序代码 <?php function fun(){ $num = rand(0,9); //10以内的数字平均分配 $num2 = rand(0,9); ($num2<=$num) ? $return.=$num2 : $return.=$num; return $return; }…

2011-06-28 17:05 · Algorithm

常见的海量数据处理方法

给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 s 遍历文件a,对每个url求取 ,然后根据所取得的值将url分别存储到1000个小文件(记为 )中。这样每个小文件的大约为300M。 s 遍历文件b,采取和a相同的方式将url分别存储到1000各小文件(记为 )。这样处理后,所有可能相同的url都在对应的小文件( )中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小…

2011-06-23 23:43 · Algorithm

遇敌概率

对于传统RPG游戏踩地雷遇敌方式的概率设定通常有以下两种。 一、每步遇敌率,即设定一个遇敌概率值X,每走一步系统投骰子都有X的几率遇敌。 二、固定步数遇敌,即从某个起点(进入地图,或者从上一场战斗结束)系统投骰子决定下一次遇敌是X步之后,那么走到第X步遇敌。 问题: 一、以第一种方式设定,遇敌率为20%,请计算从起点走到第10步遇敌的概率(前9步都不遇敌) 二、以第二种方式设定,遇敌步数为5~15,请计算从起点走到第10步遇敌的概率(前9步都不遇敌

2011-03-03 17:10 · Algorithm

关于SLG中人物可到达范围计算的想法

下面的没有经过实践,因此很可能是错误的,觉得有用的初学朋友读一读吧:) 希望高人指点一二 :) 简介: 在标准的SLG游戏中,当在一个人物处按下鼠标时,会以人物为中心,向四周生成一个菱形的可移动区范围,如下: 0 000 00s00 000 0 这个图形在刚开始学习PASCAL时就应该写过一个画图的程序(是否有人怀念?)。那个图形和SLG的扩展路径一样。 一、如何生成路径: 从人物所在的位置开始,向四周的四个方向扩展,之后的点再进行扩展。即从人物所在的位置从近到远进行扩展(类似广宽优先)。 二、扩展时会遇到的问题: 1、当扩展到一个点时,人物的移动力没有了。 2、当扩展的时候遇到了一个障碍点…

2011-01-06 18:08 · Algorithm

小谈网络游戏同步

同步在网络游戏中是非常重要的,它保证了每个玩家在屏幕上看到的东西大体是一样的。其实呢,解决同步问题的最简单的方法就是把每个玩家的动作都向其他玩家广播一遍,这里其实就存在两个问题:1,向哪些玩家广播,广播哪些消息。2,如果网络延迟怎么办。事实上呢,第一个问题是个非常简单的问题,不过之所以我提出这个问题来,是提醒大家在设计自己的消息结构的时候,需要把这个因素考虑进去。而对于第二个问题,则是一个挺麻烦的问题,大家可以来看这么个例子: 比如有一个玩家A向服务器发了条指令,说我现在在P1点,要去P2点。指令发出的时间是T0,服务器收到指令的时间是T1,然后向周围的玩家广播这条消息,消息的内容是“玩家A…

2010-11-26 10:28 · Algorithm

较重要的算法

下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部份摘自Wikipedia,因为维基百科描述的很专业了) A*搜寻算法 俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。 Beam Search 束搜索…

2010-10-21 10:10 · Algorithm

什么是UUID 以及UUID的版本

什么是UUID? UUID是Universally Unique Identifier的缩写,它是在一定的范围内(从特定的名字空间到全球)唯一的机器生成的标识符。UUID具有以下涵义: 经由一定的算法机器生成 为了保证UUID的唯一性,规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。UUID的复杂特性在保证了其唯一性的同时,意味着只能由计算机生成。 非人工指定,非人工识别 UUID是不能人工指定的,除非你冒着UUID重复的风险。UUID的复杂性决定了“一般人“不能直接从一个UUID知道哪个对象和它关联。 在特…

2009-11-14 22:59 · Algorithm