Pathfinding with MicroPather : costs calculations with sectors and portals

  • Pathfinding with MicroPather : costs calculations with sectors and portals Adan

    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 -  N  - 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.

c++ ai path-finding
Related questions and answers
  • position when you compare the two programs. As beginner which method should I stick to?(all I want is smooth animations). ...I'm new to Game programmming and SDL, and I have been following Lazyfoo's SDL tutorials. My question is related to time based motion and frame rate based motion, basically which is better or appropriate depending on situations?. Could you give me an example where each of these methods are used?. Another question I have is that, in lazyfoo's two Motion tutorials (FPS based and time based

  • I'm writing a game engine which is going very fine. However, I'm now posed with handling textures. My Engine is in 2D, for simplicity reasons mostly to get a good idea of how to work with OpenGL. I do this in C++, and I have a hierarchical set-up when it comes to classes. There's a base class and some other classes derive from that. So now I'm onto the part where I want to load up some textures and apply them to polygons. The way my engine works in drawing things is like this: Load up a tile map file and parse it. The tile map contains all the information like events, lights, passability

  • for other players should only be sent to a game client if their player is near the other players (i.e. you shouldn't get health updates for people you can't see on the other side of the map). The main problem is that if you had to compare all the players every time an update is sent, it would just take way too long as the number of players scales (think up to a few thousand players per map and each... with the system though, as it isn't that efficient (besides knowing which grid they are in, no other caching) and sometimes visibility limits should extend beyond 2 grids of distance. Is there a better

  • Alright so i'm making a vertical side scroller where you are an '8' character traveling downward while avoiding my randomly generated walls (the "generation" function) on the left and right sides... from it. As an added touch i have made it so after you collide while traveling down the randomly generated map (or rather as the walls move uppward while your character stays put) the X chars you've... #include <sstream> // gives access to rand function #include <cstdlib> //gives access to time functions #include <ctime> // mySTOPWATCH i think i'm gonna cry.... =') #include <

  • well... I'm building the animation system of my game engine (the skeletal and skinned animation stuff), and I came to a point where I added so much functionality in the frame and node structures... don't want to find out in the end that I have to rewrite everything again, as a lot of other objects will be working with these data. Sorry if it's a too subjective matter, but I need some insight. I'm... constructing a node object it's done referencing a pool of structure instances to prevent allocation for 2 equal frames. Also the lights are something that I'm not sure on how to handle as I need

  • to send those corresponding objects an "apply" request, and have them apply themselves? Or is there a better way? Question 3: If I have a completely dynamic map, but with objects that won't change very often, are there any guidelines as to the performance differences between GL_STATIC_DRAW and GL_DYNAMIC_DRAW? Final Question: Should I even consider using vertex lists? Or are VBOs just a better...I've been using OpenGL for a short time now- and I'd like some clarification on VBOs. As I understand it, a VBO is an object stored on VRAM. In immediate mode, to apply a texture we simply bind

  • Choosing an Audio API Aidan Knight

    Free - 3000$ - 6000$ which pretty much excludes this. BASS - So far this is what I am leaning towards. Simple API, great feature list, and quite a bit more. The pricing structure looks somewhat similar..., features seem generic. Pretty much coming down to a battle between this and BASS. I have heard good and bad things. The other libraries such as OpenAL, PortAudio, Audiere, etc. were considered, but I am looking for something more drag and drop rather than something I am going to be basically writing my own front-end for. I am curious though, I remember stumbling across another library or two a few

  • the players double-wall the whole map, I'm going to beat them to it. Every wall has two halves that are attached to the edge of the tile from inside. So, to make a single "Wall unit" I'll have to create...". As you can see in the picture, a corner will basically cry for a "cap" object. I'm actually cool with it, it's not so hard to add. Hey, I already have a plan for thin columns made out of four connected..., nothing to change in the engine. Cons: Two things. One - it might be just in my head, but some combinations just look ugly. Second - this approach allows to make a double-wall from two adjacent tiles

  • , they are horrible. Absolutely unusable, I'd need to make my own for sure. I didn't look at their API, but if their tools are so bad, I'm not inclined to look further. Unity3D. This one is quite nice, but I really.... I just do this for fun, and it would be even better if there were proper animation/particle editors available and if the engine I were to use, would be available for multiple platforms. (so more...? I prefer: C#, Actionscript. I don't mind using c++ if the toolset is above average, but I highly doubt that there is something out there like that. Please prove me wrong :) So summary: I'd like

Data information