pathfinding, waypoints and built-in engine stuff

[casperjeff]

While I see that there is some sort of pathfinding/waypointing exposed in the engine for AI's to use, I am not sure how it works or how 'good' it is. Is it A*? BFS? Djikstra? Does it take into consideration buildings/factories? Map features (trees, etc) other than slope?
If I issue a simple 'move' command to a certain point, will it pathfind around high-slope areas (untraversable by the unit)?

Because I need my pathfinding to take into consideration 'expected' enemy locations and other characteristics, I am working on my own A* implementation.....but would like to know how the built-in stuff works to see if I can play off it in any way.

Any info would be appreciated.

[Kloot]

Is it A*?

yes (with some extensions)

Does it take into consideration buildings/factories?

yes

Map features (trees, etc) other than slope?

yes

If I issue a simple 'move' command to a certain point, will it pathfind around high-slope areas (untraversable by the unit)?

yes

[casperjeff]

wow...
sounds robust!! (although I do hear grumblings on some of the forums about the pathfinding in the engine...not sure what they are complaining about)

Any way to give 'hints' to it to avoid certain map locations when creating waypoints?

[Neddie]

If I recall, I may be wrong, but pathfollowing might be the issue behind most of the pathfinding problems, though that has been addressed of late. Also, recall that the terrain deforms and pathfinding has to compensate.

[Kloot]

Most of the complaints relate to pathfollowing (which can get messy), not -finding (which Just Works).

Any way to give 'hints' to it to avoid certain map locations when creating waypoints?

Nope, that's the main reason why many AI's include their own pathfinder.

[Tobi]

A bit more specific, it's indeed A* as Kloot said, with some approximations on top (to calculate rough path first, and detailed only when it becomes necessary.)

These approximations and some other speedups* make it non-complete and non-exact.

*the circular constraint

[casperjeff]

Thanks everyone....

I will continue with my own code but with a healthy respect for what is in place already!

:)

[AF]

It would be good if you could work on an AI generic C or C++ pathfinder, with the aim that all AI devs could sue it, and the eventual intention to lift it into the engine itself as a replacement.

[casperjeff]

"It would be good if you could work on an AI generic C or C++ pathfinder"

Well....my C development career ended some 10 years ago.....

But I will assuredly make my Java pathfinder logic generic enough that can be re-used by other AI's when/if it gets finished.

[casperjeff]

Can anyone enlighten me as to the issues that have been seen/had related to 'pathfollowing' in general?

[Kloot]

Just order some large groups of units around in areas with many obstacles and see what happens. (Short version: units can push each other into the physical space occupied by blocking objects and get stuck permanently.)

[hoijui]

This issue has come up quite a few times now already, and it seems like every AI dev does the same thing again from scratch, write his own path-finding-algo to include a thread map.
i agree we should have it in the engine/available through the interface, but i neither know the path finder in spring, nor have i done an AI yet.
First of all, what additional data would be required?
eg. is it just the thread map (representable through a float[] or int[] in some resolution, comparable to the metal or slope map)?

[casperjeff]

Each AI coder is going to keep track of 'threats' in his/her own way. Some will cheat and know globabl locations of every enemy unit. Some will use only unit and radar LOS data and produce 'probability' maps of enemy placements. Some will 'guess' based on resource locations and observed strategies.

And more to that point, pathfinding techniques will probably be just as unique. Units that are being sent on scouting or even raiding missions may NOT want to avoid enemy placements. Some will want units to 'stick to the high ground' while moving in order to get better angle of attacks on enemy units (and increase defilade of themselves).

MAYBE something generic enough could be coded up....but it seems to me that the pathfinding is the EASIEST part of the AI coding process. The hard part is overall strategy (including resource management). When to create units....what types...how many.....leveling 'up' technology....when to utilize air units....how to effectively use transport units (especially if battling a porched opponent)....etc etc etc.

And to that point, that is the FUN of seeing what other AI coders have come up with.

JMHO

[hoijui]

if i am not wrong, all your examples could be done with what i explained (supplying a thread-/avoidance-/guideance-/whatever-map to the pathfinder).
i though it is desireable to take away the boring work fro mthe AI devs, and let them concentrate on the interesting things. in addition, Java devs could possibly even profit from a speed boost.

[AF]

It is well known on these forums that the spring pathfinder is absolute sh*te in comparison to what it should be. Even its original author decries it as a tangled up mess.

The only advantage is the information it would provide which is currently missing. For example, upto date maps of what can be built where, and what can move where.

[hoijui]

yeah.. thats no argument against using the spring algorithm. if you can make a better one, i guess it would be easier even to put it right into the engine, as htere you surely have al hte info you need available, and no latency in getting it, plus everyone would profit then, as in: everyone playing spring plus every AI dev, compared to only one ai dev.

[AF]

Making a pathfinder yourself for your AI, is not of equal difficulty to building one and hoisting it into the engine. The requirements are far greater for the engine, and the environment is not as clear and pretty as it would be in an AI.

[Kloot]

It is well known on these forums that the spring pathfinder is absolute sh*te in comparison to what it should be.

[citation needed]

(afair K-man never expressed those kinds of sentiments either)

The engine PF doesn't need replacement; the one thing it could be said to lack is the ability to influence node weights, which is _only_ relevant for AI's and would still be of limited value compared to what an AI-specific pathfinder allows.

[AF]

k-man said it was not nice on the command engine forums