The Argorha Pathfinding is aimed to find a path into the polygon soup without man intervention. The Argorha Pathfinding looks like this: The src and binaries for Argorha pathfinding can be found there : http://sourceforge.net/project/platformdownload.php?group_id=202941 The license for Argorha Pathfinding is LGPL. The main idea of this pathfinding is to put together all the areas where an actor can move. A freely movable area is called a sector. Having sectors is not sufficient; we need to know how to go trough from a sector to another sector. This is defined by portals. These sectors and portals are pre-processed in an editor and they will be used into a game to find the path of an NPC. In the pictures, the red parts are the sectors and the blue parts are the portals. Once the sectors and portals are generated, we use an algorithm called A* to know where to move. The A* is made between the portals. At the end, a list of AStarNode is returned, from which the actor can move from. If you use just a list of distanced points to move your NPC, it will give the impression that your NPC is a robot. To counter that, in Argorha Pathfinding there are functions to calculate a path between portals: The cardinal splines and Bezier curves. Those functions make sure that the path is always into the sectors. In the pictures, the straight line is yellow, the Bezier curve is green and the cardinal spline is pink. In the pictures, I'm using a map editor named GOOF built on top of OGRE. GOOF is in alpha state and not maintain anymore, but it's enough usable for me to prove the pathfinding. Globally, you need to understand that there is the Argorha Pathfinding which do the algorithms and don't know anything about the engine and there is GOOF which uses Argorha Pathfinding to make the pathfinding into GOOF. That way, you can integrate the pathfinding in your engine without too much effort, you need to implement 3 abstract classes to tell the Argorha Pathfinding how your character moves in your engine and it's gonna work. I’ve put an online documentation for the pathfinding. It can be found there: http://membres.lycos.fr/bibiteinfo/docPathfinding/ The algorithm is heavily based on this gamasutra article: http://www.gamasutra.com/features/20020405/smith_pfv.htm If you speak French, here's my final Cegep report, explaining how the pathfinding works. http://membres.lycos.fr/fredericjoanis/ On my todo list I’ve got: - Find and use systems such as doors, ladders, elevators, and teleports. - Enhance A* and organic paths with Patrick Smith tought I can't do the doors, ladders, etc with GOOF actually. If anyone has an engine that handles those kind of mechanism, and need pathfinding into it, I'm interest in making the integration. At last, I hope this is going to be useful to the community. It has been the topic of my internship in winter 2006. When I came back to the code I’ve made at that time was so messy I needed to start it all over. Now it’s a really cleaner solution. It’s my part time project from that winter until now. Enjoy. [Edited by - bibiteinfo on October 23, 2007 5:16:04 PM]

Seems like very good stuff for a cegep student!

"Portal" have another meaning in game development though (ok, several other meanings). What you describe as portals are more commonly refered in this context as navigation links, and the "sectors" as a navigation mesh. But I see you took your nomenclature from the gamasutra article (which date from 2002).

Quote:

Original post by Steadtler "Portal" have another meaning in game development though (ok, several other meanings).

Eh, portal seems like as good a word as any here. In rendering, portals represent connections between sectors, and they do the exact same thing here. The sectors and portals are just based on navigability instead of visibility, and the use is slightly different because the goal is to find a path rather than to compute the visible areas. They're just "navigation portals" instead of "visibility portals".

It's such a general concept...in the game "Portal", the user created portals serve as both visibility and navigation portals that are added dynamically by the player.

Quote:

Original post by Vorpy Quote: Original post by Steadtler "Portal" have another meaning in game development though (ok, several other meanings). Eh, portal seems like as good a word as any here. In rendering, portals represent connections between sectors, and they do the exact same thing here. The sectors and portals are just based on navigability instead of visibility, and the use is slightly different because the goal is to find a path rather than to compute the visible areas. They're just "navigation portals" instead of "visibility portals". It's such a general concept...in the game "Portal", the user created portals serve as both visibility and navigation portals that are added dynamically by the player.

I guess... I just wanted to give him a few keywords if he want to do more research to expand his tool. Im not so good with nomenclature myself...

"Le défaut du A* est qu'il a été pensé pour des mondes en 2 dimensions."

What do you mean ?

there is no dimensionality in A*, you provide a cost measure that suit your model. Beside, nothing prevents you to use a directed graph, if what you meant is that the cost to go down a hill was not the same as going up.

Quote:

Original post by germain "Le défaut du A* est qu'il a été pensé pour des mondes en 2 dimensions." What do you mean ? there is no dimensionality in A*, you provide a cost measure that suit your model. Beside, nothing prevents you to use a directed graph, if what you meant is that the cost to go down a hill was not the same as going up.

@Damian : This is over simplification, you're right when you mean that A* does not have dimensionality. What I think I meant at that time (2 years ago I've wrote this paper) is that every example I saw for A* where given for 2D grids and the add of a third dimension brings up a new complexity, which is harder to handle.

@Steadtler : I know portals can mean a lot of things like visibility portals in rendering engine, portals can mean Half-Life 2 Portals and such. As you guess, I've stick to the gamasutra Article nomenclature.