Pathfinding in Supreme Commander 2

Hi! Thought this was interesting:
http://www.youtube.com/watch?v=udmL7EoJeWo&feature=channel

Just out of interest (not cause I am currently in need of it, but because I love programming such structures), anyone have any idea how they do this?

As the name of the video suggests, this could base on flow fields and direction maps.
Flow Field Following steering behavior: http://www.red3d.com/cwr/steer/FlowFollow.html
Direction maps for cooperative pathfinding: http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-031.pdf

Funny, I stumpled accross the second link as well, when googling.
This looks like lots of fun. I'm actually starting to think about if those flowcharts would make sense in a 3d-pathfinding simulation for my space-game for AI to avoid crashing into asteroids. I haven't found anything that was better-suited for 3d-pathfinding and collision avoidance yet...

Edit: Has anyone ever used flowchart pathfinding?
I was thinking: The example posted by you, Saturnus, has a fixed chart. Now, if I use such a chart around asteroids, to make sure they're avoided, then a spaceship can come from any direction towardas that asteroid. A flowchart would mean that I either have to adjust the flowchart every time a spaceship wants to fly around the asteroid (which defeats the purpose, then I don't need a flowchart and it'll also mess up any other space ships that are currently flying around the asteroid) or the ship will always go around the asteroid in the same direction...?
Any ideas on how I would compute the initial forcefield and how I'd change it, to have spaceships go around asteroids?

I've never used flow fields, so I don't know whether it would be tricky to implement them in a 3d space. The implementation shown in the video basically operates on a 2d plane, which probably is underachieving the environment of a 3d space game.

If I'm not mistaken, the flow direction around obstacles depends on the position and the movement direction (or destination) of the avoiding agent or group. So in my understanding, when you have multiple agents moving into random directions, each agent would possibly require its own flow field. This seems to be logical. By moving a group of agents, each agent could use the same flow field, what prabably makes this technique very efficient for controlling large numbers of units (in groups) in RTS games.

Well, I'm just guessing here and I really don't want to lead you astray. : )
But at a first glance those flow fields don't seem to be the best solution for your space game (unless there are large groups of space ships involved, of course).


Other collision and obstacle avoidance techniques might be an option for your game, too. In space you can benefit from the freedom of movement and (most propably) the absence of dead ends.

Have you already tried some other techniques whether they work for you?

I'm going for only single-ship-pathfinding, not large groups. You're right, that would make a huge difference in what kinds of pathfinding I could use.


I was first going to start with A*, but decided that wasn't the way to go, because of very large differences in the sizes of my ships (a large carrier vs a small fighter), where there'd be too many moving obstacles of varying sizes. So instead, I tried doing only obstacle avoidance. This was a pretty simple method:

-Trace from my position to the destination point.
-If something's in the way, then take the vector from the object's position to the target vector, add it to the targetvector (so now I have a position somewhere outside the round asteroid) and restart the process with that new point.
-Additionally, I had 4 (or 8) traces going out from the ship, towards top, bottom and the sides, checking if the ship was getting too close to any geometry there, and if it was, I rotated the velocity a little to get away from those objects.

This has its disatvantages though. For one thing, this only takes the obstacle's position into account, not its velocity (If the obstacle is a ship, then it could fly straight where I'm going. A human player would move out of the way, but then the bot-player wouldn't - cause the destination is straight ahead and there's nothing, yet, in the way - and they'd probably collide).

So I left that test alone and concentraded on multiplayer-code.
I also posted here about 2 years ago or so to see if anyone knew any good solution for 3d-pathfinding and obstacle avoidance, but didn't find any good solutions, if I remember correctly.

So, I did a little more thinking (this is all very basic, of course, I only had this idea yesterday and don't even know yet whether proper AI will make it into the game). This is the current Idea:
- I'm not going to use flowcharts as shown in the image, because I don't actually need them in empty space. Instead I'll have a "flowchart" that is only present around asteroids. At startup of the level each asteroids writes its position and the flow-nodes around it into the flowchart. This will be used for basic movement: when a ship reaches such a node it'll follow the flow around the asteroid.
- The second flowchart will be made by the moving objects. Relative to the ship, they will always stay the same.
- The resulting movement will be taking into account both the ship flowchart and the static flowchart.
- The advantage is that the flowcharts don't actually have to be changed.

I have no Idea if this will work. But it seems to make more sense than anything I've thought of so far. I have two basic problems (that I can think of atm):
- How do I represent a node in space? How can the ship know which node to follow? It can't constantly check all nodes in both fields and see how close it is to them...
- What happens when mutliple nodes "collide"? Meaning what happens when there's two contradicting nodes - one from the static and one from the dynamic field - at the same position?

Just brainstorming....
I think in this way this isn't so bad for single-entity-units (vs large groups). Maybe I shouldn't call it "flowchart" anymore though. More like "direction Nodes"...?
Any ideas on this method?

Personally I would tend to use a more straightforward approach.

You're right about your previous tracing technique ignoring the obstacles' velocities. But I can't see how your new idea would overcome this issue. The flow direction nodes (or how they might be called ; )) around the obstacles would only have a short range and they don't help by predicting future collisions.

The nodes could be stored in a 3d matrix. However, storing all the nodes in your space world would require a pretty huge matrix (depending on the dimensions of your world and the granularity of the flow field of course). This could be improved by moving a matrix of limited size with the player's ship all the time. Entities beyond this matrix won't be able to perform obstacle avoidance then, though.

I might be wrong, but I think that your brainstormed flow field implementation doesn't provide any vital information that we can't get without it. The flowing direction/information of the nodes can for example directly be derived from the obstacles' characteristics (velocity, movement direction and so on).


Perhaps you have ever seen Reynolds unaligned collision avoidance implementation?

This is an approach that takes the obstacles' velocities and future positions into consideration. It is checked, when two moving objects will have their closest approach. If the closest approach takes place in the future and ends up in a potential collision, the collsion threat will be avoided. The avoidance strategy can depend on several factors, e.g. the parallelism of the objects' velocity vectors (ger: bzw. wie sich die Objekte zueinander bewegen).

I did a steering behaviours implementation some time ago. The unaligned collisions avoidance part was never completetly finished, but if you would like to try something along these lines, feel free to ask.

I for one would try somethinglike that. : )

First of all, thanks for all the input! This will really help me a lot.

Interesting. In the unaligned collision avoidance description it says that he used containment steering behaviour http://www.red3d.com/cwr/steer/Containment.html for collision with the surrounding (the grey areas) which is exaclty the java app I was looking at when I made my original collision-avoidance.

Okay, the reason I was/am so fond of these flowchart-elements:

The top part of the image displays what this containment steering behaviour did for me.
I have many asteroids in clusters. In such a cluster, it can (and often does) happen that two asteroids are very close to each other. This is cool for multiplayer action, because loosing rockets and enemies is much more interesting, but it totally killed my collision avoidance. Here, this is what happend: The ship was on the left, and tried to get to the blue cross on the right. It "saw" the asteroid, and steered to avoid it. Once having avoided it, it steered back towards the cross. Ahead of it, there now lies another asteroid, but by using the normal like he did in the containment steering it just drives me deeper into the small area between the asteroids, out of which the ship doesn't get out any more and crahses (acceleration/decceleration aren't large enough to stop the ship in time and make it go around). A human player would see the second asteroid and go around that one too, before steering towards the cross again.
His app doesn't have any sharp concave areas, so he doesn't get that problem.

Lower part of the image: This is the reason I was thinking about using direction nodes, or flow chart like behaviour: If I somehow managed to precompute and place nodes around the asteroids which point into directions towards the next node, then I could make the ship follow these and avoid having to compute a useful path in realtime. That was my thinking here...

I was going to extend the flow direction nodes around each ship out infront of it, to make other ships try and "flow" over or below it. But I like this "unaligned collisions avoidance" and think I will use this instead. It should be much easier on the cpu, though of course also complicated to implement with rotation and movement in 3d space (why didn't I make a normal 2d-plane game instead? *sigh*). In the app, there's quite a few collisions, but then again there's much more entities than I'll be having in such a small area, with the playercount currently limited to 16 players.

So I can try to use the unaligned collision avoidance (it'll need quite some adaptation, because I also have ships of varying sizes) for the avoidance of collision with moving entities. But I'm still no further with the avoiding of asteroids...

Sorry, I was gonna make this post shorter, now it ended up being a monster-post again O.o...

Aah, I see! Obviously the asteroids in your game are static obstacles. Sorry, I missed that in the beginning and thought they were moving around, too.

I know the problem you've described in your rescent post. Most techniques only consider individual obstacles, but are not able to detect clusters that should be avoided as a whole. So an entity could be steered into a gap between two obstacles, even if there is not enough space between them.

An easy way to overcome this would be to always let an entity turn into the same direction as soon as an obstacle is found in front of it. This would be comparable with wall following behaviour. However, it will probably make the obstacle avoidance look less natural and intelligent. So presumably it's not an option for you.


Some mobile robots use vector field histograms for detecting obstacles around them. I don't really now whether this method could be utilized in a game environment, but an implementation could look like this:



The obstacles are projected onto the entities field of view (the black thingy). The FOV could be represented by an array. Each array index could be considered a sensor. By weighting and evaluating all sensors the most desired movement direction can be determinded. In theory at least. ; ) This method benefits from being able to handle clusters of obstacles.


A method I'm interested in for a while bases on projecting bounding boxes on a 2d plane. I'm not sure whether you could make any use of it, as it was designed to be used for moving entities on the ground. Basically you would project the asteroids' bounding boxes on an imaginary plane (as you don't have any floor to project on). You then would expand the bounding box projections by the hull radius of the avoiding entity. The overlapping projections form a graph. By following the most outer edges a path around an obstacle cluster can be found.



This technique can be used with arbitrary entity sizes. However, IMO its not that easy to implement. Probably something like a sweep line algorithm is required to handle all the line segment intersections in an acceptable time.

Ok, one last thing for today.
You've abandoned the A* algorithm because of the varying sizes of your space ships. However, you could use clearance based A* which takes account of entity sizes. Actually it's pretty simple:



This would also work in a 3d space of course. It should be noted, that the image above is only a simple example. Ships with a size value of 2 were not be able to fly through this cluster.


Well, no time left, sorry. : )

About the "flow field" video.

Ive use an approach like this in my old Wasteland RTS already.

Its basically just a way of unit-to-unit avoidance on low distances.
Its nothing "new". And not even part of pathfinding. But
part of dynamic close-range unitdynamics.
(its basically an additional avoidance vector added
to movement, calculated by the discance of two
collisioncircles, and defined by an exponetially growing
strength of the force the closer the units get)

Its also something you might not even want in an RTS.

Games like Age of Empires and Starcraft tried to be rigid on purpose.
(blocking the path of the enemy in a predictable manner)


BTW: if you have an RTS with hundrets of units, and want to
use a fast pathfinding, use something like a
"flood fill topography" map, starting at the
destination points.

If all units have the same destination, they can all use the
same Map to navigate, no matter where they stand right now.

This topic is getting more interesting by the day.

Damocles, this is basically what I was going to use the force field for, yes. The interesting part for me was how I could direction movement without having to make the ships check too much of their surroundings, and instead check if there's already a pre-suggested path they can follow around the object.

Saturnus, I like your first aproach (projecting onto the "field of view" and then deciding where to go from there) the most so far. Problem with this is that
a) I don't know the maths behind it, I'm just done with school and haven't studied maths (yet) and so my knowledge is somewhat limited there and
b) I don't see how it will find gaps between asteroids if they overlap. My approach here would be: project it onto the sphere and then see if there's "gaps" in the array and then fly through them. But if two asteroids overlap here (and so there's no gap in the array), I'd still need to check if there's a gap between them somehow... I'd have to do reading up on this one. Do you know what the method's called?

Actually, there were more reasons I had that kept me from using A*, I just didn't think of them when writing that post (last time I worked on this pathfinding must've been over 18 months ago) and I wanted to keep the post shorter.
- A* is based on a grid. This means I need to have a huge grid for my levels, because the smallest ships could be blocking only one cube. Also, it has to be 3d, so it would be quite a large field. Probably around 1000^3 cubes... which I find way too large.
- Also, I find A* works better (from what I understand) with static objects than with moving ones, since moving ones mean I have to recalculate the path so many times, or build in a good obstacle-avoidance which may mess up my path that I found completely.
That said I loved learning another new method for pathfinding. It's awesome, I would never have thought of filling the array with values like a minesweeper game. That's great!
Similar thing goes for the projection onto a 2d plane. It seems to be a great method, but my ships are supposed to go over or under the asteroid, if that's the shortest way. This would mean I'd need to project the scene onto an upright plane as well, which then again means that I'm back to 3 dimensions, and I think the purpose of this approach is to limit it to two.

Damocles, can you expand on your "flood fill topography"? I'm not making an RTS but I'm interested in all the possible approaches. And googling it didn't help me at all... found nothing useful there...


Some of the thinking I've been doing about this probably seems a little complicated considering most of the game's empty space. But I want to fill as many asteroids into the game as possible (it makes the game much more fun) and have them sitting very close together. So there'll probably be (and from gameplay-perspective: hopefully be) lots of complicated maneuvers. Also, I wanna do this right and not have an AI that's stupid sometimes. And even if it's over the top, I'd still like to gain the skills for more advanced pathfinding...

I use a "flood fill" pathfinding for my mobile RTS.
(where I need fast calculations, for many units)

Its a bit similar to A*, but it has no heuristics.

Here how it works:

I have a gridbased level, with passable and inpassable areas.
(works with node-based pathfinding too)

When the pathfinder receives the target position (x,y) for
the units to go, it creates a new topographic map.

This map starts from the taget position, and
checks all neighboring squares (up to 8).
Each passable square receives a value of how many steps
where taken to reach it (the first ones get a 1 naturally,
the one in the next iteration a 2)

Each square is marked, and put on a working list.

Now for each square on the list, check its neighboring passable
squares.
If the field was not visited before, or has a higher! stepcount,
overwrite it, and give it a stepcount of my-stepcount+1,
and put it on the following workinglist.

---

As long as there is a non-empty workinglist continue.

When no more squares get added, the algorythm is finished.
it should result in a topographic map, that fills the
whole playfield with a kind of "roll down" topography
at its passable squares.

Now, every unit on a passable square can easily determine
the next best square to got to, to get closer to the taget.

(just choose the suare with the lower stepcount from
the current square.
Its like letting a marble roll down-hill towards
the goal.)

-----

This way you can let hundrets of units find the path to
the target, doing just one pathfinding run.

And: even if they block each other, you can
let them find the way without a need to rerun the
flood-fill run.
(they raise the value of previously visited suares,
making them "higher")

Damocles, thank you for describing this pathfinding method. Actually I've never thought about something that, even though it's pretty straightforward.


You could do a search for "vector field histogram". However you'll most likely find articles about robotics then. I don't know whether or how it's used or called in game AI development.

The math behind it shouldn't be that complicated as it may seem at a first glance. I'm definitely not much of a mathematician, so I must know. : )

For projecting the obstacles (I assume a 2D world to make it more simple) I would treat each obstacle as a spherical bounding volume. I then would compute the two tangents to each bounding volume through the ship's center. The tangents define the light brown areas depicted in the image of my previous post. Depending on their angles, the tangents can be assigned to corresponding array indices. The distance to the obstacles can be stored in the array indices accordingly.

For your space game you would most probably want to add a third dimension to this method, of course. This could be a bit trickier, though, as simply computing two tangents for each obstacle wouldn't be sufficient anymore. Perhaps you could just project the bounding volumes onto a plane that is orthogonal to the ship's viewing direction instead. In order to find the most promising direction for avoidance you could (for example) rasterize the plane to get a two-dimensional array and then apply the clearance algorithm to it (as shown in the previous post). Just as an example. Perhaps this is too overkill or unnecessarily complicated. ; )

I'm not sure whether I understood your problem b) correctly. But maybe it was already addressed above?


To dwell a little bit on the potential field method that was already mentioned in this thread, you also could influence your ship's velocity by adding attracting and repulsing forces (which is probably very similar to your original idea?). Asteroids would naturally repulse all ships while nodes placed between the asteroids would attract them. However, a ship would only be attracted by a node whose range is at least as large as the ship itself.



Note, that these forces should only influence a ship's velocity. Nodes behind a ship can be ignored.
Presumably it requires some trial and error for tweaking the forces. It also requires a method for placing the attractor nodes properly (perhaps by placing a node between each pair of asteroids?). Each asteroid could store pointers to the adjacent nodes. So whenever a ship encounters an asteroid on its way, it could check whether it gets attracted by one of the nodes in the asteroid's node list.

Edit: Of course you could also connect each pair of nodes with line of sight to generate a small waypoint graph. Then you could go without the attracting/repulsion forces and a ship would never be steered into a dead end.