Hi,

In a game I'm developing, I am hitting the stage where I need to implement pathfinding. I've been doing research on different methods of pathfinding, to see what would work best in my situation. However, most, if not all articles I found assume different game types with problems that aren't present in mine. I have a feeling I can get away with a fairly simple method of pathfinding, and don't need a lot of the overhead traditional pathfinding methods introduce.

This topic is intended to discuss theory, but taking in mind implementational details such as ease of implementation, and performance.

Description of the game/problem:
This game is essentially an RTS, rendered in 3D but with all the game logic in 2D. (I think this is called 2.5D?) Meaning, space ships, planets, etc. move over the X, Y-plane. Meshes are 3D and the camera is fully free in 3 dimensions. For pathfinding, I will thus be working in 2D.
The game takes place online only. The client application receives all the world, ship and other data from the server, and constructs the world out of it dynamically. The universe is divided into solar systems, and the player will only know about the solar systems near to him. So basically, there's no advance knowledge when the game is started, so I can't pre-fabricate navigation layers, waypoint graphs, or anything. It all needs to be done in real time.

Every object that needs to be taken into account will have an X,Y-position, and a radius (spherical collision). The player can click on a location in space with one or multiple units selected, in order to make the units move to that position. Thus, a unit will set a destination. The server will be notified and has to be able to figure out the path the unit is moving along to predict it's position at a given time, until the destination is reached. The first issue occurs here: Should the server be able to calculate the path the unit will take, or should this be done client-side only, after which the necessary data points are all sent to the server? The issue arises because the server has full knowledge of any (enemy) units that might get in the way of a path, yet the player might not know about these ships (and if that's the case, we don't want to take those ships into account because it would give the player information that it shouldn't have).

Stepping away from the client-server problem, the real issue why I created this topic is the pathfinding algorithm itself. I've studied AI for a few years, and I've read a number of pathfinding articles recently, but I feel most of the solutions are overkill or just not well suited, given the relative simplicity we can assume (spherical objects, relatively small amount of objects in the game world), and on the other hand the dynamic nature of the world and everything in it (everything moves, planets, units, and other entities). Most algorithms use waypoints (in the A* sense of the term) or a navigation layer, both of which I don't think are particularly suitable for this game. So I set everything I knew about pathfinding overboard and decided to see if I could design a system that made sense for this particular game.

What I've come up with
Not yet taking into account moving multiple units at once (which will introduce formations, taking into account different unit properties such as velocity and turn speed, and other variables that make matters more complicated), the problem seems easy. Given a position and a destination, just calculate the straight line between the two. Scan along this line for collisions, taking into account the radius of the ship that's moving and the radius of objects that are checked for collision. If a collision is detected, project the position (not taking into account radius) of the collider onto the traceline, create a waypoint there, and move the waypoint away from the collider's position just far enough so the moving unit can go around it. Check for the new line parts if no new collisions appear, and keep repeating until we've got a proper trajectory. Follow this trajectory (which could be sent to the server as a number of destinations, so the server doesn't have to do its own pathfinding).

A number of things aren't taken into account in this simple scenario. First of all, we don't have any predictive value. All that can be done is check if there's no obstacles in the way at the time when the path is calculated. Since all obstacles are dynamic, chances are that obstacles will appear down the line later on. This will be especially true when fleets are engaged in battle, where there could be as many as fifty-or-so ships flying around quite near eachother. So, I'd somehow have to construct a mapping that not only describes the position of a given unit, but also the time at which the unit is in the given position. In itself not a hard task, but scanning this list for collisions when creating a path from a to b might become complicated and slow if not done properly. At the very least I'll need to use some kind of hash mapping to make this feasible.

Second, when two objects are planning a path, and run into eachother at some point, we wouldn't want both objects to alter their route with the logic above, since their alterations will often make them run into eachother again. How will I determine which object derives from it's ideal path, or will they both do it? Will one object slow down to a stop to let the other pass? (Note that this is very costly in space, the ships will accelerate slowly and ideally always keep moving).

Third, objects like planets, although dynamic, should obviously never stray from their defined paths. A planet isn't moving fast, but in an ongoing world, there will be occassions when a planet is about to collide into a ship that's just sitting there, and the ship should see this collision coming and move out of the way autonomically.

Fourth, since units are not completely free in their movement (they can't slow down or get to full velocity instantly, nor can they turn an infinite amount in finite time), when additional waypoints are introduced, the whole trajectory of the unit will have to be smoothed out to make sure the unit can actually follow the path. This also introduced the fifth (and last I can think of) problem (more of a constraint): though a certain path may be the shortest possible, given the parameters of the unit it might still be non-optimal because it's too slow (if a unit has to come to a full stop five times, it will take much longer than when the unit can move over a path that is longer, but requires no slowing down at all). Ideally, the time it takes to complete the path is taken into account in the search for one.

This is where YOU come in
Given this problem description, I'm looking for either/both solutions to the described problems, or existing pathfinding algorithms that match the properties of this game as well as possible. Also I'm interested to see if you can come up with problems that I've overlooked, and need to take into account.

Thanks in advance for any help!

Your algorithm will produce very unpleasant results in some situations.

Suppose you have a C-shaped area of blockage (asteroids, space stations, other units, whatever) and a unit that needs to path from just outside the "gap" of the C around to the opposite side. Your method will have the unit take a path directly forward to the wall, then stop, follow along it, and wrap around to the gap before proceeding all the way back the long way around the outside. If the blockage is visible in the fog of war (i.e. is not "unknown" to the player) this will result in very ugly paths, especially if you use this algorithm for pathfinding around/through groups of units. The obviously correct solution is for the unit to go around the outside to begin with, and never get "sucked into" the C space.

To be sure, algorithms like A* are not well suited to highly dynamic environments; indeed the typical solution is to use A* for the terrain/building blockage (where buildings move rarely or not at all, e.g. in Starcraft) and a higher-level steering-based solution for unit avoidance. Starcraft II uses a constrained Delaunay triangulation of the map terrain and buildings to produce a navmesh; A* with a funnel filter is used to path along this mesh, taking into account unit radii; then local steering and collision avoidance layers are added on top of that, including a cooperative "push idle units out of the way" feature where it is possible to displace a unit instead of pathing around it in certain cases. Additionally, units moving in parallel are ignored for collision avoidance purposes since they can be guaranteed to not affect each other; this is a simple but effective optimization for getting large numbers of units to path cooperatively with relatively low CPU power.

SC2 uses six steering forces: following, flocking, grouping, separation, avoidance, and arrival. (I can happily provide a detailed explanation of each if you aren't familiar with standard steering parlance.) These provide plenty of control and intelligence while also allowing for some cool "emergent" effects like can be seen with Zergling swarms, for instance. I'd suggest looking at a similar approach for your game.

Depending on how common it is to have truly blocked areas (space stations, etc.) you may be able to jettison traditional pathfinding entirely and work off of a combination of influence maps and steering behaviours to get the results you want. Influence maps are a great way to generate "repulsive force" that helps guide units around areas of blockage. Again I'd be happy to dig into the concept in more depth if you're not familiar with it.

Once you've plotted your ideal route, put tags along the route into the oct/quad tree that you're using for things like culling. The tags know when the unit is expecting to be at that point.

Each of the tags "watches" bits of the routes. As you create objects and move them around inside the space, they can notify routes that they're blocking and unblocking them. The ship owning the route can decide if it's something it needs to think about now, or later. If the obstruction goes away later, then the ship need never have done anything.

The same thing can be used later on for sensor systems watching for intruders and so on.

When you plot a route, you can check for potential collisions a long way off; displacing your route if you find something else there, kicking them out if you think you should have priority.

Planetary orbits are collections of tags into the tree which know about the orbital period.

If something intervenes in the route and it's quite close, that's the trigger for doing a local replanning.

Solving the "who moves" is easy. Serial number every unit. Small units give way to large units. In case of a tie in sizes, highest serial number wins.

Thanks for your replies, they are very useful.

@ApochPiQ:
I have been researching some more and have indeed decided to go with steering mechanisms like flocking. I'm reading everything I can on this, and am implementing it. So far, I've only got cohesion working, which was very straight-forward. A (slightly) detailed explanation of the steering forces you mentioned would be of great help to me. So far, any papers I found on the techniques leave a lot to the imagination.

I also think the influence maps would be the best solution in this scenario. Truly blocked areas are uncommon, and the C-shape you mentioned is very unlikely to occur for any objects other than ships, which are already taken care of by the aforementioned steering mechanisms (at least for friendly units, I'm not sure yet how to react to enemy units, but to be honest I think it might be best to tackle this problem later).

I think I have an idea of how influence maps would work, but again I wouldn't mind you explaining the concept a bit.

I really like the reactive system, instead of using a predictive system that seems overkill. I'm going to have to see if it will be easy to implement this in the client-server architecture, to see how much work will need to be done on the server to achieve synchronization, but at least for offline purposes it seems to be exactly what I was intuitively looking for. Our game will use a fog of war system that will only take into account entities that are close to your own planets/ships, so going with a reactive system makes sense.

@Katie:
I've gotten some good ideas from your post as well. Right now it seems I'll be going in a direction where not everything you said will be applicable anymore, but there are some hints in your post that I find interesting, such as 'small' units giving way to bigger ones. I've also not thought of using my quadtree for keeping track of this info, which is something I will definetly keep in mind!

Influence maps are pretty simple, conceptually: you discretize your space into, say, a regular grid; then for each cell, you apply a score based on some function. Using a combination of a flood-fill algorithm and a decay function, you propagate influence out from "source" cells into neighboring areas. You can decay this based on distance, time, a non-linear curve, and so on to get various results. A visualization of your decay function and how it operates over space and time is very useful for debugging. Essentially, the idea is to represent various influences in a normalized (0-1) scale using this format; you can then combine various influences to get compound behaviours. For instance, you can assign a score to each cell that contains a blocking object, then propagate this influence outwards with a rapid decay; then do a simple linear combination with a second function which scores "hazardous areas" and decays more slowly. Then have your steering behaviours follow areas of the influence map which have minimal score, leading to basic avoidance.

Or you can set up a simple solution where each unit in a cell propagates some influence outwards, and the sum total of several units in the same cell produces a more widely-dispersed influence. This isn't too hard to do with a little bit of algebra. Once you have that, you can easily avoid stuff like the C-situation because the influence will "blur" a bit and push units away from the densely packed area. There may still be a moment of "oops!" depending on how pathological the shape of the C is, but it should in general act much better than a simple method based on linear sampling of the direct path.

The real power of influence maps comes with layering various functions; using a mix of additive and multiplicative blending, you can combine a whole host of influences to produce a pretty sophisticated map, and use a minimal algorithm for steering along the minima of the map to produce really pleasing results. For instance, you can have units "cower" behind other units (great for the old RPG ranged/tank combo) by combining the influence of the unit with a simple ray cast check to see what's visible to the target/"scary" position.

The real trick of influence maps is twofold: first, it takes a lot of tweaking of your basis functions to get good results, so as I mentioned earlier, a good visualization is key. This becomes especially important if you use functions besides addition/multiplication to blend multiple maps, which is often central to getting really great results. Secondly, you need to be careful about how finely grained your grid is. Too fine and you'll spend a lot of time on the propagation calculations, and too coarse and you'll get really chunk results. A configurable grid is best, so you can experiment on the fly (preferably at runtime without restarting the game) with different cell sizes.



Now, on to steering forces...

[color=#1C2837][size=2]Following is pretty simple: given a target T, simply try to reach T along the straight line route. If T is moving, do some simple projection of its direction to compute an intercept point. (Some would call this a separate "intercept" force, but it's all semantics at this point anyways.) Following is generally largely about orienting the unit more than getting it to a specific place; see arrival for more on that.
[color=#1C2837][size=2]

[color=#1C2837][size=2]Flocking is essentially straight out of the infamous Boids demo. Check it out if you're not familiar with it; in a nutshell, flocking is about moving a group of agents in a cohesive and non-colliding manner without doing a huge amount of nearest-neighbor checks and coordination.
[color=#1C2837][size=2]

[color=#1C2837][size=2]Grouping just involves taking a group of units and converging them onto a target point/area. This is contrary to flocking which tries to keep units separated to an extent; it's mainly useful if you want to have a lot of agents converge and then disperse, as air units do in Starcraft, for instance. Grouping is slightly different from following in that it doesn't necessarily expect an agent to end up in a given precise location; it's more about getting into the area with a number of other units. Grouping can be expensive because it requires computing a set of units as a, well, group instead of doing them individually, so it loses out on some parallelization/SIMD potential - but unless you're dealing with thousands of units this shouldn't become a huge deal.
[color=#1C2837][size=2]

[color=#1C2837][size=2]Separation is basically the opposite of grouping. It's all about getting units as far apart as they can, within some constrained space. Think of the old classic Pac Man ghost that always tries to run away from the player, except he's stuck within the maze. Unconstrained separation is pretty trivial (just negate a Follow force) but can get interesting when dealing with groups etc. More specifically, separation is useful when you want to disperse some units without getting them "lost" in random places; I think several RTS games have a generic "scatter" order which could potentially make use of this force. When operating on multiple units, the idea is to maximize the distance between each unit to some extent.
[color=#1C2837][size=2]

[color=#1C2837][size=2]Avoidance is probably the big beast. This is where your influence maps come in handy. Basically the idea is just to do some local search along the path cone and try not to bump into anything, while simultaneously not generating stupid paths. Be warned that if you aren't careful this can quickly decay into an unsolvable n-body problem, so use some cheats like moving units in a defined order/precedence to avoid the "hallway dance" where two units dodge back and forth trying to get past each other, and end up smacking head-on.
[color=#1C2837][size=2]

[color=#1C2837][size=2]Arrival is the final piece of the puzzle. It's basically the counterpart to the follow force. As you approach the target point T, you slow down and adjust your bearings to ensure you land on the right spot and/or in the right orientation. For most games the deceleration time is negligible so you can get away without too much of a genuine slow-down phase, but if you have inertia or gravity or other forces acting on your units, you might want to factor that in up front.
[color=#1C2837][size=2]

[color=#1C2837][size=2]

[color=#1C2837][size=2]

[color=#1C2837][size=2]Hope that clarifies some things!

For all things steering, go to [url="http://red3d.com/cwr/steer/"]Craig Reynolds[/url]' site (he's the "father of flocking").

@AIDaveMark: Thanks, I found the URL myself as well and was already studying it, but it's nice to mention it in this topic in case other people end up here.

@ApochPiQ: Thanks for the explanations. I've already implemented a few of these behaviours. I've implemented seek (=Follow with or without arrival, depending on if you are moving to a desired, static position or if you are chasing an enemy ship), and flocking (separation, alignment, cohesion). What is unclear to me is how Grouping and Separation are different from resp. cohesion and seperation as in flocking. From your explanation I can't really deduce if it's a separate type of behaviour, or the same thing (maybe with different parameters).

When you are talking about Grouping, you do mention a problem that I haven't solved yet: When I have multiple units selected and I make them move to a desired location, they don't end up in a relaxed state because flocking (or even basic collision response) prevents them from reaching the exact target location, so they keep moving toward it, trying to push eachother away (sorry, I love applying semantics to emergent behaviour).