AI speed, passability & pathfinding

[Jubalbarca]

Okay, one of the biggest problems at the moment for AI speed, I'm fairly sure, is passability. Units keep getting stuck trying to get to unreachable resources, in short, and this is by far the biggest drain on AI resources. Three things need to be done to fix this;

1. The AI needs to call the pathfinding script to determine nearest resources, as opposed to a distance check. Is there any way I can currently do this?

2. All maps need to be checked and double checked to ensure that there are no resources outside the playable area. Several maps currently have this problem, including the Badlands RMS; it's fairly important that we make sure maps are compatible with the AI as well as vice versa, I feel.

3. I need to be able to determine if an area is in an impassable region (aka wholly surrounded by cliffs that can't be got up, for example. The current AI mostly, as has been noted, works on finding vector distances. This often leads to it putting foundations up cliffs where the builders can't get to them. Ideas on this much appreciated.

These above account for well over 70% of AI speed issues. The battle finding script is probably another 20, but I can mostly deal with that in fairly simple ways I think.

[chaosislife]

I think part of the problem with resources outside the playable area is not being able to see them if they're there. Unless anyone knows a way to see past the edge of the map.

[Ykkrosh]

I think this is all related to the concept of terrain analysis - there's a vaguely useful overview in Game Programming Gems 3, and there's some details about Age games, though I'm not sure whether there's more articles elsewhere that are helpful. I'd expect we need it to automatically split the map up into smallish uniform regions, then compute which regions are reachable from each other (and an approximate distance), and also find regions representing forests and water and enemy towns etc, then the AI can use that region representation somehow to decide what's a good place to look for reachable resources and to realise when it needs to send ships to an island and to work out where to attack the enemy, etc. (Probably a fairly major design task, which is why the AI system doesn't attempt to support it yet )

[Pureon]

Could any of the computing be done before a match starts?

[Ykkrosh]

Yeah, most of it should be done once at the start of the game (probably during the loading screen, so it doesn't matter too much if it's a bit slow), then occasionally either recomputed or updated dynamically when the world changes (e.g. building walls or cutting down trees might affect the reachability of areas), and stored in some form which allows very quick runtime queries when the AI is deciding what to do.

[Sayyan]

Is there anywhere where the 0 A.D.pathfinding is well documented so I can get a good overview of the current implementation?

[Chakakhan]

Is there anywhere where the 0 A.D.pathfinding is well documented so I can get a good overview of the current implementation?

Heres a good post from Philip describing lots of thoughts about current and possible future implementation details: http://www.wildfiregames.com/forum/index.php?showtopic=13042&view=findpost&p=216739&hl=pathing&fromsearch=1

Here is one I wrote that give a top down view of it:

http://www.wildfiregames.com/forum/index.php?showtopic=14883&view=findpost&p=221439&hl=pathfinding&fromsearch=1

[Sylvain Gadrat]

Hello, I am a programmer and I spend a little of my spare time to play with 0.A.D's pathfinding logic.

I currently work on determining areas of homogeneous terrain tiles to speed up the long pathfinder. Such areas allow to not run A* on each tiles, but just looking at the ones necessary to go from an area to the other.

For the moment my code is not mature at all. Understand : hacky, buggy, don't respect coding styles and slow down performances. But if you are interested by such optimization/research, I can easily create a topic to give feedbacks about progresses. If you don't specially care I'll open a topic only when (and if) it really improve performances and get polished.

So, for the current topic, I just say that I am working on some area mapping. But it is not strategic areas nor currently usable at all.

Finally, to solve your AI problems. Isn't it sufficient to add (if not already exists) a pathfinder's API to get the long path cost of traveling from a point A to a point B with a unit class C ? Given A, B and C being parameters and long path cost the return. If so it seems not so hard to provide (but I can mistake, I'm not expert).

Edited July 27, 2011 by Sylvain Gadrat

[historic_bruno]

Hello, I am a programmer and I spend a little of my spare time to play with 0.A.D's pathfinding logic.

I currently work on determining areas of homogeneous terrain tiles to speed up the long pathfinder. Such areas allow to not run A* on each tiles, but just looking at the ones necessary to go from an area to the other.

For the moment my code is not mature at all. Understand : hacky, buggy, don't respect coding styles and slow down performances. But if you are interested by such optimization/research, I can easily create a topic to give feedbacks about progresses. If you don't specially care I'll open a topic only when (and if) it really improve performances and get polished.

So, for the current topic, I just say that I am working on some area mapping. But it is not strategic areas nor currently usable at all.

Finally, to solve your AI problems. Isn't it sufficient to add (if not already exists) a pathfinder's API to get the long path cost of traveling from a point A to a point B with a unit class C ? Given A, B and C being parameters and long path cost the return. If so it seems not so hard to provide (but I can mistake, I'm not expert).

We look forward to hearing more Also for very technical discussion and (sometimes) instant feedback, try joining our #0ad-dev IRC channel on QuakeNet.

[Chakakhan]

Hi Sylvain,

Sounds like interesting stuff. Looking forward to seeing how it is going. Please post updates regularly and join us in IRC.

Cheers!