[ViewVC] Diff of: cvs/deliantra/server/random

Comparing deliantra/server/random_maps/layout.C (file contents):
Revision 1.1 by root, Wed Jun 30 20:51:02 2010 UTC vs.
Revision 1.16 by root, Sat Jul 3 11:52:11 2010 UTC

…		…
1	/*	1	/*
2	* This file is part of Deliantra, the Roguelike Realtime MMORPG.	2	* This file is part of Deliantra, the Roguelike Realtime MMORPG.
3	*	3	*
4	* Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team	4	* Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
		5	* Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
5	*	6	*
6	* Deliantra is free software: you can redistribute it and/or modify it under	7	* Deliantra is free software: you can redistribute it and/or modify it under
7	* the terms of the Affero GNU General Public License as published by the	8	* the terms of the Affero GNU General Public License as published by the
8	* Free Software Foundation, either version 3 of the License, or (at your	9	* Free Software Foundation, either version 3 of the License, or (at your
9	* option) any later version.	10	* option) any later version.
20	* The authors can be reached via e-mail to <support@deliantra.net>	21	* The authors can be reached via e-mail to <support@deliantra.net>
21	*/	22	*/
22		23
23	#include <global.h>	24	#include <global.h>
24	#include <random_map.h>	25	#include <random_map.h>
		26	#include <rproto.h>
25		27
26	LayoutData::LayoutData (int w, int h)	28	void
27	: w(w), h(h)	29	layout::alloc (int w, int h)
28	{	30	{
		31	assert (sizeof (cell) == 1);
		32
		33	this->w = w;
		34	this->h = h;
		35
		36	// we store the layout in a single contiguous memory layout
		37	// first part consists of pointers to each column, followed
		38	// by the actual columns (not rows!)
29	int size = (sizeof (char ) + sizeof (char) h) * w;	39	size = (sizeof (cell ) + sizeof (cell) h) * w;
30
31	col = (char **)salloc<char> (size);	40	data = (cell **)salloc<char> (size);
32		41
33	char data = (char )(col + w);	42	cell p = (cell )(data + w);
34		43
35	for (int x = w; x--; )	44	for (int x = 0; x < w; ++x)
36	col [x] = data + x * h;	45	data [x] = p + x * h;
37	}	46	}
38		47
39	LayoutData::~LayoutData ()	48	layout::layout (int w, int h)
40	{	49	{
41	int size = (sizeof (char ) + sizeof (char) h) * w;	50	alloc (w, h);
		51	}
42		52
		53	layout::layout (layout &copy)
		54	{
		55	alloc (copy.w, copy.h);
		56
		57	memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
		58	}
		59
		60	layout::layout (layout &orig, int x1, int y1, int x2, int y2)
		61	{
		62	w = x2 - x1;
		63	h = y2 - y1;
		64
		65	// we only allocate space for the pointers
		66	size = sizeof (cell ) w;
		67	data = (cell **)salloc<char> (size);
		68
		69	// and now we point back into the original layout
		70	for (int x = 0; x < w; ++x)
		71	data [x] = orig.data [x + x1] + y1;
		72	}
		73
		74	layout::~layout ()
		75	{
43	sfree ((char *)col, size);	76	sfree ((char *)data, size);
44	}	77	}
45		78
46	void	79	void
47	LayoutData::fill (char fill)	80	layout::fill (char fill)
48	{	81	{
49	memset (col [0], fill, w * h);	82	//memset (data [0], fill, w * h); // only when contiguous :/
		83	fill_rect (0, 0, w, h, fill);
50	}	84	}
51		85
52	void	86	void
53	LayoutData::rect (int x1, int y1, int x2, int y2, char fill)	87	layout::rect (int x1, int y1, int x2, int y2, char fill)
		88	{
		89	--x2;
		90
		91	memset (data [x1] + y1, fill, y2 - y1);
		92	memset (data [x2] + y1, fill, y2 - y1);
		93
		94	while (++x1 < x2)
		95	data [x1][y1] = data [x1][y2 - 1] = fill;
		96	}
		97
		98	void
		99	layout::fill_rect (int x1, int y1, int x2, int y2, char fill)
54	{	100	{
55	for (; x1 < x2; ++x1)	101	for (; x1 < x2; ++x1)
56	memset (col [x1] + y1, fill, y2 - y1);	102	memset (data [x1] + y1, fill, y2 - y1);
57	}	103	}
58		104
59	void LayoutData::border (char fill)	105	void layout::border (char fill)
60	{	106	{
61	for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill;	107	rect (0, 0, w, h, fill);
62	for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill;	108	}
		109
		110	void
		111	layout::fill_rand (int percent)
		112	{
		113	percent = lerp (percent, 0, 100, 0, 256);
		114
		115	for (int x = w - 1; --x > 0; )
		116	for (int y = h - 1; --y > 0; )
		117	data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
63	}	118	}
64		119
65	/////////////////////////////////////////////////////////////////////////////	120	/////////////////////////////////////////////////////////////////////////////
66		121
		122	// erode by cellular automata
67	void	123	void
		124	layout::erode_1_2 (int c1, int c2, int repeat)
		125	{
		126	layout neu (w, h);
		127
		128	while (repeat--)
		129	{
		130	for (int x = 0; x < w; ++x)
		131	{
		132	coroapi::cede_to_tick ();
		133
		134	for (int y = 0; y < h; ++y)
		135	{
		136	int n1 = 0, n2 = 0;
		137
		138	// a 5x5 area, dx, dy, distance (1 == <= 1, 0 <= 2)
		139	static I8 dds[][3] = {
		140	{ -2, -1, 0 }, { -2, 0, 0 }, { -2, 1, 0 },
		141	{ -1, -2, 0 }, { -1, -1, 1 }, { -1, 0, 1 }, { -1, 1, 1 }, { -1, 2, 0 },
		142	{ 0, -2, 0 }, { 0, -1, 1 }, { 0, 0, 1 }, { 0, 1, 1 }, { 0, 2, 0 },
		143	{ 1, -2, 0 }, { 1, -1, 1 }, { 1, 0, 1 }, { 1, 1, 1 }, { 1, 2, 0 },
		144	{ 2, -1, 0 }, { 2, 0, 0 }, { 2, 1, 0 },
		145	};
		146
		147	for (int i = array_length (dds); i--; )
		148	{
		149	int nx = x + dds [i][0];
		150	int ny = y + dds [i][1];
		151
		152	if (!IN_RANGE_EXC (nx, 0, w) \|\| !IN_RANGE_EXC (ny, 0, h) \|\| !data [nx][ny])
		153	{
		154	n1 += dds [i][2];
		155	n2++;
		156	}
		157	}
		158
		159	neu [x][y] = n1 >= c1 \|\| n2 <= c2 ? '#' : 0;
		160	}
		161	}
		162
		163	swap (neu);
		164	}
		165	}
		166
		167	/////////////////////////////////////////////////////////////////////////////
		168
		169	void
68	Layout::print ()	170	layout::print () const
69	{	171	{
70	for (int y = 0; y < ptr->h; y++)	172	for (int y = 0; y < h; y++)
71	{	173	{
72	for (int x = 0; x < ptr->w; x++)	174	for (int x = 0; x < w; x++)
73	{	175	{
74	U8 c = (U8)ptr->col[x][y];	176	U8 c = (U8)data [x][y];
75		177
76	if (!c)	178	if (!c)
77	c = ' ';	179	c = ' ';
78	else if (c < 10)	180	else if (c < 10)
79	c += '0';	181	c += '0';
…		…
92	/////////////////////////////////////////////////////////////////////////////	194	/////////////////////////////////////////////////////////////////////////////
93	// isolation remover - ensures single connected area	195	// isolation remover - ensures single connected area
94		196
95	typedef fixed_stack<point> pointlist;	197	typedef fixed_stack<point> pointlist;
96		198
97	static void
98	room (Layout &layout, int xc, int yc)
99	{
100	layout->rect (xc - 2, yc - 2, xc + 3, yc + 3, 0);
101	}
102
103	static noinline void	199	static void noinline
104	push_flood_fill (Layout maze, Layout dist, pointlist &seeds, int x, int y)	200	push_flood_fill (layout &dist, pointlist &seeds, int x, int y)
105	{	201	{
106	if (maze [x][y])	202	if (dist [x][y])
107	return;	203	return;
108		204
109	while (y > 0 && !maze [x][y - 1])	205	while (y > 0 && !dist [x][y - 1])
110	--y;	206	--y;
111		207
112	int y0 = y;	208	int y0 = y;
113		209
114	while (y < maze->h && !maze [x][y])	210	while (y < dist.h && !dist [x][y])
115	{	211	{
116	seeds.push (point (x, y));	212	seeds.push (point (x, y));
117		213
118	maze [x][y] = 1;
119	dist [x][y] = 1;	214	dist [x][y] = 1;
120	++y;	215	++y;
121	}	216	}
122		217
123	while (--y >= y0)	218	while (--y >= y0)
124	{	219	{
125	if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y);	220	if (x > 0 && !dist [x - 1][y]) push_flood_fill (dist, seeds, x - 1, y);
126	if (x < maze->w - 1) push_flood_fill (maze, dist, seeds, x + 1, y);	221	if (x < dist.w - 1 && !dist [x + 1][y]) push_flood_fill (dist, seeds, x + 1, y);
127	}	222	}
128	}	223	}
129		224
130	static inline void	225	static inline void
131	make_tunnel (Layout maze, Layout dist, pointlist &seeds, int x, int y, U8 d)	226	make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d)
132	{	227	{
133	for (;;)	228	for (;;)
134	{	229	{
		230	point neigh[4];
		231	int ncnt = 0;
		232
		233	if (x > 0 && U8 (dist [x - 1][y]) <= d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
		234	if (x < dist.w - 1 && U8 (dist [x + 1][y]) <= d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y);
		235	if (y > 0 && U8 (dist [x][y - 1]) <= d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
		236	if (y < dist.h - 1 && U8 (dist [x][y + 1]) <= d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
		237
		238	if (!ncnt)
		239	return;
		240
		241	point &p = neigh [rmg_rndm (ncnt)];
		242
135	seeds.push (point (x, y));	243	seeds.push (p);
136		244
137	maze [x][y] = 1;	245	x = p.x;
		246	y = p.y;
		247
		248	d = dist [x][y];
138	dist [x][y] = 1;	249	dist [x][y] = 1;
		250	}
		251	}
139		252
140	if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1)	253	static void inline
		254	maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d)
		255	{
		256	char &D = dist [x][y];
		257
		258	if (U8 (D) > d) // if wall and higher distance, lower distance
		259	D = d;
		260	else if (D) // otherwise, if it's no room, this space is uninteresting
		261	return;
		262
		263	seeds.push (point (x, y));
		264	}
		265
		266	// isolation remover, works on a "distance" map
		267	// the map must be initialised with 0 == rooms, 255 = walls
		268	static void noinline
		269	isolation_remover (layout &dist)
		270	{
		271	// dist contains
		272	// 0 == invisited rooms
		273	// 1 == visited rooms
		274	// 2+ shortest distance to random near room
		275
		276	// phase 1, find seed
		277	int cnt = 0;
		278	int x, y;
		279
		280	for (int i = 0; i < dist.w; ++i)
		281	for (int j = 0; j < dist.h; ++j)
		282	if (!dist [i][j] && !rmg_rndm (++cnt))
		283	x = i, y = j;
		284
		285	if (!cnt)
		286	{
		287	// map is completely massive, this is not good,
		288	// so make it empty instead.
		289	dist.fill (1);
		290	return;
		291	}
		292
		293	fixed_stack<point> seeds (dist.w * dist.h * 5);
		294
		295	// found first free space - picking the first one gives
		296	// us a slight bias for tunnels, but usually you won't
		297	// notice that in-game
		298	seeds.push (point (x, y));
		299
		300	// phase 2, while we have seeds, if
		301	// seed is empty, floodfill, else grow
		302
		303	while (seeds.size)
		304	{
		305	coroapi::cede_to_tick ();
		306
		307	point p = seeds.remove (rmg_rndm (seeds.size));
		308
		309	x = p.x;
		310	y = p.y;
		311
		312	if (!dist [x][y])
141	--x;	313	{
142	else if (x < maze->w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1)	314	// found new isolated area, make tunnel
		315	push_flood_fill (dist, seeds, x, y);
		316	make_tunnel (dist, seeds, x, y, 255);
143	++x;	317	}
144	else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1)
145	--y;
146	else if (y < maze->h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1)
147	++y;
148	else	318	else
		319	{
		320	// nothing here, continue to expand
		321	U8 d = U8 (dist [x][y]) + 1;
		322
		323	if (x < dist.w - 1) maybe_push (dist, seeds, x + 1, y, d);
		324	if (x > 0) maybe_push (dist, seeds, x - 1, y, d);
		325	if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d);
		326	if (y > 0) maybe_push (dist, seeds, x, y - 1, d);
		327	}
		328	}
		329	}
		330
		331	void
		332	layout::isolation_remover ()
		333	{
		334	layout dist (w - 2, h - 2); // map without border
		335
		336	for (int x = 1; x < w - 1; ++x)
		337	for (int y = 1; y < h - 1; ++y)
		338	dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
		339
		340	::isolation_remover (dist);
		341
		342	// now copy the tunnels over
		343	for (int x = 1; x < w - 1; ++x)
		344	for (int y = 1; y < h - 1; ++y)
		345	if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
		346	data [x][y] = 0;
		347	}
		348
		349	/////////////////////////////////////////////////////////////////////////////
		350
		351	//+GPL
		352
		353	/* puts doors at appropriate locations in a maze. */
		354	void
		355	layout::doorify ()
		356	{
		357	int ndoors = w * h / 60; /* reasonable number of doors. */
		358	int doorlocs = 0; /* # of available doorlocations */
		359
		360	uint16 doorlist_x = salloc<uint16> (w h);
		361	uint16 doorlist_y = salloc<uint16> (w h);
		362
		363	/* make a list of possible door locations */
		364	for (int i = 1; i < w - 1; i++)
		365	for (int j = 1; j < h - 1; j++)
		366	{
		367	int sindex = surround_flag (*this, i, j);
		368
		369	if (sindex == 3 \|\| sindex == 12) /* these are possible door sindex */
		370	{
		371	doorlist_x [doorlocs] = i;
		372	doorlist_y [doorlocs] = j;
		373	doorlocs++;
		374	}
		375	}
		376
		377	while (ndoors > 0 && doorlocs > 0)
		378	{
		379	int di = rmg_rndm (doorlocs);
		380	int i = doorlist_x [di];
		381	int j = doorlist_y [di];
		382	int sindex = surround_flag (*this, i, j);
		383
		384	if (sindex == 3 \|\| sindex == 12) /* these are possible door sindex */
		385	{
		386	data [i][j] = 'D';
		387	ndoors--;
		388	}
		389
		390	/* reduce the size of the list */
		391	doorlocs--;
		392	doorlist_x[di] = doorlist_x [doorlocs];
		393	doorlist_y[di] = doorlist_y [doorlocs];
		394	}
		395
		396	sfree (doorlist_x, w * h);
		397	sfree (doorlist_y, w * h);
		398	}
		399
		400	/* takes a map and makes it symmetric: adjusts Xsize and
		401	* Ysize to produce a symmetric map.
		402	*/
		403	void
		404	layout::symmetrize (int symmetry)
		405	{
		406	if (symmetry == SYMMETRY_NONE)
		407	return;
		408
		409	layout sym_layout (
		410	symmetry == SYMMETRY_X \|\| symmetry == SYMMETRY_XY ? w * 2 - 3 : w,
		411	symmetry == SYMMETRY_Y \|\| symmetry == SYMMETRY_XY ? h * 2 - 3 : h
		412	);
		413
		414	if (symmetry == SYMMETRY_X)
		415	for (int i = 0; i < sym_layout.w / 2 + 1; i++)
		416	for (int j = 0; j < sym_layout.h; j++)
		417	{
		418	sym_layout[i ][j] =
		419	sym_layout[sym_layout.w - i - 1][j] = data [i][j];
		420	}
		421
		422	if (symmetry == SYMMETRY_Y)
		423	for (int i = 0; i < sym_layout.w; i++)
		424	for (int j = 0; j < sym_layout.h / 2 + 1; j++)
		425	{
		426	sym_layout[i][j ] =
		427	sym_layout[i][sym_layout.h - j - 1] = data [i][j];
		428	}
		429
		430	if (symmetry == SYMMETRY_XY)
		431	for (int i = 0; i < sym_layout.w / 2 + 1; i++)
		432	for (int j = 0; j < sym_layout.h / 2 + 1; j++)
		433	{
		434	sym_layout[i ][j ] =
		435	sym_layout[i ][sym_layout.h - j - 1] =
		436	sym_layout[sym_layout.w - i - 1][j ] =
		437	sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = data [i][j];
		438	}
		439
		440	/* need to run the isolation remover for some layouts */
		441	#if 0
		442	switch (RP->map_layout_style)
		443	{
		444	case LAYOUT_ONION:
		445	case LAYOUT_SNAKE:
		446	case LAYOUT_SQUARE_SPIRAL:
		447	// safe
		448	break;
		449
		450	default:
		451	sym_layout.isolation_remover ();
		452	break;
		453	}
		454	#endif
		455	sym_layout.isolation_remover ();
		456
		457	swap (sym_layout);
		458	}
		459
		460	//-GPL
		461
		462	void
		463	layout::rotate (int rotation)
		464	{
		465	switch (rotation & 3)
		466	{
		467	case 2: /* a reflection */
		468	{
		469	layout new_layout (w, h);
		470
		471	for (int i = 0; i < w; i++) /* copy a reflection back */
		472	for (int j = 0; j < h; j++)
		473	new_layout [i][j] = data [w - i - 1][h - j - 1];
		474
		475	swap (new_layout);
		476	}
		477	break;
		478
		479	case 1:
		480	case 3:
		481	{
		482	layout new_layout (h, w);
		483
		484	if (rotation == 1) /* swap x and y */
		485	for (int i = 0; i < w; i++)
		486	for (int j = 0; j < h; j++)
		487	new_layout [j][i] = data [i][j];
		488
		489	if (rotation == 3) /* swap x and y */
		490	for (int i = 0; i < w; i++)
		491	for (int j = 0; j < h; j++)
		492	new_layout [j][i] = data [w - i - 1][h - j - 1];
		493
		494	swap (new_layout);
		495	}
		496	break;
		497	}
		498	}
		499
		500	/////////////////////////////////////////////////////////////////////////////
		501
		502	//+GPL
		503
		504	/*
		505	* Expands a maze by 2x in each dimension.
		506	* H. S. Teoh
		507	*/
		508
		509	/* Copy the old tile X into the new one at location (i2, j2) and
		510	* fill up the rest of the 2x2 result with \0:
		511	* X ---> X \0
		512	* \0 \0
		513	*/
		514	static void inline
		515	expand_misc (layout &newlayout, int i, int j, layout &maze)
		516	{
		517	newlayout[i * 2 + rmg_rndm (1)][j * 2 + rmg_rndm (1)] = maze[i][j];
		518	/* (Note: no need to reset rest of 2x2 area to \0 because calloc does that
		519	* for us.) */
		520	}
		521
		522	/* Returns a bitmap that represents which squares on the right and bottom
		523	* edges of a square (i,j) match the given character:
		524	* 1 match on (i+1, j)
		525	* 2 match on (i, j+1)
		526	* 4 match on (i+1, j+1)
		527	* and the possible combinations thereof.
		528	*/
		529	static int noinline
		530	calc_pattern (char ch, layout &maze, int i, int j)
		531	{
		532	int pattern = 0;
		533
		534	if (i + 1 < maze.w && maze[i + 1][j] == ch)
		535	pattern \|= 1;
		536
		537	if (j + 1 < maze.h)
		538	{
		539	if (maze[i][j + 1] == ch)
		540	pattern \|= 2;
		541
		542	if (i + 1 < maze.w && maze[i + 1][j + 1] == ch)
		543	pattern \|= 4;
		544	}
		545
		546	return pattern;
		547	}
		548
		549	/* Expand a wall. This function will try to sensibly connect the resulting
		550	* wall to adjacent wall squares, so that the result won't have disconnected
		551	* walls.
		552	*/
		553	static void inline
		554	expand_wall (layout &newlayout, int i, int j, layout &maze)
		555	{
		556	int wall_pattern = calc_pattern ('#', maze, i, j);
		557	int door_pattern = calc_pattern ('D', maze, i, j);
		558	int both_pattern = wall_pattern \| door_pattern;
		559
		560	newlayout[i * 2][j * 2] = '#';
		561
		562	if (i + 1 < maze.w)
		563	{
		564	if (both_pattern & 1)
		565	{ /* join walls/doors to the right */
		566	/* newlayout[i2+1][j2] = '#'; */
		567	newlayout[i * 2 + 1][j * 2] = maze[i + 1][j];
		568	}
		569	}
		570
		571	if (j + 1 < maze.h)
		572	{
		573	if (both_pattern & 2)
		574	{ /* join walls/doors to the bottom */
		575	/* newlayout[i2][j2+1] = '#'; */
		576	newlayout[i * 2][j * 2 + 1] = maze[i][j + 1];
		577	}
		578
		579	if (wall_pattern == 7)
		580	{ /* if orig maze is a 2x2 wall block,
		581	* we fill the result with walls. */
		582	newlayout[i * 2 + 1][j * 2 + 1] = '#';
		583	}
		584	}
		585	}
		586
		587	/* This function will try to sensibly connect doors so that they meet up with
		588	* adjacent walls. Note that it will also presumptuously delete (ignore) doors
		589	* that it doesn't know how to correctly expand.
		590	*/
		591	static void inline
		592	expand_door (layout &newlayout, int i, int j, layout &maze)
		593	{
		594	int wall_pattern = calc_pattern ('#', maze, i, j);
		595	int door_pattern = calc_pattern ('D', maze, i, j);
		596	int join_pattern;
		597
		598	/* Doors "like" to connect to walls more than other doors. If there is
		599	* a wall and another door, this door will connect to the wall and
		600	* disconnect from the other door. */
		601	if (wall_pattern & 3)
		602	join_pattern = wall_pattern;
		603	else
		604	join_pattern = door_pattern;
		605
		606	newlayout[i * 2][j * 2] = 'D';
		607
		608	if (i + 1 < maze.w)
		609	if (join_pattern & 1)
		610	/* there is a door/wall to the right */
		611	newlayout[i * 2 + 1][j * 2] = 'D';
		612
		613	if (j + 1 < maze.h)
		614	if (join_pattern & 2)
		615	/* there is a door/wall below */
		616	newlayout[i * 2][j * 2 + 1] = 'D';
		617	}
		618
		619	void
		620	layout::expand2x ()
		621	{
		622	layout new_layout (w * 2 - 1, h * 2 - 1);
		623
		624	new_layout.clear ();
		625
		626	for (int i = 0; i < w; i++)
		627	for (int j = 0; j < h; j++)
		628	switch (data [i][j])
		629	{
		630	case '#': expand_wall (new_layout, i, j, *this); break;
		631	case 'D': expand_door (new_layout, i, j, *this); break;
		632	default: expand_misc (new_layout, i, j, *this); break;
		633	}
		634
		635	swap (new_layout);
		636	}
		637
		638	/////////////////////////////////////////////////////////////////////////////
		639
		640	/* checks the maze to see if I can stick a horizontal(dir = 0) wall
		641	(or vertical, dir == 1)
		642	here which ends up on other walls sensibly. */
		643	static int
		644	can_make_wall (const layout &maze, int dx, int dy, int dir)
		645	{
		646	int i1;
		647	int length = 0;
		648
		649	/* dont make walls if we're on the edge. */
		650	if (dx == 0 \|\| dx == (maze.w - 1) \|\| dy == 0 \|\| dy == (maze.h - 1))
		651	return -1;
		652
		653	/* don't make walls if we're ON a wall. */
		654	if (maze [dx][dy] != 0)
		655	return -1;
		656
		657	if (dir == 0) /* horizontal */
		658	{
		659	int y = dy;
		660
		661	for (i1 = dx - 1; i1 > 0; i1--)
		662	{
		663	int sindex = surround_flag2 (maze, i1, y);
		664
		665	if (sindex == 1) break;
		666	if (sindex != 0) return -1; /* can't make horiz. wall here */
		667	if (maze[i1][y] != 0) return -1; /* can't make horiz. wall here */
		668
		669	length++;
		670	}
		671
		672	for (i1 = dx + 1; i1 < maze.w - 1; i1++)
		673	{
		674	int sindex = surround_flag2 (maze, i1, y);
		675
		676	if (sindex == 2) break;
		677	if (sindex != 0) return -1; /* can't make horiz. wall here */
		678	if (maze[i1][y] != 0) return -1; /* can't make horiz. wall here */
		679
		680	length++;
		681	}
		682	return length;
		683	}
		684	else
		685	{ /* vertical */
		686	int x = dx;
		687
		688	for (i1 = dy - 1; i1 > 0; i1--)
		689	{
		690	int sindex = surround_flag2 (maze, x, i1);
		691
		692	if (sindex == 4) break;
		693	if (sindex != 0) return -1; /* can't make vert. wall here */
		694	if (maze[x][i1] != 0) return -1; /* can't make horiz. wall here */
		695
		696	length++;
		697	}
		698
		699	for (i1 = dy + 1; i1 < maze.h - 1; i1++)
		700	{
		701	int sindex = surround_flag2 (maze, x, i1);
		702
		703	if (sindex == 8) break;
		704	if (sindex != 0) return -1; /* can't make verti. wall here */
		705	if (maze[x][i1] != 0) return -1; /* can't make horiz. wall here */
		706
		707	length++;
		708	}
		709
		710	return length;
		711	}
		712
		713	return -1;
		714	}
		715
		716	int
		717	make_wall (char **maze, int x, int y, int dir)
		718	{
		719	maze[x][y] = 'D'; /* mark a door */
		720
		721	switch (dir)
		722	{
		723	case 0: /* horizontal */
		724	{
		725	for (int i1 = x - 1; maze[i1][y] == 0; --i1) maze[i1][y] = '#';
		726	for (int i1 = x + 1; maze[i1][y] == 0; ++i1) maze[i1][y] = '#';
149	break;	727	break;
		728	}
		729	case 1: /* vertical */
		730	{
		731	for (int i1 = y - 1; maze[x][i1] == 0; --i1) maze[x][i1] = '#';
		732	for (int i1 = y + 1; maze[x][i1] == 0; ++i1) maze[x][i1] = '#';
		733	break;
		734	}
		735	}
150		736
151	d = dist [x][y];	737	return 0;
		738	}
		739
		740	void
		741	layout::roomify ()
		742	{
		743	int tries = w * h / 30;
		744
		745	for (int ti = 0; ti < tries; ti++)
152	}	746	{
		747	/* starting location for looking at creating a door */
		748	int dx = rmg_rndm (w);
		749	int dy = rmg_rndm (h);
		750
		751	/* results of checking on creating walls. */
		752	int cx = can_make_wall (this, dx, dy, 0); / horizontal */
		753	int cy = can_make_wall (this, dx, dy, 1); / vertical */
		754
		755	if (cx == -1)
		756	{
		757	if (cy != -1)
		758	make_wall (*this, dx, dy, 1);
		759
		760	continue;
		761	}
		762
		763	if (cy == -1)
		764	{
		765	make_wall (*this, dx, dy, 0);
		766	continue;
		767	}
		768
		769	if (cx < cy)
		770	make_wall (*this, dx, dy, 0);
		771	else
		772	make_wall (*this, dx, dy, 1);
		773	}
		774	}
		775
		776	/////////////////////////////////////////////////////////////////////////////
		777
		778	// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
		779	void
		780	layout::gen_cave (int subtype)
		781	{
		782	switch (subtype)
		783	{
		784	// a rough cave
		785	case 0:
		786	fill_rand (rmg_rndm (85, 97));
		787	break;
		788
		789	// corridors
		790	case 1:
		791	fill_rand (rmg_rndm (5, 40));
		792	erode_1_2 (5, 2, 10);
		793	erode_1_2 (5, -1, 10);
		794	erode_1_2 (5, 2, 1);
		795	break;
		796
		797	// somewhat open, roundish
		798	case 2:
		799	fill_rand (45);
		800	erode_1_2 (5, 0, 5);
		801	erode_1_2 (5, 1, 1);
		802	break;
		803
		804	// wide open, some room-like structures
		805	case 3:
		806	fill_rand (45);
		807	erode_1_2 (5, 2, 4);
		808	erode_1_2 (5, -1, 3);
		809	break;
		810	}
		811
		812	border ();
		813	isolation_remover ();
153	}	814	}
154		815
155	static void	816	static void
156	isolation_remover (Layout maze, bool dirty)	817	gen_mixed_ (layout &maze, random_map_params *RP, int dir)
157	{	818	{
158	Layout dist (maze->w, maze->h);	819	if (maze.w < 20 && maze.h < 20 && !rmg_rndm (3))
		820	dir = 2; // stop recursion randomly
159		821
160	dist->fill (255);	822	if (dir == 0 && maze.w > 16)
		823	{
		824	int m = rmg_rndm (8, maze.w - 8);
161		825
162	fixed_stack<point> seeds (maze->w * maze->h * 4);	826	layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP, !dir);
		827	layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP, !dir);
		828	}
		829	else if (dir == 1 && maze.h > 16)
		830	{
		831	int m = rmg_rndm (8, maze.h - 8);
163		832
164	// phase 1, find seed	833	layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP, !dir);
165	for (int x = 1; x < maze->w; ++x)	834	layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP, !dir);
166	for (int y = 1; y < maze->h; ++y)	835	}
167	if (!maze [x][y])	836	else
		837	{
		838	RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
		839
		840	if (RP->map_layout_style == LAYOUT_MULTIPLE)
		841	++RP->map_layout_style;
		842
		843	maze.generate (RP);
		844	}
		845	}
		846
		847	// recursive subdivision with random sublayouts
		848	static void
		849	gen_mixed (layout &maze, random_map_params *RP)
		850	{
		851	random_map_params &rp = *new random_map_params (RP);
		852	gen_mixed_ (maze, &rp, rmg_rndm (2));
		853	delete &rp;
		854
		855	maze.border ();
		856	maze.isolation_remover ();
		857	}
		858
		859	/* function selects the maze function and gives it whatever
		860	arguments it needs. */
		861	void
		862	layout::generate (random_map_params *RP)
		863	{
		864	switch (RP->map_layout_style)
		865	{
		866	case LAYOUT_ONION:
		867	map_gen_onion (*this, RP->layoutoptions1, RP->layoutoptions2);
		868
		869	if (!(rmg_rndm (3)) && !(RP->layoutoptions1 & (RMOPT_WALLS_ONLY \| RMOPT_WALL_OFF)))
		870	roomify ();
		871
		872	break;
		873
		874	case LAYOUT_MAZE:
		875	maze_gen (*this, RP->get_iv ("maze_type", rmg_rndm (4)));
		876
		877	if (rmg_rndm (2))
		878	doorify ();
		879
		880	break;
		881
		882	case LAYOUT_SPIRAL:
		883	map_gen_spiral (*this, RP->layoutoptions1);
		884
		885	if (rmg_rndm (2))
		886	doorify ();
		887
		888	break;
		889
		890	case LAYOUT_ROGUELIKE:
		891	/* Don't put symmetry in rogue maps. There isn't much reason to
		892	* do so in the first place (doesn't make it any more interesting),
		893	* but more importantly, the symmetry code presumes we are symmetrizing
		894	* spirals, or maps with lots of passages - making a symmetric rogue
		895	* map fails because its likely that the passages the symmetry process
		896	* creates may not connect the rooms.
168	{	897	*/
169	seeds.push (point (x, y));	898	RP->symmetry_used = SYMMETRY_NONE;
		899	roguelike_layout_gen (*this, RP->layoutoptions1);
		900	/* no doorifying... done already */
		901	break;
170		902
171	// phase 2, while we have seeds, if	903	case LAYOUT_SNAKE:
172	// seed is empty, floodfill, else grow	904	make_snake_layout (*this, RP->layoutoptions1);
173		905
174	while (seeds.size)	906	if (rmg_rndm (2))
175	{	907	roomify ();
176	point p = seeds.remove (rmg_rndm (seeds.size));
177		908
178	x = p.x;	909	break;
179	y = p.y;
180		910
181	if (!maze [x][y])	911	case LAYOUT_SQUARE_SPIRAL:
182	{	912	make_square_spiral_layout (*this, RP->layoutoptions1);
183	// found new isolated area, make tunnel?
184	if (!dirty)
185	push_flood_fill (maze, dist, seeds, x, y);
186		913
187	make_tunnel (maze, dist, seeds, x, y, 255);	914	if (rmg_rndm (2))
		915	roomify ();
188		916
189	if (dirty)	917	break;
190	push_flood_fill (maze, dist, seeds, x, y);
191	}
192	else
193	{
194	U8 d = U8 (dist [x][y]) + 1;
195		918
196	if (x < maze->w - 1 && U8 (dist [x + 1][y]) > d)	919	case LAYOUT_CAVE:
197	{	920	gen_cave (RP->get_iv ("cave_type", rmg_rndm (4)));
198	dist [x + 1][y] = d;
199	seeds.push (point (x + 1, y));
200	}
201		921
202	if (x > 0 && U8 (dist [x - 1][y]) > d)	922	if (rmg_rndm (2))
203	{	923	doorify ();
204	dist [x - 1][y] = d;
205	seeds.push (point (x - 1, y));
206	}
207		924
208	if (y < maze->h - 1 && U8 (dist [x][y + 1]) > d)	925	break;
209	{
210	dist [x][y + 1] = d;
211	seeds.push (point (x, y + 1));
212	}
213		926
214	if (y > 0 && U8 (dist [x][y - 1]) > d)	927	case LAYOUT_MULTIPLE:
215	{	928	gen_mixed (*this, RP);
216	dist [x][y - 1] = d;	929	break;
217	seeds.push (point (x, y - 1));
218	}
219	}
220	}
221		930
222	goto success;	931	default:
223	}	932	abort ();
224		933	}
225	success:
226	dist.free ();
227
228	// we mark free but visited floors as 1, undo this here
229	for (int x = 0; x < maze->w; ++x)
230	for (int y = 0; y < maze->h; ++y)
231	if (maze [x][y] == 1)
232	maze [x][y] = 0;
233	}	934	}
234		935
235	void	936	//-GPL
236	LayoutData::isolation_remover (bool dirty)
237	{
238	Layout maze;
239	maze.ptr = this;
240	::isolation_remover (maze, dirty);
241	}
242		937
243	#if 0	938	#if 0
244	static struct demo	939	static struct demo
245	{	940	{
246	demo ()	941	demo ()
247	{	942	{
248	Layout maze (40, 25);
249	rmg_rndm.seed (time (0));	943	rmg_rndm.seed (time (0));
250		944
251	for (int p = 80; p < 100; p += 1) {
252	maze->fill ('#');
253
254	#if 1
255	for (int x = 1; x < maze->w - 1; ++x)
256	for (int y = 1; y < maze->h - 1; ++y)
257	maze [x][y] = rmg_rndm(100) < p ? '#' : 0;
258	#else
259	room (maze, 5, 5);
260	room (maze, 30,20);
261	room (maze, 10,20);
262	room (maze, 20,10);
263	#endif
264
265	isolation_remover (maze, 1);
266	maze.print ();
267	}
268
269	#if 0
270	for(int i=1;i<10;i)	945	for(int i=1;i<100;i++)
271	{	946	{
272	maze_gen (maze, 1);	947	layout maze (40, 25);
		948	maze.fill_rand (85);
		949	maze.border ();
		950	maze.isolation_remover ();
273	maze.print ();	951	maze.print ();
274	}	952	}
275	#endif	953
276	exit (1);	954	exit (1);
277	}	955	}
278	} demo;	956	} demo;
279	#endif	957	#endif

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing deliantra/server/random_maps/layout.C (file contents): Revision 1.1 by root, Wed Jun 30 20:51:02 2010 UTC vs. Revision 1.16 by root, Sat Jul 3 11:52:11 2010 UTC

Diff Legend

Comparing deliantra/server/random_maps/layout.C (file contents):
Revision 1.1 by root, Wed Jun 30 20:51:02 2010 UTC vs.
Revision 1.16 by root, Sat Jul 3 11:52:11 2010 UTC