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...