1 /++
2 	Note: much of the functionality of gamehelpers was moved to [arsd.game] on May 3, 2020.
3 	If you used that code, change `import arsd.gamehelpers;` to `import arsd.game;` and add
4 	game.d to your build (in addition to gamehelpers.d; the new game.d still imports this module)
5 	and you should be good to go.
6 
7 	This module now builds on only [arsd.color] to provide additional algorithm functions
8 	and data types that are common in games.
9 
10 	History:
11 		Massive change on May 3, 2020 to move the previous flagship class out and to
12 		a new module, [arsd.game], to make this one lighter on dependencies, just
13 		containing helpers rather than a consolidated omnibus import.
14 +/
15 module arsd.gamehelpers;
16 
17 deprecated("change `import arsd.gamehelpers;` to `import arsd.game;`")
18 void* create2dWindow(string title, int width = 512, int height = 512) { return null; }
19 
20 deprecated("change `import arsd.gamehelpers;` to `import arsd.game;`")
21 class GameHelperBase {}
22 
23 import std.math;
24 
25 import arsd.color;
26 
27 // Some math helpers
28 
29 int nextPowerOfTwo(int v) {
30 	v--;
31 	v |= v >> 1;
32 	v |= v >> 2;
33 	v |= v >> 4;
34 	v |= v >> 8;
35 	v |= v >> 16;
36 	v++;
37 	return v;
38 }
39 
40 /++
41 	Calculates the cross product of <u1, u2, u3> and <v1, v2, v3>, putting the result in <s1, s2, s3>.
42 +/
43 void crossProduct(
44 	float u1, float u2, float u3,
45 	float v1, float v2, float v3,
46 	out float s1, out float s2, out float s3)
47 {
48 	s1 = u2 * v3 - u3 * v2;
49 	s2 = u3 * v1 - u1 * v3;
50 	s3 = u1 * v2 - u2 * v1;
51 }
52 
53 /++
54 	3D rotates (x, y, z) theta radians about the axis represented by unit-vector (u, v, w), putting the results in (s1, s2, s3).
55 
56 	For example, to rotate about the Y axis, pass (0, 1, 0) as (u, v, w).
57 +/
58 void rotateAboutAxis(
59 	float theta, // in RADIANS
60 	float x, float y, float z,
61 	float u, float v, float w,
62 	out float xp, out float yp, out float zp)
63 {
64 	xp = u * (u*x + v*y + w*z) * (1 - cos(theta)) + x * cos(theta) + (-w*y + v*z) * sin(theta);
65 	yp = v * (u*x + v*y + w*z) * (1 - cos(theta)) + y * cos(theta) + (w*x - u*z) * sin(theta);
66 	zp = w * (u*x + v*y + w*z) * (1 - cos(theta)) + z * cos(theta) + (-v*x + u*y) * sin(theta);
67 }
68 
69 /++
70 	2D rotates (rotatingX, rotatingY) theta radians about (originX, originY), putting the result in (xp, yp).
71 +/
72 void rotateAboutPoint(
73 	float theta, // in RADIANS
74 	float originX, float originY,
75 	float rotatingX, float rotatingY,
76 	out float xp, out float yp)
77 {
78 	if(theta == 0) {
79 		xp = rotatingX;
80 		yp = rotatingY;
81 		return;
82 	}
83 
84 	rotatingX -= originX;
85 	rotatingY -= originY;
86 
87 	float s = sin(theta);
88 	float c = cos(theta);
89 
90 	float x = rotatingX * c - rotatingY * s;
91 	float y = rotatingX * s + rotatingY * c;
92 
93 	xp = x + originX;
94 	yp = y + originY;
95 }
96 
97 /++
98 	Represents the four basic directions on a grid. You can conveniently use it like:
99 
100 	---
101 	Point pt = Point(5, 3);
102 	pt += Dir.N; // moves up
103 	---
104 
105 	The opposite direction btw can be gotten with `pt * -1`.
106 
107 	History: Added May 3, 2020
108 +/
109 enum Dir { N = Point(0, -1), S = Point(0, 1), W = Point(-1, 0), E = Point(1, 0) }
110 
111 /++
112 	The four directions as a static array so you can assign to a local variable
113 	then shuffle, etc.
114 
115 	History: Added May 3, 2020
116 +/
117 Point[4] directions() {
118 	with(Dir) return [N, S, W, E];
119 }
120 
121 /++
122 	A random value off [Dir].
123 
124 	History: Added May 3, 2020
125 +/
126 Point randomDirection() {
127 	import std.random;
128 	return directions()[uniform(0, 4)];
129 }
130 
131 /++
132 	Cycles through all the directions the given number of times. If you have
133 	one cycle, it goes through each direction once in a random order. With two
134 	cycles, it will move each direction twice, but in random order - can be
135 	W, W, N, E, S, S, N, E, for example; it will not do the cycles in order but
136 	upon completion will have gone through them all.
137 
138 	This can be convenient because if the character's movement is not constrained,
139 	it will always return back to where it started after a random movement.
140 
141 	Returns: an input range of [Point]s. Please note that the current version returns
142 	`Point[]`, but I reserve the right to change that in the future; I only promise
143 	input range capabilities.
144 
145 	History: Added May 3, 2020
146 +/
147 auto randomDirectionCycle(int cycleCount = 1) {
148 	Point[] all = new Point[](cycleCount * 4);
149 	foreach(c; 0 .. cycleCount)
150 		all[c * 4 .. c * 4 + 4] = directions()[];
151 
152 	import std.random;
153 	return all.randomShuffle;
154 }
155 
156 /++
157 	Represents a 2d grid like an array. To encapsulate the whole `[y*width + x]` thing.
158 
159 	History:
160 		Added May 3, 2020
161 +/
162 struct Grid(T) {
163 	private Size size_;
164 	private T[] array;
165 
166 	pure @safe nothrow:
167 
168 	/// Creates a new GC-backed array
169 	this(Size size) {
170 		this.size_ = size;
171 		array = new T[](size.area);
172 	}
173 
174 	/// ditto
175 	this(int width, int height) {
176 		this(Size(width, height));
177 	}
178 
179 	@nogc:
180 
181 	/// Wraps an existing array.
182 	this(T[] array, Size size) {
183 		assert(array.length == size.area);
184 		this.array = array;
185 		this.size_ = size;
186 	}
187 
188 	@property {
189 		///
190 		inout(Size) size() inout { return size_; }
191 		///
192 		int width() const { return size.width; }
193 		///
194 		int height() const { return size.height; }
195 	}
196 
197 	/// Slice operation gives a view into the underlying 1d array.
198 	inout(T)[] opIndex() inout {
199 		return array;
200 	}
201 
202 	///
203 	ref inout(T) opIndex(int x, int y) inout {
204 		return array[y * width + x];
205 	}
206 
207 	///
208 	ref inout(T) opIndex(const Point pt) inout {
209 		return this.opIndex(pt.x, pt.y);
210 	}
211 	// T[] opSlice
212 
213 	///
214 	bool inBounds(int x, int y) const {
215 		return x >= 0 && y >= 0 && x < width && y < height;
216 	}
217 
218 	///
219 	bool inBounds(const Point pt) const {
220 		return inBounds(pt.x, pt.y);
221 	}
222 
223 	/// Supports `if(point in grid) {}`
224 	bool opBinaryRight(string op : "in")(Point pt) const {
225 		return inBounds(pt);
226 	}
227 }
228 
229 /++
230 	Directions as a maskable bit flag.
231 
232 	History: Added May 3, 2020
233 +/
234 enum DirFlag : ubyte {
235 	N = 4,
236 	S = 8,
237 	W = 1,
238 	E = 2
239 }
240 
241 /++
242 	History: Added May 3, 2020
243 +/
244 DirFlag dirFlag(Dir dir) {
245 	assert(dir.x >= -1 && dir.x <= 1);
246 	assert(dir.y >= -1 && dir.y <= 1);
247 
248 
249 	/+
250 		(-1 + 3) / 2 = 2 / 2 = 1
251 		(1 + 3) / 2  = 4 / 2 = 2
252 
253 		So the al-gore-rhythm is
254 			(x + 3) / 2
255 				which is aka >> 1
256 			  or
257 			((y + 3) / 2) << 2
258 				which is aka >> 1 << 2 aka << 1
259 		So:
260 			1 = left
261 			2 = right
262 			4 = up
263 			8 = down
264 	+/
265 
266 	ubyte dirFlag;
267 	if(dir.x) dirFlag |= ((dir.x + 3) >> 1);
268 	if(dir.y) dirFlag |= ((dir.y + 3) << 1);
269 	return cast(DirFlag) dirFlag;
270 }
271 
272 // this is public but like i don't want do document it since it can so easily fail the asserts.
273 DirFlag dirFlag(Point dir) {
274 	return dirFlag(*cast(Dir*) &dir);
275 }
276 
277 /++
278 	Generates a maze.
279 
280 	The returned array is a grid of rooms, with a bit flag pattern of directions you can travel from each room. See [DirFlag] for bits.
281 
282 	History: Added May 3, 2020
283 +/
284 Grid!ubyte generateMaze(int mazeWidth, int mazeHeight) {
285 	import std.random;
286 
287 	Point[] cells;
288 	cells ~= Point(uniform(0, mazeWidth), uniform(0, mazeHeight));
289 
290 	auto grid = Grid!ubyte(mazeWidth, mazeHeight);
291 
292 	Point[4] directions = .directions;
293 
294 	while(cells.length) {
295 		auto index = cells.length - 1; // could also be 0 or uniform or whatever too
296 		Point p = cells[index];
297 		bool added;
298 		foreach(dir; directions[].randomShuffle) {
299 			auto n = p + dir;
300 			if(n !in grid)
301 				continue;
302 
303 			if(grid[n])
304 				continue;
305 
306 			grid[p] |= dirFlag(dir);
307 			grid[n] |= dirFlag(dir * -1);
308 
309 			cells ~= n;
310 
311 			added = true;
312 			break;
313 		}
314 
315 		if(!added) {
316 			foreach(i; index .. cells.length - 1)
317 				cells[index] = cells[index + 1];
318 			cells = cells[0 .. $-1];
319 		}
320 	}
321 
322 	return grid;
323 }
324 
325 
326 /++
327 	Implements the A* path finding algorithm on a grid.
328 
329 	Params:
330 		start = starting point on the grid
331 		goal = destination point on the grid
332 		size = size of the grid
333 		isPassable = used to determine if the tile at the given coordinates are passible
334 		d = weight function to the A* algorithm. If null, assumes all will be equal weight. Returned value must be greater than or equal to 1.
335 		h = heuristic function to the A* algorithm. Gives an estimation of how many steps away the goal is from the given point to speed up the search. If null, assumes "taxicab distance"; the number of steps based solely on distance without diagonal movement. If you want to disable this entirely, pass `p => 0`.
336 	Returns:
337 		A list of waypoints to reach the destination, or `null` if impossible. The waypoints are returned in reverse order, starting from the goal and working back to the start.
338 
339 		So to get to the goal from the starting point, follow the returned array in $(B backwards).
340 
341 		The waypoints will not necessarily include every step but also may not only list turns, but if you follow
342 		them you will get get to the destination.
343 
344 	Bugs:
345 		The current implementation uses more memory than it really has to; it will eat like 8 MB of scratch space RAM on a 512x512 grid.
346 
347 		It doesn't consider wraparound possible so it might ask you to go all the way around the world unnecessarily.
348 
349 	History:
350 		Added May 2, 2020.
351 +/
352 Point[] pathfind(Point start, Point goal, Size size, scope bool delegate(Point) isPassable, scope int delegate(Point, Point) d = null, scope int delegate(Point) h = null) {
353 
354 	Point[] reconstruct_path(scope Point[] cameFrom, Point current) {
355 		Point[] totalPath;
356 		totalPath ~= current;
357 
358 		auto cf = cameFrom[current.y * size.width + current.x];
359 		while(cf != Point(int.min, int.min)) {
360 			current = cf;
361 			cf = cameFrom[current.y * size.width + current.x];
362 			totalPath ~= current;
363 		}
364 		return totalPath;
365 	}
366 
367 	// weighting thing.....
368 	static int d_default(Point a, Point b) {
369 		return 1;
370 	}
371 
372 	if(d is null)
373 		d = (Point a, Point b) => d_default(a, b);
374 
375 	if(h is null)
376 		h = (Point a) { return abs(a.y - goal.x) + abs(a.y - goal.y); };
377 
378 	Point[] openSet = [start];
379 
380 	Point[] cameFrom = new Point[](size.area);
381 	cameFrom[] = Point(int.min, int.min);
382 
383 	int[] gScore = new int[](size.area);
384 	gScore[] = int.max;
385 	gScore[start.y * size.width + start.x] = 0;
386 
387 	int[] fScore = new int[](size.area);
388 	fScore[] = int.max;
389 	fScore[start.y * size.width + start.x] = h(start);
390 
391 	while(openSet.length) {
392 		Point current;
393 		size_t currentIdx;
394 		int currentFscore = int.max;
395 		foreach(idx, pt; openSet) {
396 			auto p = fScore[pt.y * size.width + pt.x];
397 			if(p <= currentFscore) {
398 				currentFscore = p;
399 				current = pt;
400 				currentIdx = idx;
401 			}
402 		}
403 
404 		if(current == goal) {
405 /+
406 import std.stdio;
407 foreach(y; 0 .. size.height)
408 	writefln("%(%02d,%)", gScore[y * size.width .. y * size.width + size.width]);
409 +/
410 			return reconstruct_path(cameFrom, current);
411 		}
412 
413 		openSet[currentIdx] = openSet[$-1];
414 		openSet = openSet[0 .. $-1];
415 
416 		Point[4] neighborsBuffer;
417 		int neighborsBufferLength = 0;
418 
419 
420 		// FIXME: would be kinda cool to make this a more generic graph traversal like for subway routes too
421 
422 		if(current.x + 1 < size.width && isPassable(current + Point(1, 0)))
423 			neighborsBuffer[neighborsBufferLength++] = current + Point(1, 0);
424 		if(current.x && isPassable(current + Point(-1, 0)))
425 			neighborsBuffer[neighborsBufferLength++] = current + Point(-1, 0);
426 		if(current.y && isPassable(current + Point(0, -1)))
427 			neighborsBuffer[neighborsBufferLength++] = current + Point(0, -1);
428 		if(current.y + 1 < size.height && isPassable(current + Point(0, 1)))
429 			neighborsBuffer[neighborsBufferLength++] = current + Point(0, 1);
430 
431 		foreach(neighbor; neighborsBuffer[0 .. neighborsBufferLength]) {
432 			auto tentative_gScore = gScore[current.y * size.width + current.x] + d(current, neighbor);
433 			if(tentative_gScore < gScore[neighbor.y * size.width + neighbor.x]) {
434 				cameFrom[neighbor.y * size.width + neighbor.x] = current;
435 				gScore[neighbor.y * size.width + neighbor.x] = tentative_gScore;
436 				fScore[neighbor.y * size.width + neighbor.x] = tentative_gScore + h(neighbor);
437 				// this linear thing might not be so smart after all
438 				bool found = false;
439 				foreach(o; openSet)
440 					if(o == neighbor) { found = true; break; }
441 				if(!found)
442 					openSet ~= neighbor;
443 			}
444 		}
445 	}
446 
447 	return null;
448 }