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
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>JSDoc: Source: path.js</title>
<script src="scripts/prettify/prettify.js"> </script>
<script src="scripts/prettify/lang-css.js"> </script>
<!--[if lt IE 9]>
<script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
<link type="text/css" rel="stylesheet" href="styles/prettify-tomorrow.css">
<link type="text/css" rel="stylesheet" href="styles/jsdoc-default.css">
</head>
<body>
<div id="main">
<h1 class="page-title">Source: path.js</h1>
<section>
<article>
<pre class="prettyprint source linenums"><code>/**
* Path Generation Module
*
* This module demonstrates several advanced game development concepts:
* 1. Procedural Content Generation (PCG)
* 2. Pathfinding algorithms
* 3. Constraint-based generation
*
* @module path
*/
/**
* Generates a valid path through the game grid using a modified depth-first search.
* This algorithm ensures:
* - Path always moves from left to right
* - No diagonal movements
* - No path segments touch each other (except at turns)
* - Path is always completable
*
* @param {Array<Array<string>>} grid - 2D array representing the game grid
* @returns {Promise<Array<{x: number, y: number}>>} Promise resolving to array of path coordinates
*
* Implementation uses:
* - Backtracking algorithm pattern
* - Constraint satisfaction
* - Random selection for variety
*/
function generatePath(grid) {
const width = grid[0].length;
const height = grid.length;
// Initialize with random start point on left edge
const startY = Math.floor(Math.random() * height);
let currentPos = { x: 0, y: startY };
const path = [currentPos];
grid[startY][0] = 'path';
/**
* Determines valid moves from current position based on game rules
* Uses constraint checking to ensure path validity
*
* @param {Object} pos - Current position {x, y}
* @returns {Array<{x: number, y: number}>} Array of valid next positions
*/
function getValidMoves(pos) {
const moves = [];
// Prioritize right movement for path progression
const directions = [
{ x: 1, y: 0 }, // right
{ x: 0, y: -1 }, // up
{ x: 0, y: 1 } // down
];
for (const dir of directions) {
const newX = pos.x + dir.x;
const newY = pos.y + dir.y;
// Enforce boundary constraints
if (newX < 0 || newX >= width || newY < 0 || newY >= height) {
continue;
}
// Check path isolation constraint
if (grid[newY][newX] === 'empty' && !hasAdjacentPath(newX, newY, grid)) {
moves.push({ x: newX, y: newY });
}
}
return moves;
}
/**
* Checks if a position has adjacent path tiles (excluding previous path tile)
* Implements path isolation constraint
*
* @param {number} x - X coordinate to check
* @param {number} y - Y coordinate to check
* @param {Array<Array<string>>} grid - Current grid state
* @returns {boolean} True if position has adjacent path tiles
*/
function hasAdjacentPath(x, y, grid) {
const adjacentCells = [
{ x: x, y: y - 1 }, // up
{ x: x, y: y + 1 }, // down
{ x: x - 1, y: y }, // left
{ x: x + 1, y: y }, // right
];
return adjacentCells.some(cell => {
if (cell.x < 0 || cell.x >= width || cell.y < 0 || cell.y >= height) {
return false;
}
return grid[cell.y][cell.x] === 'path' &&
!path.some(p => p.x === cell.x && p.y === cell.y);
});
}
// Main path generation loop with backtracking
while (currentPos.x < width - 1) {
const moves = getValidMoves(currentPos);
if (moves.length === 0) {
// Backtrack when no valid moves exist
if (path.length <= 1) {
// Restart if backtracking fails
return generatePath(grid);
}
path.pop();
const lastPos = path[path.length - 1];
grid[currentPos.y][currentPos.x] = 'empty';
currentPos = lastPos;
continue;
}
// Random selection for path variety
const nextMove = moves[Math.floor(Math.random() * moves.length)];
currentPos = nextMove;
path.push(currentPos);
grid[currentPos.y][currentPos.x] = 'path';
}
return Promise.resolve(path);
}
/**
* Calculates a position along the path based on a progress value
* Implements smooth entity movement along path segments
*
* @param {number} progress - Progress along path (0-1)
* @param {Array<{x: number, y: number}>} path - Array of path coordinates
* @returns {{x: number, y: number}} Interpolated position along path
*
* Uses:
* - Linear interpolation (lerp)
* - Path segment traversal
* - Normalized progress tracking
*/
function getPathPosition(progress, path) {
// Normalize progress to valid range
progress = Math.max(0, Math.min(1, progress));
// Calculate total path length for normalization
let totalLength = 0;
for (let i = 1; i < path.length; i++) {
const dx = path[i].x - path[i-1].x;
const dy = path[i].y - path[i-1].y;
totalLength += Math.sqrt(dx * dx + dy * dy);
}
// Convert progress to distance along path
const targetDistance = progress * totalLength;
// Find appropriate path segment
let currentDistance = 0;
for (let i = 1; i < path.length; i++) {
const dx = path[i].x - path[i-1].x;
const dy = path[i].y - path[i-1].y;
const segmentLength = Math.sqrt(dx * dx + dy * dy);
if (currentDistance + segmentLength >= targetDistance) {
// Linear interpolation within segment
const segmentProgress = (targetDistance - currentDistance) / segmentLength;
return {
x: path[i-1].x + dx * segmentProgress,
y: path[i-1].y + dy * segmentProgress
};
}
currentDistance += segmentLength;
}
// Fallback to end of path
return { ...path[path.length - 1] };
} </code></pre>
</article>
</section>
</div>
<nav>
<h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-game.html">game</a></li><li><a href="module-gameState.html">gameState</a></li><li><a href="module-mechanics.html">mechanics</a></li><li><a href="module-path.html">path</a></li><li><a href="module-renderer.html">renderer</a></li><li><a href="module-uiHandlers.html">uiHandlers</a></li></ul>
</nav>
<br class="clear">
<footer>
Documentation generated by <a href="https://github.com/jsdoc/jsdoc">JSDoc 4.0.3</a> on Mon Feb 17 2025 09:19:19 GMT-0500 (Eastern Standard Time)
</footer>
<script> prettyPrint(); </script>
<script src="scripts/linenumber.js"> </script>
</body>
</html>
|