Hi I have a aStar up and running, but wanna do this: Imagine a square-based battle-field. The units move from square to square to find someone to bash. But if a line of guys are hitting another line of guys, more guys will have to move round to reach their victims, not just move through. My method was to mark each guys position as "non-walkable" each frame telling aSTar to find a path around. But this gives me new problems. What is your suggestion? I dont mind redo all paths all the time. I have a small battlefield and no more then 40 guys at the same time. And thats ok couse i can do 2000 pathfinds easily. I know some people say ignore all moving units until you detect collision, but then they cannot find a path around like in my ascii-example: team a vs team b. That a-guy reinforcing will have to go round to bash a b-guy, right? _________a____ _________ab___ ___->a___ab___ _________ab___ _________a____ Thanks for your tips. E [Edited by - suliman on April 3, 2006 8:53:26 AM]

The chicken way to do this is simply to allow units to step over other units. Then any square is walkable.

I ran into this problem with a game i worked on a few years back. I never found a really brilliant way to solve it, but here is an idea:

simplify your main path to "major areas of the map" instead of specific tiles. If a guy gets in the way of your original tile-to-tile path you created, that path is suddenly invalid. Of course if you wait a few seconds it might be valid again, but you don't really know that. So you might consider simplifying the pathfinding job to making a basic "how to get there" path of major map areas, then doing a sub-path from each major area to the next. Sort of like waypoints.

You can do that by dividing the map up into major sectors. You need to gaurantee that the sectors are reachable though, in some way.

Now your units don't need to hit specific squares all the way to the goal. Their long-term goal is to get to the next major map sector. That can be done any number of ways and allows you some options of avoiding other units in the field. This is like when you take a cross country trip. You don't plan for every street and intersection until you actually get there. Until then, you just concern yourself with major highways on the map.

Another thing you can do is mark each maptile that has a unit in it with a higher movement cost. Then, the pathfinder will naturally prefer you "go around" other units. In the event that it cannot actually move through, it could be instructed to wait patiently (but possible forever).

And finally, you may divide your pathfinding into hard obstacles and soft obstacles. Hard obstacles should be completely avoided. They are unpassable. Units are not passable either, but might be later. So like you already mentioned, you can do that path and not actually stop until there is a unit in the next tile in the path.

Hope that gives you some ideas.

but that doesnt answer the question i posed. My problem is exately that, guys not moving around specific tiles to reach enemies backs if their front is blocked by other units.

The small battlefield i mentioned is small, 20x20 tiles, so that waypoint-idea is not appliable. I dont have problems with units not getting "acceptably close" or getting to the right area with such a small map. See it more of a chessboard kinda game than realistic outdoor-movement. Each unit really fills up its square.

So... More pathfinding tips any1?

Thanks

Quote: Original post by suliman
My method was to mark each guys position as "non-walkable" each frame telling aSTar to find a path around. But this gives me new problems. What is your suggestion?

I'm not an expert on the field, but, what if you move first those units that have the closest path to move away? As they go away, their position will be walkable for the rest. Even, you could follow those.

I agree. You can try sending a "pardon me" message to local units. That is, if they can continue their activities from a slightly different location (away from the path you want to walk), then they can move the 1 or 2 squares it would take for you to get through.

Likely though, you will have to come up with a greater group communication system. In your example, what should ideally happen is for one of the fringe guys attack the other team from the rear, then move your original guy into the fringe guy's previous spot.

All units being equal, you could do a "job relay", like "Hey, you're in a better position to do my job. I'll do your job if you do mine." And you get a "shuffling" effect.

It is a near certainty that you will not be able to find a globally optimal solution to this positioning problem using only local positioning rules evaluated by each agent. That means that you either need your agents to communicate to achieve a global solution or you need an oracle to evaluate the global solution given the state of each agent.

You can, however, get a sub-optimal solution that works reasonably. Try using a dynamic potential field method for vectoring your units (the discrete version is known, within game development circles, as an Influence Map). The potential field method is related to steering behaviours as well... and all of these are functionally equivalent to a communication system.

Basically, have each unit move toward the enemy units and away from their own units, with the range of influence of these attractive and repulsive forces being different. You want repulsive forces to act over shorter distances but to be stronger than attractive forces, so your units will tend to move together toward distance targets but then, up close, your units will find a reasonable spacing while engaging the enemy.

Make sense?

Cheers,

Timkin

Oh.

Thanks for your replies. I think this is a bit over my head. I will try to do an acceptable, more primitive sollution. Optimization is not important in this game-moment.

E