Re: [Algorithms] Pathfinding in a 2d grid - better algorithms than A*?

[<ali...@gm...>]

Hi Tony,

I have considered this approach - however, I'm not entirely sure how I'd
trace the path from larger clusters to the smaller, more complex areas -


|-----------------|------|
|                 | B   |
|      A         |------|
|                 | C   |
|-----------------|------|

Say node A is a larger cluster of 4 identical cells. When I'm traversing
that square, do I just assume that the path would go through the centre, and
list each adjacent cell in an array or something? Currently the algorithm
just uses a set of x y coordinates to address each node, so when expanding a
cell it looks to n-1 and n+1 to find neighbour cells. I could change this
though.

Am I along the right lines with this?

Cheers,
Alias

On 28/11/06, Tony Cox <to...@mi...> wrote:
>
> Another approach is to pre-process the grid by coalescing clusters of
> cells which have the same traversability characteristics, to form a much
> simpler graph to perform the A* algorithm on.
>
> Depending on how good your low-level "tactical" path following is (i.e.
> how to the units actually maneuver the path once computed), you probably
> need to impose a condition like convexity on the clusters in order that the
> path you generate is easy to navigate.
>
> One way to do this is to flood-fill connected regions with identical
> properties (e.g. traversable versus non-traversable, or whatever you
> have), and then compute a dissection of each region into convex pieces (
> e.g. Delaunay triangulation).
>
> A nice property of this approach is that by coalescing homogenous regions
> the resolution of the grid doesn't affect the size of the graph, the graph
> just reflects the actual complexity of the geometry.
>
> You can pre-compute the simplified graph off-line, but it's actually not
> too expensive to just do it at load time. If you have to cope with a
> changing grid, there are ways to cope with incremental changes to
> sub-regions - we had to do this on Dungeon Keeper (circa 1996!), but with
> modern processor speeds it might not be necessary (just do the full
> recompute) unless you have extremely complex maps.
>
> Tony Cox - Director of Engineering
> Microsoft Game Studios
>
> -----Original Message-----
> From: gda...@li... [mailto:
> gda...@li...] On Behalf Of
> chr...@pl...
> Sent: Monday, November 27, 2006 6:31 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Pathfinding in a 2d grid - better algorithms
> than A*?
>
> > I'm currently working on some 2d grid based pathfinding stuff, and
> > I'm a little unsatisfied with the performance of A*. It seems to
> > take a very brute force approach to the problem, and is constantly
> > causing CPU issues.
> >
> > Are there any more elegant/modern algorithms which have been
> > developed which might fit my purposes? I'm just looking to find a
> > simple path between to points, avoiding obstacles. Grid squares are
> > either empty or solid.
>
> You need to provide more information to get a good answer.  For example,
> how big is your grid? Do grid cells change status dynamically or is the
> map static?  What is the cell connectivity?  What are your "CPU issues"
> and did you implement your A* algorithm in an efficient way?  Etc.
>
> For a small static map you can precompute a two-dimensional table that
> for entry (A,B), where A represents the start cell and B the end cell,
> contains two bits that specify whether to go N, S, E, or W from the
> current start cell to end up at a new "start" cell.  This solution is
> obviously O(1) in terms of speed for finding the next position to go to,
> which is hard to beat.
>
> The only problem is that, while a 20x20 grid takes ~20K of precomputed
> data, a 100x100 grid requires ~12MB of precomputed data (if I didn't
> get those numbers exactly right, at least you get the idea).
>
> With more detail, people are more likely to be able to provide an
> answer that might be more helpful to you.
>
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> opinions on IT & business topics through brief surveys - and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>