Jump to content
  • Advertisement
Sign in to follow this  

Rasterize stopped unit in clearance-based pathfinding

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

If you intended to correct an error in the post then please contact us.

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?


Share this post

Link to post
Share on other sites

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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!