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