>Number:         23213
>Category:       bin
>Synopsis:       wump(8) contains a potential infinite loop
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    bin-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Oct 21 04:54:00 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     der Mouse
>Release:        Any (found in wump.c 1.12, still in 1.15)
>Organization:
	Dis-
>Environment:
	Any
>Description:
	games/wump/wump.c contains a loop that reads

        do {
                player_loc = (random() % room_num) + 1;
        } while (player_loc == wumpus_loc || (level == HARD ?
            (link_num / room_num < 0.4 ? wump_nearby() : 0) : 0));

	which compares the quotient of two ints to a float, a rather
	pointless operation.  Without changing the semantics, this
	portion of the test could be changed to link_num<room_num, but
	what's intended is presumably something more like
	(link_num*5)<(room_num*2).  (I also think the do-while
	condition should include cave[player_loc].has_a_pit and
	cave[player_loc].has_a_bat, so the player does not start on the
	edge of a pit or in a roomful of bats, but that's a separate
	issue.)

	This has infinite-loop potential; when starting a hard game
	with a high tunnel count (eg, wump -h -r 20 -t 15), there is a
	good chance that the Wumpus is within two of _every_ cave and
	thus no starting place can be found.  The game will
	infinite-loop in this case.
>How-To-Repeat:
	Inspect the code, and/or try running a hard game with a high -t
	value as compared to the -r value.
>Fix:
	To fix the test to what it's presumably intended to be:

	s@link_num / room_num < 0.4@(link_num*5) < (room_num*2)@

	This doesn't explicitly fix the infinite loop; with less than
	40% as many tunnels per cave as caves, it's still quite
	possible for the Wumpus to be near every cave.  For example,
	suppose there are 11 rooms with 4 tunnels per room and the hop
	delta chosen is 1, with the Wumpus in cave 1.  Then most of the
	tunnels can even be left unspecified with the Wumpus still near
	every room:

		1	2 11 5 8 (Wumpus here)
		2	3 1 x x [1]
		3	4 2 x x [2 1]
		4	5 3 x x [5 1]
		5	6 4 1 x [1]
		6	7 5 x x [5 1]
		7	8 6 x x [8 1]
		8	9 7 1 x [1]
		9	10 8 x x [8 1]
		10	11 9 x x [10 1]
		11	1 10 x x [1]

	Fixing this would require something more like
	link_num < sqrt(room_num) (though there are some constants
	needed; I haven't thought it through in detail).

	Also, unless I've mistaken something, that test should be
	level==EASY, since the test makes the game easier.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       mouse@rodents.montreal.qc.ca
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
>Release-Note:
>Audit-Trail:
>Unformatted: