Update of /cvsroot/xconq/xconq/kernel In directory sc8-pr-cvs10.sourceforge.net:/tmp/cvs-serv18084/kernel Modified Files: Tag: BRANCH_MCAMPO_PATH conq.h move.c plan.c read.c side.c task.c ui.c unit.h world.h Added Files: Tag: BRANCH_MCAMPO_PATH fsa.hpp pathfind.cc stlastar.hpp Log Message: Add changelog (mcampo.README) for BRANCH_MCAMPO_PATH. Add files necessary for A* pathfinder. Modify kernel to accomodate pathfinder. Change capture and hit-unit behavior. Index: world.h =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/world.h,v retrieving revision 1.4 retrieving revision 1.4.2.1 diff -C2 -d -r1.4 -r1.4.2.1 *** world.h 14 Mar 2005 01:48:31 -0000 1.4 --- world.h 8 Apr 2007 19:34:01 -0000 1.4.2.1 *************** *** 1354,1355 **** --- 1354,1381 ---- int *xfp, int *yfp); extern int num_people_at(int x, int y); + + #ifdef BRANCH_MCAMPO + /* pathfind interface */ + typedef struct a_position { + int x, y; // position coordinates + // int t; // terrain type: cell or connection? (presently not used) + int u; // transport type + } Position; + + typedef struct a_path_node { + Position p; + struct a_path_node* next; + } PathNode; + + PathNode* path_find (Unit *unit, Unit *unit2, int x, int y, int dist); + #endif + + enum move_to_state { + eitherway, + leftthenright, + rightthenleft, + leftonly, + rightonly, + path_not_searched, + path_searched + }; Index: ui.c =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/ui.c,v retrieving revision 1.20 retrieving revision 1.20.2.1 diff -C2 -d -r1.20 -r1.20.2.1 *** ui.c 17 Sep 2005 15:43:43 -0000 1.20 --- ui.c 8 Apr 2007 19:34:01 -0000 1.20.2.1 *************** *** 3393,3397 **** beep the player for trying to move a non-mobile unit. */ ! if (impl_move_to(side, unit, x, y, 0)) { return TRUE; } else { --- 3393,3397 ---- beep the player for trying to move a non-mobile unit. */ ! if (impl_move_to(side, unit, other, x, y, 0)) { return TRUE; } else { *************** *** 3696,3700 **** int ! impl_move_to(Side *side, Unit *unit, int x, int y, int dist) { #ifdef DESIGNERS --- 3696,3700 ---- int ! impl_move_to(Side *side, Unit *unit, Unit *unit2, int x, int y, int dist) { #ifdef DESIGNERS *************** *** 3706,3709 **** --- 3706,3724 ---- } #endif /* DESIGNERS */ + + #ifdef BRANCH_MCAMPO + if (unit2) { + // if possible, occupy unit2 + if (can_occupy(unit, unit2) && sides_allow_entry(unit, unit2)) { + net_set_occupy_task(unit, unit2); + return TRUE; + } + // move unit2's location if possible, or close to it + int dist = !side_thinks_it_can_put_type_at(side, unit->type, + unit2->x, unit2->y); + net_set_move_to_task (unit, unit2->x, unit2->y, dist); + return TRUE; + } + #endif // BRANCH_MCAMPO /* Check that we can put the unit at the destination. */ if (!side_thinks_it_can_put_type_at(side, unit->type, x, y)) { --- NEW FILE: pathfind.cc --- /* Pathfinding Copyright (C) 2007 Massimo Campostrini Xconq 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 2, or (at your option) any later version. See the file COPYING. */ // The present file contains code from astar/findpath.cpp: /////////////////////////////////////////////////////////////////////////////// // STL A* Search implementation // (C)2001 Justin Heyes-Jones // // Finding a path on a simple grid maze // This shows how to do shortest path finding using A* /* A* Algorithm Implementation using STL is Copyright (C)2001-2005 Justin Heyes-Jones Permission is given by the author to freely redistribute and include this code in any program as long as this credit is given where due. COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER THIS DISCLAIMER. Use at your own risk! */ /////////////////////////////////////////////////////////////////////////////// #include "stlastar.hpp" #include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; #include "conq.h" #include "kernel.h" #ifdef BRANCH_MCAMPO int total_entry_cost(int u1, int u3, int x1, int y1, int z1, int u2, int x2, int y2, int z2); // from move.c int path_nodes_allocated=0; int move_cost (const int u, const Position& o, const Position& n) { // "eat" const int uu = u, ou=o.u, ox=o.x, oy=o.y, nu=n.u, nx=n.x, ny=n.y; if (distance(ox, oy, nx, ny)>1) { printf(" (error) "); fflush(stdout); } if (nu==NONUTYPE) { return total_move_cost (uu, ou, ox, oy, 0, nx, ny, 0); } else { return total_entry_cost(uu, ou, ox, oy, 0, nu, nx, ny, 0); } } bool can_do (const int u, const int mp) { // "eat" const int uu = u, mpu = mp; return type_can_have_enough_mp(uu, mpu); } bool can_move (int u, const Position& o, const Position& n) { return can_do(u, move_cost(u, o, n)); } bool any_unfriendly_at (Unit *unit, int x, int y) { Unit *unit2; for_all_stack(x, y, unit2) { if (!unit_trusts_unit(unit, unit2)) return true; } return false; } bool allowed_cell (Unit *unit, int x, int y) { return type_can_occupy_cell(unit->type, x, y) && terrain_visible(unit->side, x, y) && !any_unfriendly_at(unit, x, y); } bool allowed_transport (Unit *unit, Unit *unit2) { return type_can_occupy(unit->type, unit2) && sides_allow_entry(unit, unit2); } // C++ iterators #define for_all_cell_terrain_types(v) \ for (int v = 0; v < numttypes; ++v) \ if (t_is_cell(v)) // Class definitions class PathElement { public: Position p; PathElement (); PathElement (const Position& p_); PathElement (PathElement const*const pp); double GoalCostEstimate (const PathElement& nodeGoal) const; bool IsGoal (const PathElement &nodeGoal) const; bool GetSuccessors (AStarSearch<PathElement>* astarsearch, PathElement *parent_node) const; double GetCost (const PathElement& successor) const; bool IsSameState (const PathElement &rhs) const; void PrintNodeInfo (const int i, PathElement const*const parent) const; double GoalDistanceEstimate (const PathElement& nodeGoal) const; }; PathElement::PathElement() { p.x = -1; p.y = -1; // p.t = NONTTYPE; p.u = NONUTYPE; } PathElement::PathElement (const Position& p_) { p = p_; } PathElement::PathElement (PathElement const*const pp) { if (pp) { p = pp->p; } else { p.x = -1; p.y = -1; // p.t = NONTTYPE; p.u = NONUTYPE; } } bool operator== (const PathElement& a, const PathElement& b) { if (a.p.x != b.p.x) return false; if (a.p.y != b.p.y) return false; if (a.p.u != b.p.u) return false; return true; } bool operator!= (const PathElement& a, const PathElement& b) { return !(a == b); } bool PathElement::IsSameState (const PathElement &rhs) const { return *this == rhs; } class PathGlobals { public: Unit *unit; // the traveller int u; // unit type of the traveller int dist; // the requested distance PathElement goal; // cached computations double min_mp; // min cell mp for u vector<double> terrain_cost; // added cost for each cell bool init (Unit *unit_, Unit *unit2, const int x, const int y, const int dist_); }; PathGlobals PGlobals; bool PathGlobals::init (Unit *unit_, Unit *unit2, const int x, const int y, const int dist_) { unit = unit_; dist = dist_; if (!unit || dist<0) return false; u = unit->type; if (unit2) { goal.p.x = unit2->x; goal.p.y = unit2->y; goal.p.u = unit2->type; } else { goal.p.x = x; goal.p.y = y; goal.p.u = NONUTYPE; } if (dist==0 && !unit2 && !allowed_cell(unit, goal.p.x, goal.p.y)) return false; if (dist==0 && unit2 && !allowed_transport(unit, unit2)) return false; // compute the min mp needed to enter a cell int min_e=9999, min_l=9999; for_all_cell_terrain_types(t) { min_e = min(min_e, ut_mp_to_enter(u,t)); min_l = min(min_l, ut_mp_to_leave(u,t)); } min_mp = min_e + min_l; // add a (fractional) terrain cost, // so for the same mp's we favor transports, // then terrains with good productivity and low accident rate terrain_cost.resize(numttypes,0); for_all_cell_terrain_types(t) { terrain_cost[t] = 0.01 + 0.001*max(0,100-min(ut_productivity(u,t),100)) + 0.001*max(0,ut_accident_hit(u,t)); } return true; } void PathElement::PrintNodeInfo (const int i, PathElement const*const parent) const { printf("%2d (x=%d, y=%d, u=%d", i, p.x, p.y, p.u); if (parent) { int mc = move_cost(PGlobals.u, parent->p, p); printf(", cost = %d+%g", mc, parent->GetCost(*this)-mc); } int gx=PGlobals.goal.p.x, gy=PGlobals.goal.p.y; printf(", dist = %d)\n", distance(p.x, p.y, gx, gy)); fflush(stdout); } // Here's the heuristic function that estimates the distance from a Node // to the Goal. double PathElement::GoalDistanceEstimate (const PathElement& nodeGoal) const { // "eat" const int ox=p.x, oy=p.y, nx=nodeGoal.p.x, ny=nodeGoal.p.y; return PGlobals.min_mp * distance(ox, oy, nx, ny); } bool PathElement::IsGoal (const PathElement &nodeGoal) const { return *this == nodeGoal; } // given this node, what does it cost to move to successor. double PathElement::GetCost (const PathElement &successor) const { double cost = move_cost(PGlobals.u, p, successor.p); if (successor.p.u==NONUTYPE) // add a fractional cost, so we favor transports, // then terrains with good productivity and low accident rate cost += PGlobals.terrain_cost[terrain_at(successor.p.x,successor.p.y)]; return cost; } // This generates the successors to the given Node. It uses a helper function // called AddSuccessor to give the successors to the AStar class. // The A* specific initialisation is done for each node internally, so here // you just set the state information that is specific to the application bool PathElement::GetSuccessors (AStarSearch<PathElement> *astarsearch, PathElement *parent_node) const { Unit *unit = PGlobals.unit; int u=unit->type, ox=p.x, oy=p.y; int gx=PGlobals.goal.p.x, gy=PGlobals.goal.p.y; bool error=false; PathElement parent(parent_node); PathElement NewNode; // push each possible move except allowing the search to go backwards int dir; for_all_directions(dir) { int nx, ny, mp; if (point_in_dir(ox, oy, dir, &nx, &ny)) { NewNode.p.x = nx; NewNode.p.y = ny; NewNode.p.u = NONUTYPE; if ((allowed_cell(unit, nx, ny) && can_move(u, p, NewNode.p) && !(NewNode==parent)) || distance(gx, gy, nx, ny) <= PGlobals.dist && PGlobals.dist>0) error = error || !astarsearch->AddSuccessor(NewNode); if (distance(gx, gy, nx, ny) <= PGlobals.dist && PGlobals.dist>0) // no need to check for transports continue; Unit *unit2, *occ; for_all_stack(nx, ny, unit2) { if (allowed_transport(unit, unit2)) { NewNode.p.u = unit2->type; if (can_move(u, p, NewNode.p) && !(NewNode==parent)) error = error || !astarsearch->AddSuccessor(NewNode); } // Also try occupants; we could use the recursive occupant test for_all_occupants(unit2, occ) { if (allowed_transport(unit, occ)) { NewNode.p.u = occ->type; if (can_move(u, p, NewNode.p) && !(NewNode==parent)) error = error || !astarsearch->AddSuccessor(NewNode); } } } } } return !error; } // external interface // find a path for unit to move within dist of (x,y), // or occupy unit2 (if unit2!=NULL && dist==0) // return a pointer to a list of positions PathNode* path_find (Unit *unit, Unit *unit2, int x, int y, int dist) { if (dist>2) // pathtinding is likely to be very inefficient... return 0; if (!PGlobals.init(unit, unit2, x, y, dist)) // invalid parameters return 0; PathElement start; start.p.x = unit->x; start.p.y = unit->y; start.p.u = unit->transport ? unit->transport->type : NONUTYPE; // Create an instance of the search class AStarSearch<PathElement> astarsearch; // Set Start and goal states astarsearch.SetStartAndGoalStates(start, PGlobals.goal); unsigned int SearchState; unsigned int SearchSteps = 0; do { SearchState = astarsearch.SearchStep(); SearchSteps++; } while (SearchState == AStarSearch<PathElement>::SEARCH_STATE_SEARCHING); if (SearchState != AStarSearch<PathElement>::SEARCH_STATE_SUCCEEDED) { if (SearchState == AStarSearch<PathElement>::SEARCH_STATE_FAILED) { Dprintf("A* search terminated. Did not find goal state\n"); } else { Dprintf("PATH_FIND error #1 in path_find\n"); } // Once you're done with the solution you can free the nodes up astarsearch.FreeSolutionNodes(); return 0; } // Search succeeded // Copy the solution up to the requested distance from the goal PathNode* path = (PathNode*) xmalloc(sizeof(PathNode)); path_nodes_allocated++; int gx=PGlobals.goal.p.x, gy=PGlobals.goal.p.y; int count=0; PathNode* current=path; PathElement* parent=0; PathElement* node = astarsearch.GetSolutionStart(); while (1) { if (distance(gx, gy, node->p.x, node->p.y) < dist) break; current->p = node->p; parent = node; node = astarsearch.GetSolutionNext(); if (!node) break; current->next = (PathNode*) xmalloc(sizeof(PathNode)); path_nodes_allocated++; current = current->next; current->next = 0; count++; }; // Once you're done with the solution you can free the nodes up astarsearch.FreeSolutionNodes(); Dprintf("A* search succeeded: sol. steps = %d, total steps = %d, " "alloc. nodes = %d\n", count, astarsearch.GetStepCount(), path_nodes_allocated); return path; } #endif // #ifdef BRANCH_MCAMPO /////////////////////////////////////////////////////////////////////////////// Index: side.c =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/side.c,v retrieving revision 1.24 retrieving revision 1.24.2.1 diff -C2 -d -r1.24 -r1.24.2.1 *** side.c 2 Jul 2005 21:55:21 -0000 1.24 --- side.c 8 Apr 2007 19:34:01 -0000 1.24.2.1 *************** *** 774,778 **** side_controls_side(Side *side, Side *side2) { ! return (side == side2 || side2->controlled_by == side); } --- 774,778 ---- side_controls_side(Side *side, Side *side2) { ! return (side == side2 || (side2 && side2->controlled_by == side)); } Index: move.c =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/move.c,v retrieving revision 1.8 retrieving revision 1.8.2.1 diff -C2 -d -r1.8 -r1.8.2.1 *** move.c 28 Jul 2005 03:28:27 -0000 1.8 --- move.c 8 Apr 2007 19:34:01 -0000 1.8.2.1 *************** *** 35,39 **** static int unit_traverse_blockable_by(Unit *unit, Unit *unit2); static int any_friendly_at(Unit *unit, int x, int y); ! static int total_entry_cost(int u1, int u3, int x1, int y1, int z1, int u2, int x2, int y2, int z2); static int number_member(int x, Obj *lis); static int wind_value(Unit *unit, int angle, int force, Obj *effect, int maxval); --- 35,40 ---- static int unit_traverse_blockable_by(Unit *unit, Unit *unit2); static int any_friendly_at(Unit *unit, int x, int y); ! // static ! int total_entry_cost(int u1, int u3, int x1, int y1, int z1, int u2, int x2, int y2, int z2); static int number_member(int x, Obj *lis); static int wind_value(Unit *unit, int angle, int force, Obj *effect, int maxval); Index: conq.h =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/conq.h,v retrieving revision 1.15 retrieving revision 1.15.2.1 diff -C2 -d -r1.15 -r1.15.2.1 *** conq.h 10 Jul 2005 13:28:37 -0000 1.15 --- conq.h 8 Apr 2007 19:34:01 -0000 1.15.2.1 *************** *** 16,19 **** --- 16,20 ---- */ + #define BRANCH_MCAMPO 1 /* Elements of bitmask controlling display updates. */ Index: unit.h =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/unit.h,v retrieving revision 1.10 retrieving revision 1.10.2.1 diff -C2 -d -r1.10 -r1.10.2.1 *** unit.h 25 Jun 2005 22:57:48 -0000 1.10 --- unit.h 8 Apr 2007 19:34:01 -0000 1.10.2.1 *************** *** 670,673 **** --- 670,676 ---- TaskType type; /*!< the kind of task we want to do */ int args[MAXTASKARGS]; /*!< arguments */ + #ifdef BRANCH_MCAMPO + void *argptr; /*!< pointer argument */ + #endif short execnum; /*!< how many times this has been done */ short retrynum; /*!< number of immed failures so far */ Index: plan.c =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/plan.c,v retrieving revision 1.16 retrieving revision 1.16.2.1 diff -C2 -d -r1.16 -r1.16.2.1 *** plan.c 6 Aug 2005 19:27:12 -0000 1.16 --- plan.c 8 Apr 2007 19:34:01 -0000 1.16.2.1 *************** *** 3365,3370 **** for_all_material_types(m) { ! if (((um_base_consumption(u, m) > 0) ! || (um_consumption_per_move(u, m) > 0)) && (unit->transport == NULL)) { if (unit->side) --- 3365,3374 ---- for_all_material_types(m) { ! if (((um_base_consumption(u, m) > 0 ! #ifdef BRANCH_MCAMPO ! // only watch "important" materials ! && um_hp_per_starve(u, m) > 0 ! #endif ! ) || (um_consumption_per_move(u, m) > 0)) && (unit->transport == NULL)) { if (unit->side) Index: task.c =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/task.c,v retrieving revision 1.14.2.2 retrieving revision 1.14.2.3 diff -C2 -d -r1.14.2.2 -r1.14.2.3 *** task.c 8 Apr 2007 18:37:06 -0000 1.14.2.2 --- task.c 8 Apr 2007 19:34:01 -0000 1.14.2.3 *************** *** 18,36 **** #include "aiunit2.h" /* This is the number of tasks to allocate initially. More will always be allocated as needed, so this should be a "reasonable" value. */ - #ifndef INITMAXTASKS #define INITMAXTASKS 100 #endif - enum choicestate { - eitherway, - leftthenright, - rightthenleft, - leftonly, - rightonly - }; - static int compare_directions(const void *a0, const void *a1); static int test_for_buildable(int x, int y); --- 18,36 ---- #include "aiunit2.h" + void set_task_pathinfo (Task *task, int pathinfo); + int task_pathinfo (Task *task); + void free_task_path (Task *task); + + #ifdef BRANCH_MCAMPO + static int manage_path (Unit *unit, Task *task); + extern int path_nodes_allocated; + #endif + /* This is the number of tasks to allocate initially. More will always be allocated as needed, so this should be a "reasonable" value. */ #ifndef INITMAXTASKS #define INITMAXTASKS 100 #endif static int compare_directions(const void *a0, const void *a1); static int test_for_buildable(int x, int y); *************** *** 138,141 **** --- 138,144 ---- task->args[i] = 0; task->next = NULL; + #ifdef BRANCH_MCAMPO + task->argptr = NULL; + #endif return task; } *************** *** 171,175 **** for_all_stack(x, y, unit) { if (in_play(unit) ! && !completed(unit) && unit->type == tmpbuildutype && unit->side == tmpbuilder->side) { --- 174,178 ---- for_all_stack(x, y, unit) { if (in_play(unit) ! && !fullsized(unit) && unit->type == tmpbuildutype && unit->side == tmpbuilder->side) { *************** *** 203,207 **** if (!in_play(buildee)) return TASK_FAILED; ! if (completed(buildee)) return TASK_IS_COMPLETE; uc = buildee->type; --- 206,210 ---- if (!in_play(buildee)) return TASK_FAILED; ! if (fullsized(buildee)) return TASK_IS_COMPLETE; uc = buildee->type; *************** *** 260,264 **** if (task->args[1] != 0) { occ = find_unit(task->args[1]); ! if (in_play(occ) && occ->type == u2 && !completed(occ)) return occ; } --- 263,267 ---- if (task->args[1] != 0) { occ = find_unit(task->args[1]); ! if (in_play(occ) && occ->type == u2 && !fullsized(occ)) return occ; } *************** *** 266,270 **** for_all_occupants(unit, occ) { if (in_play(occ) ! && !completed(occ) && occ->type == u2 && occ->side == unit->side) --- 269,273 ---- for_all_occupants(unit, occ) { if (in_play(occ) ! && !fullsized(occ) && occ->type == u2 && occ->side == unit->side) *************** *** 274,278 **** for_all_stack(x, y, occ) { if (in_play(occ) ! && !completed(occ) && occ->type == u2 && occ->side == unit->side) { --- 277,281 ---- for_all_stack(x, y, occ) { if (in_play(occ) ! && !fullsized(occ) && occ->type == u2 && occ->side == unit->side) { *************** *** 328,382 **** do_capture_task(Unit *unit, Task *task) { ! int u = NONUTYPE, tu = NONUTYPE; ! Side *side = NULL, *tside = NULL; ! int n = -1; ! Unit *target = NULL; ! UnitView *uvtarget = NULL; ! int capmethod = CAPTURE_METHOD_ANY; ! int tx = -1, ty = -1, dist = -1; ! int cancapture = FALSE, canattack = FALSE, canfire = FALSE; ! ! n = task->args[2]; ! // Get out, if we have exceeded number of capture attempts. ! if (task->execnum > n) ! return TASK_IS_COMPLETE; ! u = unit->type; ! side = unit->side; ! // NOTE: Looking up the actual unit is cheating. ! // We need the uview by ID, not the unit. ! target = find_unit(task->args[0]); ! if (!in_play(target)) ! return TASK_FAILED; ! uvtarget = find_unit_view(side, target); ! if (!uvtarget) ! return TASK_FAILED; ! capmethod = task->args[1]; ! tx = uvtarget->x; ty = uvtarget->y; ! tu = uvtarget->type; ! tside = side_n(uvtarget->siden); ! dist = distance(tx, ty, unit->x, unit->y); ! canattack = ((capmethod & CAPTURE_METHOD_ATTACK) ! && valid(check_attack_action(unit, unit, target, 100))); ! canfire = ((capmethod & HIT_METHOD_FIRE) ! && (dist <= (uu_zoc_range(u, tu) + 1)) ! && valid(check_fire_at_action(unit, unit, target, -1))); ! cancapture = ((capmethod & CAPTURE_METHOD_CAPTURE) ! && valid(check_capture_action(unit, unit, target))); ! if (cancapture) { ! prep_capture_action(unit, unit, target); ! return TASK_PREPPED_ACTION; ! } ! else if (canattack) { ! prep_attack_action(unit, unit, target, 100); ! return TASK_PREPPED_ACTION; ! } ! else if (canfire) { ! prep_fire_at_action(unit, unit, target, -1); ! return TASK_PREPPED_ACTION; ! } ! // TODO: Handle using transports or occs to perform capture. ! // TODO: Handle using detonations to perform capture. - #if (0) /* (should be able to say how hard to try) */ tx = task->args[0]; ty = task->args[1]; --- 331,338 ---- do_capture_task(Unit *unit, Task *task) { ! int u = unit->type, tx, ty, tu2, ts2, dist; ! Unit *unit2; ! Side *us = unit->side; /* (should be able to say how hard to try) */ tx = task->args[0]; ty = task->args[1]; *************** *** 423,428 **** return TASK_FAILED; } - #endif - return TASK_FAILED; } --- 379,382 ---- *************** *** 482,536 **** do_hit_unit_task(Unit *unit, Task *task) { ! int u = NONUTYPE, tu = NONUTYPE; ! Side *side = NULL, *tside = NULL; ! Unit *target = NULL; ! UnitView *uvtarget = NULL; ! int n = -1; ! int tx = -1, ty = -1, dist = -1; ! int hitmethod = HIT_METHOD_NONE; ! int canattack = FALSE, canfire = FALSE, candet = FALSE; ! n = task->args[2]; ! // Get out, if we have exceeded number of hit attempts. ! if (task->execnum > n) return TASK_IS_COMPLETE; ! u = unit->type; ! side = unit->side; ! // NOTE: Looking up the actual unit is cheating. ! // We need the uview by ID, not the unit. ! target = find_unit(task->args[0]); ! if (!in_play(target)) ! return TASK_FAILED; ! uvtarget = find_unit_view(side, target); ! if (!uvtarget) ! return TASK_FAILED; ! hitmethod = task->args[1]; ! tx = uvtarget->x; ! ty = uvtarget->y; ! tu = uvtarget->type; ! tside = side_n(uvtarget->siden); dist = distance(tx, ty, unit->x, unit->y); - canattack = ((hitmethod & HIT_METHOD_ATTACK) - && valid(check_attack_action(unit, unit, target, 100))); - canfire = ((hitmethod & HIT_METHOD_FIRE) - && valid(check_fire_at_action(unit, unit, target, -1))); - candet = ((hitmethod & HIT_METHOD_DETONATE) - && valid(can_detonate(unit, unit)) - && (dist >= uu_detonation_range(u, tu))); - if (canattack) { - prep_attack_action(unit, unit, target, 100); - return TASK_PREPPED_ACTION; - } - else if (canfire) { - prep_fire_at_action(unit, unit, target, -1); - return TASK_PREPPED_ACTION; - } - else if (candet) { - prep_detonate_action(unit, unit, tx, ty, unit->z); - return TASK_PREPPED_ACTION; - } - // TODO: Handle using transports or occs to perform hit. - - #if (0) if (dist <= 1) { if (can_attack_any(unit, unit)) { --- 436,458 ---- do_hit_unit_task(Unit *unit, Task *task) { ! int u = unit->type, tx, ty, dist, movedist, tu, ts; ! Unit *unit2; ! UnitView *uview; ! Side *us = unit->side; ! /* Temporary hack. Ask the planner to re-evaluate continuation of ! this task. If it wants to, then it will issue a new one. If not, ! then move on and do something more productive. */ ! /* A better solution would be to add a new arg to the task that would ! tell it the number of times to attempt execution before returning to ! the planner for guidance. */ ! if (task->execnum > 3) return TASK_IS_COMPLETE; ! /* This is to hit a (given type/side of) unit at a given place. */ ! tx = task->args[0]; ! ty = task->args[1]; ! tu = task->args[2]; ! ts = task->args[3]; dist = distance(tx, ty, unit->x, unit->y); if (dist <= 1) { if (can_attack_any(unit, unit)) { *************** *** 570,574 **** } if (dist < u_range_min(u)) { ! // TODO: Retreat from target, and then fire. return TASK_FAILED; } --- 492,496 ---- } if (dist < u_range_min(u)) { ! /* should move further away */ return TASK_FAILED; } *************** *** 578,583 **** if (ts == uview->siden && tu == uview->type) { unit2 = view_unit(uview); ! if (unit2 ! && valid(check_fire_at_action(unit, unit, unit2, -1))) { prep_fire_at_action(unit, unit, unit2, -1); return TASK_PREPPED_ACTION; --- 500,504 ---- if (ts == uview->siden && tu == uview->type) { unit2 = view_unit(uview); ! if (unit2 && valid(check_fire_at_action(unit, unit, unit2, -1))) { prep_fire_at_action(unit, unit, unit2, -1); return TASK_PREPPED_ACTION; *************** *** 605,609 **** return TASK_IS_INCOMPLETE; } - #endif return TASK_FAILED; } --- 526,529 ---- *************** *** 747,750 **** --- 667,860 ---- } + int + allowed_transport_check (Unit *unit, Unit *unit2, int check) + { + if (!can_occupy(unit, unit2)) return 0; + if (!sides_allow_entry(unit, unit2)) return 0; + if (check && !valid(check_enter_action(unit, unit, unit2))) return 0; + return 1; + } + + /* Find a transport at x, y of type tt for unit */ + /* if tt==-2, find a transport of any type */ + /* if check is true, actually check the action */ + static Unit* + find_transport_at (Unit * unit, int x, int y, int tt, int check) + { + Unit *unit2, *occ; + if (tt==NONUTYPE) return NULL; + + for_all_stack(x, y, unit2) { + if ((tt==-2 || tt==unit2->type) && + allowed_transport_check(unit, unit2, check)) + return unit2; + + /* Perhaps an occupant... */ + /* (We could use the recursive occupant test, but if + things are that complicated, the player should probably + exercise manual control here.) */ + for_all_occupants(unit2, occ) { + if ((tt==-2 || tt==occ->type) + && allowed_transport_check(unit, occ, check)) + return occ; + } + } + + return NULL; + } + + static TaskOutcome + do_single_move_subtask (Unit *unit, Task *task, + Unit *transport, int tt, + int tx, int ty, int tdist) + { + int dist = distance(tx, ty, unit->x, unit->y), check; + Unit *unit2 = (tt==NONUTYPE || tt==-2) ? NULL : + find_transport_at(unit, tx, ty, tt, 1); + + if (transport && !in_play(transport)) { + return TASK_FAILED; + } + + if (dist<=tdist && (tdist>0 || unit->transport==transport)) { + /* We're there already, nothing more to do. */ + free_task_path(task); + return TASK_IS_COMPLETE; + } else if (dist<=1 && transport) { + if (valid(check_enter_action(unit, unit, transport))) { + prep_enter_action(unit, unit, transport); + return TASK_PREPPED_ACTION; + } else { + /* Try a couple times, then fail if not working. */ + return (task->execnum < 3 ? TASK_IS_INCOMPLETE : TASK_FAILED); + } + } else if (unit2 && valid(check_enter_action(unit, unit, unit2))) { + /* There's somebody that we can enter, so we prefer to do that. */ + prep_enter_action(unit, unit, unit2); + return TASK_PREPPED_ACTION; + } else { + /* Try a basic move action. */ + if (valid(check = check_move_action(unit, unit, tx, ty, unit->z))) { + /* Move into an empty cell. */ + prep_move_action(unit, unit, tx, ty, unit->z); + return TASK_PREPPED_ACTION; + } else { + /* If we're just short on mp, wait until the next turn to + try to move. */ + if (check == A_MOVE_NO_MP) { + notify(unit->side, + "%s is resting until next turn.", + unit_handle(unit->side, unit)); + set_unit_reserve(unit->side, unit, TRUE, FALSE); + return TASK_IS_INCOMPLETE; + } + Dprintf("%s move action fails check, result is %s\n", + unit_desig(unit), hevtdefns[check].name); + } + } + free_task_path(task); + return TASK_FAILED; + } + + void set_task_pathinfo (Task *task, int pathinfo) + { + if (task->type==TASK_MOVE_TO) { + task->args[4] = pathinfo; + } else if (task->type==TASK_OCCUPY) { + task->args[1] = pathinfo; + } + } + + int task_pathinfo (Task *task) + { + if (task->type==TASK_MOVE_TO) return task->args[4]; + if (task->type==TASK_OCCUPY ) return task->args[1]; + return eitherway; + } + + int task_dist (Task *task) + { + if (task->type==TASK_MOVE_TO) return task->args[3]; + return 0; + } + + void free_task_path (Task *task) + { + #ifdef BRANCH_MCAMPO + int count = 0; + if (task->argptr != NULL) { + PathNode* current; + for (current = (PathNode*) task->argptr; current; + current = current->next) { + free(current); + path_nodes_allocated--; + count++; + } + task->argptr = NULL; + set_task_pathinfo(task, path_not_searched); + } + #endif + } + + #ifdef BRANCH_MCAMPO + // path_find interface for the task + static int manage_path (Unit *unit, Task *task) + { + int tx, ty, dist; + Unit *unit2; + + if (task->type==TASK_MOVE_TO) { + tx = task->args[0]; + ty = task->args[1]; + dist = task->args[3]; + /* If there's somebody that we can enter, prefer to do that. */ + unit2 = find_transport_at(unit, tx, ty, -2, 0); + } else if (task->type==TASK_OCCUPY) { + unit2 = find_unit_dead_or_alive(task->args[0]); + if (!unit2 || !in_play(unit2)) { + set_task_pathinfo(task, eitherway); + return 0; + } + tx = unit2->x; + ty = unit2->y; + dist = 0; + } else { + set_task_pathinfo(task, eitherway); + return 0; + } + + // check that we are on the path + if (task->argptr) { + PathNode *pos = (PathNode*) task->argptr; + if (pos->p.x!=unit->x || pos->p.y!=unit->y) { + // we strayed from the path, try to find the path again + Dprintf("manage_path: %s is at %d,%d while the path is at " + "%d,%d: find a new path to %d,%d\n", + unit_handle(NULL, unit), unit->x, unit->y, + pos->p.x, pos->p.x, tx, ty); + free_task_path(task); + } + } + + // if we did not search for a path + if (task_pathinfo(task)==path_not_searched) { + if (task->argptr) { + Dprintf("PATH_FIND error #2 in manage_path\n"); + free_task_path(task); + } + set_task_pathinfo(task, path_searched); + // search for an optimized path to tx, ty + task->argptr = + (void *) path_find(unit, unit2, tx, ty, dist); + // if path_find failed, fall back to old way of moving + if (!task->argptr) { + set_task_pathinfo(task, eitherway); + } + } + + return 1; + } + #endif // BRANCH_MCAMPO + /* The move-to task is the main way for units to get from point A to point B. In addition to the destination, the task has a required *************** *** 828,887 **** case 0: /* We're there already, nothing more to do. */ ! return TASK_IS_COMPLETE; case 1: ! /* Adjacent cell, do a single move. */ ! /* But first, if there are units here already, prefer to ! interact with them. */ ! for_all_stack(tx, ty, unit2) { ! /* If there's somebody that we can enter, prefer to do that. */ ! if (can_occupy(unit, unit2) ! && valid(check_enter_action(unit, unit, unit2))) { ! prep_enter_action(unit, unit, unit2); ! return TASK_PREPPED_ACTION; ! } ! /* Perhaps an occupant... */ ! /* (We could use the recursive occupant test, but if ! things are that complicated, the player should probably ! exercise manual control here.) */ ! for_all_occupants(unit2, occ) { ! if (can_occupy(unit, occ) ! && valid(check_enter_action(unit, unit, occ))) { ! prep_enter_action(unit, unit, occ); ! return TASK_PREPPED_ACTION; ! } ! } ! } ! #if 0 /* auto-attack on move should be player-controlled... */ ! if (!trusted_side(unit->side, unit2->side)) { ! /* This is probably not a good idea, combat odds not ! taken into account. */ ! if (valid(check_attack_action(unit, unit, unit2, 100))) { ! prep_attack_action(unit, unit, unit2, 100); ! return TASK_PREPPED_ACTION; ! } else { ! continue; ! } ! } ! #endif ! /* Now try a basic move action. */ ! if (valid(check = check_move_action(unit, unit, tx, ty, unit->z))) { ! /* Moving into an empty cell. */ ! prep_move_action(unit, unit, tx, ty, unit->z); ! return TASK_PREPPED_ACTION; ! } else { ! /* If we're just short on mp, wait until the next turn to ! try to move. */ ! if (check == A_MOVE_NO_MP) { ! notify(unit->side, ! "%s is resting until next turn.", ! unit_handle(unit->side, unit)); ! set_unit_reserve(unit->side, unit, TRUE, FALSE); ! return TASK_IS_INCOMPLETE; ! } ! Dprintf("%s move action fails check, result is %s\n", ! unit_desig(unit), hevtdefns[check].name); ! return TASK_FAILED; ! } break; default: if (dist <= u_move_range(unit->type) --- 938,950 ---- case 0: /* We're there already, nothing more to do. */ ! free_task_path(task); ! return TASK_IS_COMPLETE; ! case 1: ! /* Do a single move, old or new style */ ! return do_single_move_subtask(unit, task, NULL, ! -2, tx, ty, task->args[3]); break; + default: if (dist <= u_move_range(unit->type) *************** *** 908,914 **** Unit *unit2; - #if (0) /* If on mobile transport, let it handle things. */ - /* Comment: Umm, no. What if unit is trying to get off mobile transport? */ if (unit->transport != NULL && mobile(unit->transport->type) --- 971,975 ---- *************** *** 918,922 **** --- 979,1009 ---- return TASK_IS_INCOMPLETE; } + + #ifdef BRANCH_MCAMPO + manage_path(unit, task); + + // if we have path information, use it + if (task->argptr) { + // default: move to destination + int nx = tx, ny = ty, nt = NONUTYPE, nd = task_dist(task); + + // remove the first node of the path + PathNode* pos = ((PathNode*) task->argptr)->next; + free(task->argptr); + path_nodes_allocated--; + task->argptr = (void*) pos; + // use the new first node, if available + if (pos) { + nx = pos->p.x; + ny = pos->p.y; + nt = pos->p.u; + nd = 0; + } + /* Do a single move to a (hopefully) adjacent cell . */ + return do_single_move_subtask(unit, task, NULL, nt, nx, ny, nd); + } #endif + // no path information, use the "old" code + numdirs = choose_move_dirs(unit, tx, ty, TRUE, plausible_move_dir, *************** *** 1114,1117 **** --- 1201,1205 ---- tx = transport->x; ty = transport->y; + /* (should also fail if we don't know where transport is anymore) */ if (unit->transport == transport) { *************** *** 2059,2073 **** Unit *transport = NULL; ! if (task->next) ! nexttask = task->next; ! /* If we were waiting for a transport, and are now in it, ! then don't wait. */ ! if ((nexttask != NULL) && (nexttask->type == TASK_OCCUPY)) { ! transport = find_unit_dead_or_alive(nexttask->args[0]); ! if (in_play(transport) && (transport == unit->transport)) { ! task->next = nexttask->next; ! free_task(nexttask); } - return TASK_IS_COMPLETE; } if (task->args[0] > 0) { --- 2147,2162 ---- Unit *transport = NULL; ! if (task->next) { ! nexttask = task->next; ! /* If we were waiting for a transport, and are now in it, ! then don't wait. */ ! if (nexttask->type == TASK_OCCUPY) { ! transport = find_unit_dead_or_alive(nexttask->args[0]); ! if (in_play(transport) && (transport == unit->transport)) { ! task->next = nexttask->next; ! free_task(nexttask); ! } ! return TASK_IS_COMPLETE; } } if (task->args[0] > 0) { *************** *** 2467,2470 **** --- 2556,2560 ---- free_task(Task *task) { + free_task_path(task); task->next = freetasks; freetasks = task; *************** *** 2550,2573 **** Task * ! create_capture_task(Unit *unit, int id, int capmethod, int n) { Task *task = create_task(TASK_CAPTURE); ! task->args[0] = id; ! task->args[1] = capmethod; ! task->args[2] = n; return task; } void ! set_capture_task(Unit *unit, int id, int capmethod, int n) { ! add_task(unit, CLEAR_AGENDA, create_capture_task(unit, id, capmethod, n)); } void ! push_capture_task(Unit *unit, int id, int capmethod, int n) { ! add_task(unit, 0, create_capture_task(unit, id, capmethod, n)); } --- 2640,2663 ---- Task * ! create_capture_task(Unit *unit, int x, int y, int u, int s) { Task *task = create_task(TASK_CAPTURE); ! task->args[0] = x; task->args[1] = y; ! task->args[2] = u; ! task->args[3] = s; return task; } void ! set_capture_task(Unit *unit, int x, int y, int u, int s) { ! add_task(unit, CLEAR_AGENDA, create_capture_task(unit, x, y, u, s)); } void ! push_capture_task(Unit *unit, int x, int y, int u, int s) { ! add_task(unit, 0, create_capture_task(unit, x, y, u, s)); } *************** *** 2601,2624 **** Task * ! create_hit_unit_task(Unit *unit, int id, int hitmethod, int n) { Task *task = create_task(TASK_HIT_UNIT); ! task->args[0] = id; ! task->args[1] = hitmethod; ! task->args[2] = n; return task; } void ! set_hit_unit_task(Unit *unit, int id, int hitmethod, int n) { ! add_task(unit, CLEAR_AGENDA, create_hit_unit_task(unit, id, hitmethod, n)); } void ! push_hit_unit_task(Unit *unit, int id, int hitmethod, int n) { ! add_task(unit, 0, create_hit_unit_task(unit, id, hitmethod, n)); } --- 2691,2714 ---- Task * ! create_hit_unit_task(Unit *unit, int x, int y, int u, int s) { Task *task = create_task(TASK_HIT_UNIT); ! task->args[0] = x; task->args[1] = y; ! task->args[2] = u; ! task->args[3] = s; return task; } void ! set_hit_unit_task(Unit *unit, int x, int y, int u, int s) { ! add_task(unit, CLEAR_AGENDA, create_hit_unit_task(unit, x, y, u, s)); } void ! push_hit_unit_task(Unit *unit, int x, int y, int u, int s) { ! add_task(unit, 0, create_hit_unit_task(unit, x, y, u, s)); } *************** *** 2643,2652 **** } - void - push_move_dir_task(Unit *unit, int dir, int n) - { - add_task(unit, 0, create_move_dir_task(unit, dir, n)); - } - Task * create_move_to_task(Unit *unit, int x, int y, int dist) --- 2733,2736 ---- *************** *** 2664,2667 **** --- 2748,2755 ---- task->args[3] = dist; task->args[4] = eitherway; + #ifdef BRANCH_MCAMPO + task->args[4] = path_not_searched; + #endif + return task; } *************** *** 2686,2689 **** --- 2774,2780 ---- task->args[0] = transport->id; task->args[1] = eitherway; + #ifdef BRANCH_MCAMPO + task->args[1] = path_not_searched; + #endif /* add a waiting period also? */ return task; --- NEW FILE: fsa.hpp --- /* A* Algorithm Implementation using STL is Copyright (C)2001-2005 Justin Heyes-Jones Permission is given by the author to freely redistribute and include this code in any program as long as this credit is given where due. COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER THIS DISCLAIMER. Use at your own risk! FixedSizeAllocator class Copyright 2001 Justin Heyes-Jones This class is a constant time O(1) memory manager for objects of a specified type. The type is specified using a template class. Memory is allocated from a fixed size buffer which you can specify in the class constructor or use the default. Using GetFirst and GetNext it is possible to iterate through the elements one by one, and this would be the most common use for the class. I would suggest using this class when you want O(1) add and delete and you don't do much searching, which would be O(n). Structures such as binary trees can be used instead to get O(logn) access time. */ #ifndef FSA_H #define FSA_H #include <string.h> #include <stdio.h> template <class USER_TYPE> class FixedSizeAllocator { public: // Constants enum { FSA_DEFAULT_SIZE = 100 }; // This class enables us to transparently manage the extra data // needed to enable the user class to form part of the double-linked // list class struct FSA_ELEMENT { USER_TYPE UserType; FSA_ELEMENT *pPrev; FSA_ELEMENT *pNext; }; public: // methods FixedSizeAllocator( unsigned int MaxElements = FSA_DEFAULT_SIZE ) : m_MaxElements( MaxElements ), m_pFirstUsed( NULL ) { // Allocate enough memory for the maximum number of elements char *pMem = new char[ m_MaxElements * sizeof (FSA_ELEMENT) ]; m_pMemory = (FSA_ELEMENT *) pMem; // Set the free list first pointer m_pFirstFree = m_pMemory; // Clear the memory memset( m_pMemory, 0, sizeof( FSA_ELEMENT ) * m_MaxElements ); // Point at first element FSA_ELEMENT *pElement = m_pFirstFree; // Set the double linked free list for( unsigned int i=0; i<m_MaxElements; i++ ) { pElement->pPrev = pElement-1; pElement->pNext = pElement+1; pElement++; } // first element should have a null prev m_pFirstFree->pPrev = NULL; // last element should have a null next (pElement-1)->pNext = NULL; } ~FixedSizeAllocator() { // Free up the memory delete [] m_pMemory; } // Allocate a new USER_TYPE and return a pointer to it USER_TYPE *alloc() { FSA_ELEMENT *pNewNode = NULL; if( !m_pFirstFree ) { return NULL; } else { pNewNode = m_pFirstFree; m_pFirstFree = pNewNode->pNext; // if the new node points to another free node then // change that nodes prev free pointer... if( pNewNode->pNext ) { pNewNode->pNext->pPrev = NULL; } // node is now on the used list pNewNode->pPrev = NULL; // the allocated node is always first in the list if( m_pFirstUsed == NULL ) { pNewNode->pNext = NULL; // no other nodes } else { m_pFirstUsed->pPrev = pNewNode; // insert this at the head of the used list pNewNode->pNext = m_pFirstUsed; } m_pFirstUsed = pNewNode; } return reinterpret_cast<USER_TYPE*>(pNewNode); } // Free the given user type // For efficiency I don't check whether the user_data is a valid // pointer that was allocated. I may add some debug only checking // (To add the debug check you'd need to make sure the pointer is in // the m_pMemory area and is pointing at the start of a node) void free( USER_TYPE *user_data ) { FSA_ELEMENT *pNode = reinterpret_cast<FSA_ELEMENT*>(user_data); // manage used list, remove this node from it if( pNode->pPrev ) { pNode->pPrev->pNext = pNode->pNext; } else { // this handles the case that we delete the first node in the used list m_pFirstUsed = pNode->pNext; } if( pNode->pNext ) { pNode->pNext->pPrev = pNode->pPrev; } // add to free list if( m_pFirstFree == NULL ) { // free list was empty m_pFirstFree = pNode; pNode->pPrev = NULL; pNode->pNext = NULL; } else { // Add this node at the start of the free list m_pFirstFree->pPrev = pNode; pNode->pNext = m_pFirstFree; m_pFirstFree = pNode; } } // For debugging this displays both lists (using the prev/next list pointers) void Debug() { printf( "free list " ); FSA_ELEMENT *p = m_pFirstFree; while( p ) { printf( "%x!%x ", p->pPrev, p->pNext ); p = p->pNext; } printf( "\n" ); printf( "used list " ); p = m_pFirstUsed; while( p ) { printf( "%x!%x ", p->pPrev, p->pNext ); p = p->pNext; } printf( "\n" ); } // Iterators USER_TYPE *GetFirst() { return reinterpret_cast<USER_TYPE *>(m_pFirstUsed); } USER_TYPE *GetNext( USER_TYPE *node ) { return reinterpret_cast<USER_TYPE *> ( (reinterpret_cast<FSA_ELEMENT *>(node))->pNext ); } public: // data private: // methods private: // data FSA_ELEMENT *m_pFirstFree; FSA_ELEMENT *m_pFirstUsed; unsigned int m_MaxElements; FSA_ELEMENT *m_pMemory; }; #endif // defined FSA_H Index: read.c =================================================================== RCS file: /cvsroot/xconq/xconq/kernel/read.c,v retrieving revision 1.12 retrieving revision 1.12.2.1 diff -C2 -d -r1.12 -r1.12.2.1 *** read.c 17 Jun 2005 02:54:11 -0000 1.12 --- read.c 8 Apr 2007 19:34:01 -0000 1.12.2.1 *************** *** 14,17 **** --- 14,20 ---- #include "imf.h" + void set_task_pathinfo (Task *task, int pathinfo); + int task_pathinfo (Task *task); + extern int actually_read_lisp; *************** *** 3991,3994 **** --- 3994,4009 ---- if (form != lispnil) read_warning("Excess args for task %s", task_desig(task)); + + #ifdef BRANCH_MCAMPO + // paths are not saved; force recomputation + if (task_pathinfo(task)==path_searched) + set_task_pathinfo(task, path_not_searched); + #else + // paths are not implemented in this version + if (task_pathinfo(task)==path_searched || + task_pathinfo(task)==path_not_searched) + set_task_pathinfo(task, eitherway); + #endif + return task; } --- NEW FILE: stlastar.hpp --- /* A* Algorithm Implementation using STL is Copyright (C)2001-2005 Justin Heyes-Jones Permission is given by the author to freely redistribute and include this code in any program as long as this credit is given where due. COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER THIS DISCLAIMER. Use at your own risk! */ // used for text debugging #include <iostream> #include <stdio.h> //#include <conio.h> #include <assert.h> // stl includes #include <algorithm> #include <set> #include <vector> using namespace std; // fast fixed size memory allocator, used for fast node memory management #include "fsa.hpp" // Fixed size memory allocator can be disabled to compare performance // Uses std new and delete instead if you turn it off #define USE_FSA_MEMORY 1 // disable warning that debugging information has lines that are truncated // occurs in stl headers #pragma warning( disable : 4786 ) // The AStar search class. UserState is the users state space type template <class UserState> class AStarSearch { public: // data enum { SEARCH_STATE_NOT_INITIALISED, SEARCH_STATE_SEARCHING, SEARCH_STATE_SUCCEEDED, SEARCH_STATE_FAILED, SEARCH_STATE_OUT_OF_MEMORY, SEARCH_STATE_INVALID }; // A node represents a possible state in the search // The user provided state type is included inside this type public: class Node { public: Node *parent; // used during the search to record the parent of successor nodes Node *child; // used after the search for the application to view the search in reverse double g; // cost of this node + it's predecessors double h; // heuristic estimate of distance to goal double f; // sum of cumulative cost of predecessors and self and heuristic Node() : parent( 0 ), child( 0 ), g( 0.0f ), h( 0.0f ), f( 0.0f ) { } UserState m_UserState; }; // For sorting the heap the STL needs compare function that lets us compare // the f value of two nodes class HeapCompare_f { public: bool operator() ( const Node *x, const Node *y ) const { return x->f > y->f; } }; public: // methods // constructor just initialises private data AStarSearch( int MaxNodes = 1000 ) : m_AllocateNodeCount(0), m_FreeNodeCount(0), m_FixedSizeAllocator( MaxNodes ), m_State( SEARCH_STATE_NOT_INITIALISED ), m_CurrentSolutionNode( NULL ), m_CancelRequest( false ) { } // call at any time to cancel the search and free up all the memory void CancelSearch() { m_CancelRequest = true; } // Set Start and goal states void SetStartAndGoalStates( UserState &Start, UserState &Goal ) { m_CancelRequest = false; m_Start = AllocateNode(); m_Goal = AllocateNode(); m_Start->m_UserState = Start; m_Goal->m_UserState = Goal; m_State = SEARCH_STATE_SEARCHING; // Initialise the AStar specific parts of the Start Node // The user only needs fill out the state information m_Start->g = 0; m_Start->h = m_Start->m_UserState.GoalDistanceEstimate( m_Goal->m_UserState ); m_Start->f = m_Start->g + m_Start->h; m_Start->parent = 0; // Push the start node on the Open list m_OpenList.push_back( m_Start ); // heap now unsorted // Sort back element into heap push_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() ); // Initialise counter for search steps m_Steps = 0; } // Advances search one step unsigned int SearchStep() { // Firstly break if the user has not initialised the search assert( (m_State > SEARCH_STATE_NOT_INITIALISED) && (m_State < SEARCH_STATE_INVALID) ); // Next I want it to be safe to do a searchstep once the search has succeeded... if( (m_State == SEARCH_STATE_SUCCEEDED) || (m_State == SEARCH_STATE_FAILED) ) { return m_State; } // Failure is defined as emptying the open list as there is nothing left to // search... // New: Allow user abort if( m_OpenList.empty() || m_CancelRequest ) { FreeAllNodes(); m_State = SEARCH_STATE_FAILED; return m_State; } // Incremement step count m_Steps ++; // Pop the best node (the one with the lowest f) Node *n = m_OpenList.front(); // get pointer to the node pop_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() ); m_OpenList.pop_back(); // Check for the goal, once we pop that we're done if( n->m_UserState.IsGoal( m_Goal->m_UserState ) ) { // The user is going to use the Goal Node he passed in // so copy the parent pointer of n m_Goal->parent = n->parent; // A special case is that the goal was passed in as the start state // so handle that here if( n != m_Start ) { //delete n; FreeNode( n ); // set the child pointers in each node (except Goal which has no child) Node *nodeChild = m_Goal; Node *nodeParent = m_Goal->parent; do { nodeParent->child = nodeChild; nodeChild = nodeParent; nodeParent = nodeParent->parent; } while( nodeChild != m_Start ); // Start is always the first node by definition } // delete nodes that aren't needed for the solution FreeUnusedNodes(); m_State = SEARCH_STATE_SUCCEEDED; return m_State; } else // not goal { // We now need to generate the successors of this node // The user helps us to do this, and we keep the new nodes in // m_Successors ... m_Successors.clear(); // empty vector of successor nodes to n // User provides this functions and uses AddSuccessor to add each successor of // node 'n' to m_Successors bool ret = n->m_UserState.GetSuccessors( this, n->parent ? &n->parent->m_UserState : NULL ); if( !ret ) { typename vector< Node * >::iterator successor; // free the nodes that may previously have been added for( successor = m_Successors.begin(); successor != m_Successors.end(); successor ++ ) { FreeNode( (*successor) ); } m_Successors.clear(); // empty vector of successor nodes to n // free up everything else we allocated FreeAllNodes(); m_State = SEARCH_STATE_OUT_OF_MEMORY; return m_State; } // Now handle each successor to the current node ... for( typename vector< Node * >::iterator successor = m_Successors.begin(); successor != m_Successors.end(); successor ++ ) { // The g value for this successor ... double newg = n->g + n->m_UserState.GetCost( (*successor)->m_UserState ); // Now we need to find whether the node is on the open or closed lists // If it is but the node that is already on them is better (lower g) // then we can forget about this successor // First linear search of open list to find node typename vector< Node * >::iterator openlist_result; for( openlist_result = m_OpenList.begin(); openlist_result != m_OpenList.end(); openlist_result ++ ) { if( (*openlist_result)->m_UserState.IsSameState( (*successor)->m_UserState ) ) { break; } } if( openlist_result != m_OpenList.end() ) { // we found this state on open if( (*openlist_result)->g <= newg ) { FreeNode( (*successor) ); // the one on Open is cheaper than this one continue; } } typename vector< Node * >::iterator closedlist_result; for( closedlist_result = m_ClosedList.begin(); closedlist_result != m_ClosedList.end(); closedlist_result ++ ) { if( (*closedlist_result)->m_UserState.IsSameState( (*successor)->m_UserState ) ) { break; } } if( closedlist_result != m_ClosedList.end() ) { // we found this state on closed if( (*closedlist_result)->g <= newg ) { // the one on Closed is cheaper than this one FreeNode( (*successor) ); continue; } } // This node is the best node so far with this particular state // so lets keep it and set up its AStar specific data ... (*successor)->parent = n; (*successor)->g = newg; (*successor)->h = (*successor)->m_UserState.GoalDistanceEstimate( m_Goal->m_UserState ); (*successor)->f = (*successor)->g + (*successor)->h; // Remove successor from closed if it was on it if( closedlist_result != m_ClosedList.end() ) { // remove it from Closed FreeNode( (*closedlist_result) ); m_ClosedList.erase( closedlist_result ); } // Update old version of this node if( openlist_result != m_OpenList.end() ) { FreeNode( (*openlist_result) ); m_OpenList.erase( openlist_result ); // re-make the heap make_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() ); // make_heap rather than sort_heap is an essential bug fix // thanks to Mike Ryynanen for pointing this out and then explaining // it in detail. sort_heap called on an invalid heap does not work // sort_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() ); // assert( is_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() ) ); } // heap now unsorted m_OpenList.push_back( (*successor) ); // sort back element into heap push_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() ); } // push n onto Closed, as we have expanded it now m_ClosedList.push_back( n ); } // end else (not goal so expand) return m_State; // Succeeded bool is false at this point. } // User calls this to add a successor to a list of successors // when expanding the search frontier bool AddSuccessor( UserState &State ) { Node *node = AllocateNode(); if( node ) { node->m_UserState = State; m_Successors.push_back( node ); return true; } return false; } // Free the solution nodes // This is done to clean up all used Node memory when you are done with the // search void FreeSolutionNodes() { Node *n = m_Start; if( m_Start->child ) { do { Node *del = n; n = n->child; FreeNode( del ); del = NULL; } while( n != m_Goal ); FreeNode( n ); // Delete the goal } else { // if the start node is the solution we need to just delete the start and goal // nodes FreeNode( m_Start ); FreeNode( m_Goal ); } } // Functions for traversing the solution // Get start node UserState *GetSolutionStart() { m_CurrentSolutionNode = m_Start; if( m_Start ) { return &m_Start->m_UserState; } else { return NULL; } } // Get next node UserState *GetSolutionNext() { if( m_CurrentSolutionNode ) { if( m_CurrentSolutionNode->child ) { Node *child = m_CurrentSolutionNode->child; m_CurrentSolutionNode = m_CurrentSolutionNode->child; return &child->m_UserState; } } return NULL; } // Get end node UserState *GetSolutionEnd() { m_CurrentSolutionNode = m_Goal; if( m_Goal ) { return &m_Goal->m_UserState; } else { return NULL; } } // Step solution iterator backwards UserState *GetSolutionPrev() { if( m_CurrentSolutionNode ) { if( m_CurrentSolutionNode->parent ) { Node *parent = m_CurrentSolutionNode->parent; m_CurrentSolutionNode = m_CurrentSolutionNode->parent; return ... [truncated message content] |
