Gridless 2D Path-finding
Author
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.
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.
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*.
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*.
Author
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 -
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
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*).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
