The pathfinding script suggested by MrGuest uses a point of visibility graph which isn't reasonable for most strategy games (but for other kind of games, of course). You rather want to use a dense pathfinding grid (basically a two-dimensional matrix).

There are many ways to improve the performance of a pathfinding algorithm:

- In the first place the source code should be of good quality. Try to avoid obvious shortcomings.
- Using appropriate data structures for e.g. the open and the closed list can also improve the speed.
- Use a pathfinding manager that spreads the pathfinding computations over several frames (or something like that).
- Use hierarchical pathfinding for large pathfinding graphs.
- Share computed paths among units.
- Flood fill approach suggested by Damocles: http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=313826#Post313826

If your game world is dynamic (ability to construct and destroy buildings, destructable environment and so on) precomputed paths won't help that much, I guess. Perhaps you could cache widely used paths instead, e.g. a path between the enemy's base and the player's base. Depending on the game, you could also experiment with ACO. This might give interesting results!

With a "floodfill" approach, ou have several advantages:

With the fllodfill I basically mean to generate a topographic map,
startin ftom the target position, where the target has the
lowest count, and all other reachable points in the map
are increasingly "uphill".
You basically fill the whole map, with the target at the
lowest point in the valley.
The pathfinding, does not pre-calculate a path:
its much simpler: the units just move to a neighboring
square that is lower than the current one (going downhill)

Its slower to generate, but it lets you have an unlimited number
of units use the same pathfinding-data to reach this target.
(when you have a group of 10 units, you only need 1
search, instead of 10 with a*)

Also: when something changes on the map, like a unit
blocking the way, you dont need another serach to find
an alternative way. The unit simply uses the next-best
lower-number neighbor.
It works very well, and it fast enough on current computers.

Another thing: you can advance the search to let units
avoid dangerous areas, such as enemy stationry defences.
You do that by adding "hight" value, around the peremiter
of the enemies turrets etc.
You unit will then walk on a path, that walks
around these areas.

-----

for an RTS, a node-based approach such as Intense Pathfinding makes little sense.
An RTS works best on a 2Dimensional gridbased pathfinding map.
(all Blizzard RTS, or the Age of Empires Series use that,
I actually dont know any pure RTS that uses something else)

Your "floodfill" approach has one disadvantage.
you have to store at least one value for each node.
Even for the shortest path you need a big graph ( who knows if there is a very high wall between the target or not )
And the more targets you have the more memory it consumes.

For Zombie games it would work out fine thousand of zombies are moving to the target
But for a RTS where are diffrent groups moving to diffrent targetsthe cost are much higher

Can you give some examples where your approach is implemented?


muffel

It works in a mobile phone RTS, so speed is not an issue.

Also you will not seach for many targets at the same time.
A player will usually click to one targetlocation.
And all units can use this search,

Pathfinding speed in general is not any speedissue anymore.
Only for programmers who dont know how to write efficient code.

Speed is more an issue of good algorithms rather than efficient code... or at least should be.

Cryptic code just for speeding up things should be avoided. Instead the algorithm should be rechecked. Maybe it wasn't done the most efficient way.

Thanks for all the input guys! I haven't been working on the project lately since Christmas has been passing through, but I'll get back to it soon.

Once the pathfinding is done, I want to add different methods of input for the game, including network players and perhaps computer opponents. Then, I will build a small game that uses the system I have built and release it as a demo of my skill. Perhaps someone else can then use the system to build an real game.

I'm back on the job and I have a few questions.

@Damocles: I understand what you're saying. A floodfill approach would work well in theory, but in my thinking I discovered a few problems with it that you could perhaps shed some light on.

1. Since I'm building an RTS, each unit needs to conduct itself independently and simultaneously of all the other units on the battlefield. However, this would require all of the units to have its own pathfinding graph, otherwise ordering one unit to move somewhere will cause all of the units on the field to move to that destination. But wouldn't this solution cause memory problems with big levels and lots of units?

2. Suppose I order a unit to attack another unit. The unit I ordered should intelligently follow the unit it is attacking until its victim is dead. But wouldn't this require me to constantly recalculate my pathfinding graph so that the unit can avoid obstacles intelligently?

EDIT: I've further contemplated these problems and come up with some other solutions. I would be happy if you could tell me whether they are worth my time, of tell me of something better.

1. To avoid the memory problems, I could keep a "queue" of orders in a linked list. When a player orders a unit, to say, move to a certain location, it adds this order to the "queue" and assigns a pointer to the unit ordered that points to his order on the queue. When the unit(s) have finished executing the order, the order is removed from the queue. This method will allow multiple units to share the same pathfinding information, while simultaneously making sure that only the units that are moving are provided graphs. I believe this would effectively defeat the memory problems, but do you think it would work?

2. I know no real solution for this problem, but I figure I can help defeat part of the problem by only recalculating the unit's graph every few seconds. He won't be moving fast anyway, and I doubt the enemy unit will be either... But in my mind, such a solution seems like it would be prone to failure. What do you think?

you generate a new Floodfillgrid for each new Pathfind request.
With a 100x100 grid Map each one will take only 20kb Memory.
You make a list of array of maps, and assign it to the units that want to use it.
None used can be freed.
For example: you have a list of arrays, with an id number.
Each unit has one id number stored, of the grid it uses
currently. If the unit needs a new target, it will receive a new id number
of a newly generated grid.



In most situations, they will not chase each other for long.
You can limit the recalculation of new coordinates to like
every 2 seconds.
You can of course also test if there is a direct path, and
only use a local short-distance follow routine.
(walking to the next square closest to the target)



In RTS like Starcraft, the player and AI-commander all use the
unitselection group logic.
The currently selected units share the same pathfinding destination,
and this the same "floodfill" grid. So you only need to generate one for each new targetsearch.




First realise the simple method (generate a new path
every time the destination changes)
if it affect the performace, make a timedelay for automatic searches.
If it still affects performance, use a direct-walk search.


Also: if the player clicks outsied of the map or on a non passable
area, you can make a floodfill seachrch, assuming the map
has no obstacles. This way the unit will at least walk
towards the clickpoint.
(or you just use a normal direct walk, without pathfinding)

Once again, thanks for the helpful reply. I can see we're on the same page here.

I'll start integrating these solutions to see how well they turn out.

Another question:

I need to be able to distribute pointers to my units so they can reference their respective graphs (which are structs of my own design) without manually searching the list. However, I can't use handle() to place pointer handles in the entities skills, because handle() only works for engine objects.

Does anybody know of any workarounds for this?