🔒 Locked

A FPS bot demo to play with and a question....

Started by Maleficus Jul 2, 2004 at 1:03 AM 18 replies 4k views

Original Post

Jul 2, 2004 at 1:03 AM

I've been working on it for a while now. Its an ALPHA state A.I. ATM, theres a LOT more work to do yet before I declare it BETA, but what I have so far is fairly workable, and a lot of fun too! Its for the game Return To Castle Wolfenstein, so if you don't have it, this news really isn't for you. :( http://fritzbot.bots-united.com I'm looking for opinions and feedback from fellow A.I. programmers. Its pathing is A* (which I've found to work quite well) and the load with 9-10 bots all using it at once as been quite manageable (tho I've had times where I've dropped into the low 30s in my frames). I wonder - what are some of the best ways you guys know to speed up the A* algorithm? Over ~12 bots, the load becomes too much and I can drop into the teens at times. There are only 150 or so nodes in the map I'm testing it on, so its not a problem of too large a search space (I think). I'm thinking of breaking up the pathfinding requests into a queue of some kind, but worry that some bots may wait to long to get their path and do something stupid in the meantime. [Edited by - Maleficus on July 2, 2004 1:19:30 AM]

fup

Jul 2, 2004 at 4:12 AM

With only 150 nodes, first, I'd question if it is the A* search that is the bottleneck.

If it is, then you can limit the number of search cycles undertaken by A* each update by spreading the load of each bot's search over several update-steps. While the bot is "waiting" you can simply make it seek (a steering behavior) toward the target. As it should only be doing this for a handful of updates it shouldn't look unnatural.

If A* isn't the bottle neck then you should examine each component of the AI and limit the number of times it updates. Very rarely will every part of the AI have to be updated each tick.

Hope this helps

[Edited by - fup on July 2, 2004 2:12:39 PM]

xEricx

Jul 2, 2004 at 6:20 AM

From what I can understand, you get performance issues when a few or all bots pathfind at the same time?

Having a pathfinding manager that receives requests from bots and queue them then executes them in order is the way to go in my opinion, at least that's what we do on the game I work on.

If there is a delay between your request and the solution to your pathfind, just let your character idle, it will most likely look as a reaction time, just like a human player has when he has to decide what he'll do.

Hope this helps

Eric

BrianL

Jul 2, 2004 at 10:21 AM

Erics suggestione is a good one good. The AI Wisdom books have several articles on path splicing, though some of the devs who used it now are saying that they would avoid it. I guess it introduced too many bugs; I haven't had a chance to ask for the reasons.

Do you have your bots call A* ever frame, or do they only call it when generating an initial path?

In any case, it definitely sounds like there may be an issue in your A* code. Searching such a small graph should be very fast. How are you storing the graph you build as you search? Are you doing allocations per node?

WilliamvanderSterren

Jul 2, 2004 at 4:09 PM

Maleficius, if there's a problem with your A* implementation, adding a queue mechanism to it won't solve that problem.

For your reference, an efficient A* implementation on a 1GHz processor and a small map should be capable of finding some 3,000 paths per second. To explain a drop in framerate from 30fps to 20fps with 10 bots, the pathfinding should consume 0.3s per 1s which corresponds to 1,000 paths or 100 paths per second per bot.

I can't imagine your bots needing to find more than 20 paths/s (*), in which case your A* implementation itself isn't efficient (pick one from the AI Wisdom books) or something else is consuming the CPU (ray casts?).

William

*: if they do, then note that you'll repeatedly search for the same path from the same location; a small per bot most recently used path cache of 1KB would dramatically speed up your pathfinding in that case.

Maleficus

Jul 3, 2004 at 4:35 AM

I calculate the path only once when its needed, and during that time, I calc the whole path from beginning to end. New paths may need to be calc'd later as needed (when the goal has changed, or the bot respawns).

I have an older PC (P3, 866, 128 RAM), which may be part of the problem.

The main lag is during the start of the game, when all of the bots will start grabbing for a path at once, so I figure thats a lot of it, but I think as well that the A* setup may not be too efficient.

It uses quite a few memsets, and while it doens't ray cast, it DOES calc the distances between nodes while it goes which is probably a Bad Thing(tm).

BrianL

Jul 3, 2004 at 12:05 PM

While you may be able to precalculate the distance, depending your representation, this shouldn't really be much overhead. If you have nodes, then it should just be a vector subtraction (which is trivial) or if you are using a mesh, it may be shorest distance between edges (which is still practical to calculate as needed).

To avoid the startup issue, many game spread the first update of the AIs out over the first 1/3 of a second. If you have your AIs update every frame, if you have AI events occur based on a frequency (ie update your sensors every tenth of a second), this may help.

Still, it definitely sounds like there is an issue in your A* implementation. If the code is short, do you think you could post it here? Someone may have time to at least glance at it for potential problems.

Maleficus

Jul 3, 2004 at 11:54 PM

This is the A* function. int from/to parameters is the num of the node. malbot_t *bs is a structure the bots use.

The Cost function is posted below the A* one....

int CreatePathAStar(malbot_t *bs, int from, int to) {      //all the data we have to hold...since we can't do dynamic allocation, has to be MAX_NODES      //we can probably lower this later - eg, the open list should never have more than at most a few dozen items on it    short int openlist[MAX_NODES+1];   //add 1 because it's a binary heap, and they don't use 0 - 1 is the first used index    float gcost[MAX_NODES];    int fcost[MAX_NODES];    char list[MAX_NODES];   //0 is neither, 1 is open, 2 is closed    short int parent[MAX_NODES];   short int pathlist[128];   short int numOpen = 0;    short int atNode, temp, newnode=-1;    qboolean found = qfalse;    int count = -1;    float gc;    int i, u, v, m;    vec3_t vec;   //clear out all the arrays    memset(openlist, 0, sizeof(short int)*(MAX_NODES+1));    memset(fcost, 0, sizeof(int)*MAX_NODES);    memset(list, 0, sizeof(char)*MAX_NODES);    memset(parent, 0, sizeof(short int)*MAX_NODES);    memset(gcost, -1, sizeof(float)*MAX_NODES);   //mal: make sure have valid data before precede!   if ((from == NODE_INVALID) || (to == NODE_INVALID) || 	   (from >= MAX_NODES) || (to >= MAX_NODES) || (from == to))	   return -1; //mal: no path!   openlist[1] = from;      //add the starting node to the open list    numOpen++;    gcost[from] = 0;      //its f and g costs are obviously 0    fcost[from] = 0;    while (1)    {       if (numOpen != 0)   //if there are still items in the open list       {          //pop the top item off of the list          atNode = openlist[1];             list[atNode] = 2;      //put the node on the closed list so we don't check it again          numOpen--;          openlist[1] = openlist[numOpen+1];   //move the last item in the list to the top position          v = 1;          //this while loop reorders the list so that the new lowest fcost is at the top again          while (1)          {             u = v;             if ((2*u+1) < numOpen)   //if both children exist             {                if (fcost[openlist] >= fcost[openlist[2*u]])                   v = 2*u;                if (fcost[openlist[v]] >= fcost[openlist[2*u+1]])                   v = 2*u+1;             }             else             {                if ((2*u) < numOpen)   //if only one child exists                {                   if (fcost[openlist] >= fcost[openlist[2*u]])                      v = 2*u;                }             }             if (u != v)      //if they're out of order, swap this item with its parent             {                temp = openlist;                openlist = openlist[v];                openlist[v] = temp;             }             else                break;          }          for (i = 0; i < nodes[atNode].numLinks; i++)   //loop through all the links for this node          {             newnode = nodes[atNode].links.target;                if (list[newnode] == 2)      //if this node is on the closed list, skip it                continue;             if (list[newnode] != 1)      //if this node is not already on the open list             {                openlist[++numOpen] = newnode;   //add the new node to the open list                list[newnode] = 1;                parent[newnode] = atNode;   //record the node's parent //mal: just in case we've happened to reach our goal node, exit this!			   if (newnode == to)				   break;               fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);   //store it's f cost value                //this loop re-orders the heap so that the lowest fcost is at the top                m = numOpen;                while (m != 1)   //while this item isn't at the top of the heap already                {                   if (fcost[openlist[m]] <= fcost[openlist[m/2]])   //if it has a lower fcost than its parent                   {                      temp = openlist[m/2];                      openlist[m/2] = openlist[m];                      openlist[m] = temp;            //swap them                      m /= 2;                   }                   else                      break;                }             }             else      //if this node is already on the open list             {                gc = gcost[atNode];                VectorSubtract(nodes[newnode].pos, nodes[atNode].pos, vec);                gc += VectorLength(vec);   //calculate what the gcost would be if we reached this node along the current path                if (gc < gcost[newnode])   //if the new gcost is less (ie, this path is shorter than what we had before)                {                   parent[newnode] = atNode;   //set the new parent for this node                   gcost[newnode] = gc;      //and the new g cost                   for (i = 1; i < numOpen; i++)   //loop through all the items on the open list                   {                      if (openlist == newnode)   //find this node in the list                      {                         //calculate the new fcost and store it                         fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);                         //reorder the list again, with the lowest fcost item on top                         m = i;                         while (m != 1)                         {                            if (fcost[openlist[m]] < fcost[openlist[m/2]])   //if the item has a lower fcost than it's parent                            {                               temp = openlist[m/2];                               openlist[m/2] = openlist[m];                               openlist[m] = temp;            //swap them                               m /= 2;                            }                            else                               break;                         }                         break;   //exit the 'for' loop because we already changed this node                      } //if                   } //for                } //if (gc < gcost[newnode])             } //if (list[newnode] != 1) --> else          } //for (loop through links)       } //if (numOpen != 0)       else       {          found = qfalse;      //there is no path between these nodes          break;       }       if (list[to] == 1)      //if the destination node is on the open list, we're done       {          found = qtrue;          break;       }    } //while (1)    if (found == qtrue)      //if we found a path    {       count = 0;       temp = to;       while (temp != from)   //travel along the path (backwards) until we reach the starting point       {          pathlist[count] = temp;      //add the node to the pathlist          count++;          temp = parent[temp];      //move to the parent of this node to continue the path       }       pathlist[count] = from;         //add the beginning node to the end of the pathlist       count++;    } //mal: copy the path over into the bots pathlist      memcpy(&bs->pathlist, pathlist, sizeof(bs->pathlist)); return count;   //return the number of nodes in the path, -1 if not found }

And here is the Cost function:

int GetFCost(int to, int num, int parentNum, float *gcost) {    float gc = 0;    float hc = 0;    vec3_t v;    if (gcost[num] == -1)    {       if (parentNum != -1)       {          gc = gcost[parentNum];          VectorSubtract(nodes[num].pos, nodes[parentNum].pos, v);          gc += VectorLength(v);       }       gcost[num] = gc;    }    else       gc = gcost[num];    VectorSubtract(nodes[to].pos, nodes[num].pos, v);    hc = VectorLength(v);    return (int)(gc + hc); }

strangebreed

Jul 4, 2004 at 1:33 AM

Good, you aren't using linked lists :-)

Your implementation is pretty tight. The one thing you're missing is the open search. There's no need to search for the lowest cost in your open nodes. Think about this way: You place every node on that list, and step through it and re-cost every node every iteration. If you keep track of the index of the best node then you can cut out the entire open list search :-)

BrianL

Jul 4, 2004 at 10:47 AM

I am guessing your list reorderings are what is killing the speed for you. If you have a profiler around, I would definitely try profilings to be sure.

As a test, instead of sorting your open list at any point, you may want to try simply doing a search for the cheapest element in the list when you are picking your 'best' node at the start of your loop. There are lots of other ways of doing this too, but just as a test to see if it is any faster, it would be the easiest.

If you are commited to performing the sort, I would suggest something other than a bubble sort.

Maybe someone else can take a look at this algorithm from a correctness point of view, as the implementations I have written a structured very differently. Here is a structure more similar to what I am use to seeing (I can't vouch for correctness, I just yanked it from: http://www.cs.ualberta.ca/~games/pathfind/libpathfind/0.1.0/doc/astar_8h-source.html)

00162         AStarSearch00163             s.g = 0 // s is the start node00164             s.h = GoalDistEstimate(s)00165             s.f = s.g + s.h00166             s.parent = null00167             push s on Open00168             while Open is not empty00169                 pop node n from Open // n has the lowest f00170                 if n is a goal node00171                     construct path00172                     return success00173                 for each successor n' of n00174                     newg = n.g + cost(n,n')00175                     if n' is in Open or Closed00176                        if n'.g <= newg skip00177                        remove n' from Open or Closed00178                     n'.parent = n00179                     n'.g = newg00180                     n'.h = GoalDistEstimate(n')00181                     n'.f = n'.g + n'.h00182                     push n' on Open00183                 push n onto Closed00184             return failure // if no path found00185         @endverbatim

There are a few differences between this and your implementation which are confusing me. In yours, you never update a closed node. This doesn't seem correct. Just because you explored a nodes neighbors doesn't mean that you found the shorest path to it. The closed list is just a way to keep track of nodes whose neighbors have already been explored.

[Edit: Posting in chunks, as something is wrong with my connection.

[Edited by - BrianL on July 4, 2004 11:47:12 AM]

Maleficus

Jul 5, 2004 at 4:03 AM

BrialL and strangebreed: could you show some code examples of what your talking about and what might work better?

Maleficus

Jul 6, 2004 at 12:44 AM

Hey Teamwhore!

I was wondering what happened to you guys - the forums just disappeared one day when I tried to log on and I never knew where you guys went until The Ghost told me last week.

Good to see you guys back in action. :)

Yea, I added a "waiting list" of sorts now - the bots will pop a request into the line, if there is one, and get their path when its their turn. by keeping the number of path calcs down to only 2-3 a frame, I'm keeping the frames really steady now, which helps.

I'm also wondering about another thing - dists between nodes are calc'd even tho the distances between connected nodes can/should be pre-calc'd and stored with the nodes themselves. I'm wondering if that could give a small, but useful boost in speed?

BrianL:

As for the closed list, I'm working on adding one, but the results I've gotten so far have actually made it SLOWER (tho I may be doing it wrong).

I'm new to A* too FYI. :)

TeamWhore

Jul 6, 2004 at 10:31 AM

It would speed it up (though I don't know if it would be noticable) to store the distances in the node links - wolfbot did that originally, I'm not really sure why I took it out... probably because it made the files smaller, and originally I didn't much care about the distances. But for all the kinds of pathfinding that I've been experimenting with, it would be helpful to have the distance already calculated, so it's probably a good idea to make your node files hold that info. At the very least, it won't hurt :)

I don't know what happened to the old forums - one day the entire host (which was a major web provider) just wasn't there anymore.

Much of the help I got when writing the function came from articles on this site, and most of the code for the binary heap too :P Looking at the following two links also shows why I don't really have a formal closed list - at least in this implementation, it hardly seems necessary. And the sort I use isn't a bubble sort, it's basically a modified quicksort to make use of a binary heap - so it's like a bubble sort, but only deals with a fraction of the list. The only other way I could think to do this would be to implement some kind of priority queue where insertions wouldn't require new sorting - this way the entire list would have to be sorted once, but no further sorts would ever be needed.

http://www.gamedev.net/reference/articles/article2003.asp
http://www.policyalmanac.org/games/binaryHeaps.htm

[Edited by - TeamWhore on July 6, 2004 10:31:54 AM]

Infuscare

Jul 6, 2004 at 1:49 PM

I'm no expert, heck I might even be a retard, who knows... but couldnt you have premade paths between commonly travelled to locations (or nodes, whatever you want to call it), and then only implement the A* when something that's moving, or not part of the map gets in the way...?

wouldnt that accelerate the pathfinding by a lot...?

...this is a legitimite question, btw, don't flame me!

TeamWhore

Jul 6, 2004 at 2:56 PM

Well I probably shouldn't have used the word 'nodes'...we basically already have those paths mapped out. What we have been calling 'nodes' are what might more properly be called 'waypoints'. The reason we need pathfinding is because there is more than one valid path from many of the nodes (eg, node A connects to node B, but node B connects to nodes A, C, D and E). So to get from node A to node Q, say, requires some kind of pathfinding. The A* isn't to find the path from node A to node B (which is generally supposed to be a straight line), but to find *which* nodes/node-paths to take to get from one node to some distant node. I don't know how well I'm explaining this...I can try to get a screenshot of some of the drawn paths and nodes to explain this better, if need be.

fup

Jul 6, 2004 at 5:56 PM

I think what Infuscare is trying to say is that it's possible, and probably desirable (for a static map and given that memory isn't a problem) to precalculate all the paths and store them in a look-up table.

TeamWhore

Jul 6, 2004 at 8:03 PM

ok, thanks for the clarification :)

The main reason I didn't go with a pathing table is memory - it probably wouldn't be an issue, I'm not really sure, but I've just been trying to keep the memory down to a minimum, since all this code is running on top of an already existing, fully-fledged game. It could be minimized a lot by not mapping *every* path, but only certain 'common' paths, as Infuscare said.

I don't know if this applies to Maleficus, but I'm also trying to implement sub-optimal pathing, so that there will be some variety to the paths the bots choose. The other problem is that while the maps themselves are static, the 'available' paths are not - often some of them are blocked or otherwise inacessible for part of the time, so the bots can't use those paths until they are open. With all the issues I just figured at-need pathfinding would actually be easier, provided it is quick (enough) and effective.

choffstein

Jul 8, 2004 at 10:58 AM

I just skimmed the question and answers, and didn't see anybody mention this sort of thing and thoughtof it might be a possible simple solution. Simply say that all bots have "X" amount of time per frame to do their logic. For example, we have 20 bots. Each bot gets 20/X to perform whatever they need to do. Bots that are furthest away from the player get less than that, giving more processing time to bots that are closer (because they need to think about more stuff, like attacking, and moving, etc).

When a bot runs out of time, you simply save its state, or where it is searching in the A* algorithm, and pick it up there next frame.

This would probably force framerate to be smooth, if you could figure out an easy way to implement it.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.