Hi,

I'm just doing some research for a project that I'm working on. To do that, I've build a little TD game that continuesly spawns enemies and allows the player to keep on placing turrets (so everything is realtime). I've done quite a bit of reading on the basics of A* and such both on this forum and places such as this. I get the basics and have written a class (based on said article) that returns the next step to the enemy. The class works pretty well but the problem is not one enemy. The problem is when I have 5,10 or more enemies. Every extra enemy severely slows down the game.

Currently I only call the next target from the A* class when the enemy enters a new grid coordinate but I've tried several other approaches as well such as only recalculating the path when a new obstacle is placed but that slows down placing obstacles.
I currently have a couple of linq elements in the class but I doubt that rewriting that will give me a fluid game with 50 - 100+ enemies. Currently the grid is roughly 50*30 points, which is not small but I don't want to make that smaller either.

I've been thinking about minimising the call the the A* class by using the same path for enemies that are on the same grid coordinate but theoretically that still wouldn't solve the problem (i.e. when all enemies are on a different position).

I've also been thinking about using arrays instead of lists but that could give problems. What if the number of steps is larger than the array? The only way that I could account for that is to make the array really big but that kind of nullifies the switch from list to array (?). Besides, that is more of a memory solution and this seems more of a processing problem (?).




Sooooo..... Any suggestions how a lot of enemies can use an independent A* routine without any serious slowdown?




My A* method:




EDIT: Needless to say that I've tried several of the suggestions of the article but none really got me anywhere near the numbers where I want to be.

I haven't thoroughly looked at your code since you say it works, just slowly. Off the top of my head, it seems like you are running the algorithm each time an enemy changes grid spots and only to get the next direction to move. Do you really need to do it for each grid transition, or can you instead change the algorithm to return a full path (e.g. a list of waypoints to the goal)? This would reduce the executions to once per enemy when they are spawned and once per enemy when a new object is placed. Since you have multiple enemies, you might want to consider running the algorithm in parallel (multithreading). Enemies generally don't need to know where each other is going, so there shouldn't be any issues there.

Alternately, you could calculate the pathfinding for each grid coordinate instead of for each enemy. Each grid coordinate would only need to know which grid enemies need to go to next, not the entire path. However, you would still need to update each grid whenever a new object is added.

I used a modified A* algorithm during the AI based DBP contest awhile back. While I never got to the point of needing to multithread, I had good performance in my game. I used a "hive mind" mentality of each bug having no knowledge of the grid to start with and looking for an exit in a sweeping pattern. Once an exit is found, the bugs find the best way to the exit using the accumulated knowledge of the map so far. Additionally, the traps in the game have to be overcome somehow, and this was added to the algorithm with some "hinting" mechanisms. Basically, if no direct path could be found, the algorithm would look for indirect paths, such as making a bug go back to an acid bath so it could walk through walls to get to the goal. The algorithm I used was only called when a new bug was generated (if no goal found, the bug would pathfind to the next grid in the search pattern, else it would pathfind to the goal), when a bug got to its search goal (if no goal found, pathfind to next search grid, else pathfind to goal) or if a bug encountered an obstacle in its path (if no goal found, pathfind to the next search grid, else pathfind to the goal). If you want to see it, you can download it here (Requires 2.0 framework though): http://squeebles.pouncingkitten.com

I don't mean to be harsh, but I think using A* for your problem is a very poor decision.

A* is used for path FINDING. Do your entities need to FIND paths? Not really. Its a TD, they go on predefined paths and shouldn't really ever deviate significantly from them.

Set up way points and use flocking algorithms, it will be significantly faster and will also look way smoother. Use the flocking sample provided on this website, and add a small attraction field at pre-determined distances (waypoints). Once an entity reaches a way point, switch its waypoint to the next.

This is what I do for my AI units that just travel in a straight line / path. It works marvelously.



Edit: If you do feel the need to use A*, understand that it is not an inherently robust algorithm and it is rarely if ever used to a void collisions between two dynamic entities. One optimization you could do is use A* only when the entity is spawned and save the nodes that it wants to travel on. Then use some flocking algorithm to keep the horde of units away from each other. But then again, this approach is exactly like the one I mentioned above, except you replace pre-programmed waypoints with A* generated waypoints.

Sorry I didn't reply any sooner, I run two companies and as you can imagine, there sometimes is little time for pet projects.

Chris Covington: I don't see another way to do it, obstructions can be added on the fly. So even if I where to give them a path, I would still need to recalculate every path element for every enemy when placing the said obstruction (alternately, I could recalculate when the enemy concludes that his path is outdated but that could give some weird results). That would still slow down the game.

Because I allow the player to add obstructions, it is very well possible that there are branches in the path or even multiple paths (depending on where the enemies are when the object is placed).

I've narrowed the entire problem down to the options list, there are just too many in there when obstructions are added that it needs to consider. If I could narrow down the list, it would massively speed up things.

andorov: Nothing better than a harsh teacher. :) Quite frankly, I'm a complete n00b on many things, especially AI. I've only started last month or so. But I do like to learn about it. Al the reading material pointed towards A* being a good starting point.

Thx for the pointer on flocking and such, I'm checking it out now!

Have you run this on the 360, and how does the speed compare on the two platforms?

I only glanced at the code; but I can tell where the problem is. Each creep having it's own path is *fine*, infact probably best (it prevents subtle problems; e.g. adding a turret in the path that a creep has already passed through). However, each one must cache it's current path; doing NxA* per frame is gonna be slow. The problem with that is the creep will walk through a block that has become occupied since it's path was built. You need to recaculate all affected paths (and ONLY those paths) whenever the player places a turret. I will demonstrate with what you have to do with some odd pseudo-code. The biggest bit is the INotifyPropertyChanged; Google it if you need to understand what it does (it's pretty self-documenting).

class Cell : INotifyPropertyChanged
{
  notify bool IsOpen;
  Cell Top;
  Cell Left;
  Cell Right;
  Cell Bottom;
  // Whatever else-not.
}

The critical part is the IsOpen property than notifies subscribers. So now let's look at the path class.

class Path
{
  PathNode NextNode;
  handler OneOfMyPathNodes_PathNodeInvalidated()
  {
    PathManager.Recalculate(this);
  }
}

The next logical step is the PathNode class.

class PathNode
{
  PathNode NextNode;
  event PathNodeInvalidated;
  Cell TargetCell;
  handler TargetCell_PropertyChanged()
  {
    if(PropertyName == "IsOpen" && !TargetCell.IsOpen)
    {
       PathNodeInvalidated();
    }
  }
}

So, the basic idea that only if the path becomes obstructed (a tower is placed there) do we updated the given path. Hopefully this gets you going in the right direction (and hopefully my wierd pseudocode makes sense).

I've recently finished doing some optimisation on my A* pathfinding in my current project. Whether this will be of any use to you, I don't know.

One thing you could try, is to queue the requests as well.

When a needs to update its route (as others have said, this should be less often than you are currently doing it). It could add a request to the queue. The A* engine then pulls these off the front.

The unit could continue (attempting) to follow its current route, until the new one is done. (I think I had some code that stiched routes together, but I am not sure if I went down that path).

Each update you could evaluate 1 route, so every unit would be guaranteed to be visited in under a second (if you had 60 units).


Going on from there.... Like others have said, I think I ended up splitting up the algorithm so it could just do part of a route finding in a single update, and then I went the whole hog, and got the route finding to occur on a dedicated thread.

If you can get your algorithm to the point where it can happily do 1 route in an update, you might be able to avoid going multithreaded.

J

You cannot just use List and hope to achieve the correct running speed. A* requires a priority queue, which is a datastructure with these three operations:

I have to say, I'm with andorov.  Waypoint navigation is a much more practical solution in the real world.  Points and paths can be calculated at design time, freeing up resources at run-time.

I tend to use dynamic checks on top of the path table to deal with with path to choose, to adapt to the minor changes in the environment (ie where enemies/objects are).

If you have little guys walking around the grid and they ned to move in a certain general direction but avoid obstacles, you could use a simple random based path approach.

Step 1: Identify the current grid
Step 2: Identify the acceptable grids for the next movement
Step 3: Pick on at random
Step 4: Check if there is an obstacle, if no, move if yes, pick another grid at random.
Step 5: If all acceptable grids are blocked, have a special case to get it unstuck, like haveing it follow the left edge for a few updates or something.


Might not be exactly what you're looking for, but it would run lightning fast. :)

Cheers for the pointers peeps, some really useful stuff in there, I'll dig through it once I have some more time. As it stands now, I've drastically optimised the code through a combination of some of the approach theories posted here and the use of heaps.
Had thought out an even better script (roughly 7 times faster than the one I'm using now) but that seemed to give me a very odd bug. If the creeper was on Y coordinate 0, I could place obstructions up and down the Y coordinate but for some reason the 5th obstruction down specifically refused to register (so the creeper went through the obstruction). Needles to say that I've been over that code a million times but the bug just made no sense. At the very least you would have expected it to happen to all directions or the first or last of a list somewhere.

Not really an issue though. I've tested the code as it is up to 256 creepers (can probably go way beyond that now) but the real game should only need 20 creepers (because that's not a TD game :) ).

PS: How do you reply to a thread without replying to a specific post?