Sign in to follow this  
NiteLordz

Leafy BSP and Pathfinding

Recommended Posts

NiteLordz    808
Hey guys, i figured if anyone couuld help with this one, you could. i have a leaf based bsp engine running. very simple. nice two floor level. i have an editor. my ? is how can i auto generate the path finding nodes to store in a graph automatically. i can do it manually, but for huge levels, i could see that not being fun. thanks much

Share this post


Link to post
Share on other sites
Timkin    864
Try this method... designed for Oct-trees... but trivially adaptable to a bsptree:

Williams, M. and Jones, D. I. "A rapid method for planning paths in three dimensions for a small aerial robot", Robotica, volume 19, pp125-135. Cambridge University Press, 2001.

It's essentially a very efficient multi-dimensional flood-fill... which is just a boring name for the more interestingly named "Distance Transform Algorithm". ;)

Cheers,

Timkin

Share this post


Link to post
Share on other sites
BrianL    530
I don't have 'A rapid method for planning paths in three dimensions for a small aerial robot' on hand, so here is my best shot at a replacement. ;) :

http://www.informatics.bangor.ac.uk/~matthew/pubs/thesis.pdf

Specfically, take a look at chapter 5.

Share this post


Link to post
Share on other sites
Timkin    864
Yes, Matthew's thesis is a good read if you're so inclined... if anyone particularly just wants the paper I cited (which gives a good summary of chapter 5 of the thesis) I can provide an electronic copy via email (for research purposes only, of course). I cannot post a URL here though for copyright reasons... sorry.

Cheers,

Timkin

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