Advertisement

Rasterize stopped unit in clearance-based pathfinding

Started by January 24, 2015 11:30 AM
0 comments, last by comfy chair 10 years ago
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.

How about making your collision response more forgiving. In that way, agents can still squeeze through each other in the cases where there is a small mismatch.

This topic is closed to new replies.

Advertisement