Hi, I'm looking to create a path-finding system for a 2D RTS, where unit movement is not constrained to grids (i.e. units can fluidly move anywhere). What path-finding technique should I use to simulate this, while keeping in mind the possibility of having 200 units on the map at the same time? I've tried an A* implementation using rectangular grids, but the problem with that is that A* does not give you the most optimum path. This link better illustrates what I mean: http://img300.imageshack.us/img300/8596/astarexample2.png (pardon, but I'm not sure how to post URLs in this forum) Thanks in advance. - dadads -

There is an easy thing to do after you run grid-based A* that will make the paths look much better and that will solve your example. You first run A* normally and then you always go the the last node in the path to which you have direct line of sight.

Another modification that makes grid-based A* much better is considering larger steps. As a first step, you should allow "chess knight" moves. This will make the solution paths much more straight.

A combination of those two tricks would probably be good enough for most purposes.

If your map is basically polygon type obstacles, what you can do is generate a 'visibility graph'(what other points are visible from each point) from the vertices and then perform A* on the graph. This works because the shortest path will always lie on the visibility graph (plus the start/end points). You'll probably want to cut corners and pre-calculate as much as you can for this to work sensibly. My computational geometry book (by Berg, Krevald, Overmars, ...) has a chapter on the topic at the very end.

If you actually have terrain that is slower to pass over, then it's trickier since you can't use the visibility graph.

I was about to say exactly what jdindia was. ;-)

Also, I'm not sure about this, but IIRC there are results in the literature also for 2d path-planning with varying costs where (1) the cost is piecewise constant, and (2) the boundaries between regions of different cost are polygons. But I'm not sure how it's done. A quick google turns up, e.g.,
http://ijr.sagepub.com/cgi/content/abstract/19/2/83

My second thought is that you could keep your grid and use, e.g., Sethian's fast marching algorithm -- which is essentially Value Iteration with Interpolation made as Dijkstra-like as possible. Yet this will be slower than plain old A*.

How do people typically accommodate for the differing unit sizes in path-finding?
Am I supposed to rebuild the terrain graph/grids for each unit size, or is there some other better way?

Thanks for the ideas, by the way.

- dadads -

Points of Visibility may be of interest to you. I briefly explain it in the following post:

http://www.gamedev.net/community/forums/viewreply.asp?ID=2452752

Quote: Original post by dadads
How do people typically accommodate for the differing unit sizes in path-finding?
Am I supposed to rebuild the terrain graph/grids for each unit size, or is there some other better way?

Thanks for the ideas, by the way.

- dadads -

The usual answer seems to be yes, store different copies of the map, one for each size.
However, there are better methods, like HAA* which involve calculating clearance values at various locations on the map to work out how much free space there exists.

Similar approaches can be applied on non-grid representations using Roadmaps (which come in probabilistic or reachability flavours) and even navigation meshes (for instance, see Demyen & Buro's paper on TRA*).