Sign in to follow this  
kappa1

Two Tier Pathfinding?

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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this