[Pogamut-list] Restricted Navigation

[jakub.gemrot]

Re: Restricted Navigation

Author: jakub.gemrot

Hi!

Thanks for questions. Firstly, we cannot change the way native UT2004 path planner is working. Floyd-warshall algorithm cannot be bend every time you run it (obviously N^3). 
What you're seeking is A* with customized "map view".

I've never found time yet to fully integrated my side-project amis-path-finding with UT2004.
You may checkout it from: http://artemis.ms.mff.cuni.cz/websvn/listing.php?repname=Pogamut&path=%2Ftrunk%2Fproject%2FUtils%2FAmisPathFinding%2F&#ae4a11e01bdf8672eef02129f56486530

It is a small library containing robust implementation of A* and Floyd-Warshal. Check "test" sources for usage. To quickly point you to few classes:

1) first you have to implement IPFMap, that will adapt NavPoint & NavPointNeighboutLink for A* hidden in the library,
this implementation should be honest and do not remove any arc/node from the graph

2) second you need to implement various "view" on the map via IPFMapView interface that may restrict/extend existing IPFMap
This view on the map means to be "agent-centric", here you should specify things like "jump links costs much more", etc.

3) just assemble it all together using new AStar(IPFMap<NODE> map, IPFMapView<NODE&gtl view)
and public synchronized AStarResult<NODE> findPath(IPFGoal<NODE> goal, long iterationsMax)

Note that path-computing are not-that-costly (few ms up to 10 ms I believe) so you might go for this strategy:
1) use conventional FloydWarshalMap
2) use one or two of your customized A*-path-planners
3) compare multiple paths and pick the most suitable one

Cheers!
Jakub

P.S.: please, if you create a few implementations of IPFMap and IPFMapView, would you consider donating that code
into our repo?

-- 
Reply Link: <http://diana.ms.mff.cuni.cz/main/tiki-view_forum_thread.php?forumId=4&comments_reply_threadId=4&comments_parentId=1027&post_reply=1#form>