0%

早上到公司发现电脑是开着的,记得下班的时候是休眠的,为什么自己开了呢。打开事件查看器,发现了问题所在。

event_wake_up

电脑只休眠了不到一个小时就自动唤醒了(好像暴露了加班狗的属性)。

事件查看器显示唤醒电脑的是音频设备。估计跟电脑开着音乐有关系。

event_wake_up

网上搜了下解决方案,有说从设备管理器就可以禁掉设备自动唤醒电脑,但是我从设备管理器并没有找到这个电源管理的选项。

不过也有第二种方案,直接通过命令行来禁止。首先列出支持唤醒电脑的设备:

1
2
3
4
E:\playerground>powercfg -devicequery wake_armed
HID-compliant mouse (001)
Realtek PCIe GBE Family Controller
HID Keyboard Device

果然发现了肇事者。果断禁掉:

1
E:\playerground>powercfg -devicedisablewake "Realtek PCIe GBE Family Controller"

再列举一下:

1
2
3
E:\playerground>powercfg -devicequery wake_armed
HID-compliant mouse (001)
HID Keyboard Device

发现音频设备不见了,问题解决。要把它加回来也容易,把disable改成enable就可以了。

1
E:\playerground>powercfg -deviceenablewake "Realtek PCIe GBE Family Controller"

windows 10 睡眠唤醒检查

通过 powercfg -lastwake 可以查看上一次唤醒的原因。
检查唤醒设备没有发现问题:power /devicequery wake_armed

通过 powercfg /waketimers 可以查看下一次唤醒的定时器。
发现是 windows 的自动更新:Update Orchestrator,

使用管理员打开定时任务管理器,尝试禁用定时器,弹框提示当前用户没有权限。
找到一个帖子使用 PsTools 来启动定时任务。

psexec.exe -i -s %windir%\system32\mmc.exe /s taskschd.msc

再次尝试禁用定时器,成功!
再次用 powercfg /waketimers查询,把查询到的所有定时器干掉。

powercfg /waketimers 枚举活动的唤醒计时器
Disable Update Orchestrator from waking my computer

https://answers.microsoft.com/en-us/windows/forum/windows_10-update/disable-update-orchestrator-from-waking-my/19272430-f41f-4947-904c-71ab34b220f0

可能是与快速启动冲突,建议您尝试尝试关闭快速启动:
“Win+X”>>控制面板>>电源选项>>选择电源按钮的功能,
更改当前不可用的设置,勾选“启用快速启动”功能,确定。
https://answers.microsoft.com/zh-hans/windows/forum/all/win10%E7%9D%A1%E7%9C%A02%E7%A7%92%E5%90%8E/ac0cb7a7-9c7c-44e8-93f0-523246bd82aa

电源选项-睡眠,允许使用唤醒定时器,禁用

  1. Go to: Control Panel\Hardware and Sound\Power Options\Edit Plan Settings (it may also be called Change plan settings)
    (you can alternatively just search for “Edit power plan” in the windows search bar)
  2. Click “change advanced power settings”
  3. Go to “Sleep->Allow wake timers” and change the setting to Disable.

参考文档

ARPG游戏中经常出现多个怪物追着玩家跑的情况,如果怪物始终瞄着玩家的位置移动,那么很容易就出现怪物扎堆的情况。
本文探讨并实现了一个位置管理算法,来解决这个问题。

算法思路

我们的思路是:如果玩家已经在攻击范围内,直接攻击。否则怪物向玩家移动,形成一个以攻击距离为半径,玩家为圆心的包围圈。
在移动过程中,怪物优先选择怪物所在位置与玩家连线跟圆的交点。 如果交点被占据,则向两边搜索新的位置,直到找到一个位置为止。

具体实现

整个圆是360度,我们把它等分为18个区间,每个区间20度,18个区间基本足以满足对怪物数量的要求了。
我们首先找到怪物相对玩家位置的角度。

CurAngle = (math:atan2(Z1 - Z0, X1 - X0) / math:pi()) + 180

atan2求出的范围是弧度(-pi, pi],我们需要将其转换为(0, 360]的角度。
然后检查是否当前角度所在的区间是否已经被占用,由于区间是一个连续的范围,我们用起点来表示一个区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
-define(SLICE, 20). %% 极坐标20度为一个slot分布怪物

find_angle(PlayerId, PlayerPos, Angle) ->
PlayerPos0 = get({player_pos, PlayerId}),
PlayerPos0 /= PlayerPos andalso
begin
erase({angle, PlayerId}),
put({player_pos, PlayerId}, PlayerPos),
?INFO("~p change pos ~p", [PlayerId, PlayerPos])
end,
AdjustAngle = (Angle div ?SLICE) * ?SLICE,
Angles = occupied_angle(PlayerId),
TheAngle =
case lists:member(AdjustAngle, Angles) of
true ->
find_angle1(AdjustAngle, ?SLICE, Angles);
false ->
AdjustAngle
end,
put({angle, PlayerId}, [TheAngle|Angles]),
lib_common:random_n(TheAngle, TheAngle + ?SLICE - 1) rem 360.

occupied_angle(PlayerId) ->
case get({angle, PlayerId}) of
undefined -> [];
List -> List
end.

如果当前区间已经被占用,则向两边搜索可用的区间。
我们维护一个Delta差值,逐步增大Delta,向外扩张来搜索新的区间,直到找到为止。之所以限制Delta的范围是不想让怪物越过玩家,
所以如果所有怪都是从同一个方向向玩家移动的时候会形成一个接近半圆的包围圈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
find_angle1(AdjustAngle, Delta, _Angles) when Delta > 100 ->
AdjustAngle;
find_angle1(AdjustAngle, Delta, Angles) ->
Angle1 = (AdjustAngle + Delta) rem 360,
case lists:member(Angle1, Angles) of
true ->
Angle2 = (AdjustAngle - Delta + 360) rem 360,
case lists:member(Angle2, Angles) of
true ->
find_angle1(AdjustAngle, Delta+?SLICE, Angles);
false ->
Angle2
end;
false ->
Angle1
end.

解决了怪物分布的问题,还有一个问题就是玩家位置的维护。因为玩家是一直移动的,而且移动的频率很高。
如果每次玩家移动了以后,都清除掉老的区间,重新计算新的区间。代价会比较大,而且也不是很有必要。
所以我们只会在玩家离开一段距离导致目标点无法攻击玩家的时候,才更新圆心的位置,所以实际上圆心的位置跟玩家的位置可能存在一定的偏移,
这一点我们是可以容忍的。

1
2
3
4
5
6
7
8
9
10
11
TargetPos = if
TP =:= undefined ->
get_target_pos(PlayerId, MonsterId, PlayerPos, Distance);
true ->
%% 玩家离开一段距离了,导致目标点无法攻击玩家,则更新目标点
Dis2 = lib_map_util:calc_dis2(TP, PlayerPos),
if
Dis2 =< Distance * Distance + ?EPSILON2 -> TP;
true -> get_target_pos(PlayerId, MonsterId, PlayerPos, Distance)
end
end

TP是老的怪物目标点,如果我们发现怪物的目标点无法攻击到玩家,则更新目标点。这里比较距离的时候还有个坑,
浮点数的精度有限,所以我们需要加入一个误差,EPSILON2。否则计算出来的目标点有可能会无法满足不等式而导致怪物在玩家周围做小步调整来切换目标点。

效果图

monster_around

TODO

streering behaviour
RVO2
ORCA: Optimal Reciprocal Collision Avoidance
https://github.com/snape/RVO2

系统自带的分配器存在的缺点:

  • 小内存分配效率低。
  • 所有数据同样的分配策略,增加碎片。
  • 缺乏跨平台细粒度的统计
  • +Mea disable erts allocators and use malloc for everything
  • 多核内存管理更加重要也更加复杂

概念

  • Block: 虚拟机请求的一块内存区域。
  • Carrier: 包含一个或多个Block的内存区域,分为sbc,mbc。正常情况下大部分数据位于mbc。
    • Single Block Carrier sbc
      • 大的block进入sbc
      • +M<S>sbct 默认512k
      • 可以通过erlang:system_info(allocator)查看各个allocator的配置参数
    • Multiblock Carrier mbc
      • +M<S>smbcs smallest Multiblock carrier size
      • +M<S>lmbcs largest multiblock Carrier size
      • +M<S>mbcgs multiblock Carrier grow stage
      • 如果增加sbct一般也会相应增大smbcs和lmbcs
    • 通过mseg_alloc分配的mbc的大小
      • smbcs+nc*(lmbcs-smbcs)/mbcgs (nc <= mbcgs)
      • lmbcs (nc > mbcgs)
    • 通过sys_alloc分配的mbc
      • least number of multiple of ycs satisfying the request

各种分配器

memory_allocators

文件erl_alloc.types中列举了所有的分配器类型以及不同数据对应的分配器类型。
ERTS中一共定义了11中不同的分配器,包括最基本的sys_alloc以及mseg_alloc。
详情见下表。Flag是启动ERTS时修改分配器配置参数的标志。

Name Description C-name Type-name Flag
Basic allocator malloc interface sys_alloc SYSTEM Y
Memory segment allocator mmap interface mseg_alloc - M
Temporary allocator Temporary allocations temp_alloc TEMPORARY T
Heap allocator Erlang heap data eheap_alloc EHEAP H
Binary allocator Binary data binary_alloc BINARY B
ETS allocator ETS data ets_alloc ETS E
Driver allocator Driver data driver_alloc DRIVER R
Short lived allocator Short lived memory sl_alloc SHORT_LIVED S
Long lived allocator Long lived memory ll_alloc LONG_LIVED L
Fiexed allocator Fiexed size data fix_alloc FIXED_SIZE F
Standard allocator For most other data std_alloc STANDARD D
  • eheap,binary, driver, ets
  • temporary
    • c function scope
    • temp gc rootset
    • dist msg decode
  • short lived
    • ets match specs
    • short timers
    • fd select list
  • standard lived
    • links
    • monitors
  • long lived
    • code
    • atoms
  • fix size
    • process control block
    • port control block

分配策略(as)

allocation strategy,从mbc中找到空闲block的策略。

  • Block Oriented
    • best fit: 找到满足要求的最小block,二叉平衡树,logN
    • address order best fit
    • address order first fit
    • good fit
    • a fit
  • Carrier Oriented
    • address order first fit carrier best fit
    • address order first fit carrier address order best fit

Carrier分配器

  • mseg alloc
    • /dev/zero mmap, munmap, mremap
    • cache freeed carries
  • sys alloc
    • maps to malloc, free
    • multiple of +Muycs to help avoid fragmentation
    • used for main carrier allocaton

统计

erlang:system_info(allocator)

  • sys_alloc mseg_alloc
  • eheap_alloc, ets_alloc, binary_alloc, driver_alloc
  • temp_alloc, sl_alloc, std_alloc, ll_alloc, fix_alloc

erlang:system_info({allocator, Type})

主要配置参数

  • sbct
  • mbc allocation strategy

实例

问题一: large binary

  • 现象:性能低下,通过strace发现malloc比mmap多得多。
  • 原因: 统计发现sbcs carrier_size 比 mbcs carrier_size大得多,大量binary放到了sbc。
  • 解决方案:
    • 增大+MBsbct, 同时增大+MBlmbcs+MBsmbcs

问题二:碎片问题

这是lyse作者在实际项目中遇到的问题,详情见作者博客logplex down the rabbit hole

  • 现象:
    • erlang:memory(total) 7GB
    • top 显示 15GB
    • 崩溃日志:ets_alloc: Cannot allocate XYZ bytes of memory. Abnormal termination
  • 原因: Carrier中残留的block导致Carrier无法回收
  • 方案:减少碎片
    • +MBas aobf address order best fit 更集中
    • 减小+MBlmbcs 来分配更多的小mbc,更容易被回收

参考文档

Erlang自带三个Boot脚本:

  • start_clean.boot 加载和启动Kernel和STDLIB
  • start_sasl.boot 比上面多了一个SASL
  • no_dot_erlang.boot 跟第一个一样,只是不加载.erlang
    安装otp的时候可以选择默认脚本是start_clean还是start_sasl,选择以后会拷贝一份start.boot.

ERTS中有两种代码加载模式:

  • interactive:代码第一次被引用的时候会去代码路径中搜索并加载。
  • embedded:一开始就根据boot script来加载。

code模块对外提供接口,code_server模块处理实际的工作,注册为code_server。维护一个私有ets表code。
预加载的10个模块,包括erlang_prim_loader,erlang,init,prim_inet,prim_file等模块,需要被code_server用到的模块都属于预加载。

1
2
3
(dev@127.0.0.1)1> erlang:pre_loaded().
[erts_internal,erlang,erl_prim_loader,prim_zip,zlib,
prim_file,prim_inet,prim_eval,init,otp_ring0]

对于预定义的模块,如lists,math等等系统模块,这些模块是不能重复热更新的。这些模块所在的目录被称为sticky目录。
这是为了防止有人误操作把系统模块给替换了导致整个系统崩溃。除了这些系统模块,其他的模块都是可以热更新的。

ERTS系统中,一个模块可以存在两个版本。新版本(current)和老版本(old),两个版本都是有效的。
代码第一次加载进来的时候是新版本,当有新的代码加载的时候,新的代码变成新版本,原来的新版本变成老版本。
当有第三个版本加载进来的时候,之前的老版本就需要被移除掉(purge),
这样如果有进程还在执行老版本的代码,需要将这些还在执行老代码的进程杀死才能进行热更。杀死运行老代码然后purge老代码,然后加载最新代码,这是系统默认的热更方式。
所以一般情况下,第一次热更新模块的时候是安全的,因为系统只有一个新版本的代码。第二次热更新如果使用强制更新就可能杀死一些进程,引发一些意想不到的后果。
要避免这种情况,一方面是在调用代码的时候使用全名函数,一方面在热更新的时候使用软更新(soft purge)。这样如果还有进程在执行老代码,就不会执行热更新。
OTP框架下的模板都是支持热更新的。

purge

purge:是指将老版本的代码从系统中移除掉,如果仍有进程在执行老版本代码,则将这些进程杀掉。
soft_purge:尝试将老代码移除掉,如果仍有进程在执行老版本代码,则返回失败。

erlang模块提供的接口:

  • erlang:check_old_code(Mod) -> boolean(). 检查系统中是否存在该模块的老代码。当系统中有老代码的时候,要清除老代码(执行purge)才能加载新的代码。
    为了清除老代码要先找到仍在执行老代码的进程,将其kill掉。

  • erlang:check_process_code(Pid, Mod) -> boolean(). 检查进程是否在执行Mod的老代码。
    为了找出仍在执行老代码的进程,需要遍历进程列表processes(),依次进行检查。

进程仍在执行模块的老代码,有三种情况:

  • 进程正在执行老代码。这种情况下是不管进程调用的全名函数短名函数。对于全名函数,当前这次执行完了下次就会切换到新代码,所以一开始返回true,后面就false了。对于短名函数则始终为true。
  • 进程包含短名函数的引用。
  • 进程包含引用短名函数的fun对象。比如其他模块发送了一个fun给进程执行,这个fun对象包含了模块的短名对象,那么执行fun对象期间返回true。

如果一个常驻内存的进程拿到了一个模块构造的匿名函数,那么这个模块要热更的时候就比较麻烦了。可能必须得杀死这个常驻进程才能purge模块的老代码。
在实际工作过程中如果对热更机制缺乏了解就会犯这样的错误。在实现战斗技能的时候,前端要求如果技能杀死对象要统一结算。所以一开始实现的时候会
被杀死的对象的处理函数写成匿名函数然后存到地图进程的进程字典。结果发现有时候战斗的逻辑无法热更(因为我们热更线上的代码都是采用soft_purge,不会强制杀死进程)。

还有一个例子就是实现玩法活动的时候,管理进程会创建一些回调函数到场景进程,这些回调函数的参数一部分由管理进程提供,一部分由地图进程提供,写成匿名函数的话非常方便。
但是这样的话导致活动期间活动的逻辑代码无法热更。因为要热更就必须杀死场景进程。因此这种做法应该是尽量避免的。

检查系统中的老代码:

1
2
3
4
5
6
7
8
f(OldMods),OldMods = lists:filtermap(
fun({Module, Filename}) ->
is_list(Filename) andalso
erlang:check_old_code(Module) andalso
{true, Module}
end,
code:all_loaded()
).

检查系统中老代码无法被purge的模块:

1
2
3
4
5
6
lists:filtermap(
fun(Module) ->
not code:soft_purge(Module)
end,
OldMods
).

找出还在执行老代码Mod的进程信息:
[process_info(Pid)||Pid<-processes(),erlang:check_process_code(Pid, Mod)].

杀进程。一般先monitor,再kill,等待接收moniter消息,确认当前进程杀死。因为被杀死的进程可能需要进行一些清理的行为,如果不等待它确认死亡就将执行后续操作如移除代码,可能会导致清理过程出现找不到代码的问题。

code_server中杀死进程的过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
%% do_purge(Module)
%% Kill all processes running code from *old* Module, and then purge the
%% module. Return true if any processes killed, else false.

do_purge(Mod0) ->
Mod = to_atom(Mod0),
case erlang:check_old_code(Mod) of
false -> false;
true -> do_purge(processes(), Mod, false)
end.

do_purge([P|Ps], Mod, Purged) ->
case erlang:check_process_code(P, Mod) of
true ->
Ref = erlang:monitor(process, P),
exit(P, kill),
receive
{'DOWN',Ref,process,_Pid,_} -> ok
end,
do_purge(Ps, Mod, true);
false ->
do_purge(Ps, Mod, Purged)
end;
do_purge([], Mod, Purged) ->
catch erlang:purge_module(Mod),
Purged.

直接purge有杀死进程的危险性,所以code_server也提供了soft_purge,如果有进程仍在执行老代码,则不移除老代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
%% do_soft_purge(Module)
%% Purge old code only if no procs remain that run old code.
%% Return true in that case, false if procs remain (in this
%% case old code is not purged)

do_soft_purge(Mod) ->
case erlang:check_old_code(Mod) of
false -> true;
true -> do_soft_purge(processes(), Mod)
end.

do_soft_purge([P|Ps], Mod) ->
case erlang:check_process_code(P, Mod) of
true -> false;
false -> do_soft_purge(Ps, Mod)
end;
do_soft_purge([], Mod) ->
catch erlang:purge_module(Mod),
true.

热更机制

在开发环境中,可以使用Mochiweb的reloader模块来进行热更。reloader的实现机制主要是每隔一秒钟检测一次系统中加载的代码对应的beam文件时间戳,
如果发现时间戳从上次检测以来发生了变更,就执行热更新。在开发中使用起来非常方便。我们只需要编译代码,系统自动进行加载。
但是reloader的热更新用的是purge,也就是说如果你的进程持有热更模块的匿名函数引用,或者不符合otp规范,比如进程的主循环用的是短名函数,那么就存在进程被杀死的风险。
reloader的核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
doit(From, To) ->
[case file:read_file_info(Filename) of
{ok, #file_info{mtime = Mtime}} when Mtime >= From, Mtime < To ->
reload(Module);
{ok, _} ->
unmodified;
{error, enoent} ->
%% The Erlang compiler deletes existing .beam files if
%% recompiling fails. Maybe it's worth spitting out a
%% warning here, but I'd want to limit it to just once.
gone;
{error, Reason} ->
io:format("Error reading ~s's file info: ~p~n",
[Filename, Reason]),
error
end || {Module, Filename} <- code:all_loaded(), is_list(Filename)].

reload(Module) ->
io:format("Reloading ~p ...", [Module]),
code:purge(Module), %% **watch out**
case code:load_file(Module) of
{module, Module} ->
io:format(" ok.~n"),
case erlang:function_exported(Module, test, 0) of
true ->
io:format(" - Calling ~p:test() ...", [Module]),
case catch Module:test() of
ok ->
io:format(" ok.~n"),
reload;
Reason ->
io:format(" fail: ~p.~n", [Reason]),
reload_but_test_failed
end;
false ->
reload
end;
{error, Reason} ->
io:format(" fail: ~p.~n", [Reason]),
error
end.

实际上Erlang Shell中提供的函数的热更函数l(Module)实现就是直接purge,shell提供的函数实现在c.erl文件中,

1
2
3
l(Mod) ->
code:purge(Mod),
code:load_file(Mod).

直接load代码存在杀死进程的危险,所以一种安全的热更机制应该先尝试soft purge,如果成功,则加载代码,失败则放弃更新。
检查代码是否有改变:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
%% @doc Return a list of beam modules that have changed.
all_changed() ->
[M || {M, Fn} <- code:all_loaded(), is_list(Fn), is_changed(M)].

%% @spec is_changed(atom()) -> boolean()
%% @doc true if the loaded module is a beam with a vsn attribute
%% and does not match the on-disk beam file, returns false otherwise.
is_changed(M) ->
try
module_vsn(M:module_info()) =/= module_vsn(code:get_object_code(M))
catch _:_ ->
false
end.

%% Internal API

module_vsn({M, Beam, _Fn}) ->
{ok, {M, Vsn}} = beam_lib:version(Beam),
Vsn;
module_vsn(L) when is_list(L) ->
{_, Attrs} = lists:keyfind(attributes, 1, L),
{_, Vsn} = lists:keyfind(vsn, 1, Attrs),
Vsn.

函数code:get_object_code(Module)在代码路径下查找模块 Module 的目标代码,如果找到,则返回 {Module, Binary, Filename},否则返回 error

尝试更新代码:

1
2
3
4
case soft_purge(Mod) of
true -> code:load_file(Mod);
false -> error
end

参考文档

事务需要满足ACID特征。Mysql的innodb引擎支持事务。

  • 原子性,Atomicity, 一个事务是不可分割的整体,要么全部成功(committed),要么全部失败(rolled back),不存在部分成功。
  • 一致性,Consistency,数据总是从一致性的状态转移到另一个一致性的状态,总是处于有意义的状态。比如转账,A的钱减少,B的钱增加,总和是不变的。
  • 隔离性,Isolation,主要解决多个事务并发读写的问题,一个事务未提交,那么它对数据的修改对外是不可见的。
  • 持久性,Durability,一个事务一旦提交,对数据的影响的永久性的,就算断电,系统崩溃也是如此。

四个性质最根本的是一致性,其他三个性质都是服务于一致性的。

隔离级别

当多个进程的事务同时读写数据时,就会出现一些问题。

  • 脏读,dirty read,一个事务可以读到其他事务尚未提交的修改。尚未提交意味着可能回滚,那么该事务读到的就是无效的数据。
  • 不可重复读,unrepeatable read,同一个事务范围内多次查询却返回了不同的数据,这是因为在查询间隙,数据被另外的事务修改了(update, delete)。
  • 虚读,幻读,phantom read,同一个事务范围内,相同的操作两次读取的记录数不一样,比如多出来一行(add)。跟不可重复读的对象不一样,幻读针对的是一批数据,而后者指的是同一个数据。

innodb通过不同的锁策略支持四个级别的隔离性。

  • Read uncommitted,最低级别,任何情况都无法保证。
  • Read committed,可避免脏读。
  • Repeatable read,在Sql标准中,RR级别可避免脏读和不可重复读,但是还存在幻读。RR是innodb的默认级别,innodb的RR解决了幻读的问题。
  • Serializable,最高级别,可避免脏读,不可重复读,幻读的发生,效率最低,一般通过锁表来实现。
隔离级别 脏读 不可重复读 幻读
未提交读 Yes Yes Yes
已提交读(RC) No Yes Yes
可重复读(RR) No No Yes(注:Innodb的RR级别通过gap锁解决了幻读)
可串行化 No No No

mysql中查看隔离级别:

1
2
3
4
5
6
7
mysql> select @@global.tx_isolation, @@tx_isolation;
+-----------------------+----------------+
| @@global.tx_isolation | @@tx_isolation |
+-----------------------+----------------+
| READ-COMMITTED | READ-COMMITTED |
+-----------------------+----------------+
1 row in set (0.00 sec)

innodb可以通过下面的命令设置隔离级别,注意带global, session或者都不带效果是不一样的。

1
set [global | session] transaction isolation level [read uncommitted |read committed |repeatable read | serializable];
  • With the GLOBAL keyword, the statement applies globally for all subsequent sessions. Existing sessions are unaffected.
  • With the SESSION keyword, the statement applies to all subsequent transactions performed within the current session.
  • Without any SESSION or GLOBAL keyword, the statement applies to the next (not started) transaction performed within the current session. Subsequent transactions revert to using the SESSION isolation level.

在事务内部无法修改下一个事务的隔离级别:

1
2
3
4
5
6
7
8
mysql> begin;
Query OK, 0 rows affected (0.00 sec)
mysql> set transaction isolation level serializable;
ERROR 1568 (25001): Transaction isolation level can't be changed while a transaction is in progress
mysql> commit;
Query OK, 0 rows affected (0.00 sec)
mysql> set transaction isolation level serializable;
Query OK, 0 rows affected (0.00 sec)

或者

1
2
3
4
set tx_isolation = 'read-uncommitted';
set tx_isolation = 'read-committed';
set tx_isolation = 'repeatable-read';
set tx_isolation = 'serializable';

2PL: Two-Phase Locking

传统 RDBMS 加锁的一个原则,二阶段锁。锁操作分为两个阶段:加锁阶段和解锁阶段,并且保证加锁阶段和解锁阶段不相交。

  • 加锁阶段:只加锁,不放锁。
  • 解锁阶段:只放锁,不加锁。

行锁

如果一个条件无法通过索引快速过滤,存储引擎层面就会将所有记录加锁后返回,再由MySQL Server层进行过滤。
但在实际使用过程当中,MySQL做了一些改进,在MySQL Server过滤条件,发现不满足后,会调用unlock_row方法,把不满足条件的记录释放锁 (违背了二段锁协议的约束)。
这样做,保证了最后只会持有满足条件记录上的锁,但是每条记录的加锁操作还是不能省略的。可见即使是MySQL,为了效率也是会违反规范的。

这种情况同样适用于MySQL的默认隔离级别RR。所以对一个数据量很大的表做批量修改的时候,如果无法使用相应的索引,
MySQL Server过滤数据的的时候特别慢,就会出现虽然没有修改某些行的数据,但是它们还是被锁住了的现象。

MVCC多版本并发控制

与MVCC相对的,是基于锁的并发控制,Lock-Based Concurrency Control,最大的好处是,读不加锁,读写不冲突。
InnoDB中,每行数据后添加两个额外的隐藏的值来实现MVCC。一个记录这行数据何时被创建,另外一个记录这行数据何时过期(或者被删除)。
在实际操作中,存储的并不是时间,而是事务的版本号。每开启一个新事务,事务的版本号就会递增。
在RR事务隔离级别下:

  • select时,读取创建版本号<=当前事务版本号,删除版本号为空或者大于当前事务版本号的记录。
  • insert时,保存当前事务版本号为行的创建版本号。
  • delete时,保存当前事务版本号位行的删除版本号。
  • update时,插入一条新记录,保存当前事务版本号为行创建版本号,同时保存当前事务版本号为原来行的删除版本号。

通过MVCC,每行记录都需要额外的存储空间,更多的行检查工作和额外的维护工作,但是可以减少锁的使用。大多数操作都不用加锁。
读数据操作很简单,性能很好,并且也能保证只会读取到符合标准的行,也只锁住必要行。

Mysql的RR级别是解决了幻读的问题的。

快照读 snapshot read

简单的select操作,属于快照读,读取记录的可见版本,不用加锁。

  • select * from table where ?;

当前读 current read

特殊的读操作,以及插入,更新,删除操作,属于当前读。

  • select * from table where ? lock in share mode;
  • select * from table where ? for update;
  • insert into table values (…);
  • update table set ? where ?;
  • delete from table where ?;

读取的是记录的最新版本,并且当前读返回的记录,都会加上锁,保证其他事务不会再并发修改这条记录。
除了第一条语句对读取记录加S锁(共享锁)外,其他的操作都加的是X锁(排它锁)。

GAP间隙锁

幻读无法通过行锁来解决。
行锁防止别的事务修改或删除,GAP锁防止别的事务新增,行锁和GAP锁结合形成的的Next-Key锁共同解决了RR级别在写数据时的幻读问题。

有索引的时候,Gap锁很多时候会锁住不需要锁的区间。
没有索引的时候,Gap锁会锁住所有记录,但是innodb不会主动升级表锁。

Serializable

不区分快照读与当前读,所有读操作均为当前读。
读加共享锁(S锁),写加排它锁(X锁),读写互斥。使用悲观锁的理论,实现简单,数据更加安全,但是并发能力非常差。如果你的业务并发特别少或者没有并发,
同时有要求数据及时可靠的话,可以使用这种模式。这个级别下select也是会加锁的。

死锁

死锁的本质是两个以上的session对资源的加锁顺序不一致。解决死锁的关键在于让不同的session加锁有次序。

参考文档

通过-S选项可以将erl源文件编译成汇编文件。

1
$ erlc -S test.erl

反编译

1
beam_lib:chunks("hw.beam", [abstract_code]).

数据区

  • Code area,代码区,存放加载的编译的Erlang代码。
  • stack,调用栈,保存call frames调用帧,包括局部变量以及返回地址。
  • heap,堆,执行过程中创建的term。
    堆和栈位于同一块内存区域的两端,向彼此的方向增长,栈从高地址向低地址增长,堆从低地址向高地址增长,这种实现使得判别内存是否溢出非常简单,只要比较一下寄存器中的两个指针的大小即可。
    每个调用帧以一个返回地址CP开始,接着是局部变量。局部变量通过距离栈顶的偏移值来访问。调用帧的分配和回收通过A_op和D_op指令完成,指令后面跟调用帧的大小N。
    调用帧也能包含catch的恢复地址和下一条指令的地址。

Erlang虚拟机允许调用c编译的函数,当调用编译成c的函数,下条指令地址I保存在调用帧。CP指针指向的是函数返回时恢复I指针的代码地址。

数据对象

一个Erlang term以一个32位的无符号数表示,分为value和tag。tag为最低位4bit,用于区分term的类型。

  • 对于atom,value字段是全局atom表的索引地址。
  • 对于小整数,value字段就是整数本身。
  • 对于大整数,value是指向堆对象的一个指针,堆对象包含了整数的符号以及数字。
  • 对于list,value是一个指针,指向两个连续的堆对象,一个头,一个尾。
  • 对于tuple,指向的是堆对象,包含tuple的大小以及tuple的元素。
  • 对于浮点数,指向的是一个两个字的浮点数。
  • 对于pid,value就是pid本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define SMALL          15              /* small integer       */
#define BIG 11 /* big integer pointer */
#define FLOAT 9 /* float pointer */
#define ATOM 7 /* atom */
#define REFER 6 /* reference */
#define PORT 5 /* port */
#define PID 3 /* process identifier */
#define TUPLE 2 /* tuple pointer */
#define NIL (BIG + 16) /* empty list */
#define LIST 1 /* list pointer */
#define ARITYVAL 10 /* tuple arity */
#define MOVED 12 /* moved heap pointer */
#define CATCH THING /* resumption address */
#define THING 13 /* float value */
#define BINARY 14 /* binary pointer */
#define BLANK ARITYVAL /* blank local var */
#define IC SMALL /* next instr. pointer */

#define CP0 0 /* CP pointer */
#define CP4 4 /* CP pointer */
#define CP8 8 /* CP pointer */
#define CP12 12 /* CP pointer */

由于有些数据只可能存在堆或栈中,所以同样的tag可以被两个不同的对象使用。如CATCH和THING,BLANK和ARITYVAL。

寄存器

  • HTOP,堆顶指针
  • E,栈顶指针
  • CP,Continuation Pointer, 返回地址指针(函数返回后去哪里)
  • PC,Program Counter,下一条执行指令地址
  • I,下一个指令地址
  • x(N),1024个x寄存器,参数寄存器(用来传递函数参数),x(N)也用来保存临时变量
  • y(N),局部变量,(y(N)并不是真的寄存器,他们存在于调用帧中,通过栈顶指针的偏移值来访问)
  • fcalls,reduction计数,用于进程调度

重要的指令

函数调用时, 把参数加载到参数寄存器x(N), 更新返回地址寄存器CP,函数返回时,返回值保存在x(0)

  • test
  • move {move, Src, Dest}
  • gc_bif
  • call {call, Arity, {f, N}}
    • set P=N, CP=Next
    • jumps to label N
    • arguments are stored in X0 ~ Xn
  • return
    • does PC=CP
    • return value is stored in X0
  • receive
  • allocate
  • deallocate {deallocate, N}
    • create and remove stack frames.
    • there also exists {allocate_zero, Ny, Ng} - Ny Y registers
  • label {label, N}
    • Nth label in the module
  • function {function, Name, Arity, LabelID}
    • defines a function
  • bif {bif, FuncAtom, {f, 0}, [], {x, 0}}
  • gc_bif {gc_bif, '*', {f, A}, N1, [R1, R2, R3]}
    • jumps to a function named '*'
    • multiply R1 and R2, and set the result into R3. If any failure occurs jump to A. If GC is triggered include N1 X registers starting at X0 in the root set for GC.
  • send send.
    • sends the data in X0 ?
  • loop_rec {loop_rec, {f, N}, {x, 0}}
    • receive clause starts here, till loop_rec_end
  • wait_timeout {wait_timeout, {f, N}, {integer, T}}
  • test {test, is_eq_exact, {f, N}, [{x,0}, {atom, foo}]}
  • remove_message.

并发

每个进程有自己的堆栈空间,进程执行固定数量的reduction以后挂起加入调度队列,然后调度器从队列中取出第一个进程执行。
每个进程有自己的消息队列,发消息意味着拷贝消息到目标进程的堆中,并将消息地址加入目标进程的消息队列中。
进程在等待消息的时候被交换出去,直到有新消息到来或者超时的时候重新加入调度队列。

参考文档

Selective Receive

Joe的Programming Erlang中讲到了Selective Receive的时候,提到了一个save queue的概念。

1
2
3
4
5
6
7
8
9
10
11
> receive
> Pattern1 [when Guard1] ->
> Expressions1;
> Pattern2 [when Guard2] ->
> Expressions2;
> ...
> after
> Time ->
> ExpressionsTimeout
> end
>
  • When we enter a receive statement, we start a timer (but only if an after section is present in the expression).
  • Take the first message in the mailbox and try to match it against Pattern1, Pattern2, and so on. If the match succeeds, the message is removed from the mailbox, and the expressions following the pattern are evaluated.
  • If none of the patterns in the receive statement matches the first message in the mailbox, then the first message is removed from the mailbox and put into a “save queue.” The second message in the mailbox is then tried. This procedure is repeated until a matching message is found or until all the messages in the mailbox have been examined.
  • If none of the messages in the mailbox matches, then the process is suspended and will be rescheduled for execution the next time a new message is put in the mailbox. Note that when a new message arrives, the messages in the save queue are not rematched; only the new message is matched.
  • As soon as a message has been matched, then all messages that have been put into the save queue are reentered into the mailbox in the order in which they arrived at the process. If a timer was set, it is cleared.
  • If the timer elapses when we are waiting for a message, then evaluate the expressions ExpressionsTimeout and put any saved messages back into the mailbox in the order in which they arrived at the process.

在进入一个receive语句的时候,没有被匹配的消息被临时移到save queue中,等当前receive语句匹配到消息以后再移回消息队列。那么为什么不能直接丢弃这些没有被匹配的消息呢?
要回答这个问题,就不能把思维局限在一个receive语句。实际上,在进程中,receive语句可以是嵌套,可以是串联的,当前不能匹配的消息,是可能在嵌套的receive或者后续的receive匹配到的。
丢弃消息会出现问题。当然为了防止未知消息的堆积,一般会有一个匹配一切的语句,remove掉不需要的消息。

selective receive

嵌套的receive:

1
2
3
4
5
6
7
8
9
loop() ->
receive
{smoke, Smoker, AvailableMaterials} ->
Smoker ! smoke,
receive
doneSmoke ->
loop()
end
end

以及:

1
2
3
4
5
6
7
8
9
10
11
12
13
loop() ->
receive
{high_prio, Msg} ->
process_high;
after 0 ->
receive
{low_prio, Msg} ->
process_low;
_ ->
ok
end
end,
loop()

串联的receive:

1
2
3
4
5
6
receive
foo -> ok
end,
receive
bar -> ok
end

验证

启动一个分布式节点,方便通过远程shell连过来。

1
2
(foo@deng)1> erlang:register(shell,self()).
true

向shell进程发消息,并进入匹配。

1
2
3
4
5
6
7
8
9
(foo@deng)2> self() ! c, self() ! d, self() ! a.
a
(foo@deng)3> process_info(self(),messages).
{messages,[c,d,a]}
(foo@deng)4> receive a -> ok end.
ok
(foo@deng)5> process_info(self(),messages).
{messages,[c,d]}
(foo@deng)6> receive a -> ok end.

这时候shell进入了receive的等待过程,按照之前的说法,这时候shell的消息队列应该为空,我们通过远程shell连上来查看shell的消息队列。

1
2
(foo@deng)3> process_info(whereis(shell),messages).
{messages,[c,d]}

我们看到shell的进程队列并不为空。

求证

在官网上找到一段对receive的描述:

Each process has its own input queue for messages it receives. New messages received are put at the end of the queue. When a process executes a receive, the first message in the queue is matched against the first pattern in the receive. If this matches, the message is removed from the queue and the actions corresponding to the pattern are executed.

However, if the first pattern does not match, the second pattern is tested. If this matches, the message is removed from the queue and the actions corresponding to the second pattern are executed. If the second pattern does not match, the third is tried and so on until there are no more patterns to test. If there are no more patterns to test, the first message is kept in the queue and the second message is tried instead. If this matches any pattern, the appropriate actions are executed and the second message is removed from the queue (keeping the first message and any other messages in the queue). If the second message does not match, the third message is tried, and so on, until the end of the queue is reached. If the end of the queue is reached, the process blocks (stops execution) and waits until a new message is received and this procedure is repeated.

The Erlang implementation is “clever” and minimizes the number of times each message is tested against the patterns in each receive.

并没有提到save queue,消息没有被匹配的时候是留在消息队列中的。

深入源码

beam_receive.erl文件中有这么一段:

In code such as:

1
2
3
4
5
6
7
8
>    Ref = make_ref(),        %Or erlang:monitor(process, Pid)
> .
> .
> .
> receive
> {Ref,Reply} -> Reply
> end.
>

we know that none of the messages that exist in the message queue
before the call to make_ref/0 can be matched out in the receive
statement. Therefore we can avoid going through the entire message
queue if we introduce two new instructions (here written as
BIFs in pseudo-Erlang):

1
2
3
4
5
6
7
8
9
10
>    recv_mark(SomeUniqInteger),
> Ref = make_ref(),
> .
> .
> .
> recv_set(SomeUniqInteger),
> receive
> {Ref,Reply} -> Reply
> end.
>

The recv_mark/1 instruction will save the current position and
SomeUniqInteger in the process context. The recv_set
instruction will verify that SomeUniqInteger is still stored
in the process context. If it is, it will set the current pointer
for the message queue (the next message to be read out) to the
position that was saved by recv_mark/1.

The remove_message instruction must be modified to invalidate
the information stored by the previous recv_mark/1, in case there
is another receive executed between the calls to recv_mark/1 and
recv_set/1.

We use a reference to a label (i.e. a position in the loaded code)
as the SomeUniqInteger.

beam_emu.c文件中画出了receive语句的执行流程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Skeleton for receive statement:

recv_mark L1 Optional
call make_ref/monitor Optional
...
recv_set L1 Optional
L1: <-------------------+
<-----------+ |
| |
loop_rec L2 ------+---+ |
... | | |
remove_message | | |
jump L3 | | |
... | | |
loop_rec_end L1 --+ | |
L2: <---------------+ |
wait L1 -----------------+ or wait_timeout
timeout

L3: Code after receive...

erl_process.h定义了process结构,包含两个队列,一个公共队列,对于支持SMP的进程,可能存在多个进程同时向一个进程写消息的情况,这种情况下需要给消息队列加锁,这意味着进程自己处理消息的时候也需要加锁。
为了提高效率,引入了一个ErlMessageInQueue,其他进程先把消息写入这个进程,进程自己通过ErlMessageQueue来读取消息。这里我们重点关注ErlMessageQueue.

1
2
3
4
5
6
7
struct process {
#ifdef ERTS_SMP
ErlMessageInQueue msg_inq;
#endif
ErlMessageQueue msg; // message queue
...
}

ErlMessageQueue的结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct{
ErlMessage* first;
ErlMessage** last; /* point to the last next pointer */
ErlMessage** save;
Sint len; /* queue length */
/*
* The following two fields are used by the recv_mark/1 and
* recv_set/1 instructions.
*/
BeamInstr* mark; /* address to rec_loop/2 instruction */
ErlMessage** saved_last; /* saved last pointer */
}

获取当前消息,读取的是save指针指向的消息,最开始进入匹配的时候,save是指向链表头的,消息匹配不成功以后save向后移。

1
2
/* Get "current" message */
#define PEEK_MESSAGE(p) (*(p)->msg.save)

下面我们通过汇编文件来分析receive的过程,先编辑一个源文件:

1
2
3
4
5
6
7
8
-module(test).

-compile(export_all).

t() ->
receive
ok -> ok
end.

编译:

1
2
3
4
1> c(test).
{ok,test}
2> erts_debug:df(test).
ok

在目录下找到test.dis文件,找到函数t的实现:

1
2
3
4
5
6
7
08235938: i_func_info_IaaI 0 test t 0
0823594C: i_loop_rec_fr f(08235974) x(0)
08235954: i_is_eq_exact_immed_frc f(0823596C) x(0) ok
08235960: remove_message
08235964: move_return_cr ok x(0)
0823596C: loop_rec_end_f test:t/0
08235974: wait_locked_f test:t/0

实现在beam_emu.c中:

  • i_loop_rec_fr: Pick up the next message and place it in x(0), If no message, jump to a wait or wait_timeout instruction.
  • loop_rec_end_f: Advance the save pointer to the next message (the current message didn’t match), then jump to the loop_rec instruction.

结论

实际上并不存在save queue这一实体,也不存在消息在save queuemessage queue之间相互拷贝,save queue可能只是老爷子为了说阐述消息匹配机制引入的一个抽象。
消息没有匹配到的时候只是将save指针向后移一个单位。

  • 对于每一次receive,每个消息最多匹配一次。没有匹配的消息在有新消息进来的时候并不会重新匹配,而是直接匹配新消息。
  • 一旦有消息匹配完成或者超时,save指针重置,意味着下次进入receive仍然要消息队列的最开始进行匹配。无法匹配的消息这时候会再次进行匹配。可以通过make_ref来避免。
  • 要防止进程中存在无法匹配的消息。因为消息堆积起来对性能产生负面影响,每次receive都会对这些消息进行匹配。

PS:本文所有实现基于R1603版本。

参考

行为树,英文是Behavior Tree,简称BT,是由行为节点组成的树状结构。行为树的每个节点都会返回一个状态,成功,失败,运行,父节点根据子节点的返回值做出相应的决策。在游戏开发中,行为树主要用来实现怪物AI的行为决策,根据条件以及环境来决定怪物执行什么样的行为,如攻击,逃跑,巡逻,休息等。

为什么使用行为树

怪物行为的控制一般来说有三种方法,

  • 最简单的if-else嵌套。这种方法最直观,但是维护起来比较困难。
  • 第二种方法是有限状态机。根据怪物当前所处的状态和当前的环境,决定状态如何迁移。当状态较多时,状态之间的迁移会比较复杂。而且增加状态时需要改动的地方很多。
  • 行为树相对于前两种方式的优势在于,他实现了控制逻辑与行为逻辑的分离,控制逻辑就是行为树,行为逻辑则是各个行为节点。
    对于游戏开发来说,我们可以让策划通过行为树编辑器来编辑行为树,程序只需要实现具体的行为节点,就可以实现行为决策。

组成部分

行为树的结构如图。

bt architecture

行为树有四种类型的节点,分别是

  • 控制节点,最主要的是选择节点(Selector)和顺序节点(Sequence)。控制节点都不是叶子节点,它根据子节点的返回值返回成功,失败,运行这三种状态。
  • 行为节点,具体的行为逻辑,如逃跑,巡逻。行为节点一般是叶子节点,返回成功,失败,运行这三种状态。
  • 条件节点,叶子节点,返回成功,失败这两种状态。
  • 装饰节点,非叶子节点,实现一些附加的逻辑。如取反。

每个执行AI的实体拥有一个Tick实例,这个实例保存了这个执行实体的状态参数,以及一个可读写的黑板。
黑板(blackboard)是行为树实现中用来存储变量,感知环境的一个概念,节点可以访问黑板来存取变量。
执行实体的数据可以直接写入黑板,而行为树节点的执行数据需要加上节点id写入黑板。

行为树一般以一定的频率周期性的执行tick函数,每次tick都从根节点开始执行。有一些行为树会直接从返回运行的节点开始执行,这样的话如果有低优先级的节点一直返回运行状态,
遇到高优先级的节点时则无法打断低优先级的节点。比如怪物在巡逻的时候返回运行,这时候如果有玩家攻击它,合理的反应是进行反击或者逃跑,但是如果每次tick都从巡逻节点开始执行,
则根本不会处理到反击或逃跑的逻辑。

具体实现

Erlang版行为树的具体实现参考了Behavior3的版本。每个节点的有5个回调函数。

  • enter_cb 每次tick都会执行
  • open_cb 只有未打开的节点会执行,如果节点有running状态,意味着节点处于running状态会跨越多个tick,然而只有打开节点的那个tick会执行该函数。
    主要用来执行节点的初始化。比如移动节点设置目标点。等待节点用来设置开始时间等。
  • tick_cb 节点的主逻辑。每个tick都会执行。
  • close_cb 跟open_cb对应,只有结束节点的时候执行。意味着跨越多个tick的runing节点这个函数只会执行一次。一般用来关闭节点。
  • exit_cb 每个tick都会执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
execute(#node{id = Id} = Node, #tick{blackboard = Blackboard} = Tick) ->
Tick1 = enter_cb(Node, Tick),
Tick2 = case get_key({is_open, Id}, Blackboard, false) of
false -> open_cb(Node, Tick1);
true -> Tick1
end,
{Status, Tick3} = tick_cb(Node, Tick2),
Tick4 = case Status of
running -> Tick3;
_ -> close_cb(Node, Tick3)
end,
Tick5 = exit_cb(Node, Tick4),
{Status, Tick5}.

选择节点priority,顺序执行子节点,如果子节点返回成功则返回成功,跳过后续子节点。
如果失败则继续执行后面的子节点,直到有节点返回成功或者运行为止。如果所有节点都失败,则返回失败。
如果子节点返回运行则该节点也返回运行。

如果需要记住上次运行的节点,下次直接从该运行子节点开始执行,可以使用mem_priority类型的节点。
如果子节点包含两个以上可能返回运行的子节点,则需要考虑是否使用mem_priority版本。

1
2
3
4
5
6
7
8
9
10
11
priority([], Tick) ->
{false, Tick};
priority([C|Children], Tick) ->
case execute(C, Tick) of
{true, NewTick} ->
{true, NewTick};
{running, NewTick} ->
{running, NewTick};
{false, NewTick} ->
priority(Children, NewTick)
end.

顺序节点,顺序执行子节点,如果子节点返回失败则返回失败,跳过后续子节点。
如果子节点返回成功,则继续执行后续子节点,直到有节点返回失败或者运行为止。如果所有子节点都成功,则返回成功,
如果子节点返回运行,则该节点也返回运行。

类似mem_priority, 顺序节点也有一个mem_sequence节点,如果有两个以上子节点可能返回运行状态,则需要考虑是否使用mem_sequence.
比如,怪物执行巡逻,顺序节点有两个子节点,分别执行移动到A点,和移动到B点,那么必须使用mem_sequence,
每次tick从上次运行的地方继续运行。否则怪物只会在A点附近反复移动,无法移动到B点。

1
2
3
4
5
6
7
8
9
10
11
sequence([], Tick) ->
{true, Tick};
sequence([C|Children], Tick) ->
case execute(C, Tick) of
{running, NewTick} ->
{running, NewTick};
{false, NewTick} ->
{false, NewTick};
{true, NewTick} ->
sequence(Children, NewTick)
end.

要注意的一个问题是,当出现高优先级的行为B1打断低优先级行为B2时,因为每次从根节点开始tick,B2的无法从内部正常的关闭。这时候需要在主逻辑上额外处理一下上上次打开的节点,
即调用一下这些节点的close函数。Behavior3的实现中通过比较本次的开放节点列表和上次的开放节点列表,找出上次开放,本次没有开放的节点来关闭,这样可能存在一个问题。
也就是当上次开放的节点在本次tick正常结束的情况下,仍然会被重新关闭一次,即一个节点关闭了两次。 Behavior3的实现就存在这样的bug。
解决的办法是,在判断节点是否需要关闭的时候,检测一下节点是否开放,如果是开放,则关闭,否则不予处理。
Erlang版本的实现中通过遍历行为树节点来找到未正常关闭的节点,考虑到行为树通常不会很大,性能上也可以接受。

遍历行为树关闭未能正常关闭的节点的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
close_nodes(_, _, [], Tick) -> Tick;
close_nodes(undefined, _, _, Tick) -> Tick;
close_nodes(#node{children = [], child = undefined} = Node, CurOpenNodes, LastOpenNodes, Tick) ->
close_node(Node, CurOpenNodes, LastOpenNodes, Tick);
close_nodes(#node{children = Children, child = undefined} = Node, CurOpenNodes, LastOpenNodes, Tick) ->
NewTick = close_node(Node, CurOpenNodes, LastOpenNodes, Tick),
lists:foldl(
fun(Child, Acc) ->
close_nodes(Child, CurOpenNodes, LastOpenNodes, Acc)
end,
NewTick,
Children
);
close_nodes(#node{children = [], child = Child} = Node, CurOpenNodes, LastOpenNodes, Tick) ->
NewTick = close_node(Node, CurOpenNodes, LastOpenNodes, Tick),
close_nodes(Child, CurOpenNodes, LastOpenNodes, NewTick).
close_node(#node{id = Id} = Node, CurOpenNodes, LastOpenNodes, #tick{blackboard = Blackboard} = Tick) ->
case lists:member(Id, LastOpenNodes) andalso
not lists:member(Id, CurOpenNodes) andalso
get_key({is_open, Id}, Blackboard, false) of
true ->
%%?DEBUG("close_node ~p", [Node]),
close_cb_(Node, Tick#tick{blackboard = dict:store({is_open, Id}, false, Blackboard)});
false ->
Tick
end.

参考文档