游戏中常用的碰撞检测 发表于 2022-07-31 | 分类于 game 本文介绍3种游戏开发中常见形状间的碰撞检测方法。坐标原点均为左下角。 一、矩形物体间的碰撞检测矩形之间的碰撞检测方法有很多,比如: 检测矩形A是否有顶点在矩形B中 检测矩形A的边是否与矩形B的边相交 直接通过两矩形的坐标判断 阅读全文 »
Channel 工作原理及源码分析 发表于 2021-09-26 | 分类于 golang golang提倡使用通信的方式来共享内存,而不是通过共享内存来通信。下面介绍channel是如何实这一思想的,以及使用channel时需要注意的地方。 一、基本原理1.写入数据时若channel recvq(读阻塞队列)上有被gopark的g,则直接把数据拷贝到队首g的栈空间,并唤醒g;若recvq中没有gopark的g,但缓冲区未满,则把数据放入缓冲区。 阻塞方式:若缓冲区满,则直接gopark当前g,等待读g的唤醒。 非阻塞方式:若缓冲区满,直接返回,不对数据做任何处理。 阅读全文 »
TCP/IP 调优 发表于 2020-09-06 | 分类于 protocal TCP/IP相关的基础知识、术语已经在之前的文章中介绍过了。这里主要介绍三次握手、四次挥手、缓冲区、拥塞控制中各种状态的意义以及相关内核参数的配置。 一、三次握手 1.1 三次握手流程1)当客户端调用connect函数后,内核会向服务器发送SYN+序号,并进入SYN_SEND状态。2)服务器内核收到SYN消息后,会建立一条连接并放入半连接队列,回复SYN+ACK,进入SYN_RCVD。 阅读全文 »
JPS寻路算法 发表于 2020-08-09 | 分类于 algorithm JPS算法本质上是对A* 算法的优化,在大部分情况下比传统A* 算法快上百倍。通过性能统计可以现,A* 算法大量时间都花在操作openset和closedset上,其原因就是加入openset的节点太多。JPS只会把关键的节点(跳点)加入openset中,从而大大减少了维护最小堆的开销。 一、概念JPS在传统A* 算法基础上提出了强迫邻居和跳点的概念,这是减少openset中格子数量的关键。 阅读全文 »
Golang Netpoll 实现原理 发表于 2020-07-03 | 分类于 golang golang netpoller封装了不同平台的网络模型,由于我们的游戏服务器程几乎只运行在linux上,这里介绍epoll。epoll是linux下非阻塞的高效的网络模型,对大量文件描述符读写拥有优异的性能。下面先简单介绍epoll的原理,再从源码角度来看golang是如何封装epoll的。 一、epoll实现1.1 例子先通过一个简单的例子来看一下epoll是如何使用的,流程如下: 阅读全文 »
Golang Runtime 发表于 2020-06-01 | 分类于 golang 一、基础知识在阅读源码前,我们先来熟悉一下相关的基础知识,这是理解runtime的基础。 用户级线程:由用户运行时(runtime)来管理线程,操作系统不能感知其存在,所以也不会对其调度,一般会在用户空间提供一个线程库来操作它们。在进程中多个用户级线程对应一个内核级线程,当内核线程阻塞,进程中的所有线程都会被阻塞。Lua的协程(coroutine)、golang的goroutine都属于用户级线程。 轻量级进程(LWP):Linux中没有线程概念,跟线程比较相似的是轻量级进程(LWP),一个进程中可以有多个LWT。LWP需要和内核线程绑定才能被执行,与内核线程是一对一的绑定关系。为了方便理解,我们直接把LWP看成是内核线程。 混合模型:进程中可以同时有多个内核线程和多个用户线程,用户线程只有绑定内核线程才能被执行,多个用户线程可以进入同一个内核线程的执行队列,由runtime负责用户线程的调度以及用户线程与内核线程的绑定与解绑。golang就是采用此模型。 阅读全文 »
游戏中的排行榜 发表于 2020-03-08 | 分类于 game 排行榜是游戏中重要的功能,如何才能实现一个高效的排行榜呢?我所在的项目组做的是SLG游戏,我们游戏的很多活动都有排行榜。上周接到一个跨服排行榜的功能案,需求是让现有的排行榜支持跨服。 一、问题描述目前每个服的玩家大概4W人,如果战力排行榜做成跨服,开到300个服时,上榜人数会超过1kw。虽然很少有游戏能开到300个服,但作为服务器程序设计功能时必须要考虑极端情况,选择适合的方案,不然可能有推倒重来的风险。下面介绍2种实现排行榜的方案,一是快速排序,另一种是redis实现。 阅读全文 »
游戏中的AI-行为树 发表于 2020-02-15 | 分类于 game 游戏中,常见用AI实现方式有2种,状态机和行为树。下面主要简介绍行为树,行为树是用一棵多叉树来表示AI,树的中间节点为控制节点控制着AI的执行流程,叶子节点为行为节点,描述了AI的具体行为。 一、案例描述山贼的AI需求描述如下: 视野内没有敌人则在一定范围内巡逻 视野出现敌人则走过去攻击敌人 当自己血量 < 20% 则逃跑 下面将分别用状态机和行为树来描述山贼的AI 阅读全文 »
AOE技能目标选择器 发表于 2020-01-21 | 分类于 game 本文介绍2种常用的AOE技能目标选择器实现方法,矩形区域和扇形区域。 一、矩形区域有技能描述是“对长距离路径上的敌人造成伤害,并给予状态5秒”。长距离路径上的敌人其实就是施法者到直接目标之间所构成矩形区域中的敌人。这个需求可以化成判断点是否在矩形区域内。如下图所示: 阅读全文 »
Golang 互斥锁、读写锁实现 发表于 2020-01-13 | 分类于 golang 一、相关概念 互斥锁(mutex):获取锁失败时,线程会被休眠让出cpu。当锁被其它线程释放后,阻塞线程被内核唤醒继续执行。这里会产生2次上下文切换。 自旋转锁(cas): 获取锁失败时,线程不会被休眠,而是调用pause指令消耗cpu,直到获取成功。因为线程没被暂停所以不会有上下文切换,但由于需要调用pause指令等待锁被释放,所以在获得锁以前会一直消耗cpu。 读写锁:读写锁可以基于互斥锁或自旋转锁来实现,任意时刻支持多个线程读或者一个线程写。 适合场景:如果能确定获取锁后会快速释放,优先使用自旋转锁;如果不确定锁的释放时间或需要者长时间占用锁则使用互斥锁;如果读多写少可以考虑读写锁。 阅读全文 »