SleepyLoser's Blog

JPS 算法概念基础 JPS（Jump Point Search，跳点搜索）算法是对 A* 算法的一种优化（附A* 算法）。在 A* 算法中，当前节点周围的所有可搜索邻居都会被加入到 OpenList 中。JPS 算法则在保持 A* 算法基本框架的基础上，采用了一种更为高效的策略来确定哪些点需要被加入到 OpenList 中。这种方法能够显著减少需要评估的节点数量，从而提高路径搜索的效率。 自然邻居 自然邻居指的是在路径搜索过程中，某些节点的直接邻居是可以直接移动到达的节点，而不需要经过其他节点的中转。这些自然邻居是基于当前节点的移动方向和位置来确定的。如图所示，红色块是自然邻居（其中 p(x) 为父节点，x为当前节点）。 强迫邻居 为了减少需要评估的节点数量，JPS 算法引入了强迫邻居的概念。强迫邻居指的是在路径搜索过程中，某些节点的直接邻居是必须被考虑的，因为它们是达到更远距离节点的必经之路。在 JPS 算法中，强迫邻居用于确保搜索过程不会错过任何可能的路径选择。 强迫邻居的定义：当节点 x 的 8 个邻居中存在障碍，且节点 x 的父节点 p 经过节点 x 到达节点 n 的 ...

A* 算法概念基础Dijkstra算法 Dijkstra算法用来寻找图形中节点之间的最短路径。 在Dijkstra算法中，需要计算每一个节点距离起点的总移动代价。同时，还需要一个优先队列结构。对于所有待遍历的节点，放入优先队列中会按照代价进行排序。 在算法运行的过程中，每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。 下面对比了不考虑节点移动代价差异的广度优先搜索与考虑移动代价的Dijkstra算法的运算结果： 最佳优先搜索 在一些情况下，如果我们可以预先计算出每个节点到终点的距离，则我们可以利用这个信息更快的到达终点。 其原理也很简单。与Dijkstra算法类似，我们也使用一个优先队列，但此时以每个节点到达终点的距离作为优先级，每次始终选取到终点移动代价最小（离终点最近）的节点作为下一个遍历的节点。这种算法称之为最佳优先（Best First）算法。 这样做可以大大加快路径的搜索速度，如下图所示： 但这种算法会不会有什么缺点呢？答案是肯定的。 因为，如果起点和终点之间存在障碍物，则最佳优先算法找到的很可能不是最短路径，下图描述了这种情况。 A* ...

移动施法的动画分层 该动画分层的目的就像让你《使命召唤》里的士兵一边奔跑一边换弹夹，而且动作流畅，毫不拖沓。出现在我脑海中的第一个想法是：把奔跑动画放在骨盆及以下部位播放，而把持枪相关的动画放在躯干及以上部位播放。听起来很简单，但如果你想结合奔跑和挥剑动作会怎么样？如果你希望角色在奔跑和站立不动时都能使用相同的动画，又该怎么办呢？ 接下来我将介绍一种方法：使用角色装备、实时反向动力学（IK）和嵌套混合树来解决上述问题 为了说明我们的问题，首先创建一个包含两个层的动画控制器：一个用于腿部，一个用于上半身动画。腿部图层通常有一个处理多方向侧向移动的混合树。然后为上半身图层添加一个 Avatar 遮罩，用来遮掉腿部，然后在该图层上播放一个近战动画。许多教程都是这么做的，然后就到此为止了，但这正是我们开始发现问题的地方。 仅仅使用 Avatar 遮罩会导致胸部旋转不正确。​ 挺直脊柱 首先，躯干动画会有不正确的旋转，是因为骨盆的旋转（由于其位于层级结构的上层而影响躯干）不再与技能动画匹配，因为它被遮罩掉了，只受奔跑动画的影响。 我们通过使用一个参考 / 代理关节来解决这个问题。这个关节的父级 ...

程序断点的原理 调试器 Debugger 并不能控制程序的执行顺序，它之所以可以让 CPU 在需要的地方停住（随心所欲的停止程序的执行），主要通过软件断点和硬件断点两种方式。 软件断点 软件断点在 x86 / x32 / x64 系统中就是指令 INT 3 ，它的二进制代码 opcode 是 0xCC 。当程序执行到 INT 3 指令时，会引发软件中断。操作系统的 INT 3中断处理器 会寻找注册在该进程上的调试处理程序，从而像 Windbg 和 VS 等等调试器就有了上下其手的机会。 通过一个例子说明： 123456#include <iostream>int main(){ printf("Hello World"); // 这里断点} 此时调试器会将目标地址的指令替换为 int 3 指令（机器码 0xCC ），等到达断点的时候会还原目标地址的指令。 一般情况下，调试器维护了一大组调试断点，在并把他们都换成了 INT 3 。在被调度回来后，会都填回去，并通过现在的地址判断是到了那个断点。软件断点没有数目限制。 ...

volatile volatile 是 C 语言中的一个关键字，用于修饰变量，表示该变量的值可能在任何时候被外部因素更改，例如 硬件设备、操作系统 或 其他线程 。 当一个变量被声明为 volatile 时，编译器会禁止对该变量进行优化，以确保每次访问变量时都会从内存中读取其值，而不是从寄存器或缓存中读取。避免因为编译器优化而导致出现不符合预期的结果。 explicit 在 C++ 中，explicit 通常用于构造函数的声明中，用于防止隐式转换。 当将一个参数传递给构造函数时，如果构造函数声明中使用了 explicit 关键字，则只能使用显式转换进行转换，而不能进行隐式转换。这种机制可以防止编译器自动执行预期外的类型转换，提高代码的安全性。 什么是隐式类型转化 当你只有一个类型T1，但是当前表达式需要类型为T2的值，如果这时候T1自动转换为了T2，那么这就是隐式类型转换。如下： 1234567int a = 0;long b = a + 1; // int 转换为 long if (a == b) { // 默认的operator==需要a的类型和b相同，因此也 ...

const 与 static 关键字const const修饰符用来定义常量，具有不可变性。在类中，被const修饰的成员函数，不能修改类中的数据成员； 指针常量指的是该指针本身是一个常量，不能被修改，但是指针指向的对象可以被修改； 常量指针指的是这个指针指向的对象是一个常量，不能被修改，但是指针本身可以被修改。 如果 const 变量是在全局作用域中声明的，它将存储在静态存储区（Static Storage Area）中。 如果 const 变量是在函数内部或代码块内部声明的，它将存储在栈（Stack）上，在函数返回时释放。 const 修饰的字符串常量存储在常量存储区，在程序运行期间保持不变。 const 修饰的函数能否重载？ const修饰的函数可以重载。const成员函数既不能改变类内的数据成员，也无法调用非const的成员函数；const类对象只能调用const成员函数。非const对象无论是否是const成员函数都能调用，但是如果有重载的非const函数，非const对象会优先调用重载后的非const函数。 const 修饰函数的参数 如果参数作输出用，不论它是什么数据 ...

const 与 constexpr 的区别 如下图： 主要是用于区分只读变量和常量 只读变量：运行时确定 常量：编译时确定 性能方面：常量 > 只读变量 常见的常量表达式 字面值（如 42） 用常量表达式初始化的对象 一个对象（或表达式）是否是常量表达式取决于类型和初始值，如下： 12345int i1 = 42; // i1 不是常量表达式：初始值 42 是字面值，但 i1 不是 const / constexpr 类型const int i2 = i1; // i2 不是常量表达式：初始值 i1 不是常量表达式const int i3 = 42; // i3 是常量表达式：用字面值 42 初始化的 const 对象const int i4 = i3 + 1; // i4 是常量表达式：用常量表达式 i3 + 1 初始化的 const 对象const int i5 = getValue(); // 如果 getValue() 是普通函数，则 i5 值要到运行时才能确定，则不是常量表达式。相反，如果 getValue() 是 ...

该算法未经过大量数据验证！！！ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include <iostream>#include <string>using namespace std;string chinese[] = {"零", "一", "二", "三", "四", "五", "六", "七", "八", "九"};string bit[] = {"", "十", "百", "千"};string GetChinese(string num){ ...

手撕队列（基于数组） 关键点在于头指针和尾指针在队列清空时的调整（MyQueue::pop()），不当的操作可能导致清空后的空间无法重复使用，不断扩容。 可对扩容操作（MyQueue::push()）做进一步优化（数据前移）。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include<iostream>using namespace std;template <typename T>class MyQueue{private: T* _data; int _front; int _rear; int _size; int _capacity;public: MyQueue(); ...

Lambda 表达式如何对应到函数对象 在 C++ 中，Lambda 表达式本质上是编译器生成的匿名函数对象​（又称闭包类），其底层实现依赖于对 operator() 运算符的重载。这种机制使得 Lambda 既能保持与普通函数相似的调用方式，又能通过捕获上下文变量实现更灵活的行为。以下是其核心实现原理和对应关系的具体分析: Lambda表达式与闭包类的映射 编译器生成的匿名类 当定义一个Lambda表达式时，编译器会隐式生成一个唯一的闭包类，该类包含以下核心结构: 成员变量：存储通过值捕获或引用捕获的外部变量（若存在捕获）。 ​重载的operator()：实现Lambda的函数体逻辑。 可能的类型转换函数：用于无捕获Lambda隐式转换为函数指针（通过+运算符触发）。 12345678910auto lambda = [x](int y) { return x + y; };// 对于上面的语句，编译器生成类似以下的闭包类：class __lambda_anonymous {private: int x; // 值捕获的变量副本publi ...