// // Copyright 2020 Electronic Arts Inc. // // TiberianDawn.DLL and RedAlert.dll and corresponding source code is free // software: you can redistribute it and/or modify it under the terms of // the GNU General Public License as published by the Free Software Foundation, // either version 3 of the License, or (at your option) any later version. // TiberianDawn.DLL and RedAlert.dll and corresponding source code is distributed // in the hope that it will be useful, but with permitted additional restrictions // under Section 7 of the GPL. See the GNU General Public License in LICENSE.TXT // distributed with this program. You should have received a copy of the // GNU General Public License along with permitted additional restrictions // with this program. If not, see https://github.com/electronicarts/CnC_Remastered_Collection /* $Header: /CounterStrike/FINDPATH.CPP 1 3/03/97 10:24a Joe_bostic $ */ /*********************************************************************************************** *** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S *** *********************************************************************************************** * * * Project Name : Command & Conquer * * * * File Name : FINDPATH.CPP * * * * Programmer : Joe L. Bostic * * * * Start Date : September 10, 1993 * * * * Last Update : May 25, 1995 [PWG] * * * * The path algorithm works by following a LOS path to the target. If it * * collides with an impassable spot, it uses an Edge following routine to * * get around it. The edge follower moves along the edge in a clockwise or * * counter clockwise fashion until finding the destination spot. The * * destination is determined by Find_Path. It is the first passable that * * can be reached (so it will handle the doughnut case, where there is * * a passable in the center of an unreachable area). * * * *---------------------------------------------------------------------------------------------* * Functions: * * Clear_Path_Overlap -- clears the path overlap list * * Find_Path -- Find a path from point a to point b. * * Find_Path_Cell -- Finds a given cell on a specified path * * Follow_Edge -- Follow an edge to get around an impassable spot. * * FootClass::Unravel_Loop -- Unravels a loop in the movement path * * Get_New_XY -- Get the new x,y based on current position and direction. * * Optimize_Moves -- Optimize the move list. * * Set_Path_Overlap -- Sets the overlap bit for given cell * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ #include "function.h" //#include /* ** When an edge search is started, it can be performed CLOCKwise or ** COUNTERCLOCKwise direction. */ #define CLOCK (FacingType)1 // Clockwise. #define COUNTERCLOCK (FacingType)-1 // Counterclockwise. /* ** If defined, diagonal moves are allowed, else no diagonals. */ #define DIAGONAL /* ** This is the marker to signify the end of the path list. */ #define END FACING_NONE /* ** "- 1" test for bit manipulation. */ #define TEST /* ** If memory is more important than speed, set this define to ** true. It will then perform intermediate optimizations to get the most ** milage out of a limited movement list staging area. If this value ** is true then it figures paths a bit more intelligently. */ #define SAVEMEM true /* ** Modify this macro so that given two cell values, it will return ** a value between 0 and 7, with 0 being North and moving ** clockwise (just like map degrees). */ #define CELL_FACING(a, b) Dir_Facing(::Direction((a), (b))) /*-------------------------------------------------------------------------*/ /* ** Cells values are really indexes into the 'map'. The following value is ** the X width of the map. */ #define MODULO MAP_CELL_W /* ** Maximum lookahead cells. Twice this value in bytes will be ** reserved on the stack. The smaller this number, the faster the processing. */ #define MAX_MLIST_SIZE 300 #define THREAT_THRESHOLD 5 #define MAX_PATH_EDGE_FOLLOW 400 #ifdef NEVER typedef enum { FACING_N, // North FACING_NE, // North-East FACING_E, // East FACING_SE, // South-East FACING_S, // South FACING_SW, // South-West FACING_W, // West FACING_NW, // North-West FACING_COUNT // Total of 8 directions (0..7). } FacingType; #endif /*-------------------------------------------------------------------------*/ //static bool DrawPath; inline FacingType Opposite(FacingType face) { return( (FacingType) (face ^ 4)); } inline static FacingType Next_Direction(FacingType facing, FacingType dir) { facing = facing + dir; #ifndef DIAGONAL facing = (FacingType)(facing & 0x06); #endif return(facing); } /*=========================================================================*/ /* Define a couple of variables which are private to the module they are */ /* declared in. */ /*=========================================================================*/ static unsigned long MainOverlap[MAP_CELL_TOTAL/32]; // overlap list for the main path static unsigned long LeftOverlap[MAP_CELL_TOTAL/32]; // overlap list for the left path static unsigned long RightOverlap[MAP_CELL_TOTAL/32]; // overlap list for the right path //static CELL MoveMask = 0; static CELL DestLocation; static CELL StartLocation; /*************************************************************************** * Point_Relative_To_Line -- Relation between a point and a line * * * * If a point is on a line then the following function holds true: * * (x - x2)(z1 - z2) = (z - z2)(x1 - x2) given x,z a point on the * * line (x1,z1),(x2,z2). * * If the right side is > then the left side then the point is on one * * side of the line and if the right side is < the the left side, then* * the point is on the other side of the line. By subtracting one side* * from the other we can determine on what side (if any) the point is on* * by testing the side of the resulting subtraction. * * * * INPUT: * * int x - x pos of point. * * int z - z pos of point. * * int x1 - x pos of first end of line segment. * * int z1 - z pos of first end of line segment. * * int x1 - x pos of second end of line segment. * * int z1 - z pos of second end of line segment. * * * * OUTPUT: * * Assuming (x1,z1) is north, (x2,z2) is south: * * 0 : point is on line. * * > 0 : point is east of line. * * < 0 : point is west of line. * * * * WARNINGS: * * Remember that int means that assumes 16 bits of precision. * * * * HISTORY: * * 10/28/1994 SKB : Created. * *=========================================================================*/ int Point_Relative_To_Line(int x, int z, int x1, int z1, int x2, int z2) { return((((long)x - (long)x2) * ((long)z1 - (long)z2)) - (((long)z - (long)z2) * ((long)x1 - (long)x2))); } /*************************************************************************** * FootClass::Unravel_Loop -- Unravels a loop in the movement path * * * * While in the midst of the Follow Edge logic, it is possible (due to the * * fact that we support diagonal movement) to begin looping around a * * column of some type. The Unravel loop function will scan backward * * through the list and fixup the path to try to prevent the loop. * * * * INPUT: path - pointer to the generated path so we can pull the * * commands out of it. * * cell - the cell we tried to enter that generated the * * double overlap condition. * * dir - the direction we tried to enter from when we * * generated the double overlap condition * * startx - the start x position of this path segment * * starty - the start y position of this path segment * * destx - the dest x position for this path segment * * desty - the dest y position for this path segment * * * * OUTPUT: TRUE - loop has been successfully unravelled * * FALSE - loop can not be unravelled so abort follow edge * * * * WARNINGS: none * * * * HISTORY: * * 05/25/1995 PWG : Created. * *=========================================================================*/ bool FootClass::Unravel_Loop(PathType * path, CELL &cell, FacingType &dir, int sx, int sy, int dx, int dy, MoveType threshhold) { /* ** Walk back to the actual cell before we advanced our position */ FacingType curr_dir = dir; CELL curr_pos = Adjacent_Cell(cell, Opposite(curr_dir)); int idx = path->Length; // start at the last position FacingType * list = &path->Command[idx-1]; // point to the last command int checkx; int checky; int last_was_line = false; /* ** loop backward through the list searching for a point that is ** on the line. If the point was a diagonal move then adjust ** it. */ while (idx) { checkx = Cell_X(curr_pos); checky = Cell_Y(curr_pos); if (!Point_Relative_To_Line(checkx, checky, sx, sy, dx, dy) || last_was_line) { /* ** We have now found a point on the line. Now we must check to see ** if we left the line on a diagonal. If we did then we need to fix ** it up. */ if (curr_dir & 1 && curr_pos != path->LastFixup) { cell = curr_pos; dir = *(list-1); path->Length = idx; path->LastFixup = curr_pos; return(true); } last_was_line = !last_was_line; } /* ** Since this cell will not be in the list, then pull out its cost */ path->Cost -= Passable_Cell(curr_pos, *list, -1, threshhold); /* ** Remove this cells flag from the overlap list for the path */ #ifdef TEST path->Overlap[curr_pos >> 5] &= ~(1 << ((curr_pos & 31))); #else path->Overlap[curr_pos >> 5] &= ~(1 << ((curr_pos & 31) - 1)); #endif /* ** Adjust to the next list position and direction. */ curr_dir = *list--; curr_pos = Adjacent_Cell(curr_pos, Opposite(curr_dir)); idx--; } /* ** If we can't modify the list to eliminate the problem, then we have ** a larger problem in that we have deleted all of the cells in the ** list. */ return(false); } /*************************************************************************** * Register_Cell -- registers a cell on our path and check for backtrack * * * * This function adds a new cell to our path. If the cell has already * * been recorded as part of our path, then this function moves back down * * the list truncating it at the point we registered that cell. This * * function will eliminate all backtracking from the list. * * * * INPUT: long * list - the list to set the overlap bit for * * CELL cell - the cell to mark on the overlap list * * * * OUTPUT: BOOL - TRUE if bit has been set, FALSE if bit already set * * * * HISTORY: * * 05/23/1995 PWG : Created. * *=========================================================================*/ bool FootClass::Register_Cell(PathType * path, CELL cell, FacingType dir, int cost, MoveType threshhold) { FacingType * list; int pos = cell >> 5; #ifdef TEST int bit = (cell & 31); #else int bit = (cell & 31) - 1; #endif /* ** See if this point has already been registered as on the list. If so ** we need to truncate the list back to this point and register the ** new direction. */ if (path->Overlap[pos] & (1 << bit)) { /* ** If this is not a case of immediate back tracking then handle ** by searching the list to see what we find. However is this is ** an immediate back track, then pop of the last direction ** and unflag the cell we are in (not the cell we are moving to). ** Note: That we do not check for a zero length cell because we ** could not have a duplicate unless there are cells in the list. */ if (path->Command[path->Length - 1] == Opposite(dir)) { CELL pos = Adjacent_Cell(cell, Opposite(dir)); #ifdef TEST path->Overlap[pos >> 5] &= ~(1 << ((pos & 31))); #else path->Overlap[pos >> 5] &= ~(1 << ((pos & 31) - 1)); #endif path->Length--; } else { /* ** If this overlap is in the same place as we had our last overlap ** then we are in a loop condition. We need to signify that we ** cannot register this cell. */ if (path->LastOverlap == cell) { return(false); } else { path->LastOverlap = cell; } CELL pos = path->Start; int newlen = 0; int idx = 0; list = path->Command; /* ** Note that the cell has to be in this list, so theres no sense ** in checking whether we found it (famous last words). ** ** PWG 8/16/95 - However there is no sense searching the list if ** the cell we have overlapped on is the cell we ** started in. */ if (pos != cell) { while (idx < path->Length) { pos = Adjacent_Cell(pos, *list); if (pos == cell) { idx++; list++; break; } idx++; list++; } newlen = idx; } /* ** Now we are pointing at the next command in the list. From here on ** out we need to unmark the fact that we have entered these cells and ** adjust the cost of our path to reflect that we have not entered ** then. */ while (idx < path->Length) { pos = Adjacent_Cell(pos, *list); path->Cost -= Passable_Cell(pos, *list, -1, threshhold); #ifdef TEST path->Overlap[pos >> 5] &= ~(1 << ((pos & 31))); #else path->Overlap[pos >> 5] &= ~(1 << ((pos & 31) - 1)); #endif idx++; list++; } path->Length = newlen; } } else { /* ** Now we need to register the new direction, updating the cell structure ** and the cost. */ int cpos = path->Length++; path->Command[cpos] = dir; // save of the direction we moved path->Cost += cost; // figure new cost for cell path->Overlap[pos] |= (1 << bit); // mark the we have entered point } return(true); } /*********************************************************************************************** * Find_Path -- Find a path from point a to point b. * * * * INPUT: int source x,y, int destination x,y, char *final moves * * array to store moves, int maximum moves we may attempt * * * * OUTPUT: int number of moves it took (IMPOSSIBLE_MOVES if we could * * not reach the destination * * * * WARNINGS: This algorithm assumes that the target is NOT situated * * inside an impassable. If this case may arise, the do-while * * statement inside the inner while (true) must be changed * * to include a check to se if the next_x,y is equal to the * * dest_x,y. If it is, then return(IMPOSSIBLE_MOVES). * * * * HISTORY: * * 07/08/1991 CY : Created. * *=============================================================================================*/ PathType * FootClass::Find_Path(CELL dest, FacingType * final_moves, int maxlen, MoveType threshhold) { CELL source = Coord_Cell(Coord); // Source expressed as cell static PathType path; // Main path control. CELL next; // Next cell to enter CELL startcell; // Cell we started in FacingType direction; // Working direction of look ahead. FacingType newdir; // Tentative facing value. bool left=false, // Was leftward path legal? right=false; // Was rightward path legal? int len; // Length of detour command list. int unit_threat; // Calculated unit threat rating int cost; // Cost to enter the square FacingType moves_left[MAX_MLIST_SIZE+2], // Counterclockwise move list. moves_right[MAX_MLIST_SIZE+2]; // Clockwise move list. PathType pleft,pright; // Path control structures. PathType * which; // Which path to actually use. int threat = 0; // int threat_stage = 0; //These weren't initialized. ST - 1/8/2019 12:03PM /* ** If we have been provided an illegal place to store our final moves ** then forget it. */ if (!final_moves) return(NULL); BStart(BENCH_FINDPATH); PathCount++; if (Team && Team->Class->IsRoundAbout) { unit_threat = (Team) ? Team->Risk : Risk(); threat_stage = 0; threat = 0; } else { unit_threat = threat = -1; } StartLocation = source; DestLocation = dest; /* ** Initialize the path structure so that we can keep track of the ** path. */ path.Start = source; path.Cost = 0; path.Length = 0; path.Command = final_moves; path.Command[0] = END; path.Overlap = MainOverlap; path.LastOverlap = -1; path.LastFixup = -1; memset(path.Overlap, 0, sizeof(MainOverlap)); /* ** Clear the over lap list and then make sure that our starting position is marked ** on the overlap list. (Otherwise the harvesters will drive in circles... ) */ #ifdef TEST path.Overlap[source >> 5] |= (1 << ((source & 31))); #else path.Overlap[source >> 5] |= (1 << ((source & 31) - 1)); #endif startcell = source; /* ** Account for trailing end of list command, so reduce the maximum ** allowed legal commands to reflect this. */ maxlen--; /* ** As long as there is room to put commands in the movement command list, ** then put commands in it. We build the path using the following ** methodology. ** ** 1. Scan through the desired straight line path until we either hit an ** impassable or have created a valid path. ** ** 2. If we have hit an impassable, walk through the impassable to make ** sure that there is a passable on the other side. If there is not ** and we can not change the impassable, then this list is dead. ** ** 3. Walk around the impassable on both the left and right edges and ** take the shorter of the two paths. ** ** 4. Taking the new location as our start location start again with ** step #1. */ while (path.Length < maxlen) { top_of_list: /* ** Have we reached the destination already? If so abort any further ** command building. */ if (startcell == dest) { break; } /* ** Find the absolute correct direction to reach the next straight ** line cell and what cell it is. */ direction = CELL_FACING(startcell, dest); next = Adjacent_Cell(startcell, direction); /* ** If we can move here, then make this our next move. */ cost = Passable_Cell(next, direction, threat, threshhold); if (cost) { Register_Cell(&path, next, direction, cost, threshhold); } else { /* ** If the impassable location is actually the destination, ** then stop here and consider this "good enough". */ if (next == dest) break; /* ** We could not move to the next cell, so follow through the ** impassable until we find a passable spot that can be reached. ** Once we find a passable, figure out the shortest path to it. ** Since we have variable passable conditions this is not as ** simple as it used to be. The limiter loop below allows us to ** step through ten doughnuts before we give up. */ for (int limiter = 0; limiter < 5; limiter++) { /* ** Get the next passable position by zipping through the ** impassable positions until a passable position is found ** or the destination is reached. */ for (;;) { /* ** Move one step closer toward destination. */ newdir = CELL_FACING(next, dest); next = Adjacent_Cell(next, newdir); /* ** If the cell is passable then we have been completely ** successful. If the cell is not passable then continue. */ if (Passable_Cell(next, FACING_NONE, threat, threshhold)) { // if ((Passable_Cell(next, FACING_NONE, threat, threshhold)) || (next == dest)) { break; } /* ** If we reached destination while in this loop, we ** know that either the destination is impassible (if ** we are ignoring) or that we need to up our threat ** tolerance and try again. */ if (next == dest) { if (threat != -1) { switch (threat_stage++) { case 0: threat = unit_threat >> 1; break; case 1: threat += unit_threat; break; case 2: threat = -1; break; } goto top_of_list; } goto end_of_list; } } /* ** Try to find a path to the passable position by following ** the edge of the blocking object in both CLOCKwise and ** COUNTERCLOCKwise fashions. */ int follow_len = maxlen + (maxlen >> 1); Mem_Copy(&path, &pleft, sizeof(PathType)); pleft.Command = &moves_left[0]; pleft.Overlap = LeftOverlap; Mem_Copy(path.Command, pleft.Command, path.Length); Mem_Copy(path.Overlap, pleft.Overlap, sizeof(LeftOverlap)); // MBL 09.30.2019: We hit a runtime bounds crash where END (-1 / 0xFF) was being poked into +1 just past the end of the moves_right[] array; // The FacingType moves_left[] and moves_right[] arrays already have MAX_MLIST_SIZE+2 as their size, which may have been a previous attempted fix; // We are now passing MAX_MLIST_SIZE, since the sizeof calculations included the +2 buffering; #if 0 left = Follow_Edge(startcell, next, &pleft, COUNTERCLOCK, direction, threat, threat_stage, sizeof(moves_left)/sizeof(moves_left[0]), threshhold); // left = Follow_Edge(startcell, next, &pleft, COUNTERCLOCK, direction, threat, threat_stage, follow_len, threshhold); #endif left = Follow_Edge(startcell, next, &pleft, COUNTERCLOCK, direction, threat, threat_stage, MAX_MLIST_SIZE, threshhold); if (left) { follow_len = min(maxlen, pleft.Length + (pleft.Length >> 1)); } Mem_Copy(&path, &pright, sizeof(PathType)); pright.Command = &moves_right[0]; pright.Overlap = RightOverlap; Mem_Copy(path.Command, pright.Command, path.Length); Mem_Copy(path.Overlap, pright.Overlap, sizeof(RightOverlap)); // MBL 09.30.2019: We hit a runtime bounds crash where END (-1 / 0xFF) was being poked into +1 just past the end of the moves_right[] array; // The FacingType moves_left[] and moves_right[] arrays already have MAX_MLIST_SIZE+2 as their size, which may have been a previous attempted fix; // We are now passing MAX_MLIST_SIZE, since the sizeof calculations included the +2 buffering; #if 0 right = Follow_Edge(startcell, next, &pright, CLOCK, direction, threat, threat_stage, sizeof(moves_right)/sizeof(moves_right[0]), threshhold); // right = Follow_Edge(startcell, next, &pright, CLOCK, direction, threat, threat_stage, follow_len, threshhold); #endif right = Follow_Edge(startcell, next, &pright, CLOCK, direction, threat, threat_stage, MAX_MLIST_SIZE, threshhold); /* ** If we could find a path, break from this loop. Otherwise this ** means that we have found a "hole" of passable terrain that ** cannot be reached by normal means. Scan forward looking for ** the other side of the "doughnut". */ if (left || right) break; /* ** If no path can be found to the intermediate cell, then ** presume we have found a doughnut of some sort. Scan ** forward until the next impassable is found and then ** process this loop again. */ do { /* ** If we reached destination while in this loop, we ** know that either the destination is impassible (if ** we are ignoring) or that we need to up our threat ** tolerance and try again. */ if (next == dest) { if (threat != -1) { switch (threat_stage++) { case 0: threat = unit_threat >> 1; break; case 1: threat += unit_threat; break; case 2: threat = -1; break; } goto top_of_list; } goto end_of_list; } newdir = CELL_FACING(next, dest); next = Adjacent_Cell(next, newdir); } while (Passable_Cell(next, newdir, threat, threshhold)); } if (!left && !right) break; /* ** We found a path around the impassable locations, so figure out ** which one was the smallest and copy those moves into the ** path.Command array. */ which = &pleft; if (right) { which = &pright; if (left) { if (pleft.Length < pright.Length) { which = &pleft; } else { which = &pright; } } } /* ** Record as much as possible of the shorter of the two ** paths. The trailing EOL command is not copied because ** this may not be the end of the find path logic. */ len = which->Length; len = min(len, maxlen); if (len > 0) { memcpy(&path.Overlap[0], &which->Overlap[0], sizeof(LeftOverlap)); memcpy(&path.Command[0], &which->Command[0], len * sizeof(FacingType)); path.Length = len; path.Cost = which->Cost; path.LastOverlap = -1; path.LastFixup = -1; } else { break; } } startcell = next; } end_of_list: /* ** Poke in the stop command. */ if (path.Length < maxlen) { path.Command[path.Length++] = END; } /* ** Optimize the move list but only necessary if ** diagonal moves are allowed. */ #ifdef DIAGONAL Optimize_Moves(&path, threshhold); #endif BEnd(BENCH_FINDPATH); return(&path); } /*********************************************************************************************** * Follow_Edge -- Follow an edge to get around an impassable spot. * * * * INPUT: start -- cell to head from * * * * target -- Target cell to head to. * * * * path -- Pointer to path list structure. * * * * search -- Direction of search (1=clock, -1=counterclock). * * * * olddir -- Facing impassible direction from start. * * * * callback -- Function pointer for determining if a cell is * * passable or not. * * * * OUTPUT: bool: Could a path be found to the desired cell? * * * * WARNINGS: none * * * * HISTORY: * * 07/08/1991 CY : Created. * * 06/01/1992 JLB : Optimized & commented. * *=============================================================================================*/ bool FootClass::Follow_Edge(CELL start, CELL target, PathType * path, FacingType search, FacingType olddir, int threat, int , int max_cells, MoveType threshhold) { FacingType newdir; // Direction of facing before surrounding cell check. CELL oldcell, // Current cell. newcell; // Tentative new cell. int cost; // Working cost value. int startx; int starty; int online=true; int targetx; int targety; int oldval = 0; int cellcount=0; int forceout = false; FacingType firstdir = (FacingType)-1; CELL firstcell = -1; bool stepped_off_line = false; startx = Cell_X(start); starty = Cell_Y(start); targetx = Cell_X(target); targety = Cell_Y(target); if (!path) return(false); path->LastOverlap = -1; path->LastFixup = -1; #ifndef DIAGONAL /* ** The edge following algorithm doesn't "do" diagonals. Force initial facing ** to be an even 90 degree value. Adjust it in the direction it should be ** rotating. */ if (olddir & 0x01) { olddir = Next_Direction(olddir, search); } #endif newdir = Next_Direction(olddir, search); oldcell = start; newcell = Adjacent_Cell(oldcell, newdir); /* ** Continue until we find our target, find our original starting spot, ** or run out of moves. */ while (path->Length < max_cells) { /* ** Look in all the adjacent cells to determine a passable one that ** most closely matches the desired direction (working in the specified ** direction). */ newdir = olddir; for (;;) { bool forcefail; // Is failure forced? forcefail = false; #ifdef DIAGONAL /* ** Rotate 45/90 degrees in desired direction. */ newdir = Next_Direction(newdir, search); /* ** If facing a diagonal we must check the next 90 degree location ** to make sure that we don't walk right by the destination. This ** will happen if the destination it is at the corner edge of an ** impassable that we are moving around. */ if (newdir & FACING_NE) { CELL checkcell; // Non-diagonal check cell. //int x,y; checkcell = Adjacent_Cell(oldcell, Next_Direction(newdir, search)); if (checkcell == target) { /* ** This only works if in fact, it is possible to move to the ** cell from the current location. */ cost = Passable_Cell(checkcell, Next_Direction(newdir, search), threat, threshhold); if (cost) { /* ** YES! The destination is at the corner of an impassable, so ** set the direction to point directly at it and then the ** scanning will terminate later. */ newdir = Next_Direction(newdir, search); newcell = Adjacent_Cell(oldcell, newdir); break; } } /* ** Perform special diagonal check. If the edge follower would cross the ** diagonal or fall on the diagonal line from the source, then consider ** that cell impassible. Otherwise, the find path algorithm will fail ** when there are two impassible locations located on a diagonal ** that is lined up between the source and destination location. ** ** P.S. It might help if you check the right cell rather than using ** the value that just happened to be in checkcell. */ checkcell = Adjacent_Cell(oldcell, newdir); int checkx = Cell_X(checkcell); int checky = Cell_Y(checkcell); int checkval = Point_Relative_To_Line(checkx, checky, startx, starty, targetx, targety); if (checkval && !online) { forcefail = ((checkval ^ oldval) < 0); } else { forcefail = false; } /* ** The only exception to the above is when we are directly backtracking ** because we could be trying to escape from a culdesack! */ if (forcefail && path->Length > 0 && (FacingType)(newdir ^ 4) == path->Command[path->Length - 1]) { forcefail = false; } } #else newdir = Next_Direction(newdir, search*2); #endif /* ** If we have just checked the same heading we started with, ** we are surrounded by impassable characters and we exit. */ if (newdir == olddir) { return(false); } /* ** Get the new cell. */ newcell = Adjacent_Cell(oldcell, newdir); /* ** If we found a passable position, this is where we should move. */ if (!forcefail && ((cost = Passable_Cell(newcell, newdir, threat, threshhold)) != 0)) { break; } else { if (newcell == target) { forceout = true; break; } } } /* ** Record the direction. */ if (!forceout) { /* ** Mark the cell because this is where we need to be. If register ** cell fails then the list has been shortened and we need to adjust ** the new direction. */ if (!Register_Cell(path, newcell, newdir, cost, threshhold)) { /* ** The only reason we could not register a cell is that we are in ** a looping situation. So we need to try and unravel the loop if ** we can. */ if (!Unravel_Loop(path, newcell, newdir, startx, starty, targetx, targety, threshhold)) { return(false); } /* ** Since we need to eliminate a diagonal we must pretend the upon ** attaining this square, we were moving turned further in the ** search direction then we really were. */ newdir = Next_Direction(newdir, (FacingType)(search*2)); } /* ** Find out which side of the line this cell is on. If it is on ** a side, then store off that side. */ int newx = Cell_X(newcell); int newy = Cell_Y(newcell); int val = Point_Relative_To_Line(newx, newy, startx, starty, targetx, targety); if (val) { oldval = val; online = false; } else { online = true; } cellcount++; if (cellcount == MAX_PATH_EDGE_FOLLOW) { return(false); } } /* ** If we have found the target spot, we are done. */ if (newcell == target) { path->Command[path->Length] = END; return(true); } /* ** If we make a full circle back to our original spot, get out. */ if (newcell == firstcell && newdir == firstdir) { return(false); } if (firstcell == -1) { firstcell = newcell; firstdir = newdir; } /* ** Because we moved, our facing is now incorrect. We want to face toward ** the impassable edge we are following (well, not actually toward, but ** a little past so that we can turn corners). We have to turn 45/90 degrees ** more than expected in anticipation of the pending 45/90 degree turn at ** the start of this loop. */ #ifdef DIAGONAL olddir = Next_Direction(newdir, (FacingType)(-(int)search*3)); #else olddir = Next_Direction(newdir, (FacingType)(-(int)search*4)); #endif oldcell = newcell; } /* ** The maximum search path is exhausted... abort with a failure. */ return(false); } /*********************************************************************************************** * Optimize_Moves -- Optimize the move list. * * * * INPUT: char *moves to optimize * * * * OUTPUT: none (list is optimized) * * * * WARNINGS: EMPTY moves are used to hold the place of eliminated * * commands. Also, NEVER call this routine with a list that * * contains illegal commands. The list MUST be terminated * * with a EOL command * * * * HISTORY: * * 07/08/1991 CY : Created. * * 06/01/1992 JLB : Optimized and commented. * *=============================================================================================*/ #define EMPTY (FacingType)-2 int FootClass::Optimize_Moves(PathType * path, MoveType threshhold) //int Optimize_Moves(PathType *path, int (*callback)(CELL, FacingType), int threshold) { /* ** Facing command pair adjustment table. Compare the facing difference between ** the two commands. 0 means no optimization is possible. 3 means backtracking ** so eliminate both commands. Any other value adjusts the first command facing. */ #ifdef DIAGONAL static FacingType _trans[FACING_COUNT] = {(FacingType)0, (FacingType)0, (FacingType)1, (FacingType)2, (FacingType)3, (FacingType)-2, (FacingType)-1, (FacingType)0}; // Smoothing. #else static FacingType _trans[FACING_COUNT] = {(FacingType)0, (FacingType)0, (FacingType)0, (FacingType)2, (FacingType)3, (FacingType)-2, (FacingType)0, (FacingType)0}; #endif FacingType * cmd1, // Floating first command pointer. * cmd2, // Floating second command pointer. newcmd; // Calculated new optimized command. FacingType newdir; // Tentative new direction for smoothing. CELL cell; // Working cell (as it moves along path). /* ** Abort if there is any illegal parameter. */ if (!path || !path->Command) return(0); /* ** Optimization loop -- start scanning with the ** first pair of commands (if there are at least two ** in the command list). */ path->Command[path->Length] = END; // Force end of list. if (path->Length == 0) return(0); cell = path->Start; if (path->Length > 1) { cmd2 = path->Command + 1; while (*cmd2 != END) { /* ** Set the cmd1 pointer to point to the valid command closest, but ** previous to cmd2. Be sure not to go previous to the head of the ** command list. */ cmd1 = cmd2-1; while (*cmd1 == EMPTY && cmd1 != path->Command) { cmd1--; } /* ** If there isn't any valid previous command, then bump the ** cmd pointers to the next command pair and continue... */ if (*cmd1 == EMPTY) { cmd2++; continue; } /* ** Fetch precalculated command change value. 0 means leave ** command set alone, 3 means backtrack and eliminate two ** commands. Any other value is new direction and eliminate ** one command. */ newcmd = (FacingType)(*cmd2 - *cmd1); if (newcmd < FACING_N) newcmd = (FacingType)(newcmd + FACING_COUNT); newcmd = _trans[newcmd]; /* ** Check for backtracking. If this occurs, then eliminate the ** two commands. This is the easiest optimization. */ if (newcmd == FACING_SE) { *cmd1 = EMPTY; *cmd2++ = EMPTY; continue; } /* ** If an optimization code was found the process it. The command is a facing ** offset to more directly travel toward the immediate destination cell. */ if (newcmd) { /* ** Optimizations differ when dealing with diagonals. Especially when dealing ** with diagonals of 90 degrees. In such a case, 90 degree optimizations can ** only be optimized if the intervening cell is passable. The distance travelled ** is the same, but the path is less circuitous. */ if (*cmd1 & FACING_NE) { /* ** Diagonal optimizations are always only 45 ** degree adjustments. */ newdir = Next_Direction(*cmd1, (newcmd < FACING_N) ? (FacingType)-1 : (FacingType)1); /* ** Diagonal 90 degree changes can be smoothed, although ** the path isn't any shorter. */ if (ABS((int)newcmd) == 1) { if (Passable_Cell(Adjacent_Cell(cell, newdir), newdir, -1, threshhold)) { *cmd2 = newdir; *cmd1 = newdir; } // BOB 16.12.92 cell = Adjacent_Cell(cell, *cmd1); cmd2++; continue; } } else { newdir = Next_Direction(*cmd1, newcmd); } /* ** Allow shortening turn only on right angle moves that are based on ** 90 degrees. Always allow 135 degree optimizations. */ *cmd2 = newdir; *cmd1 = EMPTY; /* ** Backup what it thinks is the current cell. */ while (*cmd1 == EMPTY && cmd1 != path->Command) { cmd1--; } if (*cmd1 != EMPTY) { cell = Adjacent_Cell(cell, Next_Direction(*cmd1, FACING_S)); } else { cell = path->Start; } continue; } /* ** Since we could not make an optimization, we move our ** head pointer forward. */ cell = Adjacent_Cell(cell, *cmd1); cmd2++; } } /* ** Pack the command list to remove any EMPTY command entries. */ cmd1 = path->Command; cmd2 = path->Command; cell = path->Start; path->Cost = 0; path->Length = 0; while (*cmd2 != END) { if (*cmd2 != EMPTY) { cell = Adjacent_Cell(cell, *cmd2); path->Cost+= Passable_Cell(cell, *cmd2, -1, threshhold); path->Length++; *cmd1++ = *cmd2; } cmd2++; } path->Length++; *cmd1 = END; return(path->Length); } CELL FootClass::Safety_Point(CELL src, CELL dst, int start, int max) { FacingType dir; CELL next; int lp; dir = (FacingType)(CELL_FACING(src, dst) ^ 4) - 1; /* ** Loop through the different acceptable distances. */ for (int dist = start; dist < max; dist ++) { /* ** Move to the starting location. */ next = dst; for (lp = 0; lp < dist; lp ++) { next = Adjacent_Cell(next, dir); } if (dir & 1) { /* ** If our direction is diagonal than we need to check ** only one side which is as long as both of the old sides ** together. */ for (lp = 0; lp < dist << 1; lp ++) { next = Adjacent_Cell(next, dir + 3); if (!Can_Enter_Cell(next)) { return(next); } } } else { /* ** If our direction is not diagonal than we need to check two ** sides so that we are checking a corner like location. */ for (lp = 0; lp < dist; lp ++) { next = Adjacent_Cell(next, dir + 2); if (!Can_Enter_Cell(next)) { return(next); } } for (lp = 0; lp < dist; lp ++) { next = Adjacent_Cell(next, dir + 4); if (!Can_Enter_Cell(next)) { return(next); } } } } return(-1); } int FootClass::Passable_Cell(CELL cell, FacingType face, int threat, MoveType threshhold) { MoveType move = Can_Enter_Cell(cell, face); if (move < MOVE_MOVING_BLOCK && Distance(Cell_Coord(cell)) > 0x0100) threshhold = MOVE_MOVING_BLOCK; if (move > threshhold) return(0); if (Session.Type == GAME_NORMAL) { if (threat != -1) { if (::Distance(Cell_Coord(cell), Cell_Coord(DestLocation)) > (THREAT_THRESHOLD * CELL_LEPTON_W)) { // if (Map.Cell_Distance(cell, DestLocation) > THREAT_THRESHOLD) { if (Map.Cell_Threat(cell, Owner()) > threat) return(0); } } } static int _value[MOVE_COUNT] = { 1, // MOVE_OK 1, // MOVE_CLOAK 3, // MOVE_MOVING_BLOCK 8, // MOVE_DESTROYABLE 10, // MOVE_TEMP 0 // MOVE_NO }; return(_value[move]); }