螺旋矩阵:由内向外,游戏掉落问题

2025-05-14 更新

  • 老代码是很早之前从一篇blog里抄来做改动的,很惭愧没有找到blog地址补在文档上
  • 新的部分基于AI生成
    以下是一篇关于“用 C++20 编写螺旋矩阵生成器”的博客文章,面向有一定 C++ 基础的开发者:

编译期构建螺旋矩阵路径:用 C++20 实现坐标映射

在某些游戏开发或图形处理场景中,我们经常需要以螺旋方式遍历一个二维矩阵,常见于地图填充、探索算法或邻域扩展。在本文中,我将用现代 C++20 技术实现一个编译期生成螺旋路径的工具,并支持运行期通过偏移顺序依次访问矩阵所有点。

问题定义

目标是构造一个螺旋矩阵偏移列表,满足:

  • 编译期生成固定大小的 (dx, dy) 坐标偏移数组。
  • 运行期只需传入任意起点 (x, y),即可遍历整个螺旋路径。
  • 路径以 (0, 0) 为中心开始,顺时针向外扩展。

实现思路

实现分两部分:

  1. 编译期生成路径:使用 constexprstd::array 构建偏移数组;
  2. 运行期应用偏移:传入起始点,加上偏移依次访问每个位置。

螺旋路径规则

遍历方向依次为:右 → 上 → 左 → 下。每走两轮,步长加一:

1
2
Step length: 1  → 1 → 2 → 2 → 3 → 3 → ...
Directions : → ↑ → ← ↓ ← ↑ → ...

举例:

1
2
3
4
5
6
7
(0,0)
→ (1,0)
↑ (1,1)
← (0,1) → (-1,1)
↓ (-1,0) → (-1,-1)
→ (0,-1) → (1,-1)
↑ (1,0) → (1,1) ...

C++20 代码实现

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
#include <array>
#include <utility>
#include <iostream>

constexpr std::pair<int, int> directions[] = {
{1, 0}, // → right
{0, 1}, // ↑ up
{-1, 0}, // ← left
{0, -1} // ↓ down
};

template <size_t N>
constexpr auto generate_spiral_offsets() {
std::array<std::pair<int, int>, N> offsets{};
int x = 0, y = 0;
size_t idx = 0;

int step = 1;
offsets[idx++] = {x, y}; // 起点

while (idx < N) {
for (int dir = 0; dir < 4; ++dir) {
int dx = directions[dir].first;
int dy = directions[dir].second;

int len = (dir / 2 + 1) * step;

for (int i = 0; i < len && idx < N; ++i) {
x += dx;
y += dy;
offsets[idx++] = {x, y};
}
if (dir % 2 == 1) ++step; // 每两轮增长一次
}
}
return offsets;
}

constexpr size_t count = 25;
constexpr auto spiral_offsets = generate_spiral_offsets<count>();

应用:遍历矩阵

运行时,我们只需加上起点 (origin_x, origin_y) 即可:

1
2
3
4
5
6
7
8
void print_spiral_from(int origin_x, int origin_y) {
for (auto [dx, dy] : spiral_offsets) {
int x = origin_x + dx;
int y = origin_y + dy;
std::cout << "(" << x << "," << y << ") ";
}
std::cout << '\n';
}




旧:

问题

  • 游戏内怪物死亡掉落一般要求是以死亡点为圆心向周围扩散找到可用点刷新场景道具
  • 画图可以看到这是一个螺旋矩阵问题
  • 以某个点为中心点,周围的坐标都是其相对坐标
  • 要求由内向外,矩阵样式如下代码注释
  • 使用静态变量提前初始化好矩阵,之后遍历矩阵的相对坐标就可以
  • 传送目标点等可用点搜索也可以用这个array

代码

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
42
43
44
45
46
47
48
49
50
51
/*
42 43 44 45 46 47 48
41 20 21 22 23 24 25
40 19 6 7 8 9 26
39 18 5 0 1 10 27
38 17 4 3 2 11 28
37 16 15 14 13 12 29
36 35 34 33 32 31 30
*/

// 坐标点
struct cell {
unsigned x = 0;
unsigned y = 0;
};

static constexpr int __helix_radius = 3;
static constexpr int __helix_size = (__helix_radius * 2 + 1) * (__helix_radius * 2 + 1);
static cell __cell_helix[__helix_size];

static int _helix(int x, int y) {
int t = std::max(std::abs(x), std::abs(y));
int u = t + t;
int v = u - 1;

v = v * v + u;
if( x == -t )
v += u + t - y;
else if( y == -t )
v += 3 * u + x - t;
else if( y == t )
v += t - x;
else
v += y - t;

return v - 1;
}

static bool _init_helix() {
for(int y = -1 * __helix_radius; y <= __helix_radius; ++y) {
for(int x = -1 * __helix_radius; x <= __helix_radius; ++x) {
cell& cpt = __cell_helix[_helix(x, y)];
cpt.x = x;
cpt.y = y;
}
}

return true;
}

static bool __call_init_helix = _init_helix();
------ 本文结束 ------
------ 版权声明:转载请注明出处 ------

欢迎关注我的其它发布渠道