# pathfinding with obstacles in a Warcraft 3 like game

Consider A* searching on a tile based map. A straight forward code would be: If there is an unit inside that cell, then it is unreachable, this is ok.

But there is map resolution issue. When I look into Warcraft 3, there monsters and structures does have different radius, and you can walk very close, which is more like vector based, how this was implemented?

Also, what is the standard solution to incorporate moving obstacles collision detection with path finding algorithm, like Warcraft 3?

• What does "vector-based" mean? Dec 9, 2011 at 11:12

## 2 Answers

I can't say for sure what kind of approach was used by WC3 developers, but it looks pretty much like Hierarchical Annotated A*. Unit radius defined in the WC3Editor was used as-is for 3d model scaling, but actual unit size for pathfinding was discrete, maybe something like unitSize = (int)(unitRadius / 10). It wasn't vector-based, that's for sure.

Let's say there are a lot of path nodes making high-resolution node grid. Simple unit like a ghoul has a size of 2, so in order to place it somewhere in a grid we need 4 free path nodes near each other. A death knight hero is slightly larger with a size of 3, taking 9 path nodes total. Now we place 2 ziggurats together leaving a 2 node-wide space in-between, and send a ghoul and a death knight on the other side. Ghoul will be able to pass between two ziggurats, while death knight will have to move around. How can it be determined?

In order to see whether a node can accommodate a unit of specific size, let's assign a special clearance value to each node defining a maximum allowed unit size. Basically, it means that several bounding checks were made for a node, and the largest possible bounds were remembered as node's clearance. So when we want to place a death knight on some node, it becomes as simple as comparing node's clearance with death knight’s size. Of course, things are going to become much more complex when there are several units hopping around competing for nodes, but that’s another story.

For further detail you may want to check out this article:

http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/

It would use tessellation to create pathing regions AKA navigation meshes. This article explains the concept with full diagrams.

You can still maintain A* as your pathfinding approach, however your network is no longer a grid (4-connected graph), but a graph representing the arbitrary connectivity between your polygonal regions. So you will have to adapt your algorithm to suit.