Hi guys, I'd like to know if the world is divided into different sized polygons... how does the A* algorithm work? isn't it compulsory to have standard shapes around the world so that there is something to weigh which path is more costly than the others. f=g+h h can be found when measured heuristically against the goal f can be found only if g is found, how does g get found then in this case? if this sounds stupid, please bear with me because I am still learning A*...:) Thanks in advance Jack

Why whould you need the shapes/polygons of the nav mesh to determin edge weights? Couldn't you just use the distance between two nodes/portals/shapes as your weight? E.g. find the vector between them (you could use center points for edges/polygons) and use it's length as g or h?

Quote:

Original post by sebbit Why whould you need the shapes/polygons of the nav mesh to determin edge weights? Couldn't you just use the distance between two nodes/portals/shapes as your weight? E.g. find the vector between them (you could use center points for edges/polygons) and use it's length as g or h?

Thanks for the reply... I appreciate it :)
Could you please provide some examples/links to this topic? I looked the web, Most of them are related to navmesh construction or grid-based pathfinding....
Thanks
Jack

From what I read, I understood it to be you first do typical A* using the polygon centerts as nodes, then that gives you a path through each polygon. Then you find the best path through each polygon (hugging edges etc).

In one of the links on the forums here it was described as hputting a string through each point and then pulling it tight from both ends and thats your best path.

It appears I didn't save the link though :/

Quote:

From what I read, I understood it to be you first do typical A* using the polygon centerts as nodes, then that gives you a path through each polygon.

Using the polygon centers as nodes is one option; another option is to use edge midpoints as nodes.

Sorry, don't have any links. But, it's not that much different than doing A* on a grid. In essence, A* works with a graph internally. Where the edges are your available paths and the nodes are where these paths connect.

Now, when using a grid, the nodes are the center points of your grid cells and the edges are the connection from one cells center to it's 8 neighbour cells. When using a navigation mesh, instead, the midpoints of your protals (the edges where two polygons/sectors connect) are your nodes and the edges are possible connections between any two nodes of a single polygon.

So, the only thing different to grid based A* is how you find the neighbours of a node. Instead of just finding the 8 neighbour cells you have to find all polygons that share a node (e.g. the two polygons that are connected by the edge/protal the node is on) and instead of using a fixed weight use the geometric distance between nodes. Everything else is the same.

I've come up with another problem again.
What happens when 2 objects are in each other's way?
thus holding each other's position that results in deadlock
How is it handled from the programmer's perspective?

A-> <-B

Thanks
Jack

There could be several techniques here. Off the top of my head (cause i ran into something similar recently at work.

1) the mesh should provide reasonable area for the units to move around in. Assuming the units are aware of one another, they could preemptively both decide to both turn left (or both right) as they approach, so as to pass one another.
They could post-collision decide to do the same thing.

2) The units could not have a clue how much room there is (maybe there are tight doorways?)
Upon collisions, one or both the units decide to walk to a random near by location (or change their end destinations). The overall hope being that one of them no longer has to pass through the contested area.

3) Provide hint locations for them to goto when stuck. Provide hints to the edges so that the mesh acts like a set of one way streets. Every passage thus has guys walking on their perspective right hand side of the passage, so they can't collide with others going the opposite direction.


Also, because it hasn't been brought up yet. If you make some assumptions about the design of your navigation mesh you can generate all posible A* paths on the mesh at level build time. You can use that to build a "next node" matrix for your N triangles ( O(N^2) memory ) that allows you to look up the next node ( O(1) time ) in the path from A->Z.
Ie, the table shows, the shortest path from A->Z goes through B. At B you look up the same question for B->Z it tells you it goes to L, so you move to L then ask again. etc.
If you notice though, it limits the mesh, because you can't have ambiguous triangles (internal triangles) that would receive different next nodes for a given destination.

This isn't suited to all cases, but it could be an optimization you want to take.

Questions never end :)
If I test intersection of an object with the whole world,
(like intersectWorld in 3ds max), would this take substantial amount
of time to return from this function? I'd like to know where and when
this occurs

The idea is to avoid enumeration of all objects in the world that
potentially intersect the object's field of view...(or Line of Sight :)

Thanks
Jack

IN that case, spatial partitions are your friend.
If the intersect ray is long, you will still end up with a LOT of checks. In which case bounding volumes can speed things up.
Consider putting your objects and triangles in a spatial hash, quad-tree, or oct-tree partitioning structure.
You then check your ray against the cells in the structure, and then any objects held by the cells your ray intersects.