AI Pathfinding Suggestions to help the Devs fix the problems (Constructive please)

[Suranis 1]

Ok now that we know the Devs are working on the pathfinding, lets help them out with suggestions on how to improve it. And lets leave the complaining to other threads, ok? :)

Here are a couple of my own.

A) Have effectively 2 lanes of road for travel. Have say going up locked to the left and going down to the right. That will end the problem of 2 Walrus's Running into one another as they pass;

b) Make the edges of Bridges non waypointable terrain for the AI. That way they wont get stuck

c) Split up the Waypoints a little when you band select and send the walruses to the same point. This wil stup the walrus's getting tangles up on one another as much. What I mean is, create a seperate destination for each unit around the point where you click. Thats what I do in game anyway now, and should be very easy to implement.

Over to you guys!

[maddogx 13]

If AI get stuck, they should be able become aware of it and react accordingly - i.e. if a Walrus has not moved more than X meters (10?) from its last location within the last few seconds (10?), despite having a waypoint to go to, it should attempt to:

1. Detect the objects that are blocking it. (Collision detection.)

2. Create short term wayponts to navigate away from those objects (moving in reverse if necessary).

3. Once it is "free", temporarily flag the area where it got stuck as non-negotiable terrain.

4. Re-calculate the path to the original target and move on.

If the AI cannot get free, for example if they have been boxed in, it should signal the player. (Its icon could flash red, perhaps along with an audio warning.)

EDIT - addendum to point #3:

If the detected obstacle is a wreck (or any other destructable "junk" object), the AI could be made to react differently - for example by attempting to destroy it. Of course ammo will become a concern in this case, so the viability of this solution is debatable.

EDIT #2 - group awareness for Walruses:

If multiple Walruses are close together and ordered to move to the same location, they should not each try to calculate individual paths. Instead, they should calculate a single path and attempt to follow it in single file (keeping a sensible distance between each other, of course).

Bonus points if the strongest Walrus (heaviest armor / strongest weapon?) takes point. :D

Edited October 5, 2012 by MadDogX

[mikeap 0]

Bridges are a huge issues, and I've lost many a Walrus trying to have the AI cross them independently.

How about adding some barriers on the bridges? Whether it be visible or invisible for the AI.

[Tontow 1]

Formations: line adjacent and line abreast.

Or just a better follow mode - IE: If I drive along a path (train mode), then record and repeat the path for the other walrus (keeping them somewhat close together) so that they will actually keep up with me.

---------- Post added at 07:46 ---------- Previous post was at 07:43 ----------

And for Mantas, Linked formations.

IE: You set your flying formation and fly them as if they where one unit, linking the fire control to your manta as well.

[Bansheedragon 1]

When using assist, the walruses following me, tend to move slower than me or fall behind.

This means I have to stop every 50-100 meters to let them catch up or they get "lost".

Have the speed be the same as mine and have them follow at a reasonable distance, so as to not have them fall behind.

Bridges are a huge issues, and I've lost many a Walrus trying to have the AI cross them independently.

How about adding some barriers on the bridges? Whether it be visible or invisible for the AI.

I have had walruses following me not even try to cross a bridge when they come to it.

Instead of crossing the bridge, they try to go around.

Even if they are coming straight at the bridge, they can decide to go around it instead of over it.

Its as if they see the bridge as an obstacle and not a crossing point

I noticed this specifically on Thermopylae during campaign mode, when they were trying to cross a bridge.

They would come straight at the bridge, but as soon as they came to it, they would turn and go around and get stuck.

Edited October 5, 2012 by Bansheedragon

[ToxLaximus 1]

Skid steering to turn on the spot, or even steering like this ...

The front and back wheels turn opposite to each other giving a really tight turning circle.

EDIT: Yes I do have that lego model, and yes it does that stuff in the video :p

http://www.youtube.com/watch?feature=fvwp&NR=1&v=7vzOuz7DfwY

Edited October 5, 2012 by ToxLaximus

[Suranis 1]

When using assist, the walruses following me, tend to move slower than me or fall behind.

This means I have to stop every 50-100 meters to let them catch up or they get "lost".

Have the speed be the same as mine and have them follow at a reasonable distance, so as to not have them fall behind.

There's actually a good reason for that. If you watch them in strategic view, you will see that they don't go directly to a waypoint, but instead create mini waypoints to drive to as they progress. So they are continously speeding upand slowing down as they reach the mini waypoint. That's actually a really sophisticated way of doing it which allows them to weave their way through forests as I assume they are going to the area that's got the best driving factor... its just that they get caught up trying to get to the next mini waypoint, which may be behind them, or behind that rock, or behind another walrus or or or.

[sav112g 10]

Always had an interest in this from way back. Surly this was covered from early games I cant remember my Command and conquer path finding being poor and they had to work out the best way.

I understand it’s a very rich world they have created but it cant be too much to ask for a semi intelligent Ai. There should have been a basic learning algorithm put to work on every island or just on the map to continually run vehicles around and learn what works or what does not. Universities have been advancing Ai for years I just wish the Gaming industry sponsored or invested in some of there know how.

In saying that some games delight you in the fact your actually taken aback about how good enemy Ai players are.

I wish them every success in this but I’d say some of the RTS games must make huge calculations to imitate Ai when units clash on a massive scale. Half the fun in such games is just watching the Ai cope and play. I’d have thought in this day and age with the PC power we now have Ai should be a given. This so far reads as the Ai is dumb with enemy carriers not fighting or surprising ( and thats the beauty of Ai is should surprise you) Vehicles getting lost or stuck on lets face it uncomplicated maps.

[Bansheedragon 1]

There's actually a good reason for that. If you watch them in strategic view, you will see that they don't go directly to a waypoint, but instead create mini waypoints to drive to as they progress. So they are continously speeding upand slowing down as they reach the mini waypoint. That's actually a really sophisticated way of doing it which allows them to weave their way through forests as I assume they are going to the area that's got the best driving factor... its just that they get caught up trying to get to the next mini waypoint, which may be behind them, or behind that rock, or behind another walrus or or or.

I'm not talking about setting a waypoint for them.

I'm talking about when I tell them to follow me using assist

Why do they need to create waypoints when I tell them to follow me?

But that would explain why they drive like confused headless chickens.

Even when there is a straight line between me and the walrus in question I still see them try to drive off the road in some random direction.

[Scepticer 1]

Irritating as the AI might be when it gets stuck I hope they don't do any huge changes to it. I appreciate the fact that it doesn't cheat by going through objects or jump around, that it isn't restricted to just roads, etc. In many ways it is solid and good. It 'just' needs polishing.

[ToxLaximus 1]

Has anyone got the files from beta2?, those walrus were better.

[Drasta 10]

What about some command that will make AI copy your movement? This might help for going over bridges and increase speed of AI drivers. Just some simple follow command that will work just until you engage enemy or stop. I like the game so much but the AI is such a pain in the... heel.

And also is it really necessary to leave wreckage of destroyed vehicles in the game if the AI is not able to move around and exploding wreck can damage them?!

Edited October 6, 2012 by Drasta

[Thygrrr 1]

DEADLOCK is definitely a very broken island. The bridges, beaches and slopes are almost unnavigatable for Walruses.

There is a road triangle at the center of the island. The walruses try to avoid some invisible object on the road there it seems.

I think some of the islands simply have broken / suboptimal navspaces.

---------- Post added at 16:01 ---------- Previous post was at 14:38 ----------

Example of broken Deadlock (unmodded game) - http://i45.tinypic.com/264oynn.jpg (250 kB)

[Toumal 1]

Heya, I've taken a look at the script files and the general AI pathfinding. I've got extensive experience with pathfinding algorithms, and have implemented pathfinding in various mods and games. Some people may know me as "Werewolf", the author of Spoonbot for Tribes 1 and BotPilot for Tribes 2.

Basically, I saw no way to meaningfully improve pathfinding as part of a script mod, most of the relevant functions do not appear to be exposed to the script. Either that, or they're just not overridden and we don't know how to script them. The good news is that pathfinding is certainly fixable, and there are a few things BIS can do to greatly enhance the walrus AI:

1) Fix the broken islands

- As Thygrrr pointed out, some islands appear to have near-unusable pathing data. On other islands, there's quite an inconsistency of pathing data vs. actual walrus performance - sometimes the walrus can't climb a hill without missing its route waypoint, other times there's a downhill slope that is easily traversable but the pathing info marks it as no-go terrain. Obviously it makes a difference between a walrus traveling from A to B vs. the other way around if we're talking slopes, but this doesn't seem to be implemented. Top priority should be to get the pathing info right though, even if there will always be fringe cases where the AI will not go somewhere because it thinks it can't.

2) Improve waypoint positioning vs. turn radius

When the walrus needs to turn, the game adds additional route points to accomodate for this. Definitely a cool feature, but it always assumes a level ground. If this happens on a slope, the walrus will miss the waypoint.

There's an easy solution: Just cheat! Make the AI controlled walrus able to reach that waypoint under all circumstances. It's better to have the AI have a bit better vehicle performance instead of having a broken player experience.

3) Fix the Assist function

Assist is currently unusable because it makes the walrus try to directly follow the other vehicle. Instead, the game should chose a position right behind the followed vehicle as a navigation target and use waypoints to navigate, as usual. Only if our the assist target is *very* close it can use the direct route. Also, if direct route fails for any length of time, it should fall back to waypoint navigation again so these situations fix themselves.

4) Unit behavior after relinquishing control

Imagine you give a walrus an attack order, then take manual control to have it fight and eventually retreat - switching units will make that walrus attack again! That's very frustrating and very easy to fix: Once you took control of a unit, ALWAYS put it on hold after exiting. Don't assume that the old order is still valid.

5) Formation

There seems to be basic support for formation, but it is certainly not used for walruses. Not as high a priority as 1, 2 and 3, but certainly a good thing to improve.

6) Retreat

This is something I think we can probably improve via script - the units should switch to "chicken" status much sooner, especially when taking heavy damage. What can't be improved via script is enemy avoidance - ideally units should try to retreat someplace safe, preferably via a route that does not take them right through enemy lines.

I'm certain the first 4 items on this list would go a LONG way towards fixing the pathing issues. What do you think?

[ToxLaximus 1]

Is there a way to disable pathing and make the walrus go straight to the waypoint, using shift-clicks to make a route would be quicker.

[Dreadnought808 1]

Toumal, awesome post. Very informative. How did you figure out #1? Is it in fact as simple as a grid over the terrain, masking certain areas as inaccessible?

What's your thought on the short-distance waypoint calculation showing up BEHIND the moving unit?

[ToxLaximus 1]

Check this, it lifts its wheel up to turn on the spot, go to 1:30

[Toumal 1]

Toumal, awesome post. Very informative. How did you figure out #1? Is it in fact as simple as a grid over the terrain, masking certain areas as inaccessible?

Thanks for the praise ;)

I don't know for certain, but my guess is that there's a lot of pre-calculated waypoints that define where a walrus can drive and where it can't - these points are most likely precalculated because there's a db file with coordinates. The pathing algorithm, most likely Dijkstra, then finds the optimal path within that mesh of waypoints.

I think some islands have an incorrect waypoint database, and for some others it's just not optimally done.

In Spoonbot for Tribes I created the waypoints manually for each map. It took some time, and it made the AI a bit predictable, but it ensured that the bots got where they needed to be.

What's your thought on the short-distance waypoint calculation showing up BEHIND the moving unit?

I think that's a special piece of code that kicks in when the walrus misses a waypoint, or is reversing. Most of the time this works great, but I've also seen such extra waypoints being created way outside any sensible radius.

Oh and note that you do not see all the actual waypoints unless you zoom in quite a bit - the map actually skips rendering waypoints as you zoom out to make the route look less complex.

[Dreadnought808 1]

Aha. So if you're right, what they need to do is redo the pre-calculated waypoints for every map... and possibly either increase waypoint trigger size or tinker with the backing up code. Sounds like that'll take a while...

Tox, why would I skip to 1:30? The whole thing is funky.

[scorcher24 10]

Assist Function:

If the player is controlling the leading vehicle, he could lose some breadcrumbs that the AI just follows, that get deleted once all Walrus got past it.

Dunno if that is viable though.

[ToxLaximus 1]

Tox, why would I skip to 1:30? The whole thing is funky.

Anyone that makes a extra long walrus will know how to turn it :p