Quote: Original post by Timkin

Quote: Original post by Steadtler
That would give you only three nodes for your pathfinding, in your examples.

No, it would give you one node per adjoining edge. If your convex polygons were triangles, then yes, that's three nodes.

My bad, I was thinking 3 convex polygons. Hum, for the purpose of finding an optimal path, shouldnt you keep the whole edge, instead of using the mid-point of adjacent edges? Then you can apply a hierarchical pathfinding, first on the edges, next on a discreet set of points of the chosen edges... Or is it better to smooth your movement when you arrive near a node, using the lenght of the edge as the strenght of the smoothing? I dont know if Im clear here... Im just thinking, except for mostly linear paths, you will rarely want to pass trough the midpoints of the edges...

Quote: Original post by Timkin
If you can ensure that your graph size is restricted to what you can handle with your computation resources, then obviously you can apply any method you like, because your bounded by your graph and resources, not the method ;)

Oh alright :P I just wanted to show triangulation is not that bad of a process.

Quote: Original post by Timkin
Through most of the robotics literature its still called pathfinding, because they don't tend to consider deliberative pathfinding, as AI people do. From the AI perspective, the distinction is made between reactive planning/pathfinding and deliberative planning/pathfinding. From the Control Theory perspective, everything is reactive (all deliberation was done at the time of controller design), although they still like to think that they're 'finding a path'.

You know, I always disliked how, in AI litterature, they tend to talk about reactive systems in the planner chapter. I guess I associate 'planning' with deliberation. To me, its not as much planning as strolling around and hoping you'll get there :P. Which is good, if obstacles are few... But thanks for giving me the distinction :)

Quote: Original post by Timkin
Think of it more as a method of (very) limited horizon graph search. You get to look at only your next step and make a decision. ;)

Thats wierd, thats what my boss do, and *they* call that planning too! ;)

Quote: Original post by Timkin
Btw Steadtler, do you do your search on a heirarchical mesh from your triangulation, or just use the base tesselation?

Sorry for the misunderstanding, we dont use the triangulation for search purpose. Cant say more than this :P

Thanks for your insights as always.

Quote: Original post by DrEvil
Check out this neat little application: http://www.ai-blog.net/archives/000091.html
Click on the picture.

It demonstrates many different pathfinding techniques such as 4 way grid, 8 way grid, quad tree, hex grid, corner graph, waypoint graph, navmesh(triangle), navmesh(convex poly). Though unlike the app shows, I would prefer to generate the path through the edges rather than through the triangle centers.

Thanks! The convex polygonal navigation mesh in that demo is exactly what I'm looking for. I have an algorithm in mind, but I'd be glad if you could provide a link to any neat algorithm you know of for this.

I don't have a ton of links on the subject, but here you go:

http://www.cs.ubc.ca/spider/snoeyink/demos/convdecomp/MCDDemo.html
http://www.bringyou.to/compgeom/

Quote: Original post by Steadtler
Hum, for the purpose of finding an optimal path, shouldnt you keep the whole edge, instead of using the mid-point of adjacent edges? Then you can apply a hierarchical pathfinding, first on the edges, next on a discreet set of points of the chosen edges...

That's basically the methodology akin to the 'framed quad-tree' approach. Most certainly the more information you keep, the more 'optimal' path you can achieve; whether that is optimal as in shortest, or smoothest, or some other metric.

Quote: Or is it better to smooth your movement when you arrive near a node, using the lenght of the edge as the strenght of the smoothing?

This is a very common approach used in robotics. There are two basic choices: 1) pass close to the waypoint while cutting the corner; or, 2) pass through the waypoint by swinging wide (either before or after the waypoint). This gives some degree of smoothness of velocity changes while maintaining essentially linear path segments, which make the task of designing tracking controllers to follow them far easier.

Quote:
I dont know if Im clear here... Im just thinking, except for mostly linear paths, you will rarely want to pass trough the midpoints of the edges...

Absolutely. In games particularly though, as you would know, pathfinding is more about finding a useable solution quickly and then refining it to make it look nice. The alternative is to spend more effort finding a better path in the first place. Since the former may use the same computational resources but is easier to understand, implement and debug, most programmers favour that approach. That's not to say it's better. ;)

Quote:
You know, I always disliked how, in AI litterature, they tend to talk about reactive systems in the planner chapter. I guess I associate 'planning' with deliberation. To me, its not as much planning as strolling around and hoping you'll get there :P. Which is good, if obstacles are few... But thanks for giving me the distinction :)

I tend to agree. I prefer the view that reactive systems are described by an agent function of some form that maps states to actions. The view that this is planning though (and not purely reaction) is that traditionally, such agent functions were learned offline; for example, the determination of an optimal policy. During run time, this is just a reactionary system - detect which state you are in and apply the action appropriate to that state - but the creation of that policy is a planning problem (one usually solved with dynamic programming). The other perspective is that you can view planning as finding the solution to a problem defined on an horizon. Full deliberative planning would have the horizon at the goal (and is often intractable in the real world). Many robotics applications rely on finite horizon planning (the horizon is somewhere between the agent and goal). Reactive planning is just an horizon of length equivalent to one action. Indeed, in many adaptive planning methodologies these days, they tend to solve the problem on a limited horizon, commit to executing just one step and then resolve the problem after that step (or during it). This is both deliberative and reactionary. It's also computationally expensive and not very 'intelligent', which is why I've published an information theoretic method for deciding when it was appropriate to replan that is far more efficient. ;) (Got to sneak in those gratuitous self plugs!)

Quote:
Sorry for the misunderstanding, we dont use the triangulation for search purpose. Cant say more than this :P

Nps. Gotta love NDAs... not! ;)

Cheers,

Timkin