navmeshPre/main.html at main · ToasterToastsToast/navmeshPre · GitHub

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>NavMesh 与 Funnel 算法寻路演示</title>
    <style>
        :root {
            --bg-color: #f0f2f5;
            --slide-bg: #ffffff;
            --text-main: #1f2937;
            --text-muted: #4b5563;
            --primary: #3b82f6;
            --primary-hover: #2563eb;
            --code-bg: #f8fafc;
        }

        body {
            margin: 0;
            padding: 0;
            background-color: var(--bg-color);
            font-family: 'Segoe UI', Roboto, Helvetica, Arial, sans-serif;
            display: flex;
            flex-direction: column;
            align-items: center;
            justify-content: center;
            height: 100vh;
            overflow: hidden;
        }

        .presentation-container {
            width: 95%;
            max-width: 1300px;
            height: 88vh;
            background: var(--slide-bg);
            border-radius: 12px;
            box-shadow: 0 10px 25px rgba(0, 0, 0, 0.1);
            display: flex;
            flex-direction: column;
            position: relative;
        }

        .slide {
            display: none;
            flex: 1;
            padding: 50px 70px;
            animation: fadeIn 0.4s ease-in-out;
            overflow-y: auto;
        }

        .slide.active {
            display: flex;
            flex-direction: column;
            justify-content: center;
        }

        /* 标题页专用样式 */
        .title-slide {
            text-align: center;
            background: linear-gradient(135deg, #ffffff 0%, #f8fafc 100%);
        }

        .title-slide h1 {
            font-size: 4rem;
            margin-bottom: 20px;
            border-bottom: none;
            color: var(--primary);
        }

        .title-slide .subtitle {
            font-size: 1.8rem;
            color: var(--text-muted);
            margin-bottom: 50px;
        }

        .title-slide .author-info {
            margin-top: 40px;
            font-size: 1.2rem;
            color: #9ca3af;
        }

        .divider {
            width: 100px;
            height: 4px;
            background: var(--primary);
            margin: 0 auto 30px;
            border-radius: 2px;
        }

        @keyframes fadeIn {
            from {
                opacity: 0;
                transform: translateY(10px);
            }

            to {
                opacity: 1;
                transform: translateY(0);
            }
        }

        h1 {
            color: var(--primary);
            border-bottom: 2px solid #e5e7eb;
            padding-bottom: 15px;
            margin-top: 0;
            margin-bottom: 30px;
            font-size: 2.2rem;
        }

        h3 {
            color: var(--text-main);
            margin-bottom: 15px;
            font-size: 1.4rem;
        }

        ul {
            color: var(--text-muted);
            font-size: 1.25rem;
            line-height: 1.9;
            padding-left: 25px;
        }

        li {
            margin-bottom: 16px;
        }

        iframe {
            width: 100%;
            height: 100%;
            border: none;
            border-radius: 8px;
            min-height: 600px;
            box-shadow: inset 0 2px 4px rgba(0, 0, 0, 0.05);
        }

        .controls {
            display: flex;
            justify-content: space-between;
            align-items: center;
            padding: 20px 40px;
            background: #f9fafb;
            border-top: 1px solid #e5e7eb;
            border-radius: 0 0 12px 12px;
        }

        button {
            background-color: var(--primary);
            color: white;
            border: none;
            padding: 12px 28px;
            font-size: 1.1rem;
            border-radius: 6px;
            cursor: pointer;
            font-weight: 600;
            transition: background 0.2s;
        }

        button:hover {
            background-color: var(--primary-hover);
        }

        button:disabled {
            background-color: #9ca3af;
            cursor: not-allowed;
        }

        .progress {
            color: var(--text-muted);
            font-weight: 500;
            font-size: 1.1rem;
        }

        .highlight {
            color: #ef4444;
            font-weight: bold;
        }

        .layout-two-col {
            display: flex;
            gap: 50px;
            margin-top: 10px;
            flex: 1;
        }

        .col {
            flex: 1;
            display: flex;
            flex-direction: column;
            justify-content: flex-start;
        }

        pre {
            background-color: var(--code-bg);
            padding: 20px;
            border-radius: 8px;
            border: 1px solid #e2e8f0;
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            font-size: 1rem;
            line-height: 1.5;
            color: #334155;
            overflow-x: auto;
            flex: 1;
            margin: 0;
            box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1);
        }

        .math-box {
            background: #f0fdfa;
            border-left: 5px solid #0d9488;
            padding: 20px;
            border-radius: 0 8px 8px 0;
            margin-bottom: 25px;
            font-size: 1.15rem;
            line-height: 1.7;
        }

        .info-box {
            background: #f8fafc;
            border: 2px dashed #cbd5e1;
            border-radius: 8px;
            padding: 20px;
            margin-top: 20px;
            text-align: center;
        }
    </style>
</head>

<body>

    <div class="presentation-container">

        <div class="slide active title-slide">
            <h1>NavMesh 与 Funnel 算法</h1>
            <div class="divider"></div>
            <div class="subtitle">人工智能基础</div>
            <div class="author-info">
                周靖容
                2026/4/10
            </div>
        </div>

        <div class="slide">
            <h1>寻路算法的挑战：当空间变大</h1>
            <div class="layout-two-col">
                <div class="col">
                    <h3>传统网格 (Grid) 的困境</h3>
                    <ul>
                        <li>网格寻路在小规模环境中表现良好。</li>
                        <li>它将世界强行划分为一个个大小相等的正方形。</li>
                        <li><strong>致命缺陷：</strong>没有区分“大空地”和“走廊”，只要面积大，网格数量就多。</li>
                    </ul>
                </div>
                <div class="col">
                    <h3>性能与内存的考验</h3>
                    <ul>
                        <li>空间复杂时，网格数量呈指数级增长。</li>
                        <li><strong>A* 算法</strong>遍历海量网格会消耗极长的 CPU 计算时间。</li>
                        <li>大型开放世界游戏需要一种<strong>更高效的环境抽象方式</strong>。</li>
                    </ul>
                </div>
            </div>
        </div>

        <div class="slide">
            <h1>解决方案：NavMesh (导航网格)</h1>
            <div class="layout-two-col">
                <div class="col">
                    <h3>什么是 NavMesh？</h3>
                    <ul>
                        <li>源自 <strong>1986 年机器人学研究</strong>。</li>
                        <li>使用一系列<strong>相连的凸多边形</strong>，精准描绘地图中允许通过的区域集合。</li>
                        <li>多边形之间通过共享边（<strong>Portal/传送门</strong>）互相连接。</li>
                    </ul>
                </div>
                <div class="col">
                    <h3>核心：必须是“凸”多边形</h3>
                    <ul>
                        <li>凸多边形内部的任意两点连线，必定完全位于多边形内部。</li>
                        <li>只要 AI 和目标在同一个凸多边形内，<strong>可以直接走直线</strong>。</li>
                        <li>这让复杂的碰撞计算被极大地简化。</li>
                    </ul>
                </div>
            </div>
        </div>

        <div class="slide">
            <h1>NavMesh 上的寻路规则</h1>
            <div class="layout-two-col">
                <div class="col">
                    <h3>规则 1：目标就在眼前</h3>
                    <ul>
                        <li><strong>条件：</strong>目标点和智能体位于<strong>同一个多边形</strong>内。</li>
                        <li><strong>动作：</strong>直接无脑走直线前往目标。</li>
                        <li>计算开销几乎为零，非常高效。</li>
                    </ul>
                </div>
                <div class="col">
                    <h3>规则 2：跨区域宏观旅行</h3>
                    <ul>
                        <li><strong>条件：</strong>目标点在其他多边形内。</li>
                        <li><strong>机制：</strong>多边形及其传送门构成了一个<strong>图结构 (Graph)</strong>。</li>
                        <li><strong>动作：</strong>在“多边形图”上使用 A* 搜索，节点数量从数以万计锐减到几十个。</li>
                    </ul>
                </div>
            </div>
        </div>

        <div class="slide">
            <h1>A* 在 NavMesh 上的实现逻辑</h1>
            <div class="layout-two-col">
                <div class="col">
                    <div class="math-box">
                        <strong>核心估价函数：</strong> f(n) = g(n) + h(n)<br><br>
                        • <strong>g(n):</strong> 从起点走到当前多边形的实际距离。<br>
                        • <strong>h(n):</strong> 到目标的直线距离。
                    </div>
                    <h3>节点维度的降维打击</h3>
                    <ul>
                        <li>在 NavMesh 中，<strong>节点是庞大的凸多边形</strong>。</li>
                        <li>A* 结果是一个<strong>多边形通行序列 (Polygon Path)</strong>，而非具体点阵。</li>
                    </ul>
                </div>
                <div class="col" style="flex: 1.2;">
                    <pre><code>function AStarNavMesh(startPos, targetPos, mesh):
  StartNode = mesh.findPolygon(startPos)
  TargetNode = mesh.findPolygon(targetPos)
  OpenList = PriorityQueue()

  StartNode.g = 0
  StartNode.f = distance(StartNode, TargetNode)
  OpenList.push(StartNode)

  while not OpenList.isEmpty():
    curr = OpenList.popLowestF()
    if curr == TargetNode:
      return ReconstructPath(curr) // 返回多边形序列
</code></pre>
                </div>
            </div>
        </div>

        <div class="slide" style="padding: 10px;">
            <iframe src="1.html"></iframe>
        </div>

        <div class="slide">
            <h1>NavMesh 抽象带来的新问题</h1>
            <div class="layout-two-col">
                <div class="col">
                    <h3>从精细到抽象的代价</h3>
                    <ul>
                        <li>NavMesh 是对环境的一种<strong>高度抽象</strong>。</li>
                        <li>计算过程简化了，但生成的<strong>路径也因此被过度简化</strong>。</li>
                        <li>A* 只负责告诉经过哪些多边形，不负责具体每一步迈在哪里。</li>
                    </ul>
                </div>
                <div class="col">
                    <h3>“中心点连线”的后果</h3>
                    <ul>
                        <li>直接硬连多边形中心点会导致<strong>锯齿状 (Zig-zag)</strong> 路径。</li>
                        <li><strong>表现糟糕：</strong>AI 轨迹显得机械，无法贴合实际地形走捷径。</li>
                    </ul>
                    <div class="info-box">
                        <div style="color: #ef4444; font-weight: bold; font-size: 1.3rem;">
                            急需引入路径平滑 (Path Smoothing) 技术！
                        </div>
                    </div>
                </div>
            </div>
        </div>

        <div class="slide">
            <h1>引入 Funnel (漏斗) 算法</h1>
            <div class="layout-two-col">
                <div class="col">
                    <h3>让路径回归真实物理</h3>
                    <ul>
                        <li>Funnel 算法目的是平滑逻辑路线，剔除多余拐角，得出真正的最短路径。</li>
                    </ul>
                </div>
                <div class="col">
                    <h3>核心隐喻：拉绳算法</h3>
                    <ul>
                        <li>想象起点和终点之间拉了一根有弹性的绳子。</li>
                        <li>绳子穿过门框（传送门），用力<strong>拉紧</strong>，绳子会自动贴合边缘。</li>
                        <li>这就是最短的折线路径。</li>
                    </ul>
                </div>
            </div>
        </div>

        <div class="slide">
            <h1>Funnel 算法：核心推进规则</h1>
            <div class="layout-two-col">
                <div class="col">
                    <h3>漏斗的构成与收缩</h3>
                    <ul>
                        <li><strong>初始：</strong>创建一个由顶点(Apex)、左/右端点组成的"漏斗"。</li>
                        <li><strong>推进：</strong>尝试更新左右边缘。</li>
                        <li><strong>规则 1：</strong>如果新端点让漏斗变宽，则<strong>忽略</strong>。</li>
                    </ul>
                </div>
                <div class="col">
                    <h3>处理视线遮挡</h3>
                    <ul>
                        <li><strong>规则 2 (交叉折断)：</strong>如果边缘发生交叉（如左边越过右边）。</li>
                        <li>这意味着发生了<strong>物理转折</strong>！</li>
                        <li>记录拐点，并重新构建漏斗。</li>
                    </ul>
                </div>
            </div>
        </div>

        <div class="slide">
            <h1>Funnel 算法的实现细节</h1>
            <div class="layout-two-col">
                <div class="col">
                    <div class="math-box">
                        <strong>核心：2D 向量叉积 (Cross Product)</strong><br><br>
                        通过判断叉积的正负，精确判断漏斗是在收缩还是发生了边缘交叉。
                    </div>
                    <h3>执行要点</h3>
                    <ul>
                        <li>终点也视为一个宽为 0 的点传送门。</li>
                        <li>一旦发生折断，循环索引必须回退到该拐点重新扫描。</li>
                    </ul>
                </div>
                <div class="col" style="flex: 1.2;">
                    <pre><code>function Funnel(startPos, targetPos, portals):
  path = [startPos]
  apex = startPos
  left = portals[0].left, right = portals[0].right

  for i = 1 to portals.length:
    // 逻辑：不断收缩左右视锥
    // 越界则 path.push(newApex)
</code></pre>
                </div>
            </div>
        </div>

        <div class="slide" style="padding: 10px;">
            <iframe src="2.html"></iframe>
        </div>

        <div class="controls">
            <button id="prevBtn" onclick="changeSlide(-1)">❮ 上一页</button>
            <span class="progress" id="slideIndicator">1 / 11</span>
            <button id="nextBtn" onclick="changeSlide(1)">下一页 ❯</button>
        </div>
    </div>

    <script>
        let currentSlide = 0;
        const slides = document.querySelectorAll('.slide');
        const indicator = document.getElementById('slideIndicator');
        const prevBtn = document.getElementById('prevBtn');
        const nextBtn = document.getElementById('nextBtn');

        function updateUI() {
            slides.forEach((slide, index) => {
                if (index === currentSlide) {
                    slide.classList.add('active');
                } else {
                    slide.classList.remove('active');
                }
            });

            indicator.textContent = `${currentSlide + 1} / ${slides.length}`;
            prevBtn.disabled = currentSlide === 0;
            nextBtn.disabled = currentSlide === slides.length - 1;
        }

        function changeSlide(direction) {
            currentSlide += direction;
            if (currentSlide < 0) currentSlide = 0;
            if (currentSlide >= slides.length) currentSlide = slides.length - 1;
            updateUI();
        }

        updateUI();

        document.addEventListener('keydown', (e) => {
            if (e.key === 'ArrowRight' && currentSlide < slides.length - 1) changeSlide(1);
            if (e.key === 'ArrowLeft' && currentSlide > 0) changeSlide(-1);
        });
    </script>
</body>

</html>