1/*	SCCS Id: @(#)worm.c	3.4	1995/01/28	*/
2/* Copyright (c) Stichting Mathematisch Centrum, Amsterdam, 1985. */
3/* NetHack may be freely redistributed.  See license for details. */
4
5#include "hack.h"
6#include "lev.h"
7
8#define newseg()		(struct wseg *) alloc(sizeof(struct wseg))
9#define dealloc_seg(wseg)	free((genericptr_t) (wseg))
10
11/* worm segment structure */
12struct wseg {
13    struct wseg *nseg;
14    xchar  wx, wy;	/* the segment's position */
15};
16
17STATIC_DCL void FDECL(toss_wsegs, (struct wseg *,BOOLEAN_P));
18STATIC_DCL void FDECL(shrink_worm, (int));
19STATIC_DCL void FDECL(random_dir, (XCHAR_P,XCHAR_P,xchar *,xchar *));
20STATIC_DCL struct wseg *FDECL(create_worm_tail, (int));
21
22/*  Description of long worm implementation.
23 *
24 *  Each monst struct of the head of a tailed worm has a wormno set to
25 *			1 <= wormno < MAX_NUM_WORMS
26 *  If wormno == 0 this does not mean that the monster is not a worm,
27 *  it just means that the monster does not have a long worm tail.
28 *
29 *  The actual segments of a worm are not full blown monst structs.
30 *  They are small wseg structs, and their position in the levels.monsters[][]
31 *  array is held by the monst struct of the head of the worm.  This makes
32 *  things like probing and hit point bookkeeping much easier.
33 *
34 *  The segments of the long worms on a level are kept as an array of
35 *  singly threaded linked lists.  The wormno variable is used as an index
36 *  for these segment arrays.
37 *
38 *  wtails:	The first (starting struct) of a linked list.  This points
39 *		to the tail (last) segment of the worm.
40 *
41 *  wheads:	The last (end) of a linked list of segments.  This points to
42 *		the segment that is at the same position as the real monster
43 *		(the head).  Note that the segment that wheads[wormno] points
44 *		to, is not displayed.  It is simply there to keep track of
45 *		where the head came from, so that worm movement and display are
46 *		simplified later.
47 *		Keeping the head segment of the worm at the end of the list
48 *		of tail segments is an endless source of confusion, but it is
49 *		necessary.
50 *		From now on, we will use "start" and "end" to refer to the
51 *		linked list and "head" and "tail" to refer to the worm.
52 *
53 *  One final worm array is:
54 *
55 *  wgrowtime:	This tells us when to add another segment to the worm.
56 *
57 *  When a worm is moved, we add a new segment at the head, and delete the
58 *  segment at the tail (unless we want it to grow).  This new head segment is
59 *  located in the same square as the actual head of the worm.  If we want
60 *  to grow the worm, we don't delete the tail segment, and we give the worm
61 *  extra hit points, which possibly go into its maximum.
62 *
63 *  Non-moving worms (worm_nomove) are assumed to be surrounded by their own
64 *  tail, and, thus, shrink instead of grow (as their tails keep going while
65 *  their heads are stopped short).  In this case, we delete the last tail
66 *  segment, and remove hit points from the worm.
67 */
68
69struct wseg *wheads[MAX_NUM_WORMS]   = DUMMY, *wtails[MAX_NUM_WORMS] = DUMMY;
70long	    wgrowtime[MAX_NUM_WORMS] = DUMMY;
71
72/*
73 *  get_wormno()
74 *
75 *  Find an unused worm tail slot and return the index.  A zero means that
76 *  there are no slots available.  This means that the worm head can exist,
77 *  it just cannot ever grow a tail.
78 *
79 *  It, also, means that there is an optimisation to made.  The [0] positions
80 *  of the arrays are never used.  Meaning, we really *could* have one more
81 *  tailed worm on the level, or use a smaller array (using wormno - 1).
82 *
83 *  Implementation is left to the interested hacker.
84 */
85int
86get_wormno()
87{
88    register int new_wormno = 1;
89
90    while (new_wormno < MAX_NUM_WORMS) {
91	if (!wheads[new_wormno])
92	    return new_wormno; /* found an empty wtails[] slot at new_wormno */
93	new_wormno++;
94    }
95
96    return(0);	/* level infested with worms */
97}
98
99/*
100 *  initworm()
101 *
102 *  Use if (mon->wormno = get_wormno()) before calling this function!
103 *
104 *  Initialize the worm entry.  This will set up the worm grow time, and
105 *  create and initialize the dummy segment for wheads[] and wtails[].
106 *
107 *  If the worm has no tail (ie get_wormno() fails) then this function need
108 *  not be called.
109 */
110void
111initworm(worm, wseg_count)
112    struct monst *worm;
113    int wseg_count;
114{
115    register struct wseg *seg, *new_tail = create_worm_tail(wseg_count);
116    register int wnum = worm->wormno;
117
118/*  if (!wnum) return;  bullet proofing */
119
120    if (new_tail) {
121	wtails[wnum] = new_tail;
122	for (seg = new_tail; seg->nseg; seg = seg->nseg);
123	wheads[wnum] = seg;
124    } else {
125	wtails[wnum] = wheads[wnum] = seg = newseg();
126	seg->nseg    = (struct wseg *) 0;
127	seg->wx      = worm->mx;
128	seg->wy      = worm->my;
129    }
130    wgrowtime[wnum] = 0L;
131}
132
133
134/*
135 *  toss_wsegs()
136 *
137 *  Get rid of all worm segments on and following the given pointer curr.
138 *  The display may or may not need to be updated as we free the segments.
139 */
140STATIC_OVL
141void
142toss_wsegs(curr, display_update)
143    register struct wseg *curr;
144    register boolean display_update;
145{
146    register struct wseg *seg;
147
148    while (curr) {
149	seg = curr->nseg;
150
151	/* remove from level.monsters[][] */
152
153	/* need to check curr->wx for genocided while migrating_mon */
154	if (curr->wx) {
155	    remove_monster(curr->wx, curr->wy);
156
157	    /* update screen before deallocation */
158	    if (display_update) newsym(curr->wx,curr->wy);
159	}
160
161	/* free memory used by the segment */
162	dealloc_seg(curr);
163	curr = seg;
164    }
165}
166
167
168/*
169 *  shrink_worm()
170 *
171 *  Remove the tail segment of the worm (the starting segment of the list).
172 */
173STATIC_OVL
174void
175shrink_worm(wnum)
176    int wnum;	/* worm number */
177{
178    struct wseg *seg;
179
180    if (wtails[wnum] == wheads[wnum]) return;	/* no tail */
181
182    seg = wtails[wnum];
183    wtails[wnum] = seg->nseg;
184    seg->nseg = (struct wseg *) 0;
185    toss_wsegs(seg, TRUE);
186}
187
188/*
189 *  worm_move()
190 *
191 *  Check for mon->wormno before calling this function!
192 *
193 *  Move the worm.  Maybe grow.
194 */
195void
196worm_move(worm)
197    struct monst *worm;
198{
199    register struct wseg *seg, *new_seg;	/* new segment */
200    register int	 wnum = worm->wormno;	/* worm number */
201
202
203/*  if (!wnum) return;  bullet proofing */
204
205    /*
206     *  Place a segment at the old worm head.  The head has already moved.
207     */
208    seg = wheads[wnum];
209    place_worm_seg(worm, seg->wx, seg->wy);
210    newsym(seg->wx,seg->wy);		/* display the new segment */
211
212    /*
213     *  Create a new dummy segment head and place it at the end of the list.
214     */
215    new_seg       = newseg();
216    new_seg->wx   = worm->mx;
217    new_seg->wy   = worm->my;
218    new_seg->nseg = (struct wseg *) 0;
219    seg->nseg     = new_seg;		/* attach it to the end of the list */
220    wheads[wnum]  = new_seg;		/* move the end pointer */
221
222
223    if (wgrowtime[wnum] <= moves) {
224	if (!wgrowtime[wnum])
225	    wgrowtime[wnum] = moves + rnd(5);
226	else
227	    wgrowtime[wnum] += rn1(15, 3);
228	worm->mhp += 3;
229	if (worm->mhp > MHPMAX) worm->mhp = MHPMAX;
230	if (worm->mhp > worm->mhpmax) worm->mhpmax = worm->mhp;
231    } else
232	/* The worm doesn't grow, so the last segment goes away. */
233	shrink_worm(wnum);
234}
235
236/*
237 *  worm_nomove()
238 *
239 *  Check for mon->wormno before calling this function!
240 *
241 *  The worm don't move so it should shrink.
242 */
243void
244worm_nomove(worm)
245    register struct monst *worm;
246{
247    shrink_worm((int) worm->wormno);	/* shrink */
248
249    if (worm->mhp > 3)
250	worm->mhp -= 3;		/* mhpmax not changed ! */
251    else
252	worm->mhp = 1;
253}
254
255/*
256 *  wormgone()
257 *
258 *  Check for mon->wormno before calling this function!
259 *
260 *  Kill a worm tail.
261 */
262void
263wormgone(worm)
264    register struct monst *worm;
265{
266    register int wnum = worm->wormno;
267
268/*  if (!wnum) return;  bullet proofing */
269
270    worm->wormno = 0;
271
272    /*  This will also remove the real monster (ie 'w') from the its
273     *  position in level.monsters[][].
274     */
275    toss_wsegs(wtails[wnum], TRUE);
276
277    wheads[wnum] = wtails[wnum] = (struct wseg *) 0;
278}
279
280/*
281 *  wormhitu()
282 *
283 *  Check for mon->wormno before calling this function!
284 *
285 *  If the hero is near any part of the worm, the worm will try to attack.
286 */
287void
288wormhitu(worm)
289    register struct monst *worm;
290{
291    register int wnum = worm->wormno;
292    register struct wseg *seg;
293
294/*  if (!wnum) return;  bullet proofing */
295
296/*  This does not work right now because mattacku() thinks that the head is
297 *  out of range of the player.  We might try to kludge, and bring the head
298 *  within range for a tiny moment, but this needs a bit more looking at
299 *  before we decide to do this.
300 */
301    for (seg = wtails[wnum]; seg; seg = seg->nseg)
302	if (distu(seg->wx, seg->wy) < 3)
303	    (void) mattacku(worm);
304}
305
306/*  cutworm()
307 *
308 *  Check for mon->wormno before calling this function!
309 *
310 *  When hitting a worm (worm) at position x, y, with a weapon (weap),
311 *  there is a chance that the worm will be cut in half, and a chance
312 *  that both halves will survive.
313 */
314void
315cutworm(worm, x, y, weap)
316    struct monst *worm;
317    xchar x,y;
318    struct obj *weap;
319{
320    register struct wseg  *curr, *new_tail;
321    register struct monst *new_worm;
322    int wnum = worm->wormno;
323    int cut_chance, new_wnum;
324
325    if (!wnum) return; /* bullet proofing */
326
327    if (x == worm->mx && y == worm->my) return;		/* hit on head */
328
329    /* cutting goes best with a bladed weapon */
330    cut_chance = rnd(20);	/* Normally  1-16 does not cut */
331				/* Normally 17-20 does */
332
333    if (weap && is_blade(weap))	/* With a blade 1- 6 does not cut */
334	cut_chance += 10;	/*		7-20 does */
335
336    if (cut_chance < 17) return;	/* not good enough */
337
338    /* Find the segment that was attacked. */
339    curr = wtails[wnum];
340
341    while ( (curr->wx != x) || (curr->wy != y) ) {
342	curr = curr->nseg;
343	if (!curr) {
344	    impossible("cutworm: no segment at (%d,%d)", (int) x, (int) y);
345	    return;
346	}
347    }
348
349    /* If this is the tail segment, then the worm just loses it. */
350    if (curr == wtails[wnum]) {
351	shrink_worm(wnum);
352	return;
353    }
354
355    /*
356     *  Split the worm.  The tail for the new worm is the old worm's tail.
357     *  The tail for the old worm is the segment that follows "curr",
358     *  and "curr" becomes the dummy segment under the new head.
359     */
360    new_tail = wtails[wnum];
361    wtails[wnum] = curr->nseg;
362    curr->nseg = (struct wseg *) 0;	/* split the worm */
363
364    /*
365     *  At this point, the old worm is correct.  Any new worm will have
366     *  it's head at "curr" and its tail at "new_tail".
367     */
368
369    /* Sometimes the tail end dies. */
370    if (rn2(3) || !(new_wnum = get_wormno())) {
371	if (flags.mon_moving)
372	    pline("Part of the tail of %s is cut off.", mon_nam(worm));
373	else
374	    You("cut part of the tail off of %s.", mon_nam(worm));
375	toss_wsegs(new_tail, TRUE);
376	if (worm->mhp > 1) worm->mhp /= 2;
377	return;
378    }
379
380    remove_monster(x, y);		/* clone_mon puts new head here */
381    new_worm = clone_mon(worm, x, y);
382    new_worm->wormno = new_wnum;	/* affix new worm number */
383
384    /* Devalue the monster level of both halves of the worm. */
385    worm->m_lev = ((unsigned)worm->m_lev <= 3) ?
386		   (unsigned)worm->m_lev : max((unsigned)worm->m_lev - 2, 3);
387    new_worm->m_lev = worm->m_lev;
388
389    /* Calculate the mhp on the new_worm for the (lower) monster level. */
390    new_worm->mhpmax = new_worm->mhp = d((int)new_worm->m_lev, 8);
391
392    /* Calculate the mhp on the old worm for the (lower) monster level. */
393    if (worm->m_lev > 3) {
394	worm->mhpmax = d((int)worm->m_lev, 8);
395	if (worm->mhpmax < worm->mhp) worm->mhp = worm->mhpmax;
396    }
397
398    wtails[new_wnum] = new_tail;	/* We've got all the info right now */
399    wheads[new_wnum] = curr;		/* so we can do this faster than    */
400    wgrowtime[new_wnum] = 0L;		/* trying to call initworm().       */
401
402    /* Place the new monster at all the segment locations. */
403    place_wsegs(new_worm);
404
405    if (flags.mon_moving)
406	pline("%s is cut in half.", Monnam(worm));
407    else
408	You("cut %s in half.", mon_nam(worm));
409}
410
411
412/*
413 *  see_wsegs()
414 *
415 *  Refresh all of the segments of the given worm.  This is only called
416 *  from see_monster() in display.c or when a monster goes minvis.  It
417 *  is located here for modularity.
418 */
419void
420see_wsegs(worm)
421    struct monst *worm;
422{
423    struct wseg *curr = wtails[worm->wormno];
424
425/*  if (!mtmp->wormno) return;  bullet proofing */
426
427    while (curr != wheads[worm->wormno]) {
428	newsym(curr->wx,curr->wy);
429	curr = curr->nseg;
430    }
431}
432
433/*
434 *  detect_wsegs()
435 *
436 *  Display all of the segments of the given worm for detection.
437 */
438void
439detect_wsegs(worm, use_detection_glyph)
440    struct monst *worm;
441    boolean use_detection_glyph;
442{
443    int num;
444    struct wseg *curr = wtails[worm->wormno];
445
446/*  if (!mtmp->wormno) return;  bullet proofing */
447
448    while (curr != wheads[worm->wormno]) {
449	num = use_detection_glyph ?
450		detected_monnum_to_glyph(what_mon(PM_LONG_WORM_TAIL)) :
451		monnum_to_glyph(what_mon(PM_LONG_WORM_TAIL));
452	show_glyph(curr->wx,curr->wy,num);
453	curr = curr->nseg;
454    }
455}
456
457
458/*
459 *  save_worm()
460 *
461 *  Save the worm information for later use.  The count is the number
462 *  of segments, including the dummy.  Called from save.c.
463 */
464void
465save_worm(fd, mode)
466    int fd, mode;
467{
468    int i;
469    int count;
470    struct wseg *curr, *temp;
471
472    if (perform_bwrite(mode)) {
473	for (i = 1; i < MAX_NUM_WORMS; i++) {
474	    for (count = 0, curr = wtails[i]; curr; curr = curr->nseg) count++;
475	    /* Save number of segments */
476	    bwrite(fd, (genericptr_t) &count, sizeof(int));
477	    /* Save segment locations of the monster. */
478	    if (count) {
479		for (curr = wtails[i]; curr; curr = curr->nseg) {
480		    bwrite(fd, (genericptr_t) &(curr->wx), sizeof(xchar));
481		    bwrite(fd, (genericptr_t) &(curr->wy), sizeof(xchar));
482		}
483	    }
484	}
485	bwrite(fd, (genericptr_t) wgrowtime, sizeof(wgrowtime));
486    }
487
488    if (release_data(mode)) {
489	/* Free the segments only.  savemonchn() will take care of the
490	 * monsters. */
491	for (i = 1; i < MAX_NUM_WORMS; i++) {
492	    if (!(curr = wtails[i])) continue;
493
494	    while (curr) {
495		temp = curr->nseg;
496		dealloc_seg(curr);		/* free the segment */
497		curr = temp;
498	    }
499	    wheads[i] = wtails[i] = (struct wseg *) 0;
500	}
501    }
502
503}
504
505/*
506 *  rest_worm()
507 *
508 *  Restore the worm information from the save file.  Called from restore.c
509 */
510void
511rest_worm(fd)
512    int fd;
513{
514    int i, j, count;
515    struct wseg *curr, *temp;
516
517    for (i = 1; i < MAX_NUM_WORMS; i++) {
518	mread(fd, (genericptr_t) &count, sizeof(int));
519	if (!count) continue;	/* none */
520
521	/* Get the segments. */
522	for (curr = (struct wseg *) 0, j = 0; j < count; j++) {
523	    temp = newseg();
524	    temp->nseg = (struct wseg *) 0;
525	    mread(fd, (genericptr_t) &(temp->wx), sizeof(xchar));
526	    mread(fd, (genericptr_t) &(temp->wy), sizeof(xchar));
527	    if (curr)
528		curr->nseg = temp;
529	    else
530		wtails[i] = temp;
531	    curr = temp;
532	}
533	wheads[i] = curr;
534    }
535    mread(fd, (genericptr_t) wgrowtime, sizeof(wgrowtime));
536}
537
538/*
539 *  place_wsegs()
540 *
541 *  Place the segments of the given worm.  Called from restore.c
542 */
543void
544place_wsegs(worm)
545    struct monst *worm;
546{
547    struct wseg *curr = wtails[worm->wormno];
548
549/*  if (!mtmp->wormno) return;  bullet proofing */
550
551    while (curr != wheads[worm->wormno]) {
552	place_worm_seg(worm,curr->wx,curr->wy);
553	curr = curr->nseg;
554    }
555}
556
557/*
558 *  remove_worm()
559 *
560 *  This function is equivalent to the remove_monster #define in
561 *  rm.h, only it will take the worm *and* tail out of the levels array.
562 *  It does not get rid of (dealloc) the worm tail structures, and it does
563 *  not remove the mon from the fmon chain.
564 */
565void
566remove_worm(worm)
567    register struct monst *worm;
568{
569    register struct wseg *curr = wtails[worm->wormno];
570
571/*  if (!mtmp->wormno) return;  bullet proofing */
572
573    while (curr) {
574	remove_monster(curr->wx, curr->wy);
575	newsym(curr->wx, curr->wy);
576	curr = curr->nseg;
577    }
578}
579
580/*
581 *  place_worm_tail_randomly()
582 *
583 *  Place a worm tail somewhere on a level behind the head.
584 *  This routine essentially reverses the order of the wsegs from head
585 *  to tail while placing them.
586 *  x, and y are most likely the worm->mx, and worm->my, but don't *need* to
587 *  be, if somehow the head is disjoint from the tail.
588 */
589void
590place_worm_tail_randomly(worm, x, y)
591    struct monst *worm;
592    xchar x, y;
593{
594    int wnum = worm->wormno;
595    struct wseg *curr = wtails[wnum];
596    struct wseg *new_tail;
597    register xchar ox = x, oy = y;
598
599/*  if (!wnum) return;  bullet proofing */
600
601    if (wnum && (!wtails[wnum] || !wheads[wnum]) ) {
602	impossible("place_worm_tail_randomly: wormno is set without a tail!");
603	return;
604    }
605
606    wheads[wnum] = new_tail = curr;
607    curr = curr->nseg;
608    new_tail->nseg = (struct wseg *) 0;
609    new_tail->wx = x;
610    new_tail->wy = y;
611
612    while(curr)  {
613	xchar nx, ny;
614	char tryct = 0;
615
616	/* pick a random direction from x, y and search for goodpos() */
617
618	do {
619	    random_dir(ox, oy, &nx, &ny);
620	} while (!goodpos(nx, ny, worm, 0) && (tryct++ < 50));
621
622	if (tryct < 50)  {
623	    place_worm_seg(worm, nx, ny);
624	    curr->wx = ox = nx;
625	    curr->wy = oy = ny;
626	    wtails[wnum] = curr;
627	    curr = curr->nseg;
628	    wtails[wnum]->nseg = new_tail;
629	    new_tail = wtails[wnum];
630	    newsym(nx, ny);
631	} else {			/* Oops.  Truncate because there was */
632	    toss_wsegs(curr, FALSE);    /* no place for the rest of it */
633	    curr = (struct wseg *) 0;
634	}
635    }
636}
637
638/*
639 * Given a coordinate x, y.
640 * return in *nx, *ny, the coordinates of one of the <= 8 squares adjoining.
641 *
642 * This function, and the loop it serves, could be eliminated by coding
643 * enexto() with a search radius.
644 */
645STATIC_OVL
646void
647random_dir(x, y, nx, ny)
648    register xchar   x,   y;
649    register xchar *nx, *ny;
650{
651    *nx = x;
652    *ny = y;
653
654    *nx += (x > 1 ?			/* extreme left ? */
655		(x < COLNO ?		 /* extreme right ? */
656			(rn2(3) - 1)	  /* neither so +1, 0, or -1 */
657		:	-rn2(2))	 /* 0, or -1 */
658	   :	rn2(2));		/* 0, or 1 */
659
660    *ny += (*nx == x ?			/* same kind of thing with y */
661		(y > 1 ?
662		    (y < ROWNO ?
663			(rn2(2) ?
664			    1
665			:   -1)
666		    :	-1)
667		:   1)
668	    :	(y > 1 ?
669		    (y < ROWNO ?
670			(rn2(3) - 1)
671		    :	-rn2(2))
672		:   rn2(2)));
673}
674
675/*  count_wsegs()
676 *
677 *  returns
678 *  the number of visible segments that a worm has.
679 */
680
681int
682count_wsegs(mtmp)
683    struct monst *mtmp;
684{
685    register int i=0;
686    register struct wseg *curr = (wtails[mtmp->wormno])->nseg;
687
688/*  if (!mtmp->wormno) return 0;  bullet proofing */
689
690    while (curr) {
691	i++;
692	curr = curr->nseg;
693    }
694
695    return i;
696}
697
698/*  create_worm_tail()
699 *
700 *  will create a worm tail chain of (num_segs + 1) and return a pointer to it.
701 */
702STATIC_OVL
703struct wseg *
704create_worm_tail(num_segs)
705    int num_segs;
706{
707    register int i=0;
708    register struct wseg *new_tail, *curr;
709
710    if (!num_segs) return (struct wseg *)0;
711
712    new_tail = curr = newseg();
713    curr->nseg = (struct wseg *)0;
714    curr->wx = 0;
715    curr->wy = 0;
716
717    while (i < num_segs) {
718	curr->nseg = newseg();
719	curr = curr->nseg;
720	curr->nseg = (struct wseg *)0;
721	curr->wx = 0;
722	curr->wy = 0;
723	i++;
724    }
725
726    return (new_tail);
727}
728
729/*  worm_known()
730 *
731 *  Is any segment of this worm in viewing range?  Note: caller must check
732 *  invisibility and telepathy (which should only show the head anyway).
733 *  Mostly used in the canseemon() macro.
734 */
735boolean
736worm_known(worm)
737struct monst *worm;
738{
739    struct wseg *curr = wtails[worm->wormno];
740
741    while (curr) {
742	if(cansee(curr->wx,curr->wy)) return TRUE;
743	curr = curr->nseg;
744    }
745    return FALSE;
746}
747
748/*worm.c*/
749