# zaloo

Member

6

119 Neutral

• Rank
Newbie
1. ## Dynamic Obstacle Avoidance and Flocking

Your approach seems nice, but much less efficient than the ClearPath approach. I assume that in high density situations, your obstacle avoidance produces many "collisions" that have to be handled, which can be quite expensive. If you look at the ClearPath algorithm, there is a incredibly low number of collisions. In every simulation in the video on the page linked, there are 0 collisions, even in situations where there are >1000 units that are densely packed. I found a paper just 5 minutes after posting this that might be of use: http://homepages.dcc.ufmg.br/~chaimo/public/DARS2012.pdf . I haven't read it yet, but from the abstract it seems promising.
2. ## Dynamic Obstacle Avoidance and Flocking

I'm working on an RTS and I've implemented a pathfinding approach that creates sub goals for units to reach, each of which should be able to be reached by steering forces alone. I've now implemented flocking and am about to start implementing obstacle avoidance (for dynamic obstacles), but I'm having trouble figuring out how to combine the two. I've found a paper that describes an obstacle avoidance algorithm using steering (the algorithm is called ClearPath and can be found here: http://gamma.cs.unc.edu/CA/). The naive way to combine these steering forces (seek for the destination, flocking, and obstacle avoidance) is to find your initial velocity using seek, then add the flocking forces. Finally you use this velocity to calculate your obstacle avoidance steering force using an algorithm of your choice (ClearPath in this situation). My question is that is this a good way to implement steering? It seems tough to make any strong guarentees when you just add various steering forces together. I'm also concerned with problems with choke points in the future, I don't my units to get stuck in bottlenecks. This solution obviously doesn't take that into account, and if there is some implementation that does, I'd rather use that.   If you know any research papers that deal with these issues, I'd appreciate links!
3. ## Using flocking to avoid non-circular obstacles in an RTS setting

Not to sound rude, but *you* are worried about flocking forces pushing agents into obstacles, *you* admit that getting guarantees from flocking algorithms is quite impractical, and *you* think that your method isn't good enough. Applying A* to a graph of moving obstacles is simply the most straightforward way to avoid collisions with obstacles reliably; if you cannot accept collisions with obstacles, the use of flocking-like heuristics needs to be restricted to choosing movement destinations (e.g. surrounded agents want to go to the centroid of their designated neighbours) because they cannot be allowed to move agents directly. Regarding object and obstacle shapes, you can generalize from point-point distances (two circles) to point-polygon distances (circle and polygon) and if needed to polygon-polygon distances. Polygons can be assumed to be convex (after decomposing concave ones appropriately).     Sorry if I came across as sounding asshole-ish but that was not my intention! It seems like you're a bit annoyed at me lol, sorry! When you said "A* with mobile obstacles added to the navigation graph", what did you mean? Having the navigation graph account for mobile obstacles by (for my example I'm using triangular meshes) creating additional meshes? Or did you mean something else?   Also when I said that A* determined my subgoals/waypoints, I didn't mean that it determines exactly where it goes. A* will determine a waypoint destination, but the conditions for the object arriving at the waypoint are not "I am at point (x,y)". The conditions are more like finding if the agent is within some radius of the waypoint (I'm not sure if this is the best way to do it yet, I'm still working on arrival behaviors haha).    Finally, could you link some example for the obstacle avoidance for point-polygon if you don't mind? On the Reynolds webpage there isn't any method for dealing with point-polygon that I could easily find. Thanks a bunch!
4. ## Using flocking to avoid non-circular obstacles in an RTS setting

That's the problem: you should do the opposite. Choose goals with heuristics about nice places to be at (e.g. uniformly dispersed units in open spaces), and reach the goals with an algorithm that guarantees obstacle avoidance (A* with mobile obstacles added to the navigation graph). If A* is expensive, you can "cheat" by not recomputing the whole path and giving up optimality: when an obstacle appears between intermediate waypoints A and B, you can recompute (every turn) a shortest path through moving obstacles from the current position to B (in most practical cases a very small graph). Insisting on reaching the "natural" waypoints should be a reasonably smart behaviour for most units and most environments.     Not to sound rude, but I'm pretty sure the way I'm doing it is a very viable way to simulate movement in an rts. I'm fairly certain StarCraft2 uses the same method I'm using (in fact, that's where I pulled many of my ideas from). If you could explain why the method I'm using is unfeasible and point me to a link further detailing the method you are proposing, I'd be very grateful :)     I've gone through his stuff. The obstacle avoidance algorithm he explains relies on the obstacles having being circular (or giving them a radius) but the obstacles I am using are polygons.
5. ## Using flocking to avoid non-circular obstacles in an RTS setting

I'm using A* to set subgoals for my units, and steering to arrive at the goals. It's the way many rts games do pathfinding, I feel quite confident that they can both be compatible. That's not really the issue though, pretty sure my problem would occur even in a simulation that only used steering with seek and flocking behaviors.   Edit: Just for clarification, the only thing a* is set the destination for the "seek" steering behavior
6. ## Using flocking to avoid non-circular obstacles in an RTS setting

I'm working on a movement system for a pet project of mine. I'm using an a* algorithm on a navmesh created with Delauney triangulation (where each triangle vertex for a navmesh will be on the vertex of some obstacle). The a* also accounts for unit radius and prevents units from moving through choke points and corridors that are too small. The navmesh is only created to path around terrain, and immobile structures (anything that is a static object). I've also started to implement steering to keep units from colliding with dynamic objects and to flock allied units.   Here's the problem I have. When I don't include steering forces, units are guaranteed not to run into any static objects. When I include steering forces, the units in theory will behave nicely in relation to each other, but they can be pushed into static objects now. I would deal with my static objects with the same unit avoidance I plan to use for my avoidance behavior for dynamic objects, but this approach requires both objects to have a radius (be circular).  Is there any nice way to prevent my units from running into walls that has relatively quick running time? Keep in mind that I have to perform this operation every frame for possibly 50-100 units.