# Two Tier Pathfinding?

This topic is 4493 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

i am currently trying to implement pathfinding using A* with two grids, one fine grid and one larger one which is 8*8 tiles of the smaller grid, i calculate the path using the larger grid, then using the finer grid move from point to point of the larger grid. i can detect and avoid obsticles nicely with the fine graph but how do i avoid obsticles with the larger grid? say for example there is a thin wall streching across multiple large tiles, http://img259.imageshack.us/img259/6662/fsf0tn.png any ideas would be appreciated? thanks

##### Share on other sites
You can represent those divided large grid cells as 2 different (A*) cells.

So, for example, the bottom half of those divided cells would have neighboring cells down, left, and right, but not up.
(Make sure you point to the bottom half of any divided neighbors, too)

The large cell at the end of the gray line would be able to go: up, down, right, and _both_ lefts.

I have implemented a similar system, and at only two levels (fine, coarse), i got a reasonable perf benefit, but it improved as i added more. From memory, I eventually settled on 1x1, 4x4, 16x16, 64x64 and my game map was maximally 1024x1024 (but at 64x64, there were almost no walls like you have, so that affected it quite a bit).

Hope this helps.

##### Share on other sites
You might get some benefit from investigating framed quad tree approaches to pathfinding.

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
JoeJ
13

• 9
• 14
• 10
• 25
• 9
• ### Forum Statistics

• Total Topics
632645
• Total Posts
3007626
• ### Who's Online (See full list)

There are no registered users currently online

×