Sign in to follow this  
hulobet

Rasterize stopped unit in clearance-based pathfinding

Recommended Posts

Hello guys.

I am trying to make a Warcraft 3 like pathfinding and movement system. I had no idea how RTS-like game was made, and I got stuck here for weeks.

Here's what I do.
I have a 2D grid-map and units have float-value positions rather than only at center of each grid. I first used A* on the static map to find the path, ignoring dynamic units, and RVO to avoid dynamic units.
But when units are stopped or attacking, they will block others and the blocked units cannot pass it to reach the goal. So, after some search and digging, I tried to rasterized static units(stopped or attacking) on the grid map. I didn't want to do the rasterization every frame. Instead, I only recalculate the local map and do another A* when a unit's path direction collide with a static unit.
I guess Warcraft 3 is doing this way, but some implementation detail made it hard to get my desired result.

The biggest problem is I'm using round shapes for collision handle, and the gridmap for A* search. These two methods may be inconsistent when I rasterize the round shaped unit on the grid. And it may be a problem when the grid size is big (In my case, the grid size = unit size * 0.5).

In my collision system, units are round shapes with a center position and a radius. And when I rasterize a round shaped unit on grid, it will be less accurate. So there is some inconsistency between the a* gridmap and the collision system. Sometimes the A* map says you cannot be in this grid, but you are there pushed by other units. Then the A* doesn't work and the unit get stuck.

How is this usually handled? Or should I change the collision system so the A* and collision system are consistent?

I read the clearance-based pathfinding ariticle: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/
In this article, units seem to be square shape.
What is the best way in practice? What is warcraft3 or starcraft 's method?

Or anyone can help me with a practical way to handle stopped units?

Thanks.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this