I'm working on a system for ships in "space" (2D like in Asteroids) to get from point A to point B while avoiding undesirable points C, D, and E in the interim. Except of course that some ships will find C, D, and E desirable because they're combat-seeking, et cetera. Basically you have neutral ships, who usually want to avoid any combat they can, and various military ships, who want to get involved in combat if their own ships are in that combat. Here's what I have so far; does it sound feasible? This system maps out the local grid by a series of weights (e.g. combat in one grid square makes the square undesirable). Because most ships will be either combat-avoidant or combat-seeking, I can actually make this grid shared for the most part and just flip behaviours. However, there will be some things that everyone wants to avoid, like hazards in hyperspace; additionally, the grid will need to maintain faction information (so military ships know if they care about a fight), so I will need multiple values per grid. Each object may have a field that indicate that it affects the grid. For example, any missile weapon would increase the "combat" field by some certain amount; ships that are currently hostile to other ships would increase it by more, and their faction value as well. The grid containing the object in question gets a large boost; adjacent grids get a smaller boost. By setting the grid size to be something reasonably large - say 256 pixels on a side - I can get a reasonable "avoidance range" without excessive grid updates. Objects that are simply dangerous instead of indicative of combat would affect a different value in the grid. Here I'm thinking primarily in terms of hyperspace, which will have more environmental influences than realspace. As far as how this applies to movement, each ship has a maximum weight that it is willing to pass through. It fires out a ray from its current location to its target destination, and if the ray passes through a grid with unacceptable weight, then it modifies the firing angle of the ray with a preference for continuing its current direction of motion (head-on movement, while unlikely, can be settled with a coin toss). It iterates this a few times (not remotely continuous; at the very least, there's only 72 frames most ships can face in because of their sprites), and heads along the ray that allows the ship to get closest to its target. One nice thing about this is that once it's running, I have a continuum from "cowardly" to "brave" simply by setting the maximum weight that a ship is willing to pass through. By setting ranges on the weights instead, I can create a "smart" combat-seeking behaviour, where ships are willing to help out their allies only so long as the combat zone isn't too hot. The big problem I have with this idea is that I've no idea how expensive it will be. If a solar system is, say, 8,192 pixels on a side, and the grid squares are 256 pixels each, then that's 1024 grid squares to keep updated on a regular basis. Additionally, there may be a lot of bullets and things flying around; having all of them regularly updating the grid could be expensive. Though, there I can probably just have each sprite only update on 1 out of every 10 frames that it's active (with something to keep the distribution even). Anything moving fast enough to pass through multiple grid squares in 10 frames is too fast to be worth considering for pathfinding. I also don't need to update each ship's destination every frame, which is some savings. But there's tradeoffs there; how much decreased reaction time can I accept in favor of improved game performance? Of course, it's possible that this won't be at all expensive, but I don't want to go about implementing it if it clearly will be. EDIT: I should note that in this game, ships will be allowed to fly "over" each other and in-system asteroids; however, fired shots and certain environmental effects affect anyone who touches them. A desire to avoid ships in combat is mainly because they are likely to be sources of bullets; ships have no need to avoid each other in peacetime.

When you fire off a ray from your ship, do you set off some pathfinding then aswell to se how good the shot is?

Given that there aren't any actual barriers in space, just regions to be avoided, I'm figuring that I don't need actual pathfinding; I just need a way to get to the target destination as quickly as possible without violating safety constraints. In empty space, this is just a straight line; if there's a combat on the line, then the ship should skirt the combat zone until it can fly straight to the destination, and so on.

A "good shot" is simply a shot that is minimally off-bore while still getting close to the destination. This can actually be determined programmatically - if the ray passes through a "blocked" square, then we just shunt the ray to the side until it doesn't pass through that square any more.

Edit: the assumption I'm making here is that most grid squares are not going to be blocked; thus, for the most part, ships will be flying straight to their destinations. I just want ships to react appropriately when squares they "want" to pass through are blocked. This is macro-level avoidance, really.

Quote: Original post by Derakon
Edit: the assumption I'm making here is that most grid squares are not going to be blocked; thus, for the most part, ships will be flying straight to their destinations. I just want ships to react appropriately when squares they "want" to pass through are blocked. This is macro-level avoidance, really.

From your assumptions and description of the problem, these 'obstacles' don't densely populate your game. Thus, it would be more efficient to use simple obstacle avoidance behaviours when encountered, than to try and plan for all possible obstacles in advance. Your obstacles are essentially spherical (or circular) regions of space that you want to dodge when you get close to them.

If you found that your space area was more densely populated with these regions, you would need to apply risk-based pathfinding techniques. There's plenty of research literature on this, particularly with regards to combat UAVs.

Cheers,

Timkin

Depending on your space partitioning, you could even do a really cheap test as to how close you getting to obstacles.

Just check the dot product from the vector ship->target and ship->enemy. Trying to widen that gives surprisingly good results.

Timkin - that's a basically accurate summation of the situation. What I'm not certain on right now is how to do that kind of analysis without performing O(n) comparisons (where n = #ships + #bullets) for every pathfinding ship. While I don't anticipate there being many "danger zones", I do anticipate having a lot of ships flying around (not necessarily hostile), and certainly there can be a lot of bullets in the air. I thought of the grid system as a way to abstract away the concept of "ships" and "bullets". It involves a lot more potentially costly bookkeeping, but the timeframe for finding a safe path becomes dependant on the length of the path instead of the number of ships.

It seems like if I don't use something like the grid system, then this generalizes nicely to "how do I find all of the objects near this object without iterating over all active objects?". I'm storing things in a quadtree, which works well for collision-detection pruning, but is less good for finding nearby things, since two objects may be close spatially and very far apart in the data structure. I can of course have a redundant data structure for spatially-related objects, but I haven't been able to think of a design that would achieve what I need, and I don't know what kinds of keywords to use to look up literature on the subject.

Edit: it occurs to me that the natural answer to that question is just to have an actual grid where each square holds pointers to all the objects in that square. Duh.

Well, if you can come up with a system in quickly detecting what's near, then that actually makes things alot easier. Personally, I'm the type of person who would rather NOT have any explicit pathfinding behavior in real space, unless absolutely needed. I'm a big proponent of using the rather dumb gradient method.

Just think of it this way, when you're walking down the street, trying to get where you're going, most of the time, you have a vague direction as to where you want to go. This is, of course, unless you know the exact route you want to take. Now, assuming you don't know the exact path, but just know a general direction. So, you'll go in hat direction while circling around any obstacles and detouring for something interesting. The same goes for your problem. Each ship knows the direction in which they need to go, what interests them, and what repels them. So, this lends itself perfectly to a gradient field. No pathfinding ahead of time, just some simple book keeping and the ships build their own paths along gradients satisfying their own little needs as they travel towards their goals. The path builds itself. Add a little randomness here and there and you'll get some very interesting behavior.

That's my take on it.

Well, how do you recognize an obstacle before you've collided with it? That requires knowing which objects are nearby, unless I'm horribly off-base. I suppose I could give ships an additional "large" circular collision-detection check...

WeirdoFu was basically describing the use of potential field methods for collision avoidance. This is not an improvement over distinct obstacle detection, but rather transforms the problem into one of maintaining potential field values on a fine grid overlaying your space. Objects emanate a field which either attracts or repels other objects in the game (so, for example, you can have attracting objects representing movement goals). Potential field methods are equivalent functionally to steering behaviours. They can also be viewed as a type of a message passing event system. Here though, messages are writting to the grid in the form of contributing terms in a potential equation and read by objects that pass through. In that vein, you could handle collision detection by having moving objects pass messages to fixed (invisible) 'tranceivers' in your space. Then, each moving object need only read messages from their neighbouring tranceivers to find out which other objects are close by.

Putting that aside, the issue of finding neighbouring objects via search is not that troublesome. You could use your quadtree and a range search over that tree, although there are easier methods. The simplest is to store the relative ordering of objects in each dimension in a linear array (one array per dimension). Then, you only need to check for collisions between objects that fall within the number of bins given by the displacement over the next time step. A potential collision will only occur between objects that fall within this range in all arrays. This is a poor mans range search, but only works well on easily discretised grids. For continuous domains, you're better off going with your tree. Range search on trees is a well known problem with documented solutions.

Cheers,

Timkin