? civscore.log ? prof ? gmon.out ? straightest_direction.diff ? void_tile_remove.diff Index: server/gotohand.c =================================================================== RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v retrieving revision 1.119 diff -u -r1.119 gotohand.c --- server/gotohand.c 2001/09/23 16:09:39 1.119 +++ server/gotohand.c 2001/09/23 20:38:57 @@ -14,6 +14,7 @@ #include #include #include +#include #include "combat.h" #include "game.h" @@ -464,8 +465,215 @@ there can be more than one straight path (fx going NW then W is the same as going W then NW) **************************************************************************/ -static int straightest_direction(int src_x, int src_y, int dest_x, int dest_y) + +static int jason_straightest_direction(int src_x, int src_y, int dest_x, + int dest_y) +{ + int best_dir = -1, dir; + float best = -1; + int diff_x, diff_y; + + /* This code is topology-dependent */ + diff_x = dest_x - src_x; + if (diff_x < -map.xsize / 2) + diff_x += map.xsize; + if (diff_x > map.xsize / 2) + diff_x -= map.xsize; + diff_y = dest_y - src_y; + + for (dir = 0; dir < 8; dir++) { + float product = diff_x * DIR_DX[dir] + diff_y * DIR_DY[dir]; + product /= sqrt(DIR_DX[dir] * DIR_DX[dir] + DIR_DY[dir] * DIR_DY[dir]); + + if (product > best) { + best = product; + best_dir = dir; + } + } + + assert(best >= 0 && best_dir >= 0); + return best_dir; +} + +static int raimar_straightest_direction(int src_x, int src_y, int dest_x, + int dest_y) { + int best_dir = -1, dir; + float best = -1; + int diff_x, diff_y; + + /* This code is topology-dependent */ + diff_x = dest_x - src_x; + if (diff_x < -map.xsize / 2) + diff_x += map.xsize; + if (diff_x > map.xsize / 2) + diff_x -= map.xsize; + diff_y = dest_y - src_y; + + /* + * The straightest direction is the direction which has the most + * minimal |angle| of all directions. angle is the angle between the + * difference vector (diff) and one of the direction vectors (d_i). + * + * cos(angle) = (diff * d_i)/(||diff|| * ||d_i||) + * + * The direction which has the smallest |angle| is the direction + * which has the largest cos(angle). ||diff|| is constant and so + * doesn't affect the maximum searching of m. + * + * m = (diff * d_i)/||d_i|| + * + * Any direction for which (diff * d_i) is negative isn't a solution + * (wrong semi-circle). If both dividend and divisor are >=0 the + * fraction can be squared without affecting the maximum search. + * + * m2=(diff * d_i)^2 / ||d_i||^2 + * + * ||d_i||^2 can have the values 1 and 2. So the division will not + * loose any precision if the dividend is multiplied by 2 and the + * whole operation is carried out with integer numbers. + */ + for (dir = 0; dir < 8; dir++) { + int di_x = DIR_DX[dir], di_y = DIR_DY[dir]; + int m2 = diff_x * di_x + diff_y * di_y; + + /* freelog(LOG_NORMAL, "dx=%d, dy=%d diff_x=%d, diff_y=%d, m2=%d", di_x, + di_y, diff_x, diff_y, m2);*/ + if (m2 < 0) + continue; + m2 = (2 * m2 * m2) / (di_x * di_x + di_y * di_y); + + if (best_dir == -1 || m2 > best) { + best = m2; + best_dir = dir; + } + } + + assert(best >= 0 && best_dir >= 0); + return best_dir; +} + +static int raimar2_straightest_direction(int src_x, int src_y, int dest_x, + int dest_y) +{ + int diff_x, diff_y; + int xpos, ypos, m; + + /* This code is topology-dependent */ + diff_x = dest_x - src_x; + if (diff_x < -map.xsize / 2) + diff_x += map.xsize; + if (diff_x > map.xsize / 2) + diff_x -= map.xsize; + diff_y = dest_y - src_y; + +#define K 65536 + +// M1=tan(pi/8)*K +#define M1 27146 + +// M2=tan(pi/2-pi-8)*K=(K*K)/M1 +#define M2 158218 + + xpos = (diff_x > 0); + ypos = (diff_y > 0); + + assert(!(diff_x == 0 && diff_y == 0)); + + if (diff_x == 0) { + if (ypos) { + return DIR8_SOUTH; + } else { + return DIR8_NORTH; + } + } + + m=abs((diff_y*K)/diff_x); + + if (m < M1) { + if (xpos) { + return DIR8_EAST; + } else { + return DIR8_WEST; + } + } + + if (m > M2) { + if (ypos) { + return DIR8_SOUTH; + } else { + return DIR8_NORTH; + } + } + + if (xpos) { + if (ypos) { + return DIR8_SOUTHEAST; + } else { + return DIR8_NORTHEAST; + } + } else { + if (ypos) { + return DIR8_SOUTHWEST; + } else { + return DIR8_NORTHWEST; + } + } + + assert(0); + return -1; +} + +static int ross_straightest_direction(int src_x, int src_y, int dest_x, + int dest_y) +{ + static int tx[8] = { + DIR8_SOUTHEAST, DIR8_EAST, DIR8_NORTHEAST, DIR8_NORTH, + DIR8_SOUTHWEST, DIR8_SOUTH, DIR8_NORTHWEST, DIR8_WEST + }; + int temp, delta_x, delta_y, nn = 0; + + /* Sanitize */ + normalize_map_pos(&src_x, &src_y); + normalize_map_pos(&dest_x, &dest_y); + + /* compute sign and magnitude of x delta */ + if ((delta_x = dest_x - src_x) < 0) + nn |= 4, delta_x = -delta_x; + + /* if wrapped and closer, flip sign and save new delta */ + if (1 /*has_mapwrap(MAP_TYPE_WRAPX)*/ + && (temp = map.xsize - delta_x) < delta_x) nn ^= 4, delta_x = temp; + + /* compute sign and magnitude of y delta */ + if ((delta_y = dest_y - src_y) < 0) + nn |= 2, delta_y = -delta_y; + + /* if wrapped and closer, flip sign and save new delta */ + if (/*has_mapwrap(MAP_TYPE_WRAPY)*/ 0 + && (temp = map.ysize - delta_y) < delta_y) nn ^= 2, delta_y = temp; + + /* + * - 3 - If point is closer to the cardinal axes vs diagonals + * 7 s 1 then update the index nn using these index positions. + * - 5 - Test for 2 dy < dx (or dy < dx-dy) for cardinal x, etc. + * diagonal move--^ ^--residual x move + */ + if (delta_y < delta_x) { + if (delta_y + delta_y < delta_x) + nn = ((nn & 4) ? 7 : 1); + } else if (delta_x + delta_x < delta_y) + nn = ((nn & 2) ? 3 : 5); + + /* + * 6 3 2 nn should now be one of these 8 possibilities. + * 7 s 1 Translate (tx) it to your favourite DX ordering. + * 4 5 0 + */ + return tx[nn]; +} +static int orig_straightest_direction(int src_x, int src_y, int dest_x, int dest_y) +{ int best_dir; int go_x, go_y; @@ -488,6 +696,30 @@ return (best_dir); } +static int straightest_direction(int src_x, int src_y, int dest_x, + int dest_y) +{ + int orig = orig_straightest_direction(src_x, src_y, dest_x, dest_y); + int jason = jason_straightest_direction(src_x, src_y, dest_x, dest_y); + int ross = ross_straightest_direction(src_x, src_y, dest_x, dest_y); + int raimar = raimar_straightest_direction(src_x, src_y, dest_x, dest_y); + int raimar2 = raimar2_straightest_direction(src_x, src_y, dest_x, dest_y); + + if ( /*jason != orig || */ /*jason != ross || */jason != raimar + || jason != raimar2) { + freelog(LOG_NORMAL, "src=(%d,%d) dest=%d,%d)", src_x, src_y, dest_x, + dest_y); + freelog(LOG_NORMAL, " orig=%s, jason=%s, ross=%s, raimar=%s, raimar2=%s", + dir_get_name(orig), dir_get_name(jason), dir_get_name(ross), + dir_get_name(raimar),dir_get_name(raimar2)); + } + /* + else + freelog(LOG_NORMAL, "src=(%d,%d) dest=%d,%d) dir=%s", src_x, src_y, dest_x, + dest_y,dir_get_name(orig));*/ + return orig; +} + /************************************************************************** Can we move between for ZOC? (only for land units). Includes a speciel case only relevant for GOTOs (see below). @@ -616,6 +848,9 @@ orig_y = punit->y; if ((dest_x == orig_x) && (dest_y == orig_y)) return 1; /* [Kero] */ + + for (igter = 0; igter < 10000; igter++) + straightest_direction(punit->x, punit->y, dest_x, dest_y); local_vector[orig_x][orig_y] = 0;