I''ve explored most of the A*/pathfinding threads and haven''t found the answer to this one, so ... I was recently reading an article by the designers of Age of Empires on their pathfinding algorithms at: http://www.ensemblestudios.com/news/devnews/terrain1.shtml A* pathfinding can consume enormous amounts of CPU time but, according to the author, this can be reduced by simplifying the map down to a more manageable size (a "mip map"). A smaller, simplified map has fewer nodes/squares that need to be explored, and thus your pathfinding can be achieved much more quickly, at least in theory. Unfortunately, that article doesn''t explain the process of reducing a map to a mip map very well. Can anyone else out there explain the process? Patrick Lester - Blitz Basic User Compaq Laptop AMD-K6(tm)-2/ at 350 MHz : Memory 160 Megabytes Video = ATI RAGE LT PRO AGP Graphics Controller

I''m not a big fan of A*, but I can see how the mipmap creation process would be done.

You know how to create mip-maps in graphics right? It''s a bit the same here, except each grid cell stores a boolean: the presence or absence of an obstacle.

Instead of averaging the pixels (or another filter -- like in graphics), you perform an OR operation. This implies that when your MIPMAP is clear, then so are ALL the cells in the original map. If the MIPMAP contains an obstacle, then the underlying map has some obstacles; either you avoid it, or process that cell hierarchically.

Make sense?


Artificial Intelligence Depot - Maybe it''s not all about graphics...

Thanks for the reply! A few follow ups ...

(1) Actually I don''t know how mip maps are created in graphics, but I can guess. Since creating a mip map involved shrinking an image, I would presume that it averages the colors in adjacent pixels, and then uses the combination to represent in one pixel what was previously represented in several. You end up losing detail, but it looks like a smaller version of the original image. (Or, maybe I''m totally wrong about this).

(2) With respect to mip maps in pathfnding, how would you do it hierarchically? Have you seen any papers/web sites on hierarchical pathfinding?

(3) What do you prefer over A*?

Patrick Lester - Blitz Basic User
Compaq Laptop
AMD-K6(tm)-2/ at 350 MHz : Memory 160 Megabytes
Video = ATI RAGE LT PRO AGP Graphics Controller

just a stab at the hierarchy..... I'd say do it somewhat how a quadtree is setup....have one "mipmap" that covers the whole map but is realy low res then have another that is only the upper left section of the map upper right ect. then each of those are broke down again and again and again as needed..... then then just do an A* search on the sub mipmaps that the path crosses....

anyways look up so articals on quadtrees I think you'll see what I'm talking about

[edited by - Great Milenko on April 15, 2002 3:40:28 PM]