The game I'm making isn't an RTS, but there are lots of people needing to find their way to a place, while avoiding any obstacles.

I have a grid of 128*128 nodes, perhaps more if I can optimise enough. I'm using the A* algorithm to move my people around, and they are constantly moving. When a person decides they want to go somewhere, they set their destination variable, and add their index to a list. A seperate thread is looping in the background. It checks the list and removes the first index. It uses the index to read the position and destination of said person. It calculates the path and puts it into the person's waypoint list and then continues to the next iteration. The person then has its path and removes each waypoint when reached, ending up at the destination.

The problem is, if my people don't calculate their paths quickly, the game lags a bit, looks bad, and the people actually die, as they really need to get to their destination. Basically I want to know how to fix this. I have seen games such as Stronghold send over a hundred units on their way on a huge grid without stopping to think. How do these games manage it? And how should I deal with it?

Thanks for any help,
Frozenwounds.

First optimization is ofcourse to check your algorithm for easy speed gains:

-Any looping of nodes inside the main loop is costly, and should really be avoided. Dont store closed/open lists as actual lists.

-If path doesnt always have to be optimal, you can cheat a little by finishing the search when destination is found - not when its marked closed.

-Limit search for example to 500-1000 nodes, after which tell the character go to node with smallest estimated distance to goal found and calculate another path when he gets there.

u551:

First optimization is ofcourse to check your algorithm for easy speed gains:
-Any looping of nodes inside the main loop is costly, and should really be avoided. Dont store closed/open lists as actual lists.

What else would I do? I've implemented a binary heap, but using Lists underneath it all for the open list, but I don't see how this would make a difference with the closed list?
And thanks, I might implement the 'cheating' method. I don't know about limiting the search though, there are situations when that would make the search unsolvable.

Ive usually set closedness as a boolean attribute of node rather than have list of closed nodes and then just check if (node.closed).

And you think that would be faster than just querying the list?
I suppose the Contains method would have to loop through the list itself?

You also want to optimize at a higher level. 16,000 nodes is *a lot*, even on a desktop CPU (and on the Xbox, it will absolutely crawl).

You probably want to split your playing field into sectors, where each sector might be 10x10 cells, and then build a separate connectedness graph of sectors to sectors. Within each sector, build a graph of paths from inputs to outputs. Both of those are easy to pre-calculate -- in fact, you can use Dijkstra to pre-calculate the entire sector/sector and cell input/output path finding solutions.

Then, when path finding, you want to run four find passes:
1) Pathfind from the sector you're in, to the sector the target is in. If both are in the same sector, just pathfind from source to target, and you're done.
2) Pathfind from source to the exit of the sector it's in leading to the next sector in the higher-level path.
3) When entering a new sector, set the local path to the (pre-calculated) path that takes you from entry to the next cell you want to go to.
4) When entering the sector that contains the target, pathfind from the entry node to the target node.

This has several benefits:

a) You pre-calculate the vast majority of paths, spending no time path finding while on the "cell to cell" network.
b) The local path-finding that you actually do is much shorter, as it's only within a single sector, rather than potentially spreading to the entire game board.
c) The state stored per entity is actually less, as you only need to store the high-level path (sector-to-sector), plus a short local path within the current sector.

Frozenwounds:

And you think that would be faster than just querying the list?
I suppose the Contains method would have to loop through the list itself?

I suppose so too. MSDN states its O(n) operation where n is the length of the list, and it tends to get somewhat large towards the end of the calculation. Single boolean comparison on the other hand takes virtually no time.

@u551
Thanks, I'll do that.

@JWatte
Ouch! This will take me a while to implement but I see your logic. Also, surely the instance would have to calculate two paths itself, the one to the next 'big' node, but no the one in its own sector as this could result in doubling back. Then it should calculate from the second last big node to the finishing point. This would make sure there was very little going back on itself. I'll post back if/when I eventually implement this method.

Because each sector (big node) has a finite set of entry points and exit points, each sector could store the result of pre-calculating the path finding from each entry to each exit. That way, each unit don't have to calculate that, once entering a sector. The only two paths needed are from the current position to the next "big node," and from entering the final "big node" to the actual position within that node. The rest is taken care of by the navigation system pre-calculation. Also, note the special case: when source and destination is in the same big node, you just calculate a single path, from src to dst, but within a single sector.

Also, you don't want to calculate the final path segment up front, if it's possible that the unit can die before getting there. That's why you should keep only a local path for the current sector in each unit.

Take a look at BRAINS which has part of what JWatte describes

jwatte:

Because each sector (big node) has a finite set of entry points and exit points, each sector could store the result of pre-calculating the path finding from each entry to each exit. That way, each unit don't have to calculate that, once entering a sector. The only two paths needed are from the current position to the next "big node," and from entering the final "big node" to the actual position within that node. The rest is taken care of by the navigation system pre-calculation. Also, note the special case: when source and destination is in the same big node, you just calculate a single path, from src to dst, but within a single sector.

Also, you don't want to calculate the final path segment up front, if it's possible that the unit can die before getting there. That's why you should keep only a local path for the current sector in each unit.

What I've done is calculate paths from/to the center of each sector, the method using every entry point won't work for me, as the loading time is already atrocious. I might double the distance between nodes (half the grid width and height) to ease off a bit on the pathfinding, depending on whether this works with my graphics. I still don't seem to be achieving as much as other games however, such as Stronghold which I mentioned before. Has anybody played that game? Most of the routes my people have to figure out are short anyway, so it's actually quite rare for the sectors to be used.

the loading time is already atrocious

If level are designed (rather than random), you can pathfind at compile time rather than load time.

jwatte:

the loading time is already atrocious

If level are designed (rather than random), you can pathfind at compile time rather than load time.

Unfortunately they're wonderfully generated. Anyway this still doesn't seem to be working. I did consider the option of saving every path calculated so that one path wouldn't be calculated more than once, however some paths would have to be deleted as the map changed, and would this end up a major memory drain? It would obviously take a while for the saved paths to encompass much. But the up side is that they do encompass paths from anywhere in their list to anywhere else on their list, so they would contain more than one path. I would probably have to create some imaginitive class to store all that information however.

Wow I can really rant sometimes.

Edit:
A float is 4 byes, *2 for a Vector2, so a path with 128 steps would take up a kilobyte. With 512mb RAM in an Xbox, I think a couple of megabytes of paths would be fine? Also, I could create my own class with a number smaller than a float, this would cut down on the memory needed. I would realistically only need one byte to store a coordinate number of the grids I'll be using.

Frozenwounds:

the loading time is already atrocious

Hmm... In case every 10x10 node sector had all the sides open, roughly 40*40 pathfindings would have to be done per sector, you would end up with like bit over 200k calculations, which should be pretty much superfast considering the size of the areas. So it shouldnt be more than a couple of seconds +loading time, maximum? Could we see some of your pathfinding code please?

Frozenwounds:

A float is 4 byes, *2 for a Vector2, so a path with 128 steps would take up a kilobyte. With 512mb RAM in an Xbox, I think a couple of megabytes of paths would be fine? Also, I could create my own class with a number smaller than a float, this would cut down on the memory needed. I would realistically only need one byte to store a coordinate number of the grids I'll be using.

For path from every node to every node youd need (128*128)^2 paths (again, if all areas were open). And supposing one path is on average a kilobyte, the storage would take up almost 270Gb of memory... (woah, did i really calculate this right?)

u551:

For path from every node to every node youd need (128*128)^2 paths (again, if all areas were open). And supposing one path is on average a kilobyte, the storage would take up almost 270Gb of memory... (woah, did i really calculate this right?)

Not quite. I wouldn't be saving every possible path, just the ones that an instance had asked for. One path could actually encompass several too, for instance I save a path from point A to B to C to D. When an instance wants a path from D to B it would search through the archive of paths for a path that contained both D and B, and come up with the aforementioned path. It would then clip the ends and reverse the path if necessary. Also, you have a valid point, I would have to make sure that I set a reasonable limit on the memory that can be taken up. There would be other mechanisms with this too, such as when a new, longer path is calculated, if it contains one of the paths from the archive, it would overwrite that one rather than add a new one.

Also this idea of saving every entrance to every sector, just doesn't seem right to me, I'm not sure how I would program anything to make use of this. The idea of using the centre of each one to try to compute a mostly pre-calculated path works for me, but I'm struggling with the concept of why I would want to figure out all the edges.

I would post some code, but there's so much abstraction that it would probably make no sense without a huge page. Basically if the destination isn't in the same sector, it figures out a path through the sectors, then adds all of the saved paths between the sectors together, and adds a path from the start position to the second sector node, and from the second last sector node to the destination. Second first and last to prevent the instance from travelling to the centre of the sector it's in before heading out to the second because this could cause it to retrace its steps.

You don't have to precalculate every exit->exit on sectors if that doesnt seem right to you, but the multilayered pathfinding can be used in some way regardless, like i see you've done already.

So how fast is it working now?

Speaking of huge code citations here's a crude pathfinder class i wrote a while ago for a zombie game, it doesnt use any very fancy optimizations but still works without noticeable fps hit even with hundreds of enemies. Probably is of no help now but anyways...

Hey thanks for the help. I think I've got the A* about as optimised as it's gonna get. The thing with saving previously calculated paths works really well, I made a little counter to see how many times something used a previously calculated path, and you'd be surprised, it racks up a few hundred in a couple of minutes, and that's with only 12-16 people wandering about. I think my next hurdle will be the graphics, as each person has their own model to draw. The speed of the pathfinding actually takes a noticable hit as you have more people, and not just because more paths are calculated. Thanks again, I'll mark the topic as solved. :)

You don't need to save a Vector2 for each step of a pathfind. Just save the direction you need to move in from each step. This can easily be stored in a byte. (If you're really gung-ho, you can store 4 steps in a single byte, if you only allow N/E/W/S movement, even :-)

That wouldn't work with the saved paths though. :\
Good idea if it wasn't for that method. :)

Edit:

Also, next problem: http://forums.xna.com/forums/p/41791/246739.aspx#246739 ;)

That wouldn't work with the saved paths though. :\

As long as you know where you start for each path, it will work. You can calculate the next position by adding/subtracting the tile size from the previous step.