From 1b321e92bc9c054dc8d4389277cac179446a1831 Mon Sep 17 00:00:00 2001 From: cohrs Date: Sat, 13 Apr 2002 16:00:13 +0000 Subject: [PATCH] remove prescient travel command behavior Addresses reports R718, R772.1, P's extra move bug - when there is a previously seen path or a straight path, always take it - incorporate fix to ensure no extra "." turn at the end of traveling, but still avoid stepping into traps/pools, et al - include a general "G"-command (and travel) fix to avoid stepping in known pools/lava while blind - when there is no such path, "guess" at a path by finding an intermediate location that the hero couldsee that is closest to the actual goal, the intermediate goal is re-determined at each step - when Blind, don't use couldsee for determining straight paths, just direction - do not consider doors or most boulders obstacles for picking travel paths, test_move has a new mode to differentiate this case from the regular test case - don't include known trap locations in the travel path, avoids unnecessary stops along the way, and usually doesn't affect the path length - reformatted the code a bit so I could follow it --- doc/Guidebook.mn | 5 +- doc/Guidebook.tex | 7 +- doc/fixes34.1 | 2 + include/extern.h | 2 +- include/hack.h | 5 ++ src/cmd.c | 2 +- src/hack.c | 203 +++++++++++++++++++++++++++++++++------------- 7 files changed, 163 insertions(+), 63 deletions(-) diff --git a/doc/Guidebook.mn b/doc/Guidebook.mn index 05ec127be..fcd533a48 100644 --- a/doc/Guidebook.mn +++ b/doc/Guidebook.mn @@ -476,7 +476,10 @@ Prefix: move until something interesting is found. .lp "G[yuhjklbn] or [yuhjklbn] Prefix: same as `g', but forking of corridors is not considered interesting. .lp _ -Travel to a map location via a shortest-path algorithm. Stops on most of +Travel to a map location via a shortest-path algorithm. The shortest path +is computed over map locations the hero knows about (e.g. seen or +previously traversed). If there is no known path, a guess is made instead. +Stops on most of the same conditions as the `G' command, but without picking up objects, similar to the `M' command. For ports with mouse support, the command is also invoked when a mouse-click takes place on a diff --git a/doc/Guidebook.tex b/doc/Guidebook.tex index 7a4be6bbf..8b53be132 100644 --- a/doc/Guidebook.tex +++ b/doc/Guidebook.tex @@ -27,7 +27,7 @@ \begin{document} % % input file: guidebook.mn -% $Revision: 1.39 $ $Date: 2002/03/31 07:19:43 $ +% $Revision: 1.40 $ $Date: 2002/04/04 03:44:18 $ % %.ds h0 " %.ds h1 %.ds h2 \% @@ -638,7 +638,10 @@ Prefix: Same as `{\tt g}', but forking of corridors is not considered interesting. %.lp \item[\tb{_}] -Travel to a map location via a shortest-path algorithm. Stops on most of +Travel to a map location via a shortest-path algorithm. The shortest path +is computed over map locations the hero knows about (e.g. seen or +previously traversed). If there is no known path, a guess is made instead. +Stops on most of the same conditions as the `G' command, but without picking up objects, similar to the `M' command. For ports with mouse support, the command is also invoked when a mouse-click takes place on a diff --git a/doc/fixes34.1 b/doc/fixes34.1 index 373d67f61..ed4493e88 100644 --- a/doc/fixes34.1 +++ b/doc/fixes34.1 @@ -67,6 +67,8 @@ randomize starting position on goal level for M, P, and S quests prevent the Wizard of Yendor from displacing the high priest of Moloch out of the Sanctum's temple ATR_BOLD on spell menu header +travel command should restrict its shortest paths to areas of the map the + hero knows about or might reasonably guess Platform- and/or Interface-Specific Fixes diff --git a/include/extern.h b/include/extern.h index 57094c4d0..cb8ce0803 100644 --- a/include/extern.h +++ b/include/extern.h @@ -662,7 +662,7 @@ E boolean FDECL(may_dig, (XCHAR_P,XCHAR_P)); E boolean FDECL(may_passwall, (XCHAR_P,XCHAR_P)); E boolean FDECL(bad_rock, (struct permonst *,XCHAR_P,XCHAR_P)); E boolean FDECL(invocation_pos, (XCHAR_P,XCHAR_P)); -E boolean FDECL(test_move, (int, int, int, int, BOOLEAN_P)); +E boolean FDECL(test_move, (int, int, int, int, int)); E void NDECL(domove); E void NDECL(invocation_message); E void FDECL(spoteffects, (BOOLEAN_P)); diff --git a/include/hack.h b/include/hack.h index 3a3aadffb..794b900b2 100644 --- a/include/hack.h +++ b/include/hack.h @@ -178,6 +178,11 @@ NEARDATA extern coord bhitpos; /* place where throw or zap hits or stops */ /* Flags to control dotrap() in trap.c */ #define NOWEBMSG 0x01 /* suppress stumble into web message */ +/* Flags to control test_move in hack.c */ +#define DO_MOVE 0 /* really doing the move */ +#define TEST_MOVE 1 /* test a normal move (move there next) */ +#define TEST_TRAV 2 /* test a future travel location */ + /*** some utility macros ***/ #define yn(query) yn_function(query,ynchars, 'n') #define ynq(query) yn_function(query,ynqchars, 'q') diff --git a/src/cmd.c b/src/cmd.c index 3070c8d63..cbedd1569 100644 --- a/src/cmd.c +++ b/src/cmd.c @@ -1977,7 +1977,7 @@ click_to_cmd(x, y, mod) dir = xytod(x, y); - if (!m_at(u.ux+x, u.uy+y) && !test_move(u.ux, u.uy, x, y, 1)) { + if (!m_at(u.ux+x, u.uy+y) && !test_move(u.ux, u.uy, x, y, TEST_MOVE)) { cmd[1] = (iflags.num_pad ? ndir[dir] : sdir[dir]); cmd[2] = 0; if (IS_DOOR(levl[u.ux+x][u.uy+y].typ)) { diff --git a/src/hack.c b/src/hack.c index ac84a9439..7a579f386 100644 --- a/src/hack.c +++ b/src/hack.c @@ -12,7 +12,7 @@ STATIC_DCL int FDECL(still_chewing,(XCHAR_P,XCHAR_P)); #ifdef SINKS STATIC_DCL void NDECL(dosinkfall); #endif -STATIC_DCL void NDECL(findtravelpath); +STATIC_DCL boolean FDECL(findtravelpath, (BOOLEAN_P)); STATIC_DCL boolean FDECL(monstinroom, (struct permonst *,int)); STATIC_DCL void FDECL(move_update, (BOOLEAN_P)); @@ -526,22 +526,27 @@ xchar x, y; #endif /* OVL1 */ #ifdef OVL3 -/* return TRUE if (dx,dy) is an OK place to move */ +/* return TRUE if (dx,dy) is an OK place to move + * mode is one of DO_MOVE, TEST_MOVE or TEST_TRAV + */ boolean -test_move(ux, uy, dx, dy, test_only) +test_move(ux, uy, dx, dy, mode) int ux, uy, dx, dy; -boolean test_only; +int mode; { int x = ux+dx; int y = uy+dy; register struct rm *tmpr = &levl[x][y]; register struct rm *ust; + /* if this is the next step, must treat as if TEST_MOVE were used */ + if (mode == TEST_TRAV && distmin(x, y, u.ux, u.uy) <= 1) mode = TEST_MOVE; + /* * Check for physical obstacles. First, the place we are going. */ if (IS_ROCK(tmpr->typ) || tmpr->typ == IRONBARS) { - if (Blind && !test_only) feel_location(x,y); + if (Blind && mode == DO_MOVE) feel_location(x,y); if (Passes_walls && may_passwall(x,y)) { ; /* do nothing */ } else if (tmpr->typ == IRONBARS) { @@ -549,34 +554,34 @@ boolean test_only; return FALSE; } else if (tunnels(youmonst.data) && !needspick(youmonst.data)) { /* Eat the rock. */ - if (!test_only && still_chewing(x,y)) return FALSE; + if (mode == DO_MOVE && still_chewing(x,y)) return FALSE; } else if (flags.autodig && !flags.run && !flags.nopick && uwep && is_pick(uwep)) { /* MRKR: Automatic digging when wielding the appropriate tool */ - if (!test_only) + if (mode == DO_MOVE) (void) use_pick_axe2(uwep); return FALSE; } else { - if ( !test_only ) { + if (mode == DO_MOVE) { if (Is_stronghold(&u.uz) && is_db_wall(x,y)) pline_The("drawbridge is up!"); if (Passes_walls && !may_passwall(x,y) && In_sokoban(&u.uz)) - pline_The("Sokoban walls resist your ability."); + pline_The("Sokoban walls resist your ability."); } return FALSE; } } else if (IS_DOOR(tmpr->typ)) { if (closed_door(x,y)) { - if (Blind && !test_only) feel_location(x,y); + if (Blind && mode == DO_MOVE) feel_location(x,y); if (Passes_walls) ; /* do nothing */ else if (can_ooze(&youmonst)) { - if ( !test_only ) You("ooze under the door."); + if (mode == DO_MOVE) You("ooze under the door."); } else if (tunnels(youmonst.data) && !needspick(youmonst.data)) { /* Eat the door. */ - if (!test_only && still_chewing(x,y)) return FALSE; + if (mode == DO_MOVE && still_chewing(x,y)) return FALSE; } else { - if ( !test_only ) { + if (mode == DO_MOVE) { if (amorphous(youmonst.data)) You("try to ooze under the door, but can't squeeze your possessions through."); else if (x == ux || y == uy) { @@ -596,7 +601,7 @@ boolean test_only; } else pline("That door is closed."); } } - return FALSE; + if (mode != TEST_TRAV) return FALSE; } } else if (dx && dy && !Passes_walls && ((tmpr->doormask & ~D_BROKEN) @@ -605,7 +610,7 @@ boolean test_only; #endif || block_door(x,y))) { /* Diagonal moves into a door are not allowed. */ - if ( Blind && !test_only ) + if (Blind && mode == DO_MOVE) feel_location(x,y); return FALSE; } @@ -614,21 +619,27 @@ boolean test_only; && bad_rock(youmonst.data,ux,y) && bad_rock(youmonst.data,x,uy)) { /* Move at a diagonal. */ if (In_sokoban(&u.uz)) { - if ( !test_only ) + if (mode == DO_MOVE) You("cannot pass that way."); return FALSE; } if (bigmonst(youmonst.data)) { - if ( !test_only ) + if (mode == DO_MOVE) Your("body is too large to fit through."); return FALSE; } if (invent && (inv_weight() + weight_cap() > 600)) { - if ( !test_only ) + if (mode == DO_MOVE) You("are carrying too much to get through."); return FALSE; } } + /* pick a path that does not require crossing a trap */ + if (flags.run == 8 && mode != DO_MOVE) { + struct trap* t = t_at(x, y); + + if (t && t->tseen) return FALSE; + } ust = &levl[ux][uy]; @@ -645,80 +656,152 @@ boolean test_only; } if (sobj_at(BOULDER,x,y) && (In_sokoban(&u.uz) || !Passes_walls)) { - if (!(Blind || Hallucination) && (flags.run >= 2)) + if (!(Blind || Hallucination) && (flags.run >= 2) && mode != TEST_TRAV) return FALSE; - if (!test_only) { + if (mode == DO_MOVE) { /* tunneling monsters will chew before pushing */ if (tunnels(youmonst.data) && !needspick(youmonst.data) && !In_sokoban(&u.uz)) { if (still_chewing(x,y)) return FALSE; } else if (moverock() < 0) return FALSE; + } else if (mode == TEST_TRAV) { + struct obj* obj; + + /* don't pick two boulders in a row, unless there's a way thru */ + if (sobj_at(BOULDER,ux,uy) && !In_sokoban(&u.uz)) { + if (!Passes_walls && + !(tunnels(youmonst.data) && !needspick(youmonst.data)) && + !carrying(PICK_AXE) && !carrying(DWARVISH_MATTOCK) && + !((obj = carrying(WAN_DIGGING)) && + !objects[obj->otyp].oc_name_known)) + return FALSE; + } } - /* test_only will assume you'll be able to push it when you get there... */ + /* assume you'll be able to push it when you get there... */ } /* OK, it is a legal place to move. */ return TRUE; } -static void findtravelpath() +/* + * Find a path from the destination (u.tx,u.ty) back to (u.ux,u.uy). + * A shortest path is returned. If guess is TRUE, consider various + * inaccessible locations as valid intermediate path points. + * Returns TRUE if a path was found. + */ +static boolean +findtravelpath(guess) +boolean guess; { - if ( u.tx != u.ux || u.ty != u.uy ) { + if (u.tx != u.ux || u.ty != u.uy) { xchar travel[COLNO][ROWNO]; xchar travelstepx[2][COLNO*ROWNO]; xchar travelstepy[2][COLNO*ROWNO]; - int n=1; - int set=0; - int dia=1; - - (void) memset((genericptr_t)travel,0,sizeof(travel)); - - travelstepx[0][0] = u.tx; - travelstepy[0][0] = u.ty; - while ( n ) { - int i; - int nn=0; - for (i=0; i %d,%d by %d,%d\n",u.ux,u.uy,u.tx,u.ty,u.dx,u.dy); - */ - return; - } else { - /*printf("%d %d %d",isok(nx,ny), !travel[nx][ny], ACCESSIBLE(levl[nx][ny].typ));*/ - if ( !travel[nx][ny] ) { - travelstepx[1-set][nn]=nx; - travelstepy[1-set][nn]=ny; - travel[nx][ny]=dia; - nn++; + + if (!isok(nx, ny)) continue; + if (test_move(x, y, nx-x, ny-y, TEST_TRAV) && + (levl[nx][ny].seenv || (!Blind && couldsee(nx, ny)))) { + if (nx == ux && ny == uy) { + if (!guess) { + u.dx = x-ux; + u.dy = y-uy; + if (x == u.tx && y == u.ty) { + nomul(0); + /* reset run so domove run checks work */ + flags.run = 8; + } + return TRUE; } + } else if (!travel[nx][ny]) { + travelstepx[1-set][nn] = nx; + travelstepy[1-set][nn] = ny; + travel[nx][ny] = radius; + nn++; } } } } + n = nn; set = 1-set; - dia++; + radius++; } - /* give up */ + /* if guessing, find best location in travel matrix and go there */ + if (guess) { + int px = tx, py = ty; /* pick location */ + int dist, d; + + dist = distmin(ux, uy, tx, ty); + for (tx = 1; tx < COLNO; ++tx) + for (ty = 0; ty < ROWNO; ++ty) + if (travel[tx][ty]) { + d = distmin(ux, uy, tx, ty); + if (d < dist && couldsee(ux, uy)) { + px = tx; py = ty; dist = d; + } + } + + if (px == u.ux && py == u.uy) { + /* no guesses, just go in the general direction */ + u.dx = sgn(u.tx - u.ux); + u.dy = sgn(u.ty - u.uy); + if (test_move(u.ux, u.uy, u.dx, u.dy, TEST_MOVE)) + return TRUE; + goto done; + } + tx = px; + ty = py; + ux = u.ux; + uy = u.uy; + set = 0; + n = radius = 1; + guess = FALSE; + goto noguess; + } + return FALSE; } +done: u.dx = 0; u.dy = 0; nomul(0); + return FALSE; } void @@ -736,8 +819,9 @@ domove() u_wipe_engr(rnd(5)); - if ( flags.travel ) - findtravelpath(); + if (flags.travel) + if (!findtravelpath(FALSE)) + (void) findtravelpath(TRUE); if(((wtcap = near_capacity()) >= OVERLOADED || (wtcap > SLT_ENCUMBER && @@ -823,7 +907,10 @@ domove() nomul(0); return; } - if((trap = t_at(x, y)) && trap->tseen) { + if (((trap = t_at(x, y)) && trap->tseen) || + (Blind && !Levitation && !Flying && + !is_clinger(youmonst.data) && + (is_pool(x, y) || is_lava(x, y)) && levl[x][y].seenv)) { if(flags.run >= 2) { nomul(0); flags.move = 0; @@ -1121,7 +1208,7 @@ domove() return; } - if ( !test_move( u.ux, u.uy, x-u.ux, y-u.uy, 0 ) ) { + if (!test_move(u.ux, u.uy, x-u.ux, y-u.uy, DO_MOVE)) { flags.move = 0; nomul(0); return; -- 2.40.0