From 41974ae5265fbc23a06f276f9e008d5dad020e0b Mon Sep 17 00:00:00 2001 From: Ben Longbons Date: Thu, 30 Aug 2012 16:16:25 -0700 Subject: Rename files for C++ conversion. Does not compile. After updating, you can remove these files, as shown in 'git status': Untracked files: (use "git add ..." to include in what will be committed) src/map/magic-interpreter-lexer.c src/map/magic-interpreter-parser.c src/map/magic-interpreter-parser.h --- src/map/path.c | 445 --------------------------------------------------------- 1 file changed, 445 deletions(-) delete mode 100644 src/map/path.c (limited to 'src/map/path.c') diff --git a/src/map/path.c b/src/map/path.c deleted file mode 100644 index 7a864ed..0000000 --- a/src/map/path.c +++ /dev/null @@ -1,445 +0,0 @@ -// $Id: path.c,v 1.1.1.1 2004/09/10 17:27:00 MagicalTux Exp $ -#include -#include -#include - -#include "map.h" -#include "battle.h" -#include "../common/nullpo.h" - -#ifdef MEMWATCH -#include "memwatch.h" -#endif - -//#define PATH_STANDALONETEST - -#define MAX_HEAP 150 -struct tmp_path -{ - short x, y, dist, before, cost; - char dir, flag; -}; -#define calc_index(x,y) (((x)+(y)*MAX_WALKPATH) & (MAX_WALKPATH*MAX_WALKPATH-1)) - -/*========================================== - * 経路探索補助heap push - *------------------------------------------ - */ -static void push_heap_path (int *heap, struct tmp_path *tp, int index) -{ - int i, h; - - if (heap == NULL || tp == NULL) - { - printf ("push_heap_path nullpo\n"); - return; - } - - heap[0]++; - - for (h = heap[0] - 1, i = (h - 1) / 2; - h > 0 && tp[index].cost < tp[heap[i + 1]].cost; i = (h - 1) / 2) - heap[h + 1] = heap[i + 1], h = i; - heap[h + 1] = index; -} - -/*========================================== - * 経路探索補助heap update - * costが減ったので根の方へ移動 - *------------------------------------------ - */ -static void update_heap_path (int *heap, struct tmp_path *tp, int index) -{ - int i, h; - - nullpo_retv (heap); - nullpo_retv (tp); - - for (h = 0; h < heap[0]; h++) - if (heap[h + 1] == index) - break; - if (h == heap[0]) - { - fprintf (stderr, "update_heap_path bug\n"); - exit (1); - } - for (i = (h - 1) / 2; - h > 0 && tp[index].cost < tp[heap[i + 1]].cost; i = (h - 1) / 2) - heap[h + 1] = heap[i + 1], h = i; - heap[h + 1] = index; -} - -/*========================================== - * 経路探索補助heap pop - *------------------------------------------ - */ -static int pop_heap_path (int *heap, struct tmp_path *tp) -{ - int i, h, k; - int ret, last; - - nullpo_retr (-1, heap); - nullpo_retr (-1, tp); - - if (heap[0] <= 0) - return -1; - ret = heap[1]; - last = heap[heap[0]]; - heap[0]--; - - for (h = 0, k = 2; k < heap[0]; k = k * 2 + 2) - { - if (tp[heap[k + 1]].cost > tp[heap[k]].cost) - k--; - heap[h + 1] = heap[k + 1], h = k; - } - if (k == heap[0]) - heap[h + 1] = heap[k], h = k - 1; - - for (i = (h - 1) / 2; - h > 0 && tp[heap[i + 1]].cost > tp[last].cost; i = (h - 1) / 2) - heap[h + 1] = heap[i + 1], h = i; - heap[h + 1] = last; - - return ret; -} - -/*========================================== - * 現在の点のcost計算 - *------------------------------------------ - */ -static int calc_cost (struct tmp_path *p, int x1, int y1) -{ - int xd, yd; - - nullpo_retr (0, p); - - xd = x1 - p->x; - if (xd < 0) - xd = -xd; - yd = y1 - p->y; - if (yd < 0) - yd = -yd; - return (xd + yd) * 10 + p->dist; -} - -/*========================================== - * 必要ならpathを追加/修正する - *------------------------------------------ - */ -static int add_path (int *heap, struct tmp_path *tp, int x, int y, int dist, - int dir, int before, int x1, int y1) -{ - int i; - - nullpo_retr (0, heap); - nullpo_retr (0, tp); - - i = calc_index (x, y); - - if (tp[i].x == x && tp[i].y == y) - { - if (tp[i].dist > dist) - { - tp[i].dist = dist; - tp[i].dir = dir; - tp[i].before = before; - tp[i].cost = calc_cost (&tp[i], x1, y1); - if (tp[i].flag) - push_heap_path (heap, tp, i); - else - update_heap_path (heap, tp, i); - tp[i].flag = 0; - } - return 0; - } - - if (tp[i].x || tp[i].y) - return 1; - - tp[i].x = x; - tp[i].y = y; - tp[i].dist = dist; - tp[i].dir = dir; - tp[i].before = before; - tp[i].cost = calc_cost (&tp[i], x1, y1); - tp[i].flag = 0; - push_heap_path (heap, tp, i); - - return 0; -} - -/*========================================== - * (x,y)が移動不可能地帯かどうか - * flag 0x10000 遠距離攻撃判定 - *------------------------------------------ - */ -static int can_place (struct map_data *m, int x, int y, int flag) -{ - int c; - - nullpo_retr (0, m); - - c = read_gatp (m, x, y); - - if (c == 1) - return 0; - if (!(flag & 0x10000) && c == 5) - return 0; - return 1; -} - -/*========================================== - * (x0,y0)から(x1,y1)へ1歩で移動可能か計算 - *------------------------------------------ - */ -static int can_move (struct map_data *m, int x0, int y0, int x1, int y1, - int flag) -{ - nullpo_retr (0, m); - - if (x0 - x1 < -1 || x0 - x1 > 1 || y0 - y1 < -1 || y0 - y1 > 1) - return 0; - if (x1 < 0 || y1 < 0 || x1 >= m->xs || y1 >= m->ys) - return 0; - if (!can_place (m, x0, y0, flag)) - return 0; - if (!can_place (m, x1, y1, flag)) - return 0; - if (x0 == x1 || y0 == y1) - return 1; - if (!can_place (m, x0, y1, flag) || !can_place (m, x1, y0, flag)) - return 0; - return 1; -} - -/*========================================== - * (x0,y0)から(dx,dy)方向へcountセル分 - * 吹き飛ばしたあとの座標を所得 - *------------------------------------------ - */ -int path_blownpos (int m, int x0, int y0, int dx, int dy, int count) -{ - struct map_data *md; - - if (!map[m].gat) - return -1; - md = &map[m]; - - if (count > 15) - { // 最大10マスに制限 - if (battle_config.error_log) - printf ("path_blownpos: count too many %d !\n", count); - count = 15; - } - if (dx > 1 || dx < -1 || dy > 1 || dy < -1) - { - if (battle_config.error_log) - printf ("path_blownpos: illeagal dx=%d or dy=%d !\n", dx, dy); - dx = (dx >= 0) ? 1 : ((dx < 0) ? -1 : 0); - dy = (dy >= 0) ? 1 : ((dy < 0) ? -1 : 0); - } - - while ((count--) > 0 && (dx != 0 || dy != 0)) - { - if (!can_move (md, x0, y0, x0 + dx, y0 + dy, 0)) - { - int fx = (dx != 0 && can_move (md, x0, y0, x0 + dx, y0, 0)); - int fy = (dy != 0 && can_move (md, x0, y0, x0, y0 + dy, 0)); - if (fx && fy) - { - if (rand () & 1) - dx = 0; - else - dy = 0; - } - if (!fx) - dx = 0; - if (!fy) - dy = 0; - } - x0 += dx; - y0 += dy; - } - return (x0 << 16) | y0; -} - -/*========================================== - * path探索 (x0,y0)->(x1,y1) - *------------------------------------------ - */ -int path_search (struct walkpath_data *wpd, int m, int x0, int y0, int x1, - int y1, int flag) -{ - int heap[MAX_HEAP + 1]; - struct tmp_path tp[MAX_WALKPATH * MAX_WALKPATH]; - int i, rp, x, y; - struct map_data *md; - int dx, dy; - - nullpo_retr (0, wpd); - - if (!map[m].gat) - return -1; - md = &map[m]; - if (x1 < 0 || x1 >= md->xs || y1 < 0 || y1 >= md->ys - || (i = read_gatp (md, x1, y1)) == 1 || i == 5) - return -1; - - // easy - dx = (x1 - x0 < 0) ? -1 : 1; - dy = (y1 - y0 < 0) ? -1 : 1; - for (x = x0, y = y0, i = 0; x != x1 || y != y1;) - { - if (i >= sizeof (wpd->path)) - return -1; - if (x != x1 && y != y1) - { - if (!can_move (md, x, y, x + dx, y + dy, flag)) - break; - x += dx; - y += dy; - wpd->path[i++] = - (dx < 0) ? ((dy > 0) ? 1 : 3) : ((dy < 0) ? 5 : 7); - } - else if (x != x1) - { - if (!can_move (md, x, y, x + dx, y, flag)) - break; - x += dx; - wpd->path[i++] = (dx < 0) ? 2 : 6; - } - else - { // y!=y1 - if (!can_move (md, x, y, x, y + dy, flag)) - break; - y += dy; - wpd->path[i++] = (dy > 0) ? 0 : 4; - } - if (x == x1 && y == y1) - { - wpd->path_len = i; - wpd->path_pos = 0; - wpd->path_half = 0; - return 0; - } - } - if (flag & 1) - return -1; - - memset (tp, 0, sizeof (tp)); - - i = calc_index (x0, y0); - tp[i].x = x0; - tp[i].y = y0; - tp[i].dist = 0; - tp[i].dir = 0; - tp[i].before = 0; - tp[i].cost = calc_cost (&tp[i], x1, y1); - tp[i].flag = 0; - heap[0] = 0; - push_heap_path (heap, tp, calc_index (x0, y0)); - while (1) - { - int e = 0, fromdir; - - if (heap[0] == 0) - return -1; - rp = pop_heap_path (heap, tp); - x = tp[rp].x; - y = tp[rp].y; - if (x == x1 && y == y1) - { - int len, j; - - for (len = 0, i = rp; len < 100 && i != calc_index (x0, y0); - i = tp[i].before, len++); - if (len == 100 || len >= sizeof (wpd->path)) - return -1; - wpd->path_len = len; - wpd->path_pos = 0; - wpd->path_half = 0; - for (i = rp, j = len - 1; j >= 0; i = tp[i].before, j--) - wpd->path[j] = tp[i].dir; - - return 0; - } - fromdir = tp[rp].dir; - if (can_move (md, x, y, x + 1, y - 1, flag)) - e += add_path (heap, tp, x + 1, y - 1, tp[rp].dist + 14, 5, rp, - x1, y1); - if (can_move (md, x, y, x + 1, y, flag)) - e += add_path (heap, tp, x + 1, y, tp[rp].dist + 10, 6, rp, x1, - y1); - if (can_move (md, x, y, x + 1, y + 1, flag)) - e += add_path (heap, tp, x + 1, y + 1, tp[rp].dist + 14, 7, rp, - x1, y1); - if (can_move (md, x, y, x, y + 1, flag)) - e += add_path (heap, tp, x, y + 1, tp[rp].dist + 10, 0, rp, x1, - y1); - if (can_move (md, x, y, x - 1, y + 1, flag)) - e += add_path (heap, tp, x - 1, y + 1, tp[rp].dist + 14, 1, rp, - x1, y1); - if (can_move (md, x, y, x - 1, y, flag)) - e += add_path (heap, tp, x - 1, y, tp[rp].dist + 10, 2, rp, x1, - y1); - if (can_move (md, x, y, x - 1, y - 1, flag)) - e += add_path (heap, tp, x - 1, y - 1, tp[rp].dist + 14, 3, rp, - x1, y1); - if (can_move (md, x, y, x, y - 1, flag)) - e += add_path (heap, tp, x, y - 1, tp[rp].dist + 10, 4, rp, x1, - y1); - tp[rp].flag = 1; - if (e || heap[0] >= MAX_HEAP - 5) - return -1; - } - return -1; -} - -#ifdef PATH_STANDALONETEST -char gat[64][64] = { - {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, - {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, - {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, - {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, - {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, -}; - -struct map_data map[1]; - -/*========================================== - * 経路探索ルーチン単体テスト用main関数 - *------------------------------------------ - */ -void main (int argc, char *argv[]) -{ - struct walkpath_data wpd; - - map[0].gat = gat; - map[0].xs = 64; - map[0].ys = 64; - - path_search (&wpd, 0, 3, 4, 5, 4); - path_search (&wpd, 0, 5, 4, 3, 4); - path_search (&wpd, 0, 6, 4, 3, 4); - path_search (&wpd, 0, 7, 4, 3, 4); - path_search (&wpd, 0, 4, 3, 4, 5); - path_search (&wpd, 0, 4, 2, 4, 5); - path_search (&wpd, 0, 4, 1, 4, 5); - path_search (&wpd, 0, 4, 5, 4, 3); - path_search (&wpd, 0, 4, 6, 4, 3); - path_search (&wpd, 0, 4, 7, 4, 3); - path_search (&wpd, 0, 7, 4, 3, 4); - path_search (&wpd, 0, 8, 4, 3, 4); - path_search (&wpd, 0, 9, 4, 3, 4); - path_search (&wpd, 0, 10, 4, 3, 4); - path_search (&wpd, 0, 11, 4, 3, 4); - path_search (&wpd, 0, 12, 4, 3, 4); - path_search (&wpd, 0, 13, 4, 3, 4); - path_search (&wpd, 0, 14, 4, 3, 4); - path_search (&wpd, 0, 15, 4, 3, 4); - path_search (&wpd, 0, 16, 4, 3, 4); - path_search (&wpd, 0, 17, 4, 3, 4); - path_search (&wpd, 0, 18, 4, 3, 4); -} -#endif -- cgit v1.2.3-70-g09d2