# A* Path Finding in Free Form movement

This topic is 5194 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

So most of us have played warcraft 2 where units are rigidly expected to occupy a tile. In games like warcraft 3 when doing path finding, units don't have to sit on a tile, they can be at any x/y position, and some units can be larger than a tile so even though there is a path the unit might not fit. Anyone come across articles dealing with these problems?

##### Share on other sites
There are some pretty straightforward ways of solving this.

If units can have arbritary positions, you can still consider them to be "on" a tile. You can then pathfind from that tile to the tile nearest the target, *then* change the path to a series of straight lines (by using a line-of-sight algorithm I described in an earlier post).

That works nicely.

Then for bigger units - that sounds somewhat tricky, until you realise that you can redefine a blocked tile as being rather than "on top of a wall", but "adjacent to a wall", then do the path finding algorithm normally, and it will automatically avoid gaps too narrow for your large object.

Mark

##### Share on other sites
Well, this is what I'm thinking. Instead of path finding for a single unit, it'll be for the whole group of units being moved (save CPU) and the group uses a sub system designed to stick to the path as close as possible. For the actual finding though, I figure I could get the largest unit and use a intersect test between nodes. I'm not sure how much speed reduction this will have on the path find though since it'd be like doing N collisions where N is the number of nodes created. It'd definitely find a clean path though. Of course, the entire path doesn't have to be found instantaneously. I doubt anyone would notice even 100ms delay before the path is found. I will continue to research and look at the LoS engine.

##### Share on other sites
You could run different pathfind requests for each type of units in your group (this way flying units can go directly to the target).

While following the path, I'd recommend something simple like steering.

Also, are you SURE units in Warcraft 3 don't stand on invisible tiles? I mean, it would be pretty easy to mark tiles as used when a character reaches destination, and if your destination (as a single click will give destination to a few units) is marked as used, you can still check if your tile is adjacent to a used tile connected to your destination, this way you will avoid having characters that jerk trying to reach a point they'll never reach because someone else is blockin their destination.

Hope this made sense ;)

Eric

##### Share on other sites
Warcraft 3 does some handelling when a path is blocked. Units will try to walk it, if another unit is in the way of their path they'll end up retracing and taking a different path. I believe they might wait for the unit if it's moving. Not 100% sure. Warcraft 3 is tile based though, but units don't occupy tiles as in a rigid x/y system, that I'm sure of.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 23
• 36
• 16
• 75