# Pathfinding with MicroPather : costs calculations with sectors and portals

I'm considering using micropather to help me with pathfinding. I'm not using a discrete map : I'm working in 2d with sectors and portales. However, I'm just wondering what is the best way to compute costs with this library in this context.

Just to be more clear about geometrical shapes I'm using : sectors are basically convex polygons, and portals are segments that lies on sector's edge.

Micropather exposes a pure virtual Graph class that you must inherate and overrides 3 functions. I understand how pathfinding works, so there's no problem in overriding those functions. Right now, my implementation give me results, i.e I'm able to find a path in my map, but I'm not sure I'm using an optimal solution.

For the AdjacentCost method : I just take the distance between sector's centers as the cost. I think a better solution should be to use the portal between the two sectors, compute its center, and then the cost should be : distance( sector A center, portal center ) + distance ( sector B center, portal center ). I'm pretty sure the approximation I'm using with just sector's center is enough for most cases, but maybe with thin and long sectors that are perpendicular, this approximation could mislead the A* algorithm.

For the LeastCostEstimate method : I just take the midpoint of the two sectors.

So, as you understand, I'm always working with sectors' centers, and it's working fine. And I'm pretty sure there's a better way to work.

Any suggestions or feedbacks? Thanks in advance!

I've been looking at micropather as well. If you are happy with the results, stick with it. If not...

Since you have control over the Graph, you can add arbitrary nodes. Thus, rather than going through the calculation to add distance from sector center to portal center, just stick a node in the middle of your sectors, connected to each portal for that sector. Micropather will take the distance from the portal to the middle of the sector in it's path finding algorithm.

You could also go crazy and add edges between the portals bounding a sector. (If I understand correctly, a sector is like a room, and portals are the doors out of the rooms). Then the path finding would be able to "cut corners" if it didn't need to go to the center of the room.

Should be easy to try these out.

For example, if your sectors are square rooms with doors on all four sides, your graph might look like this:

N - N - N
|   |   |
N - N - N


Where N are nodes/sectors, and the lines represent edges. There is no explicit node for portals.

If you include portals/doors in the graph you get for one room (with P for portal):

     P
|
P -  N  - P
|
P


If you put a bunch of these together:

     P       P
| \   / |
P -  N - P - N  - P
|  /  \ |
P       P


So you can go directly from the north door to the east door in the left hand room.

• I'm not sure your suggestion might work well with Micropather. With Micropather, it's up to you to compute the cost to move from one sector to another one. It's also up to you to say "this sector is connected to this one". The Graph class is not technically a graph (at least, not in the usual sense of the term!). So it will not take into account the node to add you're speaking about. In fact, if I add a new node, I'll have to compute the cost also with that node! – Adan Feb 24 '11 at 21:30
• Oh ok, I understand better what you mean. Meanwhile, I looked for an the source of Lilith 3d and it uses centroid too to compute distances cost. So I think using centroid to compute costs is not as bad as I thought. – Adan Feb 25 '11 at 8:26