Etude de la source de duke nukem 3d

**supernewbienoob** · 31/12/2010, 15h16

Bonjour,

Je me remets à étudier la source de duke nukem 3d ( on peut la dl ici par ex: http://www.fileshack.com/login.x?file=2585 )

Mon but est de comprendre comment fonctionne un moteur basé sur les secteurs.
J'avais étudié la source de quake comme tout le monde (plus facile car très documentée) et je suis un peu frustré par les bsp qui sont statiques, je voudrais me pencher sur les maps en secteur qui ont l'avantage de pouvoir déformer le décor... la contrepartie c'est que c'est plus lent et plus compliqué à parcourir.

J'avais réussi sans trop de mal à extraire les specs du format de maps de duke3d. l'encodage des secteurs est assez simple, ce sont des polys quelconques avec des index stockés dans les walls, qui permettent de connecter le wall à un autre secteur s'il s'agit de la face d'un portail.

Maintenant j'essaye de comprendre quelque chose à l'algorithme utilisé pour localiser un point dans le graph de secteurs.

Les fichiers sources sont assez énormes et plus ou moins illisibles, donc j'aimerais savoir s'il y'a quelqu'un parmi vous qui s'est déjà tapé l'étude de la source et qui pourrait me guider vers le bout de code qui contient la formule de calcul permettant de savoir dans quel secteur se trouve un point.

il y'a des versions plus simples du build engine sur la page du développeur, je trouverai peut-être plus facilement dedans: http://www.advsys.net/ken/buildsrc/default.htm

je crois que les calculs se trouvent dans la fonction clipmove

je ne saurais dire à quel endroit, je cherche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
clipmove (long *x, long *y, long *z, short *sectnum,
			 long xvect, long yvect,
			 long walldist, long ceildist, long flordist, unsigned long cliptype)
{
	walltype *wal, *wal2;
	spritetype *spr;
	sectortype *sec, *sec2;
	long i, j, templong1, templong2;
	long oxvect, oyvect, goalx, goaly, intx, inty, lx, ly, retval;
	long k, l, clipsectcnt, startwall, endwall, cstat, dasect;
	long x1, y1, x2, y2, cx, cy, rad, xmin, ymin, xmax, ymax, daz, daz2;
	long bsz, dax, day, xoff, yoff, xspan, yspan, cosang, sinang, tilenum;
	long xrepeat, yrepeat, gx, gy, dx, dy, dasprclipmask, dawalclipmask;
	long hitwall, cnt, clipyou;
 
	if (((xvect|yvect) == 0) || (*sectnum < 0)) return(0);
	retval = 0;
 
	oxvect = xvect;
	oyvect = yvect;
 
	goalx = (*x) + (xvect>>14);
	goaly = (*y) + (yvect>>14);
 
 
	clipnum = 0;
 
	cx = (((*x)+goalx)>>1);
	cy = (((*y)+goaly)>>1);
		//Extra walldist for sprites on sector lines
	gx = goalx-(*x); gy = goaly-(*y);
	rad = nsqrtasm(gx*gx + gy*gy) + MAXCLIPDIST+walldist + 8;
	xmin = cx-rad; ymin = cy-rad;
	xmax = cx+rad; ymax = cy+rad;
 
	dawalclipmask = (cliptype&65535);        //CLIPMASK0 = 0x00010001
	dasprclipmask = (cliptype>>16);          //CLIPMASK1 = 0x01000040
 
	clipsectorlist[0] = (*sectnum);
	clipsectcnt = 0; clipsectnum = 1;
	do
	{
		dasect = clipsectorlist[clipsectcnt++];
		sec = &sector[dasect];
		startwall = sec->wallptr; endwall = startwall + sec->wallnum;
		for(j=startwall,wal=&wall[startwall];j<endwall;j++,wal++)
		{
			wal2 = &wall[wal->point2];
			if ((wal->x < xmin) && (wal2->x < xmin)) continue;
			if ((wal->x > xmax) && (wal2->x > xmax)) continue;
			if ((wal->y < ymin) && (wal2->y < ymin)) continue;
			if ((wal->y > ymax) && (wal2->y > ymax)) continue;
 
			x1 = wal->x; y1 = wal->y; x2 = wal2->x; y2 = wal2->y;
 
			dx = x2-x1; dy = y2-y1;
			if (dx*((*y)-y1) < ((*x)-x1)*dy) continue;  //If wall's not facing you
 
			if (dx > 0) dax = dx*(ymin-y1); else dax = dx*(ymax-y1);
			if (dy > 0) day = dy*(xmax-x1); else day = dy*(xmin-x1);
			if (dax >= day) continue;
 
			clipyou = 0;
			if ((wal->nextsector < 0) || (wal->cstat&dawalclipmask)) clipyou = 1;
			else if (editstatus == 0)
			{
				if (rintersect(*x,*y,0,gx,gy,0,x1,y1,x2,y2,&dax,&day,&daz) == 0)
					dax = *x, day = *y;
				daz = getflorzofslope((short)dasect,dax,day);
				daz2 = getflorzofslope(wal->nextsector,dax,day);
 
				sec2 = &sector[wal->nextsector];
				if (daz2 < daz-(1<<8))
					if ((sec2->floorstat&1) == 0)
						if ((*z) >= daz2-(flordist-1)) clipyou = 1;
				if (clipyou == 0)
				{
					daz = getceilzofslope((short)dasect,dax,day);
					daz2 = getceilzofslope(wal->nextsector,dax,day);
					if (daz2 > daz+(1<<8))
						if ((sec2->ceilingstat&1) == 0)
							if ((*z) <= daz2+(ceildist-1)) clipyou = 1;
				}
			}
 
			if (clipyou)
			{
					//Add 2 boxes at endpoints
				bsz = walldist; if (gx < 0) bsz = -bsz;
				addclipline(x1-bsz,y1-bsz,x1-bsz,y1+bsz,(short)j+32768);
				addclipline(x2-bsz,y2-bsz,x2-bsz,y2+bsz,(short)j+32768);
				bsz = walldist; if (gy < 0) bsz = -bsz;
				addclipline(x1+bsz,y1-bsz,x1-bsz,y1-bsz,(short)j+32768);
				addclipline(x2+bsz,y2-bsz,x2-bsz,y2-bsz,(short)j+32768);
 
				dax = walldist; if (dy > 0) dax = -dax;
				day = walldist; if (dx < 0) day = -day;
				addclipline(x1+dax,y1+day,x2+dax,y2+day,(short)j+32768);
			}
			else
			{
				for(i=clipsectnum-1;i>=0;i--)
					if (wal->nextsector == clipsectorlist[i]) break;
				if (i < 0) clipsectorlist[clipsectnum++] = wal->nextsector;
			}
		}
 
		for(j=headspritesect[dasect];j>=0;j=nextspritesect[j])
		{
			spr = &sprite[j];
			cstat = spr->cstat;
			if ((cstat&dasprclipmask) == 0) continue;
			x1 = spr->x; y1 = spr->y;
			switch(cstat&48)
			{
				case 0:
					if ((x1 >= xmin) && (x1 <= xmax) && (y1 >= ymin) && (y1 <= ymax))
					{
						k = ((tilesizy[spr->picnum]*spr->yrepeat)<<2);
						if (cstat&128) daz = spr->z+(k>>1); else daz = spr->z;
						if (picanm[spr->picnum]&0x00ff0000) daz -= ((long)((signed char)((picanm[spr->picnum]>>16)&255))*spr->yrepeat<<2);
						if (((*z) < daz+ceildist) && ((*z) > daz-k-flordist))
						{
							bsz = (spr->clipdist<<2)+walldist; if (gx < 0) bsz = -bsz;
							addclipline(x1-bsz,y1-bsz,x1-bsz,y1+bsz,(short)j+49152);
							bsz = (spr->clipdist<<2)+walldist; if (gy < 0) bsz = -bsz;
							addclipline(x1+bsz,y1-bsz,x1-bsz,y1-bsz,(short)j+49152);
						}
					}
					break;
				case 16:
					k = ((tilesizy[spr->picnum]*spr->yrepeat)<<2);
					if (cstat&128) daz = spr->z+(k>>1); else daz = spr->z;
					if (picanm[spr->picnum]&0x00ff0000) daz -= ((long)((signed char)((picanm[spr->picnum]>>16)&255))*spr->yrepeat<<2);
					daz2 = daz-k;
					daz += ceildist; daz2 -= flordist;
					if (((*z) < daz) && ((*z) > daz2))
					{
							//These lines get the 2 points of the rotated sprite
							//Given: (x1, y1) starts out as the center point
						tilenum = spr->picnum;
						xoff = (long)((signed char)((picanm[tilenum]>>8)&255))+((long)spr->xoffset);
						if ((cstat&4) > 0) xoff = -xoff;
						k = spr->ang; l = spr->xrepeat;
						dax = sintable[k&2047]*l; day = sintable[(k+1536)&2047]*l;
						l = tilesizx[tilenum]; k = (l>>1)+xoff;
						x1 -= mulscale16(dax,k); x2 = x1+mulscale16(dax,l);
						y1 -= mulscale16(day,k); y2 = y1+mulscale16(day,l);
						if (clipinsideboxline(cx,cy,x1,y1,x2,y2,rad) != 0)
						{
							dax = mulscale14(sintable[(spr->ang+256+512)&2047],walldist);
							day = mulscale14(sintable[(spr->ang+256)&2047],walldist);
 
							if ((x1-(*x))*(y2-(*y)) >= (x2-(*x))*(y1-(*y)))   //Front
							{
								addclipline(x1+dax,y1+day,x2+day,y2-dax,(short)j+49152);
							}
							else
							{
								if ((cstat&64) != 0) continue;
								addclipline(x2-dax,y2-day,x1-day,y1+dax,(short)j+49152);
							}
 
								//Side blocker
							if ((x2-x1)*((*x)-x1) + (y2-y1)*((*y)-y1) < 0)
								{ addclipline(x1-day,y1+dax,x1+dax,y1+day,(short)j+49152); }
							else if ((x1-x2)*((*x)-x2) + (y1-y2)*((*y)-y2) < 0)
								{ addclipline(x2+day,y2-dax,x2-dax,y2-day,(short)j+49152); }
						}
					}
					break;
				case 32:
					daz = spr->z+ceildist;
					daz2 = spr->z-flordist;
					if (((*z) < daz) && ((*z) > daz2))
					{
						if ((cstat&64) != 0)
							if (((*z) > spr->z) == ((cstat&8)==0)) continue;
 
						tilenum = spr->picnum;
						xoff = (long)((signed char)((picanm[tilenum]>>8)&255))+((long)spr->xoffset);
						yoff = (long)((signed char)((picanm[tilenum]>>16)&255))+((long)spr->yoffset);
						if ((cstat&4) > 0) xoff = -xoff;
						if ((cstat&8) > 0) yoff = -yoff;
 
						k = spr->ang;
						cosang = sintable[(k+512)&2047]; sinang = sintable[k];
						xspan = tilesizx[tilenum]; xrepeat = spr->xrepeat;
						yspan = tilesizy[tilenum]; yrepeat = spr->yrepeat;
 
						dax = ((xspan>>1)+xoff)*xrepeat; day = ((yspan>>1)+yoff)*yrepeat;
						rxi[0] = x1 + dmulscale16(sinang,dax,cosang,day);
						ryi[0] = y1 + dmulscale16(sinang,day,-cosang,dax);
						l = xspan*xrepeat;
						rxi[1] = rxi[0] - mulscale16(sinang,l);
						ryi[1] = ryi[0] + mulscale16(cosang,l);
						l = yspan*yrepeat;
						k = -mulscale16(cosang,l); rxi[2] = rxi[1]+k; rxi[3] = rxi[0]+k;
						k = -mulscale16(sinang,l); ryi[2] = ryi[1]+k; ryi[3] = ryi[0]+k;
 
						dax = mulscale14(sintable[(spr->ang-256+512)&2047],walldist);
						day = mulscale14(sintable[(spr->ang-256)&2047],walldist);
 
						if ((rxi[0]-(*x))*(ryi[1]-(*y)) < (rxi[1]-(*x))*(ryi[0]-(*y)))
						{
							if (clipinsideboxline(cx,cy,rxi[1],ryi[1],rxi[0],ryi[0],rad) != 0)
								addclipline(rxi[1]-day,ryi[1]+dax,rxi[0]+dax,ryi[0]+day,(short)j+49152);
						}
						else if ((rxi[2]-(*x))*(ryi[3]-(*y)) < (rxi[3]-(*x))*(ryi[2]-(*y)))
						{
							if (clipinsideboxline(cx,cy,rxi[3],ryi[3],rxi[2],ryi[2],rad) != 0)
								addclipline(rxi[3]+day,ryi[3]-dax,rxi[2]-dax,ryi[2]-day,(short)j+49152);
						}
 
						if ((rxi[1]-(*x))*(ryi[2]-(*y)) < (rxi[2]-(*x))*(ryi[1]-(*y)))
						{
							if (clipinsideboxline(cx,cy,rxi[2],ryi[2],rxi[1],ryi[1],rad) != 0)
								addclipline(rxi[2]-dax,ryi[2]-day,rxi[1]-day,ryi[1]+dax,(short)j+49152);
						}
						else if ((rxi[3]-(*x))*(ryi[0]-(*y)) < (rxi[0]-(*x))*(ryi[3]-(*y)))
						{
							if (clipinsideboxline(cx,cy,rxi[0],ryi[0],rxi[3],ryi[3],rad) != 0)
								addclipline(rxi[0]+dax,ryi[0]+day,rxi[3]+day,ryi[3]-dax,(short)j+49152);
						}
					}
					break;
			}
		}
	} while (clipsectcnt < clipsectnum);
 
 
	hitwall = 0;
	cnt = clipmoveboxtracenum;
	do
	{
		intx = goalx; inty = goaly;
		if ((hitwall = raytrace(*x, *y, &intx, &inty)) >= 0)
		{
			lx = clipit[hitwall].x2-clipit[hitwall].x1;
			ly = clipit[hitwall].y2-clipit[hitwall].y1;
			templong2 = lx*lx + ly*ly;
			if (templong2 > 0)
			{
				templong1 = (goalx-intx)*lx + (goaly-inty)*ly;
 
				if ((klabs(templong1)>>11) < templong2)
					i = divscale20(templong1,templong2);
				else
					i = 0;
				goalx = mulscale20(lx,i)+intx;
				goaly = mulscale20(ly,i)+inty;
			}
 
			templong1 = dmulscale6(lx,oxvect,ly,oyvect);
			for(i=cnt+1;i<=clipmoveboxtracenum;i++)
			{
				j = hitwalls[i];
				templong2 = dmulscale6(clipit[j].x2-clipit[j].x1,oxvect,clipit[j].y2-clipit[j].y1,oyvect);
				if ((templong1^templong2) < 0)
				{
					updatesector(*x,*y,sectnum);
					return(retval);
				}
			}
 
			keepaway(&goalx, &goaly, hitwall);
			xvect = ((goalx-intx)<<14);
			yvect = ((goaly-inty)<<14);
 
			if (cnt == clipmoveboxtracenum) retval = clipobjectval[hitwall];
			hitwalls[cnt] = hitwall;
		}
		cnt--;
 
		*x = intx;
		*y = inty;
	} while (((xvect|yvect) != 0) && (hitwall >= 0) && (cnt > 0));
 
	for(j=0;j<clipsectnum;j++)
		if (inside(*x,*y,clipsectorlist[j]) == 1)
		{
			*sectnum = clipsectorlist[j];
			return(retval);
		}
 
	*sectnum = -1; templong1 = 0x7fffffff;
	for(j=numsectors-1;j>=0;j--)
		if (inside(*x,*y,j) == 1)
		{
			if (sector[j].ceilingstat&2)
				templong2 = (getceilzofslope((short)j,*x,*y)-(*z));
			else
				templong2 = (sector[j].ceilingz-(*z));
 
			if (templong2 > 0)
			{
				if (templong2 < templong1)
					{ *sectnum = j; templong1 = templong2; }
			}
			else
			{
				if (sector[j].floorstat&2)
					templong2 = ((*z)-getflorzofslope((short)j,*x,*y));
				else
					templong2 = ((*z)-sector[j].floorz);
 
				if (templong2 <= 0)
				{
					*sectnum = j;
					return(retval);
				}
				if (templong2 < templong1)
					{ *sectnum = j; templong1 = templong2; }
			}
		}
 
	return(retval);
}

**supernewbienoob** · 01/01/2011, 18h03

je me suis gourré j'ai posté une fonction de collision

pour savoir si un point est dans un sector j'ai trouvé c'est un calcul tout simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inside (long x, long y, short sectnum)
{
	walltype *wal;
	long i, x1, y1, x2, y2;
	unsigned long cnt;
 
	if ((sectnum < 0) || (sectnum >= numsectors)) return(-1);
 
	cnt = 0;
	wal = &wall[sector[sectnum].wallptr];
	i = sector[sectnum].wallnum;
	do
	{
		y1 = wal->y-y; y2 = wall[wal->point2].y-y;
		if ((y1^y2) < 0)
		{
			x1 = wal->x-x; x2 = wall[wal->point2].x-x;
			if ((x1^x2) >= 0) cnt ^= x1; else cnt ^= (x1*y2-x2*y1)^y2;
		}
		wal++; i--;
	} while (i);
	return(cnt>>31);
}

reste plus qu'à y comprendre quelque chose...
cette formule doit avoir un nom bien précis

le coup des xor je capte ça sert à comparer les signes

l'algo général apparemment c'est celui là: http://en.wikipedia.org/wiki/File:Re...venPolygon.svg
écrit à la sauce code illisible des années 80

bon après avoir un peu étudié ça j'ai compris tout le code sauf cette partie là:

cnt ^= (x1*y2-x2*y1)^y2;

ça m'a l'air d'être un genre de produit scalaire mais j'ai pas tout compris
et l'imbrication des xor je commence à décrocher... j'avais compris à quoi ils servent dans le reste du code mais là je sèche
si quelqu'un peut me l'expliquer ce serait super

**Emmanuel Deloget** · 05/01/2011, 11h15

Envoyé par supernewbienoob

bon après avoir un peu étudié ça j'ai compris tout le code sauf cette partie là:

ça m'a l'air d'être un genre de produit scalaire mais j'ai pas tout compris
et l'imbrication des xor je commence à décrocher... j'avais compris à quoi ils servent dans le reste du code mais là je sèche
si quelqu'un peut me l'expliquer ce serait super

C'est pas un produit scalaire : c'est le calcul de la troisième composante d'un produit vectoriel (donc, étant donné que les murs ne sont pas inclinés dans ce jeu, c'est la composante sur Z de la normale au mur ; si j'ai bien tout compris. En tout cas, c'est une composante de normale

).

**supernewbienoob** · 05/01/2011, 18h36

j'ai pijé le truc, ça sert à calculer si le point se trouve à gauche du plan incliné

l'algo point-to-polygon consiste à voir si le nombre d'intersections à gauche est impair

je l'ai retraduit en version plus lisible en remplacant les xor par des <= et l'int count par un booléen inside

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inside (long x, long y, short sectnum)
{
   walltype *wal;
    long i, x1, y1, x2, y2;
    bool ins;
 
    if ((sectnum < 0) || (sectnum >= numsectors)) return(-1);
 
    ins = false;
    wal = &wall[sector[sectnum].wallptr];
    i = sector[sectnum].wallnum;
    do
    {
        y1 = wal->y-y; y2 = wall[wal->point2].y-y;
        if (y1>=0) != (y2>=0)
        {
            x1 = wal->x-x; x2 = wall[wal->point2].x-x;
            if ((x1>=0)==(x2>=0)) ins = (ins==(x1>=0)); // change bool si intersection à gauche 
            else ins = (ins==(((x1*y2-x2*y1)>=0)==(y2>=0))); // change bool si intersection à gauche 
        }
        wal++; i--;
    } while (i);
    return ins;
}

je n'ai pas testé si c'est plus rapide comme ça.
il me semble que c'est pas pour des questions de perfs que la source utilisait des xor, mais parce qu'à l'époque le type booléen n'existait pas en C

bon bien donc j'ai compris comment on localise un point dans un sector 2d codé en integer

à priori c'est pas possible avec des float, y'a un risque d'erreur parce que les opérations entre float ça renvoie un résultat approximatif.. par précaution j'essayerais donc pas avec des float... donc un sector engine ça se baserait sur des integer contrairement à un bsp engine

maintenant je vais essayer d'appliquer cet algo sur des solids 3d avec des coords integer (je cherche pas à cloner ce vieux moteur mais à comprendre comment on parcourt une map de secteurs)
à priori c'est pas compliqué, on fait d'abord le test point/polygon en 2d sur tous les triangles (sur plan x/y), et puis on finit avec un test point/plan en 3d sur l'axe z (l'astuce de ce système c'est qu'on décompose le calcul sur les 3 axes, comme ça on renvoie des résultats exacts)

par contre je sais pas si c'est optimal d'appliquer le test point/poly concave sur des triangles, y'a pas un algo plus simple pour les convexes ? (qui fonctionne avec la même logique de décomposition sur x & y ?)

**Mat.M** · 05/01/2011, 23h31

Salut Duke Nukem c est quelque chose qui est totalement dépassé d un point de vue technique.
Ceci dit si tu y tiens...

**supernewbienoob** · 06/01/2011, 01h38

ben c'est pas grave parce que d'une part je bosse pas chez epic, je suis un petit amateur qui fait des petits jeux dans son coin donc je cherche pas à rivaliser avec l'unreal engine

ensuite je veux pas faire un jeu basé sur le vieux moteur de dn3d (même si ça se fait chez les indie) je cherche à comprendre comment ça marche une map en secteur. c'est pour ça que j'ai décortiqué l'algo en vue de l'appliquer à la 3d

Etude de la source de duke nukem 3d

Développement 2D, 3D et Jeux

Discussions similaires

Partager

Partager