Welcome Guest ( Log In | Register )

欢迎访问本站。游客仅能浏览首页新闻、版块主题、维基条目与资源信息,需登录后方可获得内容发布、话题讨论、维基编辑与资源下载等权限。若无账号请先完成注册流程。
 
Reply to this topicStart new topic
> 《再下一层(One More Level)》3 月开发日志
Bozar
2021-04-03, 18:34
Post #1


GEEKs will Eventually Evolve into Kryptonians. | All my jokes are cries for help.
Group Icon
 1347
   75

Group: Avatar
Posts: 1132
Joined: 2008-05-18
Member No.: 21346




> 秦时明月汉时关,二十二年人未还。
> 干将若有重铸日,游侠再无少年时。

《再下一层(One More Level)》是一款使用 [Godot 引擎](https://godotengine.org) 制作的回合制 Roguelike 游戏。最新版本是 0.3.0,可以通过 [GitHub](https://github.com/Bozar/OneMoreLevel/releases) 下载。这次我想讲一讲游戏中用到的两套视野算法:十字形视野(cross shaped field of view)和递归投影视野(recursive shadow casting field of view),因为篇幅问题分为上下两部分(本文即上篇,[下篇在此](https://trow.cc/board/showtopic=50128&st=0&gopid=208743&#))。两篇文章在 GitHub 上发布了英文版:

* [十字形视野](https://github.com/Bozar/DevBlog/wiki/Program_CrossShapedFOV)
* [递归投影视野](https://github.com/Bozar/DevBlog/wiki/Program_ShadowCastFOV)

十字形视野的原理是从指定位置出发,向上下左右四个方向发出射线。所有射线的宽度是一致的,但是最大距离可以分别指定。在当前版本里,轨道枪(Railgun)地下城采用了该视野:玩家人物穿过狭长走廊,正前方看得最远,两侧稍近些,身后只能看到一格。具体代码详见 [CrossShapedFOV.gd](https://github.com/Bozar/OneMoreLevel/blob/master/library/CrossShapedFOV.gd),[RailgunPCAction.gd](https://github.com/Bozar/OneMoreLevel/blob/4c04dc73b4fb8ce042bc02b725b256edbd721272/library/pc_action/RailgunPCAction.gd#L40) 提供了一个应用实例。

» Click to show Spoiler - click again to hide... «

图 1:十字形视野

如果要在 Godot 项目中使用 `CrossShapedFOV.gd`,首先在脚本里设置地下城的宽度和高度:

const DUNGEON_WIDTH: int = 21
const DUNGEON_HEIGHT: int = 15

然后载入并初始化脚本:

var _new_CrossShapedFOV := preload("res://library/CrossShapedFOV.gd").new()

该脚本提供了两个公共函数。首先用 `set_rectangular_sight()` 设置内部变量,然后用 `is_in_sight()` 检查某个位置是否在视野内。这两个函数的签名如下:

set_field_of_view(center_x: int, center_y: int,
face_x: int, face_y: int, half_width: int,
front_range: int, right_range: int,
back_range: int, left_range: int,
func_host: Object, is_obstacle_func: String,
opt_arg: Array) -> void

is_in_sight(x: int, y: int) -> bool

在 `set_rectangular_sight()` 里面,`center_x` 和 `center_y` 是射线的起始位置;`[face_x, face_y]` 只能是 `[0, y]` 或者 `[x, 0]`,它们表示正面的朝向,其它三个方向(左、右和背后)由此决定;射线的宽度等于 `half_width * 2 + 1`。我们还需要另一个来自 `func_host` 的函数 `is_obstacle_func(x: int, y: int, opt_arg: Array)`,用于检查某个格子是否挡住了射线,详见 Godot 文档([FuncRef](https://docs.godotengine.org/en/stable/classes/class_funcref.html#funcref))。

如果视野比较对称,不妨用 `set_t_shaped_sight()` 或者 `set_symmetric_sight()` 代替 `set_rectangular_sight()`。

set_t_shaped_sight(center_x: int, center_y: int,
face_x: int, face_y: int, half_width: int,
front_range: int, side_range: int,
func_host: Object, is_obstacle_func: String,
opt_arg: Array) -> void

set_symmetric_sight(center_x: int, center_y: int,
half_width: int, max_range: int,
func_host: Object, is_obstacle_func: String,
opt_arg: Array) -> void:

接下来看看视野算法的实现细节。在 `set_rectangular_sight()` 内部,我们发出四条射线,它们遇到障碍物或者到达最远距离后停止,返回一对最远距离的坐标。根据四组坐标,我们能够画出一个限定了视野范围的长方形,其位置记录在四个私有变量里:`_max_x`,`_max_y`,`_min_x` 和 `_min_y`。

^
| 左
|
<- 后 - @ - 前 ->
|
| 右
v

在 `is_in_sight()` 内部,我们首先检查某个位置是否在上述长方形里面,然后确认它是否足够靠近坐标轴。

func is_in_sight(x: int, y: int) -> bool:
if (x < _min_x) or (x > _max_x) or (y < _min_y) or (y > _max_y):
return false
elif (abs(x - _center_x) > _half_width) \
and (abs(y - _center_y) > _half_width):
return false
return true

回头来看 `set_rectangular_sight()`。它的核心是先发射一条射线,再更新长方形位置,循环四遍。

func set_rectangular_sight(...) -> void:
for i in ...:
end_point = _cast_ray(...)
_update_min_max(end_point[0], end_point[1])

函数 `_cast_ray()` 返回了射线终点的坐标。它需要至少三组参数:起始位置,射线能抵达的最远距离,以及设法判定某个格子是否阻挡射线。关于判定方法,我们可以把它直接写在视野脚本里,传递一个函数,传递一个实现了接口的对象,或者在 Godot 脚本里传递一个函数引用。具体做法不重要,不妨假定 `_cast_ray()` 接受了一个返回布尔值的函数 `_ray_is_blocked()`。

func _cast_ray(start_x: int, start_y: int, shift_x: int, shift_y: int,
max_range: int, ...) -> Array:
var x: int = start_x
var y: int = start_y

for _i in range(max_range):
x += shift_x
y += shift_y
if not _is_inside_dungeon(x, y):
x -= shift_x
y -= shift_y
break
elif _ray_is_blocked(x, y):
break
return [x, y]

请注意 `_cast_ray()` 还需要 `shift_x` 和 `shift_y` 这两个参数,因为我们要向四个方向发出射线,不妨让函数调用者决定发射方向。

函数 `_update_min_max()` 负责更新私有变量。

func _update_min_max(x: int, y: int) -> void:
if x > _max_x:
_max_x = x
elif x < _min_x:
_min_x = x

if y > _max_y:
_max_y = y
elif y < _min_y:
_min_y = y

在 `set_rectangular_sight()` 内部,我们需要给 `_cast_ray()` 传递四组参数。假定我们已经处理了 `face_x` 和 `face_y`,其中一个是 0,另一个是 1 或者 -1。接下来我们定义四组参数:

func set_rectangular_sight(center_x: int, center_y: int,
face_x: int, face_y: int, half_width: int,
front_range: int, right_range: int,
back_range: int, left_range: int, ...) -> void:
...

if face_x == 0:
cast_ray_arg = [
[face_x, face_y, front_range],
[face_x, -face_y, back_range],
[face_y, face_x, right_range],
[-face_y, face_x, left_range],
]
else:
cast_ray_arg = [
[face_x, face_y, front_range],
[-face_x, face_y, back_range],
[face_y, -face_x, right_range],
[face_y, face_x, left_range],
]

for i in cast_ray_arg:
end_point = _cast_ray(center_x, center_y, i[0], i[1], i[2], ...)
_update_min_max(end_point[0], end_point[1])

就这样我们用 Godot 脚本语言实现了十字形视野。



This post has been edited by Bozar: 2021-04-03, 18:35
TOP
Bozar
2021-04-03, 18:35
Post #2


GEEKs will Eventually Evolve into Kryptonians. | All my jokes are cries for help.
Group Icon
 1347
   75

Group: Avatar
Posts: 1132
Joined: 2008-05-18
Member No.: 21346




> 红拂夜奔,朱砂痣烙印胸口
> 卫公策马,眉间尺计上心头

这是三月开发日志的下篇,[上篇在此](https://trow.cc/board/showtopic=50128#)。

递归投影视野的原理详见这篇 [RogueBasin 文章](http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting)。[libtcod](https://libtcod.github.io/docs/html2/fov_compute.html) 和 [rot.js](http://ondras.github.io/rot.js/manual/#fov) 内置了这个视野算法,我用 Godot 脚本语言重新实现了一遍,详见 [ShadowCastFOV.gd](https://github.com/Bozar/OneMoreLevel/blob/master/library/ShadowCastFOV.gd)。在《再下一层(One More Level)》的最新版本里([0.3.0](https://github.com/Bozar/OneMoreLevel/releases/tag/0.3.0)),五个地下城使用了投影视野:气球(Balloon),沙漠(Desert),青蛙(Frog),骑士(Knight)和镜子(Mirror)。

» Click to show Spoiler - click again to hide... «

图 1:递归投影视野

如果要在 Godot 项目中使用 `ShadowCastFOV.gd`,首先在脚本里设置地下城的宽度和高度:

const DUNGEON_WIDTH: int = 21
const DUNGEON_HEIGHT: int = 15

然后载入并初始化脚本:

var _new_ShadowCastFOV := preload("res://library/ShadowCastFOV.gd").new()

该脚本提供了两个公共函数。首先用 `set_field_of_view()` 设置内部变量,然后用 `is_in_sight()` 检查某个位置是否在视野内。这两个函数的签名如下:

set_field_of_view(x: int, y: int, max_range: int,
func_host: Object, block_ray_func: String, opt_arg: Array) -> void

is_in_sight(x: int, y: int) -> bool

函数 `set_field_of_view()` 需要另一个来自 `func_host` 的函数 `block_ray_func(x: int, y: int, opt_arg: Array)`,用于检查某个格子是否挡住了射线,详见 Godot 文档([FuncRef](https://docs.godotengine.org/en/stable/classes/class_funcref.html#funcref))。[PCActionTemplate.gd](https://github.com/Bozar/OneMoreLevel/blob/4c04dc73b4fb8ce042bc02b725b256edbd721272/library/pc_action/PCActionTemplate.gd#L156) 提供了一个使用实例。

接下来分享一些实现算法过程中的注意事项。根据 RogueBasin 文章的说法,视野渲染分成四个步骤:

* 步骤 1:选择一个起始位置,把整个地下城分成八个区域。
* 步骤 2:选择一个区域。
* 步骤 3:渲染该区域。
* 步骤 4:按照类似步骤渲染其它区域。

步骤 1 很简单。通常我们把玩家人物的位置作为起始位置,然后按要求分割区域。但是接下来,首先选择哪个区域?渲染过程中有哪些容易忽视的细节?怎样在其它区域重复渲染步骤呢?

\ 5 | 6 /
\ | /
4 \ | / 7
[email protected]>
3 / | \ 0
/ | \
/ 2 | 1 \
|
v

我们从步骤 4 开始。首先假定 `_set_octant()` 渲染了区域 0。注意到在区域 0,随着 `x` 增长逐列扫描该区域;但是在区域 1,随着 `y` 增长逐行扫描该区域。扫描过程是一样的,区别仅在于坐标不同。如果坐标系原点是玩家人物所在位置,那么区域 0 和 1 的坐标之间存在如下对应关系:

x_2 = y_1
y_2 = x_1

如果坐标系原点在地图左上角,上述等式改写为:

x_2 - pc_x = y_1 - pc_y
y_2 - pc_y = x_1 - pc_x

因此:

x_2 = (y_1 - pc_y) + pc_x
y_2 = (x_1 - pc_x) + pc_y

在 `_set_octant()` 内部,如果我们把 `x_1` 和 `y_1` 转换成 `x_2` 和 `y_2`,就可以用同一个函数渲染两个区域了。详见下文,`_convert_coord()`。

接下来考虑步骤 2。选择哪个区域其实都可以,但是出于方便起见,不妨选择横坐标和纵坐标都是正的,并且斜率 `(y_2 - y_1) / (x_2 - x_1)` 不会增长到无穷大的分区。只有区域 0 和 1 的坐标均为正数,只有区域 0 的斜率不会增长到无穷大。因此我们把它选为第一个渲染区。

地下城里的每个格子都对应一个布尔值,用来表示它是否在视野内。假定 `_dungeon` 是一个用起来像二维数组的私有变量,我们可以这样实现 `is_in_sight()`:

func is_in_sight(x: int, y: int) -> bool:
return _dungeon[x][y]

在 `set_field_of_view()` 内部,首先把 `_dungeon` 里的每个布尔值重置为 `false`,然后针对每个分区调用 `_set_octant()`:

func set_field_of_view(...) -> void
_reset_dungeon()

# i = 0, 1, 2, ..., 7
for i in range(0, 8):
_set_octant(i, ...)

现在开始讨论怎样用 `_set_octant()` 渲染单个区域。假如只需要扫描区域 0,那么该函数包含了两个循环:随着 `x` 增长,递减地扫描每一列:

_set_octant(...) -> void
for x in range(source_x + 1, max_x, 1):
end_loop = true

for y in range(max_y, min_y, -1):
...
_set_octant(...)
...
if ...:
end_loop = false
...

if end_loop:
break

这里要注意三点。首先,函数 `_set_octant()` 是递归的。其次,起始坐标 `[source_x, source_y]` 在区域 0 之外,因此循环范围是从 `source_x + 1` 到 `max_x`。如果从 `source_x` 循环到 `max_x`,那么递归地调用 `_set_octant()` 时,应当输入 `new_x + 1` 而不是 `new_x`,因为对区域 0 来说,递归应该从下一列开始。最后,默认只扫描一列。当且仅当本列最后一格不阻挡射线时,才继续扫描下一列——请特别注意这个终止递归的条件。

函数 `_set_octant()` 显然需要以下参数:`source_x`,`source_y` 和 `max_x`。既然我们要根据斜率计算 `min_y` 和 `max_y`,该函数还需要两个斜率。因此 y 循环之外的代码改写如下:

_set_octant(source_x: int, source_y: int, max_x: int,
left_slope: float, right_slope: float, ...) -> void
for x in range(source_x + 1, max_x, 1):
max_y = ceil(right_slope * (x - source_x) + source_y) as int
min_y = floor(left_slope * (x - source_x) + source_y) as int
min_y -= 1
end_loop = true

for y in range(max_y, min_y, -1):
...

请注意对 y 轴来说,往下是正方向,另外我们把斜率定义为 `delta_y / delta_x`。如果一条射线经过某个格子,这个格子是在视野内的。因此 `max_y` 向上取整,`min_y` 向下取整。但是在 Godot 脚本里,`range(left_value, right_value)` 包括 `left_value` 但是不包括 `right_value`。为了把 `min_y` 纳入 y 循环,需要把它减 1。这是 Godot 脚本特有的问题。

在 y 循环内部,我们需要渲染一列格子。以下是大致框架:

for y in range(max_y, min_y, -1):
# 第 1 部分。
if not _is_inside_dungeon(x, y):
continue
_dungeon[x][y] = true

# 第 2 部分。
if _ray_is_blocked(x, y):
...
_set_octant(...)
# 第 3 部分。
else:
...
if _last_grid_is_not_blocked(y):
end_loop = false

if end_loop:
break

第 1 部分很简单。在第 2 部分,`_ray_is_blocked()` 这个函数决定了某个格子是否阻挡射线。我们有多种方法实现该函数:直接定义在视野脚本内部;把该函数作为参数传递给 `set_field_of_view()` 和 `_set_octant()`;传递实现了接口的对象;或者在 Godot 脚本里,传递一个函数引用。具体细节不重要,我们假定 `_ray_is_blocked()` 返回了一个布尔值。递归地调用 `_set_octant()`,如果当前格子阻挡了射线,并且上一个扫描的格子不阻挡射线。为了判定第二个条件,我们需要两个私有变量:`is_blocked` 和 `sub_y`。

for x in range(source_x + 1, max_x, 1):
...
is_blocked = false
for y in range(max_y, min_y, -1):
...
if _ray_is_blocked(x, y):
# 开始下一个循环,如果当前格不是第一个阻挡射线的格子。
if is_blocked:
continue
is_blocked = true
# 后退 1 格。如果当前格子已经超出区域 0 的范围,开始下一个循环。
sub_y = y + 1
if sub_y > max_y:
continue
# 计算新的左斜率。
sub_left_slope = _get_slope(source_x, source_y, x, sub_y)
# 递归地调用自身。
_set_octant(x, # 无变化。
sub_y, # 有变化。
max_x, # 无变化。
sub_left_slope, # 有变化。
right_slope, # 无变化。
...)

在第 3 部分,我们需要计算新的右斜率,并决定是否扫描下一列格子。

else:
# 一旦离开连续的障碍物,立即计算新的右斜率。
if is_blocked:
is_blocked = false
right_slope = _get_slope(source_x, source_y, x, y)
# 如果当前列最后一格没有阻挡射线,继续扫描下一列。
if y == min_y + 1:
end_loop = false

为了在其它区域使用函数 `_set_octant()`,我们需要在以下三个场合转换坐标:检查某个格子是否在地下城内,把 `_dungeon` 的某个值设为 `true`,检查某个格子是否阻挡射线。

for y in range(max_y, min_y, -1):
convert_x = _convert_coord(which_octant, x, y, true)
convert_y = _convert_coord(which_octant, x, y, false)

if not _is_inside_dungeon(convert_x, convert_y):
continue
_dungeon[convert_x][convert_y] = true

if _ray_is_blocked(convert_x, convert_y):
...

函数 `_convert_coord()` 把区域 `which_octant` 的坐标(`x` 和 `y`)转换成新坐标。变量 `which_octant` 是 `_set_octant()` 的一个参数。以上就是实现递归投影算法时的若干细节。



This post has been edited by Bozar: 2021-04-03, 18:36
TOP
Fast ReplyReply to this topicStart new topic
 


Time is now: 2021-04-13, 09:55